25 Mar 2002 01:14:12 -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: | "SLK Parsers" <dr_feriozi@prodigy.net> |

Newsgroups: | comp.compilers |

Date: | 25 Mar 2002 01:14:12 -0500 |

Organization: | Parsers Inc. |

References: | 02-03-106 |

Keywords: | parse |

Posted-Date: | 25 Mar 2002 01:14:12 EST |

Neelakantan Krishnaswami <neelk@alum.mit.edu> wrote in message

*> I'm working on the syntax for a small programming language, and I'd*

*> like to make sure that my language is parseable with an LL(1) grammar.*

*> However, I'm still messing around with the grammar, and it's quite*

*> unpleasant to have to write my grammar rules in an epsilon-free,*

*> left-factored left-recursion-free form.*

LL(1) grammars are not required to be epsilon-free. The need to left-factor

and eliminate left-recursion justifiably gives top-down grammars a bad

reputation. The indirect forms are even much more trouble to handle than the

direct forms. For example,

A -> d e | B

B -> C

C -> D

D -> d f

The indirect forms require first hoisting up the offending productions

until a direct form results, and then removing the direct form.

There are published algorithms that will remove these constructs from

somewhat limited grammar forms. One in the Dragon book requires an

epsilon-free grammar to guarantee success, so I assume this is why you

included that requirement. The algorithms that I have seen tend to

transform the original grammar in such a way as to make it pretty much

unrecognizable, so useless to the human reader.

SLK contains new heuristics that can left-factor and remove

left-recursion from context-free grammars. The resulting grammars are

usually quite readable. This is especially true for left-recursion

elimination, which tends to be straightforward.

A benefit of LL(k) over LL(1) is that left-factoring is not always

necessary. The grammar shown above is LL(2), but not LL(1). SLK can

detect which productions do not need to be left-factored for a given k

value, and leave them alone.

The free educational version of SLK on http://parsers.org/slk handles

small grammars of up to 64 nonterminals and 256 productions.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.