Re: predictive parsing

j0mbolar wrote:
> I am running into an issue with my LL(1) parser
> in representing some of the nonterminals.
>
> The problem is this:
>
> suppose that I have the following grammar:
>
> start: A B
> A: C | C A | D | D A
> B: '*'
> C: '!' | '@'
> D: 'X' | 'Y'
>
> Where A, B, C, D are nonterminals
> that are represented by functions.
>
> The issue arises in representing the following production:
> A: C | C A | D | D A
>
> Imagine my initial lookahead token is '!'.


So your A expands to either C or to C A, because ! only is in the FIRST
set of C. If you want a LL parser, you'd usually have to transform the
above grammar into something like:
A: C A1 | D A2
A1: empty | A
A2: empty | A


so the parser knows right at the beginning which production to choose.
If A has different clauses that both start with C, as in your example,
an LL parser couldn't choose on of them without lookahead (while LR can,
because it only chooses after parsing the whole production, if I'm not
mistaken).


> C() would be called and I would get my next
> token. How then could I determine if A() should
> be called or if the lookahead token applies to B,
> where I should return and then call B?


You would end up after C, so in my grammar you are inside A1. Either
now you get something which is FIRST(A), or you return.


> I would also like to generate a syntax error
> if the initial lookahead token does not follow
> one of the rules of A.


Sure. If there is no "empty" production rule, and you have some input
that doesn't match, print an error.


> I think this has to do with properly computing
> what should be in the FIRST() set.


Yes, for predictive parsing knowing FIRST is crucial (unless all your
rules start with a terminal symbol, which would be trivial to turn into
a parser).


--
Suffering from Gates-induced brain leakage...

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