Note 4, DM546, fall 2019
Lecture February 14
-
Abstract Syntax Trees.
-
Weeding.
-
Symbol tables.
Background material: Appel Chapters 4 and 5.
You can find support for my approach at the lecture with regards to
symbol tables in the Supplementary Notes for DM546;
see the literature page.
Exercises February 22
-
Extend tiny expressions
with a modulo operator % and an absolute value function |_|.
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:
-
S → N$ N → f N → f ; N
-
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.
With regards to literature and material on flex, bison, and
tiny expressions, see the literature page.