Thu, 21 Aug 2008 11:19:57 +0200

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: | torbenm@pc-003.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen) |

Newsgroups: | comp.compilers |

Date: | Thu, 21 Aug 2008 11:19:57 +0200 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 08-08-041 |

Keywords: | parse, LL(1) |

Posted-Date: | 23 Aug 2008 14:43:34 EDT |

Gilbert Mirenque <formatzeh@gmx.de> writes:

*> I'm not so familiar with compiler construction just interested in it.*

*> What appears curious is that I have heard that it is only possible to*

*> implement recursive descent parsers for LL(1)-grammars. But I imagine*

*> that it isn't a problem to look ahead more than just one symbol. So my*

*> question is why it is only possible for LL(1)-grammars?*

That depends on how you define recursive descent. It is often defined

as deterministically deciding the next action by only looking at the

next input symbol. This effectively reduces lookahead to 1, but it is

easy to generalise recursive descent to arbitrary lookaheads and even

backtracking, which will allow parsing larger classes of grammars.

If you allow backtracking, you can parse all CF languages, but time

may be exponential.

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.