2 Jul 2003 00:37:31 -0400

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

From: | Derk Gwen <derkgwen@HotPOP.com> |

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

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.