Re: Is this an LL(1) Grammar ?

bmcsweeney@bigfoot.com
30 Mar 1998 21:42:40 -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: bmcsweeney@bigfoot.com
Newsgroups: comp.compilers
Date: 30 Mar 1998 21:42:40 -0500
Organization: Deja News - The Leader in Internet Discussion
References: 98-03-207 98-03-222
Keywords: LL(1), parse

I figure I'm mixing description with implementation but I have to ask:
Would Martin's grammar be suitable as LL(1) if implemented via
recursive descent? As I see it, when token '=' is recognized after a
token symbol (A or B) then making a recursive call back to the current
proc (read as current production rule) would effectively give the
grammar an enhanced LL flavor? Does that make sense? If the grammar
is defined as:


        start = assignment
        assignment = ID '=' assign
                            { if isID( tok) { // not punct, not '=', not KEYWD
                                    gettok() ;
                                    if( isEQL(tok)) assign(); // tok = '='?
                                          // expect ID or NBR here and recurse.
                                    else WhatOP(tok); // determine value of OP
                                }
                                else error( "ID expected!");
                            }
        assign = unaryop term
        unaryop = '!' | '~' | '-'
        term = addop factor
        addop = '-' | '+' | '|'
        factor = mulop symbol
        mulop = '*' | '/' | '&'
        symbol = ID | NBR


then A=B=C=4 would be parsed as (A=(B=(C=4))))


(in forth that would be: A B C dup dup ! ! !
(Sorry, the forth coder in struggles to write forth code all the time!)


and A+B-C*D/E would parse as: CDE*E/B-A+
A B C D E / * - +


Well, I think that's most of it... did I teach myself correctly or did I
completely miss the point of LL(1) and RDP?


"Give it to me straight, Doc!"


brianm.




===
    Alan Southall <alan.southall@bk.bosch.de> wrote:
>
> 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)?
>
> I don't know if I have understood your question properly, as
> the notation you have used is not familar to me, but here
> goes anyway. If you mean is the following BNF LL(1):
>
> prod ::= a = b = 1;
> | a = b;
>
> Then the answer in no. The reason for this is that LL(1)
> requires the first token in production alternatives to be
> unique. Therefore, using your example the parser will not
> know which option in the production it must take. The
> following is LL(1):
>
> prod ::= a = b prod`
>
> prod` ::= = 1;
> | ;
>
> P.S. Have a look in the "Dragon Book" - it covers topics
> like this rather well.
--


Post a followup to this message

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