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

Felipe Angriman <felipeangriman@gmail.com>
Sun, 13 Jun 2010 13:15:37 -0300

          From comp.compilers

Related articles
Purple Dragon Book: Newbie questions on Chapter 4 text. simonsharry@gmail.com (Harry) (2010-06-08)
Re: Purple Dragon Book: Newbie questions on Chapter 4 text. Pidgeot18@verizon.invalid (Joshua Cranmer) (2010-06-09)
Re: Purple Dragon Book: Newbie questions on Chapter 4 text. felipeangriman@gmail.com (Felipe Angriman) (2010-06-09)
Re: Purple Dragon Book: Newbie questions on Chapter 4 text. simonsharry@gmail.com (Harry) (2010-06-10)
Re: Purple Dragon Book: Newbie questions on Chapter 4 text. cdodd@acm.org (Chris Dodd) (2010-06-12)
Re: Purple Dragon Book: Newbie questions on Chapter 4 text. felipeangriman@gmail.com (Felipe Angriman) (2010-06-13)
| List of all articles for this month |

From: Felipe Angriman <felipeangriman@gmail.com>
Newsgroups: comp.compilers
Date: Sun, 13 Jun 2010 13:15:37 -0300
Organization: Compilers Central
References: 10-06-023 10-06-025 10-06-026
Keywords: parse, theory, books
Posted-Date: 13 Jun 2010 13:37:13 EDT

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


Post a followup to this message

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