29 Nov 2001 23:05:49 -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: | haberg@matematik.su.se (Hans Aberg) |

Newsgroups: | comp.compilers |

Date: | 29 Nov 2001 23:05:49 -0500 |

Organization: | Mathematics |

Keywords: | parse, yacc, question |

Posted-Date: | 29 Nov 2001 23:05:49 EST |

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.

This seems to differ from the description in say Aho et al

"Compilers", which creates the deterministic machine directly. (The

book has hints to the effect that this corresponds to the NFA -> DFA

translation, but does not describe this explicitly in detail.)

Hans Aberg * Anti-spam: remove "remove." from email address.

* Email: Hans Aberg <remove.haberg@member.ams.org>

* Home Page: <http://www.matematik.su.se/~haberg/>

* AMS member listing: <http://www.ams.org/cml/>

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.