30 Mar 1998 21:42:40 -0500

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) |

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.