Joachim Durchholz <>
23 Aug 2003 23:06:11 -0400

          From comp.compilers

Related articles
DFAs,NFAs,REs,CFGs,PDAs ARGH! (Anthony Webster) (2003-08-04)
Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! (2003-08-10)
Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! (Thomas Skora) (2003-08-10)
Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! (Derk Gwen) (2003-08-10)
Re: Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! (Bob Foster) (2003-08-20)
Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! (Joachim Durchholz) (2003-08-23)
| List of all articles for this month |

From: Joachim Durchholz <>
Newsgroups: comp.compilers
Date: 23 Aug 2003 23:06:11 -0400
Organization: Compilers Central
References: <> <084801c36559$e4bea560$6701a8c0@snobird> <> 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 :-)


Post a followup to this message

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