Grammar and Torture |
Written by Mike James | |||||
Thursday, 16 May 2019 | |||||
Page 4 of 4
Travelling the TreeNow that we have said the deeply unfashionable thing that syntax is not isolated from semantics we can now see why we bother to use a grammar analyzer within a compiler. Put simply a syntax tree or its equivalent can be used to generate the machine code or intermediate code that the expression corresponds to. The syntax tree can be considered as a program that tells you how to evaluate the expression. For example, a common method of generating code from a tree is to walk all its nodes using a “depth first” algorithm. That is, visit the deepest nodes first and generate an instruction corresponding to the value or operator stored at each node. The details of how to do this vary but you can see the general idea in this diagram.
So now you know. We use grammar to parse expressions, to make syntax trees, to generate the code. Now find out about different types of grammar and parsing methods – they are important. A Real Grammar Of ArithmeticYou might like to see what a real grammar for simple arithmetic expressions looks like: <Exp> -> <Exp> + <Term> |<Exp> - <Term> |<Term> <Term> -> <Term> * <Factor> | <Term> / <Factor> <Factor> -> x | y | ... | Of course it leaves out proper variable names, operators other than +, -, * and / but it is a reasonable start. Further reading:Assemblers and assembly language John Backus - the Father of Fortran A Concise Introduction to Languages and Machines Language Implementation Patterns
A Programmers Guide To Theory
|
|||||
Last Updated ( Thursday, 16 May 2019 ) |