29 Nov 2001 22:52:19 -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: | "Sönke Kannapinn" <kan@cs.tu-berlin.de> |

Newsgroups: | comp.compilers |

Date: | 29 Nov 2001 22:52:19 -0500 |

Organization: | Siemens Inc. |

References: | 01-11-123 |

Keywords: | LR(1), parse |

Posted-Date: | 29 Nov 2001 22:52:19 EST |

Hello,

First of all, note that, in general, there is no need for a special

LR(k) version of "first". "first" maps nonterminals to k-length

strings of terminal symbols and depends on the grammar only, not on

any parsing algorithm. Circular dependencies between (computation

orders of) first(x) sets have nothing to do with LR(k)-ness.

(Essentially, they indicate left recursion which is no problem for

LR(k).) You need an appropriate algorithm to compute "first", namely

an algorithm that deals with the strongly connected components in a

certain directed graph. The algorithm described in the old Aho et

al. "Compilers..." book produces correct results but is inelegant and

"slow". (Similar remarks hold for "follow".)

I have commented on this some time ago in comp.compilers. I hope that

you will find the contents of

http://compilers.iecc.com/comparch/article/01-04-079

satisfying. (Sorry for a few typos there.)

Regards,

Soenke Kannapinn

--

Dr.-Ing. Sönke Kannapinn

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.