Re: LL(1)/Recursive Descent Parsing Question

On Tuesday, March 19, 2002, at 08:54 , Neelakantan Krishnaswami wrote:


> Is there an algorithm that will take a general context-free grammar,
> and then computes an epsilon-free, left-factored, left-recursive
> grammar from it if that is possible, and signals an error if it isn't?


Well, one approach would be to use a LL(1) parser generator like
COCO and feed it your grammar in EBNF. That would tell you what is
wrong. If you need to have your grammar in LL(1), then why not work
with a tool like that.


I have to admit that a tool that takes any grammar and then spits
out whether it is in one or the other class would be nice, but I
would guess the problem is undecidable. Insights, anybody?


On a personal note, I learned to write LL(1) grammars by reading
several of them excessively, so when I sit down to design a grammar
these days, it will pretty much be LL(1) without much work on my
side. Only drawback with this "undecent exposure" to LL(1) grammars
is that I have a hard time using Bison... :-)


> sequence(start:RPAREN, element:<expr>, delimiter:COMMA, close:LPAREN)


Huh? What is wrong with


      Sequence = "(" Expression {"," Expression} ")" .


in EBNF? Meyer's book on programming language theory defines
notations like the one you are alluding to, but mostly for abstract
grammars.


Peter
--
Peter H. Froehlich []->[!]<-[] http://nil.ics.uci.edu/~phf/
OpenPGP: D465 CBDD D9D2 0D77 C5AF 353E C86C 2AD9 A6E2 309E

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