Re: Purple Dragon Book: Newbie questions on Chapter 4 text.

Harry,


> It seems, the three conditions will be necessary *only* when writing
> a table-driven, predictive top-down parser and *not* when writing a
> backtracking, top-down parser. Is this true, btw?


Keep in mind that the conditions are for the grammar, not the parser.
Those conditions establish which grammar belongs to the LL family of
grammars (and in the case of the dragon book - LL(1)) Any grammar that
meets those conditions is an LL(1) grammar, hence it can be parsed by
an LL(1) parser, either a table-driven parser or a code-driven parser.


Backtracking parsers are much more powerful than LL parsers and in
fact they can parse some languages that are not LL. This is why
grammars with fewer restrictions can be parsed by backtracking parser.
The power a backtracking parser lies basically on the fact that if the
parser made a "wrong choice" (a wrong choice is applying a production
rule that doesn't fit the input) it can backtrack to a point where it
can choose another alternative and keep on parsing. LL parser on the
other hand always makes the "right choice". The 3 conditions assure
that a parser will always be able to make right parsing choices
without any backtrack and by looking at most k symbol from the input
(in the case of the dragon book k = 1)


HTH,
Felipe Angriman

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