17 Jan 2004 23:29:38 -0500

From: | Chris F Clark <cfc@world.std.com> |

Newsgroups: | comp.compilers |

Date: | 17 Jan 2004 23:29:38 -0500 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 04-01-027 04-01-033 04-01-071 04-01-080 |

Keywords: | parse, theory |

Posted-Date: | 17 Jan 2004 23:29:38 EST |

*> There may be errors in my reasoning, but I guess I am pretty close now.*

Yes, you have the fundamental understanding and have even worked

through the details for the reverse case. And, the intent of the

exercise was exactly to show you that the extra A's as the "end of the

rule", and thus not in the conflicting context, don't affect the

grammar's class (and thus don't effect the language's class). That's

really about all there is to LL grammars, you can look at the *starts*

of the rules that can appear together at some point during the parse

and count the number of tokens it takes to distinguish them, and then

you know the k for the grammar.

To figure out the k for the language, you have to determine if there

is any way to rearrange the rules to eliminate those conflicts. If

the conflicting rules are part of the same recursive cycle (in your

sample grammar s->a->s->a... are a recursive cycle, since you can

derive an a from an s (technically you can derive a string which

contains the non-terminal a, not a string which is exactly a), and

from that derive another s, etc.), the rearrangement is probably not

possible. If the conflicting rules are part of separate paths, then

the necessary rearrangement to lower the k of the grammar can probably

be done. Thus, the following language is LL(1) despite the grammar

itself being LL(k+1). I will leave it as the obligatory "exercise for

the reader" to find the LL(1) grammar.

s: a | b:

a: A^k A;

b: A^k B;

Here is a slightly more subtle variant that you should consider. What

k is this language? What does the grammar with the smallest k for the

language look like?

s: a | b:

a: A^k a | A;

b: A^k b | B;

*> Let me ask one more question though. What is this C in rule a for?*

The C in the rule is to end the recursion. However, I believe it is

unnecessary, as the empty alternative of "s" can also terminate the

recursion. A basic rule of thumb is that in a recursive cycle of

rules (e.g. s->a->s->a...) there must be at least one rule in the

cycle which has a non-recursive alternative. Otherwise, the grammar

doesn't describe any finite strings and there aren't any legal finite

inputs to the grammar. Your grammar has two non-recursive

alternatives s->empty and a->C, so it is "doubly safe" ;-). As a

result, the a->C alternative is not neceesary for the grammar to be

correct, nor does it effect what language class the grammar is in.

Hope this helps,

-Chris

*****************************************************************************

Chris Clark Internet : compres@world.std.com

Compiler Resources, Inc. Web Site : http://world.std.com/~compres

19 Bronte Way #33M voice : (508) 435-5016

Marlboro, MA 01752 USA fax : (508) 251-2347 (24 hours)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.