7 Dec 2001 23:40:46 -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: | Pete Jinks <pjj@cs.man.ac.uk> |

Newsgroups: | comp.compilers |

Date: | 7 Dec 2001 23:40:46 -0500 |

Organization: | Computer Science Dept, University of Manchester |

References: | 01-11-134 |

Keywords: | yacc |

Posted-Date: | 07 Dec 2001 23:40:46 EST |

Hans Aberg wrote:

*>*

*> Can somebody give a reference to a description of the LALR(1)*

*> algorithm that Bison uses?*

*>*

*> The file state.h of the Bison sources says that first, a*

*> non-deterministic finite state machine that parses the specified*

*> grammar is created; it is then converted into a deterministic finite*

*> state machine.*

I don't know what Bison uses, but your description sounds like the

algorithm I first came across in:

Syntax Analysis and Software Tools

K.John Gough

Addison-Wesley 1988

chapter 9 Bottom-up parsing

The references there point to

D.E.Knuth (1965)

On the translation of languages from left to right

Information and control v8 pp323-350

which apparently covers both this and the "usual" form of the algorithm.

--

Peter J. Jinks, Room 2.99, Department of Computer Science,

University of Manchester, Oxford Road, Manchester, M13 9PL, U.K.

(+44/0)161-275 6186 http://www.cs.man.ac.uk/~pjj

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.