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

Thank for all replies and private communications with Chris Dodd
<chrisd@reservoir.com>. Here is a summary response:


In article 01-11-129, "Sönke Kannapinn"
<kan@cs.tu-berlin.de> wrote:
>The algorithm described in the old Aho et
>al. "Compilers..." book produces correct results but is inelegant and
>"slow". (Similar remarks hold for "follow".)


Whenever it converges:


In article 01-11-142, max@gustavus.edu (Max Hailperin) wrote:
>What Aho, Sethi, and Ullman do not clearly explain is that this is an
>iterative algorithm, convering on a least fixed point by working up
>from below. So at each point in the iteration, you have some lower
>bound on the eventual FIRST sets. Based on the current (iteration n)
>lower bounds on the FIRST(yi), you calculate a new (iteration n+1)
>lower bound on FIRST(x), in the manner you summarize above.


This was what confused me: Strictly speaking, the description in Aho,
Sethi, and Ullman is mathematically incorrect for use with LR(1), as it
may not converge. (An LL(1) grammar cannot contain left recursion, so the
algorithm always converges for LL(1) grammars.)


In article 01-11-144, kgw-news@stiscan.com wrote:
>Compute the empty relation first.
>empty(x) if x->
> or x->y[1],...,y[n] and empty(y[i])
>This can be done by iterating until there are no changes
>or if you have an inverted production list(used by)
>you can add potentially affected productions to a todo list
>until the todo list becomes empty.
>
>Then first and last and next are easy and local.


Actually, I was thinking of this myself, so it is good that you confirm
this is a good way to go. Your "empty(x)" function above is in reality
what one would denote $first_0(x)$. For any n >= 0, one defines
$first_n(x)$ to be the set of at most n terminals long heads of all
strings derivable from x with respect to the given grammar (including the
empty string, if derivable). Then $first = first_1$.


I have a book by Walte, Goos, "Compiler Construction", which I like
because it uses a more mathematical language, describing some of this.
(But most would think it is overly formal and unreadable. It is a good
complement to more informal descriptions.)


Also, Axel Kittenberger <axel@dtone.org> pointed out a nice book available
online at:
    http://www.cs.vu.nl/~dick/PTAPG.html
with some details.


    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/>

Return to the comp.compilers page.
Search the comp.compilers archives again.