Re: FIRST function computation problem.

# 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,
WEIGHT(X...Y) = WEIGHT(X)+...+WEIGHT(Y),
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.


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


FIRST(A)
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 http://derkgwen.250free.com/html/index.html
TEMPORARILY CLOSED
BE OPENED AFTER FIRST PERIOD

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