Re: Computing "first" in LR(1) parsing

"Sönke Kannapinn" <kan@cs.tu-berlin.de>
29 Nov 2001 22:52:19 -0500

          From comp.compilers
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)
| List of all articles for this month |
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.