Re: question about lookahead

Beeblebrox <jjan@cs.rug.nl>
16 Feb 1999 23:20:17 -0500

          From comp.compilers
Related articles
question about lookahead snowscan100@yahoo.com (1999-02-15)
Re: question about lookahead jjan@cs.rug.nl (Beeblebrox) (1999-02-16)
Re: question about lookahead torbenm@diku.dk (Torben Mogensen) (1999-02-16)
Re: question about lookahead cfc@world.std.com (Chris F Clark) (1999-02-18)
Re: question about lookahead paul.janssens@skynet.be (JPA) (1999-02-21)
| List of all articles for this month |
From: Beeblebrox <jjan@cs.rug.nl>
Newsgroups: comp.compilers
Date: 16 Feb 1999 23:20:17 -0500
Organization: Groningen University (NL)
References: 99-02-078
Keywords: parse

snowscan100@yahoo.com 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,
Netherlands.
email: jjan@cs.rug.nl

Post a followup to this message

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