Work Note 4, DM516, Spring 2012
Lecture February 13
-
Abstract Syntax Trees.
-
Weeding.
-
Symbol tables.
-
Type checking.
Background material: Appel Chapters 4 and 5.
Exercises February 20
-
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:
-
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 and bison, see the
literature page.
Announcements
-
During the last lecture on February 2, we discovered a misprint
during a parsing example. In Table 3.19 on page 58 in the textbook
(and the corresponding slide in the hand-outs), add "s16" in
state 15 under '+'.
-
In weeks 6, 7, and 8, there will be some changes compared with
the announced by the faculty as to which slots are used for
lectures and exercises, respectively; see the work notes.
Last modified: Mon Feb 6 09:46:45 CET 2012
Kim Skak Larsen
(kslarsen@imada.sdu.dk)