TERM PAPER

COMPILER DESIGN

Translator For Simple Expression

Submitted to:Harshpreet Sir
Submitted by:Kapish Mahajan
Registration no. 11207646
Section : K2202
Roll no. A-19

Syntax Directed Translation

1. Syntax Directed Definitions

There are two notations for associating semantic actions with productions: syntax-directed definitions and translation schemes.

The Syntax-Directed Definitions are a mechanism for specifying translations for the programming language constructs. A syntax-directed definition specifies the translation of a construct in terms of the attributes associated with its syntactic components.

A syntax-directed definition uses a context-free grammar to specify the structure of the input: with each grammar symbol it associates a set of attributes; and with each production a set of semantic rules for computing the values of the attributes associated with the symbols in it.

A Translation Scheme is like a syntax-directed translation except that the order of evaluation of the semantic rules is explicitly shown. A translation scheme is a context-free grammar in which program fragments called semantic actions are embedded within the right sides of the productions. Translation schemes show the order in which the semantic rules has to be evaluated, so they show implementation details.

With both syntax-directed definitions and translation schemes the input token stream is parsed, the parse tree is constructed, and next it is traversed in order to execute the corresponding semantic actions. The evaluation of the semantic actions could be code generation, storing symbol table information, or printing error messages.

2. Synthesized and Inherited Attributes

Both syntax-directed definitions and translation schemes has associated sets of attributes with each grammar symbol, which indicate a relevant semantic action. An attribute can represent various things, such as: a string, a number, a memory address, etc..

There are two kinds of attributes: synthesized and inherited.

The value of a synthesized attribute is computed from the values of attributes at the children nodes of the current in the parse tree.

The value of an inherited attribute is computed from the values of attributes at the parent nodes of the current in the parse tree.

Example: This a syntax-directed definition of a language for implementing an arithmetic calculator (using synthesized attributes)

|Production |Semantic rule |
| L ® E n | print( E.val ) |
| E ® E1 + T | E.val := E1.val + T.val |
| E ® T | E.val := T.val |
| T ® T1 * F | T.val := T1.val * F.val |
| T ® F | T.val := F.val |
| F ® ( E ) | F.val := E.val |
| F ® digit |F.val := digit.lexval |

Using the above grammar there can be constructed the following parse tree with synthesized attributes for the arithmetic expression:

3 * 5 + 4 n [pic]

Example: This a syntax-directed definition for specifying declarations in a programming language (using inherited attributes)

|Production |Semantic rule |
| D ® T L | L.in := T.type |
| T ® int | T.type := integer |
| T ® real | T.type := real |
| L ® L1 , D | L1.in := L.in |
| |addtype( id.entry, L.in ) |
| L ® id | addtype( id.entry, L.in ) |

Using the above grammar there can be constructed the following parse tree with inherited attributes for the expression:

real id1, id2, id3

[pic]

3. Syntax Trees and Parse Trees

Example: Consider the following syntax-directed

|Production |Semantic rule |
| E ® E1 + T | E.nptr := mknode( '+', E1.nptr, T.nptr) |
| E ® E1 - T | E.nptr := mknode( '-', E1.nptr, T.nptr) |
| E ® T | E.nptr := T.nptr |
| T ® ( E ) | T.nptr := E.nptr |
| T ® id | T.nptr := mkleaf( id, id.entry ) |
| T ® num | T.nptr := mkleaf( num, num.val ) |

The figure below illustrates a syntax tree and a parse tree drawn with dotted lines for the expression: a - 4 + c

[pic]

4. Directed Acyclic Graph:
[pic]

Conclusion: In this term paper we learn how to translate simple expression using Syntax Directed Translation. We learn to make parse tree after which we need to make Directed Acyclic Graph so that we can further convert into three-address code generation and thus the simple expression get translated .

References: http://www.d.umn.edu/~rmaclin/cs5641/Notes/Lecture11.pdf http://www.iis.sinica.edu.tw/~tshsu/compiler/2007/slides/slide4.pdf http://cse.iitkgp.ac.in/~bivasm/notes/ http://web.cse.ohio-state.edu/~gurari/course/cse756/cse756su33.xht