Re: FIRST function computation problem.

Derk Gwen <>
2 Jul 2003 00:37:31 -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: Derk Gwen <>
Newsgroups: comp.compilers
Date: 2 Jul 2003 00:37:31 -0400
Organization: Quick STOP Groceries
References: 03-06-103
Keywords: parse
Posted-Date: 02 Jul 2003 00:37:31 EDT

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

Borrowing some notions from Ancona, Dodero, Gianuzzi, and Morgavi _Efficient
Construction of LR(k) States and Tables_, you can easily compute
WEIGHT(A) = length of smallest nonull string A can generate,
and NULLABLE(A) = if A can generate a NULL string.

FW(X...Y...Z,k) = X...Y...Z if WEIGHT(X...Y...Z) < k
                                = X...Y the minimum prefix such that WEIGHT(X...Y)>=k

DUP(X) = {X,e} if NULLABLE(X)
              = {X} if not NULLABLE(X)

DUP(X...Y) = DUP(X) || ... || DUP(Y)

So for FIRST(A,k) let F = {A}
while this adds new elements to F,
    choose an unexamined element of F that contains a nonterminal a..bAX...
            where A --> Y...Z
        and add FW(DUP(a...bY...Z...X...),k) to F
Then FIRST(A,k) is subset of F that are all terminals.

A ::= BCD 2 F
B ::= CAD | x 1 F
C ::= y | e 1 T
D ::= z 1 F

F = {A}
A ::= BCD
FW(DUP(BCD)) = FW({BCD,BD}) = {B}
F = {A;B}
B ::= CAD | x
FW(DUP(CAD)) = FW({CAD,AD}) = {C,A}
FW(DUP(x)) = FW(x) = x
F = {A,B,x;C}
C ::= y | e
FW(DUP(y)) = FW({y}) = {y}
F = {A,B,x,y}
FIRST(A) = {x,y}

Derk Gwen

Post a followup to this message

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