Re: predictive parsing and non-recursive predictive parsing

torbenm@pc-003.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Mon, 30 Jun 2008 13:02:42 +0200

          From comp.compilers

Related articles
[9 earlier articles]
Re: predictive parsing and non-recursive predictive parsing torbenm@pc-003.diku.dk (2008-06-27)
Re: predictive parsing and non-recursive predictive parsing kamalpr@hp.com (kamal) (2008-06-27)
Re: predictive parsing and non-recursive predictive parsing max@gustavus.edu (Max Hailperin) (2008-06-28)
Re: predictive parsing and non-recursive predictive parsing DrDiettrich1@aol.com (Hans-Peter Diettrich) (2008-06-28)
Re: predictive parsing and non-recursive predictive parsing ang.usenet@gmail.com (Aaron Gray) (2008-06-28)
Re: predictive parsing and non-recursive predictive parsing max@gustavus.edu (Max Hailperin) (2008-06-28)
Re: predictive parsing and non-recursive predictive parsing torbenm@pc-003.diku.dk (2008-06-30)
Re: predictive parsing and non-recursive predictive parsing ang.usenet@gmail.com (Aaron Gray) (2008-06-30)
| List of all articles for this month |

From: torbenm@pc-003.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Newsgroups: comp.compilers
Date: Mon, 30 Jun 2008 13:02:42 +0200
Organization: Department of Computer Science, University of Copenhagen
References: 08-06-053 08-06-056 08-06-064 08-06-067 08-06-069 08-06-076
Keywords: parse
Posted-Date: 30 Jun 2008 09:42:18 EDT

"Aaron Gray" <ang.usenet@gmail.com> writes:


> "Torben "Fgidius" Mogensen" <torbenm@pc-003.diku.dk> wrote
>> "Aaron Gray" <ang.usenet@gmail.com> writes:
>>>> there is a less-known, elegant recursive formulation for LR parsers
>>>> as well. Google "recursive LR parser" for a few papers.
>>>
>>> Is this what is refered to as Recursive Ascent ?
>>
>> It is indeed.


> 1) How does it work as I cannot remember, it was used in Philip's Elegant
> Compiler compiler infrastructure, which I looked at some eight years ago.
> Would you please give a description of how it works for those who don't
> know.


Basically, you use the call stack as a replacement of the explicit
stack. A shift is a call and a reduce is a return (through several
stack levels).


A reasonably good account can be found in "The Essense of LR Parsing"
by Sperber and Thiemann (PEPM'95, ACM Press). It includes several
different implementations in Scheme and a description of how you can
use partial evaluation to generate specialised parsers from the
general parser.


> 2) Is it limited to LR(1) lookahead wise ?


No.


Torben


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.