|Push Down Automata email@example.com (2000-02-05)|
|Re: Push Down Automata firstname.lastname@example.org (2000-02-10)|
|From:||email@example.com (Torben AEgidius Mogensen)|
|Date:||10 Feb 2000 01:15:09 -0500|
|Organization:||Department of Computer Science, U of Copenhagen|
firstname.lastname@example.org (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
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 (email@example.com)
Return to the
Search the comp.compilers archives again.