6 Mar 2000 23:39:15 -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: | torbenm@diku.dk (Torben AEgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | 6 Mar 2000 23:39:15 -0500 |

Organization: | Department of Computer Science, U of Copenhagen |

References: | 00-03-029 |

Keywords: | LALR |

muzzetta@videobank.it (Alessandro Muzzetta) writes:

*>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? 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)??? Wouldn't that be the follow set of*

*>list?*

You should be able to find the answer to this in any textbook that

describes parser generation. Basically, when treating a rule like

list -> list expr NEWLINE

you must know if list and expr can generate the empty string. IN some

textbooks (e.g., The Dragon Book) this is indicated by epsilon being in

the FIRST set. However, I prefer to keep this separate and calculate a

nullable function first, as done in, e.g., Appels "Tiger" books.

It is not hard to see that list is nullable (the first production is a

dead giveaway) but I can't see if expr is. I'll assume that it isn't.

The equations generated for FIRST(list) are then:

/* list -> */

\emptyset \subseteq FIRST(list) /* this is vacuous */

/* list -> list NEWLINE */

FIRST(list) \cup FIRST(NEWLINE) \subseteq FIRST(list)

/* list -> list expr NEWLINE */

FIRST(list) \cup FIRST(expr NEWLINE) \subseteq FIRST(list)

where \cup is the set-union symbol (using TeX-notation here). This

quickly reduces to FIRST(list) = FIRST(expr) \cup { NEWLINE }

*>Another question: what are suitable data structures for representing*

*>sets of arbitrary strings denoting the first/follow set of a symbol?*

*>Fast insertions are necessary.*

You don't want to use sets of strings, you want to use sets of tokens.

Give each token a number and use bit-vectors. This makes all the set

operations very fast.

Torben Mogensen (torbenm@diku.dk)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.