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

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)

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