2 Jul 2003 00:39:09 -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: | haberg@matematik.su.se (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 |

mefrill@yandex.ru (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*

*>not...*

*>*

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

algorithm:

http://www1.ics.uci.edu/~eppstein/161/960220.html#sca

Adapted to computing FIRST:

http://compilers.iecc.com/comparch/article/01-04-079

It just works through the incidence graph once.

For example, Bison http://gnu.org/ 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 <remove.haberg@member.ams.org>

* Home Page: <http://www.math.su.se/~haberg/>

* AMS member listing: <http://www.ams.org/cml/>

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.