6.5 INTERMEDIATE CODE GENERATION

6.4 SYNTAX-DIRECTED TRANSLATION SCHEMES

A syntax-directed translation scheme is a context-free grammar in which attributes are associated with the grammar symbols, and semantic actions, enclosed within braces ({ }), are inserted in the right sides of the productions . These semantic actions are basically the subroutines that are called at the appropriate times by the parser, enabling the translation. The position of the semantic action on the right side of the production indicates the time when it will be called for execution by the parser. When we design a translation scheme, we must ensure that an attribute value is available when the action refers to it. This requires that:

1. An inherited attribute of a symbol on the right side of a production must be computed in an action immediately preceding (to the left of) that symbol, because it may be referred to by an action computing the inherited attribute of the symbol to the right of (following) it.

2. An action that computes the synthesized attribute of a nonterminal on the left side of the production should be placed at the end of the right side of the production, because it might refer to the attributes of any of the right-side grammar symbols. Therefore, unless they are computed, the synthesized attribute of a nonterminal on the left cannot be computed.

These restrictions are motivated by the L -attributed definitions. Below is an example of a syntax-directed translation scheme that satisfies these requirements, which are implemented during predictive parsing:

The advantage of a top-down parser is that semantic actions can be called in the middle of the productions. Thus, in the above translation scheme, while using the production D ’ TL to expand D , we call a routine after recognizing T (i.e., after T has been fully expanded), thereby making it easier to handle the inherited attributes. Whereas a bottom-up parser reduces the right side of the production D ’ TL by popping T and L from the top of the parser stack and replacing them by D , the value of the synthesized attribute T .type is already on the parser stack at a known position. It can be inherited by L . Since L .type is defined by a copy rule, L .type = T .type, the value of T .type can be used in place of L .type. Thus, if the parser stack is implemented as two parallel arrays ”state and value ”and state [ I ] holds a grammar symbol X , then value [ I ] holds a synthesized attribute of X . Therefore, the translation scheme implemented during bottom-up parsing is as follows , where [top] is value of stack top before the reduction and [newtop] is the value of the stack top after the reduction: