16 Feb 1999 23:20:39 -0500

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) |

From: | Torben Mogensen <torbenm@diku.dk> |

Newsgroups: | comp.compilers |

Date: | 16 Feb 1999 23:20:39 -0500 |

Organization: | Compilers Central |

References: | 99-02-078 |

Keywords: | parse |

*>It Seems Like Lookahead Is Used By Various Parsing Methods*

*>To Choose (Disambiguate) Between Several Productions That*

*>Can Be Taken At Any Point.*

*>My Question Is Why Lookahead At All ? Just Use A*

*>*Non Deterministic* PDA As Your Engine. (Just As You Use*

*>NFA'S To Find Reg-Expressions). A NPDA Would Then Choose*

*>All Productions That Were Applicable, As Opposed To Looking*

*>Ahead And Deciding Which One To Choose Beforehand.*

Some parser generators (e.g. Ratatosk, which can be found through my

webpage at http://www.diku.dk/users/torbenm) use nondeterministic

PDA's, but there is a cost penalty: The parsers may use up to cubic

time compared to linear time for deterministic PDA's. It is even worse

if the NPDA's are implemented naively by backtracking (as is the case

with Ratatosk). However, in practice you rarely get into the worst

case, and there are numerous examples from real programming languages

that require unbounded lookahead but are easily handled in (average)

linear time by a naively implemented NPDA.

See also Daniel J. Salomon, Gordon V. Cormack: Scannerless NSLR(1)

Parsing of Programming Languages from PLDI'89.

*>The NPDA Would Of Course Be Converted Into An *Equivalent**

*>Deterministic PDA In Order To Actually Run It...*

That, I'm afraid is not possible. Or to be precise, it is AFAIK still

an open problem: Noone knows of a way to convert arbitrary NPDA's to

DPDA's (or even methods that can simulate NPDA's in linear time) but

it has not been proven to be impossible, though few people expect it

to be.

Torben Mogensen (torbenm@diku.dk)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.