6 Mar 2000 23:40:47 -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: | "Joachim Durchholz" <joachim.durchholz@halstenbach.com.or.de> |

Newsgroups: | comp.compilers |

Date: | 6 Mar 2000 23:40:47 -0500 |

Organization: | Compilers Central |

References: | 00-03-029 |

Keywords: | LALR |

Alessandro Muzzetta <muzzetta@videobank.it> wrote:

*>*

*> list: /* empty */*

*> | list NEWLINE*

*> | list expr NEWLINE*

*> ;*

*> expr: ...*

*> ;*

*>*

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

If the first item of an alternative can return the empty string, you

have to add the FIRST of the following item. I.e. the first

alternative of 'list' gives "empty", so this applies to alternatives

that start with 'list'. The second and third alternatives of 'list'

start with 'list', so this applies, giving you NEWLINE and FIRST

(expr) as additional canditates for your FIRST set. (If 'expr' could

return an empty string as well, you'll get NEWLINE a second time from

the third alternative.)

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

No. FOLLOW (list) is what can follow 'list' in an arbitrary context, not

just what can follow within the rules for a specific syntactic

construct. (At least that was the definition last time I looked; FIRST

and FOLLOW are mental constructs that get named and defined at a

particular author's whim, so you can never be totally sure in a

discussion with an unrestricted audience like Usenet.)

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

Anything that allows fast insertions. The best is probably to follow

whatever standard data structure library that you can find for your

language. Rolling one's own data structures is usually more effort than

just obtaining a library and learning to use it.

If you really have to roll your own, first get it to run at all, then

make it fast. I.e. go for a simple linear list (or even a preallocated

array) first, and if it's really a bottleneck, try hash tables or

red-black trees.

But try all alternatives first before doing this - it's a lot of work to

get any of these right. The details depend on the programming language

you're using anyway: In Fortran, dynamic data structures are a pain in

the neck, in C or Pascal there are various libraries of varying

usefulness, in C++, Smalltalk, or Eiffel, you have standard data

structure libraries. (You may even consider switching to another

language to get at such a library, depending on what other factors

determine your choice of language.)

Regards,

Joachim

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.