Re: question about lookahead

Beeblebrox <>
16 Feb 1999 23:20:17 -0500

          From comp.compilers

Related articles
question about lookahead (1999-02-15)
Re: question about lookahead (Beeblebrox) (1999-02-16)
Re: question about lookahead (Torben Mogensen) (1999-02-16)
Re: question about lookahead (Chris F Clark) (1999-02-18)
Re: question about lookahead (JPA) (1999-02-21)
| List of all articles for this month |

From: Beeblebrox <>
Newsgroups: comp.compilers
Date: 16 Feb 1999 23:20:17 -0500
Organization: Groningen University (NL)
References: 99-02-078
Keywords: parse wrote:
> -- why use lookahead when a NPDA can be used to choose all
> productions at the same time (similar to what is done for
> reg exps) ?

Because the deterministic and nondeterministic models are
not equivalent with respect to the languages accepted.
E.g., ww' is accepted by a NPDA, but not by any deterministic PDA.
(note w' is w reversed)

For more on this, see Hopcroft and Ullman, "Introduction to Automata
Theory, Languages and Computation".

Consequence is that we need lookahead as an extra tool to be
able to find a deterministic PDA for a given language.
Jan Jongejan 8-{) --me with moustache
Dept. Comp.Sci.,
Univ. of Groningen,

Post a followup to this message

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