1 Bottom-up parsing
1.1 LR(0) automaton
Consider the following grammar:
A → aB|D|F B → Bb|b
D → EB|dBEF E → e
F → c|f
Construct the LR(0) automaton, and identify any shift/reduce conflicts.
1.2 SLR
Is this grammar SLR(1)? Justify your answer.
2 Tree simplification
The VSL compiler in the provided archive ps3 skeleton.tgz is extended with a function ’simplify tree’ in tree.c; this function is called from main.c, after the initial syntax tree construction. Implement the function so that it traverses the syntax tree, and makes the following modifications:
2.1 Eliminate nodes of purely syntactic value
Delete nodes which can only ever have 1 child and no meaningful data, and associate their child directly with their parent.
2.2 Flatten list structures
Delete internal nodes of list structures, leaving only a parent node with a list type, and all list items as its children. Print list items can be associated directly with the print statement.
2.3 Resolve constant expressions
Compute the value of subtrees representing arithmetic with constants, and re- place them with their value.
