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

Chris Dodd <cdodd@acm.org>
Sun, 27 Apr 2008 23:36:54 -0500

          From comp.compilers

Related articles
I don't see how they arrive at the parsing table cdalten@gmail.com (grocery_stocker) (2008-04-26)
Re: I don't see how they arrive at the parsing table cdodd@acm.org (Chris Dodd) (2008-04-27)
| List of all articles for this month |

From: Chris Dodd <cdodd@acm.org>
Newsgroups: comp.compilers,comp.theory
Date: Sun, 27 Apr 2008 23:36:54 -0500
Organization: Compilers Central
References: 08-04-100
Keywords: parse, LL(1)
Posted-Date: 28 Apr 2008 22:43:39 EDT

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


Post a followup to this message

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