Work Note 4, DM546, Spring 2018
Lecture February 13
Background material: Appel Chapters 4, Bison documentation.
With regards to literature and material on bison, see the
Abstract Syntax Trees.
Exercises February 16
With regards to literature and material on flex and bison, see the
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:
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?
S → N$ N → f N → f ; N
S → N$ N → f N → N ; f
Appel 5.1 a; do this with basis in you own hash table like
implementation from an earlier work note.