Tue, 30 May 1995 11:32:28 GMT

Related articles |
---|

LL(1) grammar for dangling else? MLF@VM.CPD.UA.ES (Mikel L. Forcada) (1995-05-28) |

Re: LL(1) grammar for dangling else? lumpe@aragorn.unibe.ch (Markus Lumpe) (1995-05-30) |

Re: LL(1) grammar for dangling else? leichter@zodiac.rutgers.edu (1995-06-23) |

Newsgroups: | comp.compilers |

From: | Markus Lumpe <lumpe@aragorn.unibe.ch> |

Keywords: | LL(1), parse |

Organization: | Compilers Central |

References: | 95-05-133 |

Date: | Tue, 30 May 1995 11:32:28 GMT |

Status: | RO |

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 *

***********************************************************************

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.