Compilers (COMP 3048) Lab 07
Interpreting
WhenLPparsing there’llbechoicesto make Cshiftor reduce
(a) Explain shift/reduce and reduce/reduce conflicts in the context of LR parsing. reducebywhichnite
(b) This question is on the well-known ‘dangling else’ problem: Consider the following portion of the C grammar:
selection-statement = …
| IF ( expression ) statement x
| IF ( expression ) statement ELSE statement
t it b X 1
Note that:
a concrete if statement in C.
I
• exp is a non-terminal;
exp :: { Bool } exp : exp and exp
| exp or exp |notexp |tt
|ff
| ’(’ exp ’)’
{1} {2} {3} {4} {5} {6}
1
Ix it9gbthenx o
(i) Explainhowthisrulemayleadtoambiguityinparsing.Youneedtoillustrateyouranswerthrough
f
naturalway. if shift theelsewilltravebacktothefirst (c) Consider the following grammar for a very simple expression language: declared if
else
(ii) As discussed in our lectures, a typical default option for resolving shift/reduce conflicts is opting for shifting. This is indeed the default option in commonly used parser generators such as Yacc, Bison, and Happy.
Explain (succinctly) how, by opting for shifting, the dangling else problem may be resolved in a
exp ! expandexp | exporexp | notexp | tt|↵
| (exp)
• and, or, not, tt, ↵, (, and ), are all terminals;
• and denotes logical conjunction, or denotes logical disjunction, not denotes logical negation, tt and ↵ are literals denoting the truth values true and false, respectively, and parentheses are used for grouping as usual.
The following is part of a Happy parser specification for this grammar. We wish to implement an inter- preter that directly evaluates a parsed expression to a Boolean. The type of the semantic value of the non-terminal exp is thus Bool:
The grammar is ambiguous, but we assume that operator precedence and associativity declarations are used to disambiguate. The semantic actions for evaluating an expression have been left out, indicated by boxed numbers (e. g., ).
(i) Complete the fragment above by providing suitable semantic actions in place of . . . for evaluating each form of expression.
(ii) We now wish to extend the language with a notion of let-bound variables. The Happy grammar is thus extended as follows:
| ident { } |letident’=’expinexp { }
Here, ident, let, in, and = are all new terminals. For simplicity, the semantic value of ident is a string; i. e., the name of the identifier.
Explain, in words, how to restructure the interpreter to handle let-bound variables. In particular, what should the type of the semantic values of the non-terminals exp be now? Give the exact Haskell types and define any auxiliary types you introduce.
(iii) Implement an interpreter for the extended expression language by providing suitable semantic actions for all productions (in place of . . . ) following the idea you described in (b).
1
7
8
2
1
6
1
8