# Re: FIRST function computation problem.

## Derk Gwen <derkgwen@HotPOP.com>2 Jul 2003 00:37:31 -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: 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,
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
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}
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

Post a followup to this message