COMS W4115
Programming Languages and Translators
Lecture 13: Syntax-Directed Translation
March 5, 2008

Lecture Outline

1. Review
2. Error recovery in Yacc
3. Syntax-directed definitions
4. Synthesized and inherited attributes
5. SDD for binary-to-decimal translation
6. From arithmetic expressions to syntax trees
7. Reading

1. Review

• Parsing action conflicts
• Resolving shift/reduce conflicts
• Using Yacc to generate LALR(1) parsers
• Using Yacc with ambiguous grammars

2. Error Recovery in Yacc

• In Yacc, error recovery can be performed with error productions.
• To process errors at the level of a nonterminal A, add an error production A → error &alpha where error is a Yacc reserved word, and α is a string of grammar symbols, possibly empty. Yacc will generate a parser including this production.
• If Yacc encounters an error during parsing, it pops symbols from its stack until it finds the topmost state on its stack whose underlying set of items includes an item of the form
     A → . error &alpha
  The parser then shifts the special token error onto the stack as though it saw the token error on the input.
• If α is not empty, Yacc skips ahead on the input looking for a substring that can be "reduced" to α on the stack. Now the parser will have error α on top of its stack, which it will reduce to A. The parser then resumes normal parsing.
• Example: See Fig. 4.61, p. 296. This yacc specification contains a translation rule

      lines : error '\n'  { yyerror("reenter previous line:"); yyerrok; }
  

On encountering an error, the parser starts popping symbols from its stack until it encounters a state with a shift action on error. The parser shifts the token error on to the stack and then skips ahead in the input until it finds a newline which it shifts onto the stack. The parser reduces error '\n' to lines and emits the error message "reenter previous line:". The special Yacc routine yyerrok resets the parser to its normal mode of operation.

3. Syntax-Directed Definitions

• The syntax analyzer translates its input token stream into an intermediate language representation of the source program, usually an abstract syntax tree.
• A syntax-directed definition can be used to specify this translation.
• An SDD is a context-free grammar with semantic rules attached to the productions.
• The semantic rules define values for attributes associated with the nonterminal symbols of the productions. These values can be computed by creating a parse tree for the input and then making a sequence of passes over the parse tree, evaluating some or all of the rules on each pass.

4. Synthesized and Inherited Attributes

• Attributes are values attached to the nodes of a parse tree.
• Synthesized attributes are values that can be computed bottom-up in the parse tree. The identifiers $$, $1, $2, etc., in Yacc actions are synthesized attributes. Synthesized attributes can be easily computed by a shift-reduce parser that keeps the values of the attributes on the parsing stack. See Fig. 5.19, p. 325.
• Inherited attributes are values that can be computed top-down in the parse tree.

5. SDD for Binary-to-Decimal Translation

• Here is an SDD translating signed bit strings into decimal numbers. The attributes, BNum.val, Sign.val, List.val, and Bit.val, are all synthesized attributes that represent integers.

   BNum → Sign List      { BNum.val = Sign.val × List.val }
   Sign → +              { Sign.val = +1 }
   Sign → -              { Sign.val = -1 }
   List → List1 Bit      { List.val = 2 × List1.val + Bit.val }
   List → Bit            { List.val = Bit.val }
   Bit  → 0              { Bit.val = 0 }
   Bit  → 1              { Bit.val = 1 }
  

• Same example in Yacc:

   BNum : Sign List      { $$ = $1 * $2; }
        ;
   Sign : '+'            { $$ = +1; }
        | '-'            { $$ = -1; }
        ;
   List : List Bit       { $$ = 2*$1 + $2; }
        | Bit
        ;        
   Bit  : '0'            { $$ = 0; }
        | '1'            { $$ = 1; }
        ;
  

6. From Arithmetic Expressions into Syntax Trees

• Here is a Yacc program that translates arithmetic expressions into syntax trees. The function mkleaf(op, left, right) returns a pointer to a node with three fields: the first labeled op, the second a pointer to a left subtree, and the third a pointer to a right subtree. mkleaf(num, value) returns a pointer to a node with two fields, the first labeled num and the second its value.

   E : E '+' T      { $$ = mknode('+', $1, $3); }
     | T
     ;
   T : T '*' F      { $$ = mknode('*', $1, $3); }
     | T
     ;
   F : '(' E ')'    { $$ = $2; }
     | num          { $$ = mkleaf('num', $1); }
     ;
  

6. Reading

• ALSU: Sections 4.9, 5.1-5.3