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

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.

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