|Recursive Descent Parsers only with LL(1)-grammars? firstname.lastname@example.org (Gilbert Mirenque) (2008-08-20)|
|Re: Recursive Descent Parsers only with LL(1)-grammars? email@example.com (SLK Mail) (2008-08-20)|
|Re: Recursive Descent Parsers only with LL(1)-grammars? firstname.lastname@example.org (2008-08-21)|
|Re: Recursive Descent Parsers only with LL(1)-grammars? email@example.com (Johannes) (2008-08-21)|
|From:||firstname.lastname@example.org (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)|
|Date:||Thu, 21 Aug 2008 11:19:57 +0200|
|Organization:||Department of Computer Science, University of Copenhagen|
|Posted-Date:||23 Aug 2008 14:43:34 EDT|
Gilbert Mirenque <email@example.com> 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.
Return to the
Search the comp.compilers archives again.