Re: Push Down Automata (Torben AEgidius Mogensen)
10 Feb 2000 01:15:09 -0500

          From comp.compilers

Related articles
Push Down Automata (2000-02-05)
Re: Push Down Automata (2000-02-10)
| List of all articles for this month |

From: (Torben AEgidius Mogensen)
Newsgroups: comp.compilers
Date: 10 Feb 2000 01:15:09 -0500
Organization: Department of Computer Science, U of Copenhagen
References: 00-02-020
Keywords: parse (Shah I) writes:

>I am currently doing a project which converts the rules of a Context
>Free Grammar into Push Down Automata. This way you can check programs
>to see if they are valid. Does anyone know if this has been done
>before or is currently being used

Most compiler books show one or two ways of converting context free
grammars to push-down automata: Predictive parsers and LR parsers.
Normally, these parsers are intended for deterministic PDA's, so
parse-tables with conflicts are rejected. But these just represent
nondeterministic PDA's.

The above are one-way automata. Some CFG's that when converted to
one-way PDA's give rise to nondeterminism can be converted to
deterministic two-way PDA's. AFAIK, it is still an open question if
all CFG's can be thus converted.

Torben Mogensen (

Post a followup to this message

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