Re: Push Down Automata

torbenm@diku.dk (Torben AEgidius Mogensen)
10 Feb 2000 01:15:09 -0500

          From comp.compilers
Related articles
Push Down Automata an145@city.ac.uk (2000-02-05)
Re: Push Down Automata torbenm@diku.dk (2000-02-10)
| List of all articles for this month |
From: torbenm@diku.dk (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

an145@city.ac.uk (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 (torbenm@diku.dk)

Post a followup to this message

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