6 Mar 2000 23:38:58 -0500

Related articles |
---|

Computing FIRST(X) for a left recursive grammar muzzetta@videobank.it (2000-03-06) |

Re: Computing FIRST(X) for a left recursive grammar vugluskr@unicorn.math.spbu.ru (2000-03-06) |

Re: Computing FIRST(X) for a left recursive grammar torbenm@diku.dk (2000-03-06) |

Re: Computing FIRST(X) for a left recursive grammar joachim.durchholz@halstenbach.com.or.de (Joachim Durchholz) (2000-03-06) |

Re: Computing FIRST(X) for a left recursive grammar rsherry@home.com (Robert Sherry) (2000-03-07) |

Re: Computing FIRST(X) for a left recursive grammar johnmce@texas.net (2000-03-07) |

From: | vugluskr@unicorn.math.spbu.ru (Roman Shaposhnick) |

Newsgroups: | comp.compilers |

Date: | 6 Mar 2000 23:38:58 -0500 |

Organization: | St.Petersburg University |

References: | 00-03-029 |

Keywords: | LALR, parse |

On 6 Mar 2000 00:32:26 -0500, Alessandro Muzzetta wrote:

*>Hello,*

*>*

*>can some kind soul please answer this silly question of mine...*

*>*

*>Assuming you have the following yacc rules*

*>*

*>list: /* empty */*

*> | list NEWLINE*

*> | list expr NEWLINE*

*> ;*

*>expr: ...*

*> ;*

*>*

*>How do I calculate FIRST(list) for this left recursive grammar?*

First of all, I can not help you calculate FIRST(list), since I don't

know what it is, but I cat certainly help with FIRSTk(list). The

simplest definition for FIRSTk(N) is the set of terminal strings

each has no more than k terminals that can be a prefix of a

terminal string "produced" from nonterminal N. E.g.

N : 'a'

| 'a' 'b'

| 'a' 'b' 'c'

FIRST1(N) = { 'a' }

FIRST2(N) = { 'a', 'ab' }

FIRST3(N) = { 'a', 'ab', 'abc' }

*>I'm*

*>working on an SLR parser generator, and I don't know how to handle*

*>this case. What should FIRST(list) contain besides the empty string?*

*>FIRST(NEWLINE) and FIRST(expr)???*

I assume that you are talking about FIRST1(list) ? If yes, than

FIRST1(list) = { EMPTY-STRING, NEWLINE, FIRST1(expr) }.

If you would like to know more general algorithm -- fill free to ask.

Thanks,

Roman.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.