Homework Assignments Week 1.3: Parsing
Submit your answers in WebLab (Assignment Week 1.3).
The language that was used in the lecture to define context-free grammars, derivations, parse tables, and more is defined in this Spoofax project:
- https://github.com/TUDelft-CS4200-2018/cc.syntax.parsing
Derivations
Consider the following syntax definition, assuming that ID
is defined as alphanumeric identifiers as usual:
sorts S E ID
context-free syntax
S.S = E
E.Var = ID
E.Add = E "+" E
E.Mul = E "*" E
E.Par = "(" E ")"
- Give a right-most derivation for the sentence
x + (x ∗ x)
. - Give two different abstract syntax trees for the sentence
x + x ∗ x
.
Derivations
Consider the following syntax definition,
sorts S P ID
context-free syntax
S.S = "f" "(" P ")"
P.V = ID
P.C = P "," ID
P.R = ID "," P
- Describe the language defined by this syntax definition in English.
- Give a left-most derivation for the sentence
f(x, x, x)
. - Use
f(x, x)
as an example to explain why the syntax definition is ambiguous.
Disambiguation by Rules
Consider the following ambiguous syntax definition in SDF3 for a small expression language. Use prioritity and associativity rules to disambiguate the syntax definition. Discuss why you chose to disambiguate the operators in the way you have. Illustrate the resulting disambiguation using examples. Did you catch all ambiguities?
sorts S E ID
context-free syntax
S.S = E
E.Var = ID
E.Neg = "-" E
E.Add = E "+" E
E.Sub = E "-" E
E.Div = E "/" E
E.Mul = E "*" E
E.Pow = E "^" E
E.Par = "(" E ")"
Disambiguation by Transformation
Consider the following ambiguous syntax definition in SDF3 for a small expression language. Transform the syntax definition to an unambiguous syntax definition without using disambiguation rules.
sorts S E ID
context-free syntax
S.S = E
E.Var = ID
E.Neg = "-" E
E.Add = E "+" E
E.Sub = E "-" E
E.Div = E "/" E
E.Mul = E "*" E
E.Pow = E "^" E
E.Par = "(" E ")"
Binary Operators
Consider the following grammar in the grammar formalism introduced in Lecture 4, with $
representing end of file:
grammar
productions
E.I = ID
E.B = E B E
B.P = "+"
B.S = "-"
B.M = "*"
B.D = "/"
-
Demonstrate that this grammar is ambiguous by giving two different abstract syntax terms for the sentence
ID "+" ID "*" ID
and the left-most derivations that give rise to these trees. -
Rewrite the grammar in SDF3 notation and use declarative priority and associativity rules to disambiguate it following standard rules. Define a translation from the ASTs of this grammar to the ASTs of the original grammar.
-
Instead of using separate disambiguation rules, transform the grammar to an unambiguous context-free grammar
SLR Parsing
Consider the following grammar in the grammar formalism introduced in Lecture 4, with $
representing end of file:
grammar
start S
non-terminals S T E
terminals ID "+"
productions
S = E $
E = T "+" E
E = T
T = ID
-
Construct the LR(0) automaton for the grammar using the language of item-set states defined in the lecture
-
Compute the FIRST and FOLLOW sets for the grammar
-
Construct the SLR parse table for the grammar
-
What kind of conflict does the resulting parse table contain?
-
Explain two strategies to resolve this conflict.
-
Assume the conflict is resolved in favour of a shift. Use the parse table to recognise the sentence
ID "+" ID
. Show the stack and the remaining input after each step.
LR Parsing
Consider the following grammar in the grammar formalism introduced in Lecture 4, with $
representing end of file:
grammar
start S
non-terminals S T E
terminals ID "+"
productions
S = E $
E = ID
E = ID "(" E ")"
E = E "+" ID
-
Construct the LR(0) automaton for the grammar using the language of item-set states defined in the lecture
-
Compute the FIRST and FOLLOW sets for the grammar
-
Construct the SLR parse table for the grammar
| state | ID | "+" | "(" | ")" | $ | S | E |
| | | | | | | | |
-
Is this an SLR grammar? Why (not)?
-
Use the parse table to recognize the sentence
ID "(" ID "(" ID ")" "+" ID ")" $
. Show the stack and the remaining input after each step.
Dangling Else
grammar
start S
non-terminals S E
productions
S.S = E $
E.If = "if" E "then" E
E.IfE = "if" E "then" E "else" E
E.Var = ID
-
Show that this grammar is ambiguous by presenting an input program that has (at least) two left-most derivations. Write down the program, its left-most derivations, and corresponding abstract syntax trees.
-
Construct the LR(0) automaton for the grammar using the language of item-set states defined in the lecture
-
Compute the FIRST and FOLLOW sets for the grammar
-
Construct the SLR parse table based on the automaton
-
Assuming a disambiguation policy that specifies that an
else
branch should belong to the closestif-then
, which action should be preferred in the parse table when the parser reaches a conflict, with anelse
symbol as the lookahead?