Re: LL(1)/Recursive Descent Parsing Question

"Peter H. Froehlich" <pfroehli@ics.uci.edu>
21 Mar 2002 21:53:43 -0500

          From comp.compilers

Related articles
LL(1)/Recursive Descent Parsing Question neelk@alum.mit.edu (2002-03-19)
Re: LL(1)/Recursive Descent Parsing Question jacob@jacob.remcomp.fr (jacob navia) (2002-03-21)
Re: LL(1)/Recursive Descent Parsing Question pfroehli@ics.uci.edu (Peter H. Froehlich) (2002-03-21)
Re: LL(1)/Recursive Descent Parsing Question joachim_d@gmx.de (Joachim Durchholz) (2002-03-22)
Re: LL(1)/Recursive Descent Parsing Question dr_feriozi@prodigy.net (SLK Parsers) (2002-03-25)
| List of all articles for this month |

From: "Peter H. Froehlich" <pfroehli@ics.uci.edu>
Newsgroups: comp.compilers
Date: 21 Mar 2002 21:53:43 -0500
Organization: Compilers Central
References: 02-03-106
Keywords: parse
Posted-Date: 21 Mar 2002 21:53:43 EST

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


Post a followup to this message

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