Re: Computing FIRST(X) for a left recursive grammar

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

Return to the comp.compilers page.
Search the comp.compilers archives again.