Re: I don't see how they arrive at the parsing table

grocery_stocker <cdalten@gmail.com> wrote in news:08-04-100@comp.compilers:
> The question stems from the following URL
> http://en.wikipedia.org/wiki/LL_parser
>
> For the following grammar rules
>
> 1. S -> F
> 2. S -> ( S + F )
> 3. F -> 1
>
> They have a parsing table for ( 1 + 1 ) that looks like
>
> | ( | ) | 1 | + | $ |
> --+---+---+---+---+---+
> S | 2 | - | 1 | - | - |
> --+---+---+---+---+---+
> F | - | - | 3 | - | - |
> --+---+---+---+---+---+
>
> How do they arrive at this table? For example, they use first '(' from
> the input stream. How do they know know to apply rule 2 and say not
> rule 1?


The table is computed directly from the FIRST sets of the grammar. If
rule N is A -> RHS, then for each terminal t in FIRST(RHS), we put N in
the table for A,t.


In this example, for rule 1, FIRST(F) is '1', so we put 1 in the table at
S,'1'. Similarly, FIRST( "( S + F )" ) is '(', so 2 goes in S,'('. Finally,
FIRST(1) is '1' so 3 goes in F,'1' and the table is complete.


If there are multiple rules for the same terminal that have non-disjoint
FIRST(RHS) sets, then you'll put two rules in the same spot (a conflict)
and the grammar is not LL(1). You also need special handling for any RHS
that may expand to epsilon (the empty string), in which case you also need
to add the rule to A,t for every terminal t in FOLLOW(A) as well.


Chris Dodd
cdodd@acm.org

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