Re: Recursive Descent Parsers only with LL(1)-grammars?

torbenm@pc-003.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Thu, 21 Aug 2008 11:19:57 +0200

          From comp.compilers

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)
| List of all articles for this month |

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.