26 Nov 2001 21:57:11 -0500

Related articles |
---|

Computing "first" in LR(1) parsing remove.haberg@matematik.su.se (2001-11-26) |

Re: Computing "first" in LR(1) parsing kan@cs.tu-berlin.de (Sönke Kannapinn) (2001-11-29) |

Re: Computing "first" in LR(1) parsing chrisd@reservoir.com (2001-11-29) |

Re: Computing "first" in LR(1) parsing max@gustavus.edu (2001-11-29) |

Re: Computing "first" in LR(1) parsing kgw-news@stiscan.com (2001-11-29) |

Re: Computing "first" in LR(1) parsing remove.haberg@matematik.su.se (2001-12-03) |

From: | remove.haberg@matematik.su.se (Hans Aberg) |

Newsgroups: | comp.compilers |

Date: | 26 Nov 2001 21:57:11 -0500 |

Organization: | Mathematics |

Keywords: | LR(1) |

Posted-Date: | 26 Nov 2001 21:57:11 EST |

I want to compute the function "first" of LR(1) parsing: If x is a

string of grammar symbols, first(x) is the set of terminals that begin

the strings derivable from x with respect to the given grammar, plus

the empty string, if derivable as well. In Aho et al, "Compilers", sec

4.4, p.189, 3, it says that if x is a nonterminal and there is a

production x -> y1 ... yk, then to first(x) one should add first(yi)

if the empty string is part of first(y1), ..., first(y{i-1}).

But it does not say what happens if this procedure recurses, that is,

if say when computing first(y1), one recurses back via some other

relations to first(x). If that happens, is that not a LR(1) grammar,

or how should this situation be handled?

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.