Wed, 9 Jun 2010 21:32:07 -0300

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) |

From: | Felipe Angriman <felipeangriman@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Wed, 9 Jun 2010 21:32:07 -0300 |

Organization: | Compilers Central |

References: | 10-06-023 |

Keywords: | books, parse |

Posted-Date: | 10 Jun 2010 05:27:29 EDT |

I will answer partially to the first question with a trivial grammar.

*> Question 1. Page 223, last para*

*>*

*> "A grammar G is LL(1) if and only if whenever A -> alpha | beta are*

*> two distinct productions of G, the following conditions hold:*

*>*

*> 1. For no terminal 'a' do both alpha and beta derive strings*

*> beginning with 'a'.*

*>*

*> 2. At most one of alpha and beta can derive the empty string.*

*>*

*> 3. If beta *=> epsilon, then alpha does not derive any string*

*> beginning with a terminal in FOLLOW(A). Likewise, if*

*> alpha *=> epsilon, then beta does not derive any string beginning*

*> with a terminal in FOLLOW(A).*

*>*

*> [Continued on next page]*

*>*

*> The third condition is equivalent to stating that if epsilon is*

*> in FIRST(beta), then FIRST(alpha) and FOLLOW(A) are disjoint*

*> sets, and likewise if epsilon is in FIRST(alpha)."*

*>*

*> Now...*

*> Why is condition 3 even required for LL(1), is my question. I mean,*

*> why aren't conditions 1 and 2 enough to remove the ambiguity in the*

*> choice of productions which should then allow the parsing process to*

*> continue?*

Say you have a grammar like this

1. S -> A a

2. A -> a

3. A -> [epsilon]

where [epsilon] is the null string.

Now for Production rule 1 all tree condition are met.

However for Production rule 2 and 3 just condition 1 and 2 are met.

Basically the third condition is stating that the Select-Set(k) with k

= 1 for production rules with the same non terminal must be disjoint.

In the case above the Select-Set(k) with k = 1 for rules 2 and 3 is { a }.

This means that when the parser need to make a choice between

production rule 2 or 3 it will no be able to make such a choice

because the select set are not disjoint.

In this particular case this can be addressed by rewriting the grammar

or by adding lookahead, but that is a thing for a different thread.

HTH,

Felipe

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.