The Heart Of A Compiler
Written by Mike James   
Thursday, 01 April 2021
Article Index
The Heart Of A Compiler
Formula translation
A Solution

Fortran at last!

This order of evaluation problem was what faced the IBM team who had been assembled (no pun intended) to make the assault on computer science’s equivalent of getting a man on the moon - the automatic translation of arithmetic expressions.

The team, under the leadership of John Backus, was to construct a compiler for a computer language that could compile any arithmetic expression that a programmer cared to throw at it.

To do this they had to invent a way of writing down and making use of the rules of grammar for artificial languages such as programming languages and mathematical expressions. They invented the production rules as described above and a method of using the rules to parse the language and generate the correct assembly code.

The trick is to convert the expression into a syntax tree which makes clear the relationships between the operators and their priorities. Once you have the syntax tree then you can use it to generate the operations in the correct order by simply "walking" the tree.  For a more detailed explanation see: Grammar and Torture.

The six-month project actually took two years before the first compiler was available in 1956 and it took until April 1957 before working compilers were distributed to customers. It consisted of 25,000 lines of machine code on a magnetic tape and it was distributed, complete with bugs, to every IBM 704 installation.

The language was called FORTRAN standing for FORmula TRANslation and when they finally got it to work it revolutionized programming and made IBM the number one computer company for decades.

Notice that the name of the language was derived from FORMula TRANslation. Even though the language had lots of other new features, it was the fact that it could successfully convert an arbitrary arithmetic expression or formula into machine code that was its great claim to fame. Once you work out how to do this particular job the rest of the compiler was a matter of comparatively simple book keeping.

 

Related Articles

Assemblers and assembly language

Grammar and Torture

John Backus - the Father of Fortran

Brackets are Trees

CPU

Computer Memory and Pigeonholes

Hexadecimal

How Memory Works

Inside the Computer - Addressing

Inside the processor

Interpreters

The Essence Of Programming

Variables revisited

 

What Programmers Know

knowcover

Contents

  1. The Computer - What's The Big Idea?*
  2. The Memory Principle - Computer Memory and Pigeonholes*
  3. Principles of Execution - The CPU
  4. The Essence Of Programming
  5. Variables - Scope, Lifetime And More*
  6. Binary Arithmetic
  7. Hexadecimal*
  8. Binary - Negative Numbers
  9. Floating Point Numbers
  10. Inside the Computer - Addressing
  11. The Mod Function
  12. Recursion
  13. The Lost Art Of The Storage Mapping Function *
  14. Hashing - The Greatest Idea In Programming
  15. XOR - The Magic Swap
  16. Programmer's Introduction to XML
  17. From Data To Objects*
  18. What Exactly Is A First Class Function - And Why You Should Care*
  19. Stacks And Trees
  20. The LIFO Stack - A Gentle Guide*
  21. Data Structures - Trees
  22. Inside Random Numbers
  23. The Monte Carlo Method
  24. Cache Memory And The Caching Principle
  25. Data Compression The Dictionary Way
  26. Dates Are Difficult*
  27. Sequential Storage*
  28. Magic of Merging*
  29. Power of Operators
  30. The Heart Of A Compiler*
  31. The Fundamentals of Pointers
  32. Functional And Dysfunctional Programming*

* Recently revised

square

 



 

Comments




or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Banner


Reverse Polish Notation - RPN

RPN or Reverse Polish Notation used to be a basic of the computer programmer's world, but today it is not as well known. Hence there may be some perfectly clued up programmers who are still left wonde [ ... ]



Kolmogorov Complexity

This xkcd cartoon provides an ideal excuse to explain Kolmogorov complexity. It is an interesting topic and one that gets right to the heart of programming of how programming relates to ideas like inf [ ... ]


Other Articles

 


<ASIN:0805321667>

<ASIN:1590591348>

<ASIN:0954161793>

<ASIN:0534939724>



Last Updated ( Thursday, 01 April 2021 )