6.5.2 L-Attributed Attribute Grammars

A top-down parser can evaluate attributes as it parses if the attribute values can be computed in a top-down fashion. Such attribute grammars are termed L-Attributed.       First, we introduce a new type of symbol called an action symbol. Action symbols appear in the grammar in any place a terminal or nonterminal may appear. They may also have their own attributes. They may, however, be pushed onto their own stack, called a semantic stack or attribute stack.

      We illustrate action symbols using the notation "<>" which indicates that the symbol within the brackets is to be pushed onto the semantic stack when it appears at the top of the parse stack. By inserting this action in appropriate places, we will create a translator which converts from infix expressions to postfix expressions.

We parse and translate a + b * c. The top is on the left for both stacks.

When the semantic stack is popped, the translated string is:

           a b c * +

the input string translated to postfix. In Example 6, the action symbol did not have any attached attributes.

     The BNF in Example 6 is in LL(1) form. This is necessary for the top-down parse.

      The formal definition of an L-attributed grammars is as follows. An attribute grammar is L-attributed if and only if for each production X₀ X₁ X₂. . . X_i. . . X_n,

 (1) {X_i.inh} = f ({X_j.inh} , {X_k.att})            i, j >= 1, 0<=k<i

 (2) {X₀.syn} = f ({X₀.inh} , {X_j.att})            1<=j<=n

 (3) {ActionSymbol.Syn} = f ({ActionSymbol.Inh})

     (1) says that each inherited attribute of a symbol on the right-hand side depends only on inherited attributes of the right-hand side and arbitrary attributes of the symbols to the left of the given right-hand side symbol.

     (2) says that each synthesized attributes of the left-hand-side symbol depends only on inherited attributes of that symbol and arbitrary attributes of right-hand-side symbols.

     (2) says that the synthesized attributes of any action symbol depend only on the inherited attributes of the action symbol.

      Conditions (1), (2), and (3) allow attributes to be evaluated in one left-to-right pass (see Exercise 2).

      If the underlying grammar is LL(1), then an L-attributed grammar allows attributes to be evaluated while parsing. The reader may wish to review the LL(1) parsing driver in Chapter 4. The evaluation algorithm is:

      Exercise 3 asks the reader to combine this algorithm with the LL(1) driver algorithm given in Chapter 4.

      For the next few sections, we focus on restrictions to attributes that allow for efficient attribute evaluation.