Wed, 20 Aug 2008 16:50:23 -0400

Related articles |
---|

Recursive Descent Parsers only with LL(1)-grammars? formatzeh@gmx.de (Gilbert Mirenque) (2008-08-20) |

Re: Recursive Descent Parsers only with LL(1)-grammars? parsersinc@earthlink.net (SLK Mail) (2008-08-20) |

Re: Recursive Descent Parsers only with LL(1)-grammars? torbenm@pc-003.diku.dk (2008-08-21) |

Re: Recursive Descent Parsers only with LL(1)-grammars? jaluber@gmail.com (Johannes) (2008-08-21) |

From: | SLK Mail <parsersinc@earthlink.net> |

Newsgroups: | comp.compilers |

Date: | Wed, 20 Aug 2008 16:50:23 -0400 |

Organization: | Compilers Central |

References: | 08-08-041 |

Keywords: | parse, LL(1) |

Posted-Date: | 23 Aug 2008 14:42:55 EDT |

In general, it is very hard (NP-Hard) to determine "where to go next"

for an LL(k) grammar for k>1. Doing it by hand in a hand coded parser

would take forever and produce a huge program because of the large

number of possibilities, if done using naive algorithms. So,

impractical but not impossible, depending on the grammar.

Tools like ANTLR solve this problem by using a linear approximation to

LL(k). SLK does a real LL(k) analysis, usually very quickly. The

complexity of the proprietary algorithm that it uses is proportional

to the number of conflicts present in the grammar, which can become

exponential in the worst case, but not usually, or for any real world

grammars that I have seen.

SLK produces table-driven parsers. However, you can use it to analyze

your LL(k) grammar and tell you what the lookahead token strings are

where k>1. This information can be used to write an LL(k) recursive

descent parser because the number of such strings is small for many

grammars.

I have considered providing a library that would give access to an

LL(k) conflict table. This would give the advantage of tabular "where

to go next" that could be used along with most parsing paradigms, even

LR(k) in an SLR(k) sort of way.

SLK Parser Generator: http://home.earthlink.net/~slkpg/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.