Wed, 09 Jun 2010 19:51:54 -0400

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: | Joshua Cranmer <Pidgeot18@verizon.invalid> |

Newsgroups: | comp.compilers |

Date: | Wed, 09 Jun 2010 19:51:54 -0400 |

Organization: | Georgia Institute of Technology |

References: | 10-06-023 |

Keywords: | parse, books |

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

On 06/09/2010 02:16 AM, Harry wrote:

*> 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?*

Consider the grammar:

S -> A a

A -> a | epsilon

This language is not LL(1), but it satisfies conditions one and two.

The reason that it's ambiguous is that if First(alpha) intersection

Follow(A) is not empty, we can't tell if that terminal is part of alpha,

and by consequent A, or if A is supposed to evaluate to epsilon and the

terminal be part of Follow(A).

The textbook I had for parsing (Louden's Compiler Construction:

Principles and Practice) gave the following as the rules for LL(1) grammar:

1. For every production A -> alpha_1 | alpha_2 | ... | alpha_n,

First(alpha_i) intersection First(alpha_j) is empty for all i and j,

where 1 <= i, j <= n and i != j.

2. For every nonterminal A such that First(A) contains epsilon, First(A)

intersection Follow(A) is empty.

(These rules immediately follow the rules for constructing a parse table

for LL(1) grammars, so the rationale behind them is more evident.)

(Point of order: what are the rules about using non-ASCII characters in

this newsgroup?)

--

Beware of bugs in the above code; I have only proved it correct, not

tried it. -- Donald E. Knuth

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.