20 Dec 2001 02:03:48 -0500

Related articles |
---|

Bison version of the LALR(1) algorithm haberg@matematik.su.se (2001-11-29) |

Re: Bison version of the LALR(1) algorithm pjj@cs.man.ac.uk (Pete Jinks) (2001-12-07) |

Re: Bison version of the LALR(1) algorithm johnl@iecc.com (2001-12-07) |

Re: Bison version of the LALR(1) algorithm haberg@matematik.su.se (2001-12-15) |

Re: Bison version of the LALR(1) algorithm thp@cs.ucr.edu (2001-12-20) |

From: | thp@cs.ucr.edu |

Newsgroups: | comp.compilers |

Date: | 20 Dec 2001 02:03:48 -0500 |

Organization: | University of California, Riverside |

References: | 01-12-063 |

Keywords: | parse, LALR |

Posted-Date: | 20 Dec 2001 02:03:48 EST |

Hans Aberg <haberg@matematik.su.se> wrote:

[...]

*: The book at http://www.cs.vu.nl/~dick/PTAPG.html explains how to produce*

*: non-deterministic parsers from grammars.*

Given a context-free grammar, it's easy to produce an equivalent

nondeterministic push-down automaton, and vice versa. Unfortunately,

there are nondeterministic pushdown automata (and their equivalent

context-free grammars) for which there are no equivalent deterministic

push-down automata. The goal of LR-parsing is to come up with

algorithms -- generalizations of the set-of-states algorithm for

determinizing nondeterministic finite-state automata -- that can

determinize as many nondeterministic push-down automata as possible

without the resulting deterministic PDAs being overly large. (As of

the mid '70s, the LALR algorithm was considered to be the right

tradeoff between generality and size of the resulting DPDAs.)

Tom Payne

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.