Work Note 4, DM546, Spring 2018

Lecture February 13

• The tool bison.
• Abstract Syntax Trees.

Exercises February 16

• Extend tiny expressions with a modulo operator % and an absolute value funktion |_|. In the action parts associated with the rules in the Bison definition file, write out the expression again, but with enough parentheses that you can verify the parsing result.
• Introduce unary minus, -x, into the language as so-called syntactic sugar for 0-x, i.e., you may write -x according to the new grammar, but internally (in the AST), it is just represented as 0-x. Again, verify your result.
• Discuss in detail how you can avoid building lists backwards in an LALR(1) parser. Rewrite the lecture example to obtain this.
• What happens if you switch neformals and formal in the grammar in order to grammatically avoid the backwards lists problem? Try to study that problem in a simple scenario by considering the two grammars:
  1. S → N$   N → f   N → f ; N
  2. S → N$   N → f   N → N ; f
  where f is a terminal symbol. Draw the DFAs, translate to table representations, and run them on the input sequence "f ; f ; f ; f $". Can you see any reasons to choose left recursion instead of right recursion for LR (and LALR) parsing?
• Appel 5.1 a; do this with basis in you own hash table like implementation from an earlier work note.