Re: DFAs,NFAs,REs,CFGs,PDAs ARGH!

Joachim Durchholz <joachim.durchholz@web.de>
23 Aug 2003 23:06:11 -0400

          From comp.compilers
Related articles
DFAs,NFAs,REs,CFGs,PDAs ARGH! tony@transCendenZ.co.uk (Anthony Webster) (2003-08-04)
Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! p2sam@uwaterloo.ca (2003-08-10)
Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! usenet0@skora.net (Thomas Skora) (2003-08-10)
Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! derkgwen@HotPOP.com (Derk Gwen) (2003-08-10)
Re: Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! bobkfoster@comcast.net (Bob Foster) (2003-08-20)
Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! joachim.durchholz@web.de (Joachim Durchholz) (2003-08-23)
| List of all articles for this month |
From: Joachim Durchholz <joachim.durchholz@web.de>
Newsgroups: comp.compilers
Date: 23 Aug 2003 23:06:11 -0400
Organization: Compilers Central
References: <20030818051131.4276.qmail@tom.iecc.com> <084801c36559$e4bea560$6701a8c0@snobird> <Pine.BSI.4.56.0308181033270.26284@tom.iecc.com> 03-08-060
Keywords: parse
Posted-Date: 23 Aug 2003 23:06:11 EDT

Bob Foster wrote:
>
> [...] What Vere actually found was that a context-free
> language can be parsed as a nested regular language if it observes a
> few not very onerous restrictions with respect to recursion. The first
> (conventional) restriction is that left recursion is either removed or
> disallowed. The second (unconventional) restriction can be summed up
> tidily as "it cannot be ambiguous whether to push or pop". In other
> words, there cannot be an ambiguous choice one branch of which is in
> the First set of a recursive rule and another not, nor an ambiguous
> choice one branch of which is in the Follow set of a recursive rule
> and another not.


Do you have a URL that lists the algorithm in pseudocode, preferrably
with a (short) explanation how and why it works? I'd like to experiment
with that approach, but I'd like to avoid stupid mistakes :-)


Regards,
Jo

Post a followup to this message

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