Re: LL(1) grammar for dangling else?

The interlocking of if-then-else without additional brackets can never be
described with a LL(k)- or LR(k)-grammar.


A context-free grammar G = (V, A, R, s) is LL(k) only if when for the following
derivations hold:


      + r *
s ---> w1zw2 ---> w1vw2 ---> w1w and
      G G


      + r' *
s ---> w1zw2' ---> w1v'w2' ---> w1w'
      G G


with r = (z,v) and r' = (z,v') in R, w1,w,w' in A*, w2,w2' in V*
and for r != r' must hold always Firstk(w) != Firstk(w').
A* - set of all terminal strings
V* - set of all grammar strings (nonterminal and terminal)


Now we have the following grammar:


r1 = (s, St)
r2 = (St, if C then St else St)
r3 = (St, if C then St)


and the input string


if C then if C then St else St


This string can be represented by two derivations:


      + r2
s ---> if C then St ---> if C then if C then St else St


      + r3
s ---> if C then St else St ---> if C then if C then St else St


Now set w1 = if C then and
w = if C then St else St (first derivation)
w' = if C then St else St (second derivation)


It is obvious that Firstk(w) == Firstk(w') for every k. This means that this
grammar is not LL(k). (I have omitted the further derivation of C and St
because
this does not influence the result)


The same problem appears also in LR(k). The algorithm for constructing the
state closures will lead to a state with contains the following situations:


stateI:
...
                if C then St . else St
                if C then St .


For the first situation the shift operation on else has to be produced and for
the second situation a reduce action on else has to be produced because else
is in Follow(St). This leads to the shift-reduce conflict on else.


Markus


***********************************************************************
* Markus Lumpe *
* Institute of Computer Science and Applied Mathematics *
* University of Berne *
* e-mail: lumpe@iam.unibe.ch *
***********************************************************************
--

Return to the comp.compilers page.
Search the comp.compilers archives again.