Syntax-Directed Translation
Introduction: Syntax-Directed translation associates a set of attribute with each grammar symbol and a set of semantic rule with each production. It is also done by attaching rules or program fragments to productions in a grammar.
For example, consider an expression expr generated by the production
expr -» exprx term
Here, expr is the sum of the two sub-expressions exprx and term. (The subscript in exprx is used only to distinguish the instance of expr in the production body from the head of the production). We can translate expr by exploiting its structure, as in the following pseudo-code:
translate exprx;
translate term;
handle ;
Using a variant of this pseudocode, we shall build a syntax tree for expr in Section 2.8 by building syntax trees for exprt and term and then handling by constructing a node for it. For convenience, the example in this section is the translation of infix expressions into postfix notation.
This section introduces two concepts related to syntax-directed translation:
- Attributes. An attribute is any quantity associated with a programming construct. Examples of attributes are data types of expressions, the number of instructions in the generated code, or the location of the first instruction in the generated code for a construct, among many other possibilities. Since we use grammar symbols (non-terminals and terminals) to represent programming constructs, we extend the notion of attributes from constructs to the symbols that represent them.
- (Syntax-directed) translation schemes. A translation scheme is a notation for attaching program fragments to the productions of a grammar. The program fragments are executed when the production is used during syntax analysis. The combined result of all these fragment executions, in the order induced by the syntax analysis, produces the translation of the program to which this analysis/synthesis process is applied.
Syntax-directed translations will be used throughout this chapter to translate infix expressions into postfix notation, to evaluate expressions, and to build syntax trees for programming constructs.
Postfix Notation: The examples in this section deal with translation into postfix notation. The postfix notation for an expression E can be defined inductively as follows:
1. If E is a variable or constant, then the postfix notation for E is E itself.
2. If E is an expression of the form E\ op E2, where op is any binary operator, then the postfix notation for E is E[ E'2 op, where E[ and E'2 are the postfix notations for E\ and E2, respectively.
3. If E is a parenthesized expression of the form (Ei), then the postfix notation for E is the same as the postfix notation for E\.