# Re: FIRST function computation problem.

## haberg@matematik.su.se (Hans Aberg)2 Jul 2003 00:39:09 -0400

From comp.compilers

Related articles
FIRST function computation problem. mefrill@yandex.ru (2003-06-22)
Re: FIRST function computation problem. derkgwen@HotPOP.com (Derk Gwen) (2003-07-02)
Re: FIRST function computation problem. torbenm@diku.dk (2003-07-02)
Re: FIRST function computation problem. haberg@matematik.su.se (2003-07-02)
Re: FIRST function computation problem. soenke.kannapinn@wincor-nixdorf.com (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2003-07-02)
| List of all articles for this month |

 From: haberg@matematik.su.se (Hans Aberg) Newsgroups: comp.compilers Date: 2 Jul 2003 00:39:09 -0400 Organization: Mathematics References: 03-06-103 Keywords: parse Posted-Date: 02 Jul 2003 00:39:09 EDT

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