Syntax Directed Translation in Compiler Design Tutorial with Examples
Syntax Directed Translation
Grammar symbols are associated with attributes to associate information with the programming language constructs that they represent. Values of these attributes are evaluated by the semantic rules associated with the production rules.
Evaluation of the semantic rules are as follows
- May generate intermediate codes
- May put information into the symbol table
- May perform type checking
- May issue error messages
- May perform some other activities
- An attribute may hold a string, a number, a memory location, a complex record etc.
- Evaluation of a semantic rule defines the value of an attribute, but a semantic rule may also have some side effects such as printing a value. g.,
- Symbols E, T and F are associated with an attribute value.
- The token digit has an attribute lexval (it is assumed that it is evaluated by the lexical analyzer).
- The program fragment above represents the implementation of the semantic rule for a bottom-up Parser.
- At each shift of digit, we also push digit. Lexval into val_stack.
- At all other shills, we do not put anything into val_stack because other terminals don’t have attributes (but we increment the stack pointer val stack).
- The above model is suited for a desk calculator, where the purpose Iv; evaluate and to generate code.
Intermediate Code Generation
Intermediate codes are machine independent codes, but they are close to machine instructions. The given program in a source language is converted to an equivalent program in an intermediate language by the intermediate code generator.
The designer of the compiler decides the intermediate language.
- Syntax trees can he used as an intermediate language.
- Postfix notations, three address code (quadruples) can be used as an intermediate
Syntax tree is a variant of the parse tree, where each leaf represents an operand and each interior node represent an operator.
A sentence a * (b + d) would have the following syntax tree
When each statement contains three addresses (two for operands and one for result), Most general kind of three-address code is
x= y op z
Where x, y and z are names, constants or compiler generated temporaries and op is any operator.
But we can also use the following notation for quadruples (much better notation because it looks like a machine code instruction)
op y, z, x
Apply operator op to y and z and store the result in x.
Representation of Three-Address Codes
Tree-address code can be represented in various forms r e quadruples Triples and indirect triples. These forms are demonstrated by way of examples below.
e.g., A = — B* (C D)
Three address code is as follow
T2 =C +D
T3 = T1* T2
Sorting in Design and Analysis of Algorithm Study Notes with Example
Learn Sorting in Handbook Series: Click here