Re: Is this an LL(1) Grammar ?

Joachim Durchholz <joachim.durchholz@munich.netsurf.de>
24 Mar 1998 22:50:13 -0500

          From comp.compilers

Related articles
Is this an LL(1) Grammar ? martin_mf@hotmail.com (Martin) (1998-03-22)
Re: Is this an LL(1) Grammar ? alan.southall@bk.bosch.de (Alan Southall) (1998-03-24)
Re: Is this an LL(1) Grammar ? joachim.durchholz@munich.netsurf.de (Joachim Durchholz) (1998-03-24)
Re: Is this an LL(1) Grammar ? bmcsweeney@bigfoot.com (1998-03-30)
Re: Is this an LL(1) Grammar ? cfc@world.std.com (Chris F Clark) (1998-04-03)
| List of all articles for this month |

From: Joachim Durchholz <joachim.durchholz@munich.netsurf.de>
Newsgroups: comp.compilers
Date: 24 Mar 1998 22:50:13 -0500
Organization: Compilers Central
References: 98-03-207
Keywords: parse, LL(1)

Martin wrote:
> My CFG grammar can accept:
> a = b = 1;
> and
> a = b;
>
> Is it LL(1)? Yes? How I can make it LL(1)?


Any grammar of the form
    S ::= P1 | P2
    P1 ::= F F1
    P2 ::= F F2
is not LL(1). If F is a nonterminal that could become arbitrarily long,
the grammar isn't LL at all.
To make it LL(1), you must restructure it according to the following
pattern:
    S ::= F F1_or_F2
    F1_or_F2 ::= F1 | F2
This may make your grammar more difficult to read, and it may make it
more difficult to write semantic actions. These problems are among the
reasons why yacc uses LALR(1) grammars instead of LL(k) ones - LR
grammars and their variants don't have this problem, they just defer the
problem of deciding whether it's a P1 or a P2 until they have seen
enough input, while an LR(1) parser must decide when seeing the very
first symbol.


Regards,
Joachim
--


Post a followup to this message

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