21 Mar 2002 21:53:43 -0500

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

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.