|I don't see how they arrive at the parsing table email@example.com (grocery_stocker) (2008-04-26)|
|Re: I don't see how they arrive at the parsing table firstname.lastname@example.org (Chris Dodd) (2008-04-27)|
|From:||Chris Dodd <email@example.com>|
|Date:||Sun, 27 Apr 2008 23:36:54 -0500|
|Posted-Date:||28 Apr 2008 22:43:39 EDT|
grocery_stocker <firstname.lastname@example.org> wrote in news:email@example.com:
> The question stems from the following URL
> 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.
Return to the
Search the comp.compilers archives again.