Re: FIRST function computation problem.

  mefrill@yandex.ru (Vladimir) wrote:


>I have a problem with FIRST function for 1 lookahead symbol evalation.
>To lookup such the symbols for some nonterminal A I am doning follows:
>
>1. go through all rules that left part is A. Here I do following:
>a) If I have rule A --> aB, where a is terminal. I just add this
>terminal to lookahead set for A.
>b) If I have rule A --> e, where e is epsilon, I add e to lookahead
>set for A.
>c) If I have rule A --> B C ... where B - nonterminal, I at first
>compute the lookahead set for B, if B's lookahead set contains
>epsilon, check C and etc. I found that recursive function here is the
>best. But I do not know how to work with rules like follows: A --> B,
>B --> C A D... To compute lookahead set for A I have to at first
>compute lookaheads for B, but if lookaheads for C contain epsilon I
>need to know the same about A to understand do checking of D or
>not...
>
>Please, help to decide this problem and there may be the good FIRTS
>computaion algorithm?


(This is coming up so frequently, so shouldn't this be in the
comp.compilers FAQ? :-)


There are two ways to compute FIRST:


The first method is to simply recurse through all steps above for FIRST(A)
for all nonterminals A simultaneously until the process terminates: It
must terminate, as one has an ascending chain of sets within a given
finite set. I practise, one will know that it has terminated when one has
worked through all nonterminals once, and that produces no more additions
to the FIRST(A) sets. It is easy see that when it has terminated, these
sets must be the FIRST(A) sets.


The second method is to use Tarjan's strongly connected components (SCC)
algorithm:
        http://www1.ics.uci.edu/~eppstein/161/960220.html#sca
Adapted to computing FIRST:
        http://compilers.iecc.com/comparch/article/01-04-079
It just works through the incidence graph once.


For example, Bison http://gnu.org/ uses the first method. If you want to
implement the second method, you are most welcome.


    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <remove.haberg@member.ams.org>
                                    * Home Page: <http://www.math.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>

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