Re: FIRST function computation problem. (Hans Aberg)
2 Jul 2003 00:39:09 -0400

          From comp.compilers

Related articles
FIRST function computation problem. (2003-06-22)
Re: FIRST function computation problem. (Derk Gwen) (2003-07-02)
Re: FIRST function computation problem. (2003-07-02)
Re: FIRST function computation problem. (2003-07-02)
Re: FIRST function computation problem. (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2003-07-02)
| List of all articles for this month |

From: (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 (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
>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)
Adapted to computing FIRST:
It just works through the incidence graph once.

For example, Bison 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 <>
                                    * Home Page: <>
                                    * AMS member listing: <>

Post a followup to this message

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