next up previous
Next: Translation Schemes Up: Compiler Theory: Syntax-Directed Translation Previous: Syntax-Directed Definitions

Syntax Trees for Expressions

In this section, we consider the case where In this case,


ARITHMETIC EXPRESSIONS. A language L over an alphabet $ \Sigma$ is a language of arithmetic expressions (or expressions for short) if there exists

  1. a partition $ \Sigma$ = $ \Sigma_{{{op}}}^{{}}$  $ \cup$  $ \Sigma_{{{val}}}^{{}}$  $ \cup$  {$ \bf ($,$ \bf )$},
  2. a grammar G generating L such that each production has one of the forms
The elements of $ \Sigma_{{{op}}}^{{}}$ are called operators and those of $ \Sigma_{{{val}}}^{{}}$ are called values. The nonterminals on the right side of a production where an operator appears are called operands of the production.

The language L is said


KEY IDEAS.


CONSTRUCTING SYNTAX TREES FOR EXPRESSIONS. Each node in a syntax tree for an (arithmetic) expression is a record with several fields.

We use here the following functions to create the nodes of syntax trees for expressions with binary operators. Each function returns a pointer to a newly created node.
make_node
(op, left, right) creates an operator node with label op and two fields containing pointers to left and right.
make_leaf
($ \bf id$, entry) creates an identifier leaf with label $ \bf id$ and a field containing entry a pointer to the symbol-table entry for the identifier.
make_leaf
($ \bf num$, val) creates a number leaf with label $ \bf num$ and a field containing val.

Example 7   The following syntax-directed definition allows the construction of a syntax tree for a binary infix arithmetic expression. The synthesized attributes E.ptr, T.ptr and F.ptr keep track of the pointers returned by the function calls.
Production Semantic Rule
E $ \longmapsto$ E1 + T E.ptr := make_node( $ \bf +$, E1.ptr, T.ptr)
E $ \longmapsto$ E1 - T E.ptr := make_node( $ \bf -$, E1.ptr, T.ptr)
E $ \longmapsto$ T E.ptr := T.ptr
T $ \longmapsto$ T1*F T.ptr := make_node( $ \bf *$, T1.ptr, F.ptr)
T $ \longmapsto$ F T.ptr := F.ptr
F $ \longmapsto$ (E) F.ptr := E.ptr
F $ \longmapsto$ $ \bf id$ F.ptr := make_leaf($ \bf id$, $ \bf id$.entry)
F $ \longmapsto$ $ \bf num$ F.ptr := make_leaf($ \bf num$, $ \bf num$.val)


USING DAGS FOR SYNTAX TREES OF EXPRESSIONS.

Figure 10: A dag for the expression a + a*(b - c) + (b - c)*d.
\begin{figure}\htmlimage
\centering\includegraphics[scale=.4]{dagForArithmeticSubexpression.eps}
\end{figure}


IMPLEMENTING DAGS FOR SYNTAX TREES OF EXPRESSIONS.


next up previous
Next: Translation Schemes Up: Compiler Theory: Syntax-Directed Translation Previous: Syntax-Directed Definitions
Marc Moreno Maza
2004-12-02