Wed, 10 Feb 2010 20:42:56 -0500

Related articles |
---|

[7 earlier articles] |

Re: An example LL(K) language that is not LL(K-1) ? slkpg@cox.net (SLK Mail) (2010-02-05) |

Re: An example LL(K) language that is not LL(K-1) ? cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-05) |

Re: An example LL(K) language that is not LL(K-1) ? kkylheku@gmail.com (Kaz Kylheku) (2010-02-06) |

Re: An example LL(K) language that is not LL(K-1) ? klyjikoo@gmail.com (klyjikoo) (2010-02-06) |

Re: An example LL(K) language that is not LL(K-1) ? slkpg@cox.net (SLK Mail) (2010-02-06) |

Re: An example LL(K) language that is not LL(K-1) ? kkylheku@gmail.com (Kaz Kylheku) (2010-02-10) |

Re: An example LL(K) language that is not LL(K-1) ? cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-10) |

Re: An example LL(K) language that is not LL(K-1) ? klyjikoo@gmail.com (klyjikoo) (2010-02-14) |

Re: An example LL(K) language that is not LL(K-1) ? cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-13) |

From: | Chris F Clark <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers |

Date: | Wed, 10 Feb 2010 20:42:56 -0500 |

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

References: | 10-02-009 10-02-015 10-02-026 |

Keywords: | LL(1) |

Posted-Date: | 13 Feb 2010 11:32:13 EST |

klyjikoo <klyjikoo@gmail.com> writes:

*> Chris Wrote:*

*>>Although, I'm not an LL-language expert, I believe the trick to LL(k)*

*>>languages that aren't LL(k-1) is to have a (center) recursive rule*

*>>that needs k tokens to disambiguate.*

*>*

*> I think your example grammar is an LL(2) grammar,and after left*

*> factoring of production that have B on left ...we can obtain an LL(1)*

*> grammar.*

Here is the original grammar:

S := A

A := B C

B := b A d // 1 form of recursion

B := b a A a d // other form of recursion

B := a c

C := A

C := epsilon

There is only 1 production with B on the left. There is nothing to

left factor on that. Perhaps, you mean to left factor the two B rules

that start with b.

S := A

A := B C

B := b D

B := a c

C := A

C := epsilon

D := A d // 1 form of recursion

D := a A a d // other form of recursion

Or perhaps, you want to substitute B in the one place it occurs:

S := A

A := b D C

A := a c C

C := A

C := epsilon

D := A d // 1 form of recursion

D := a A a d // other form of recursion

Or this version (without D):

S := A

A := b A d C

A := b a A a d C

A := a c C

C := A

C := epsilon

which left factors to this:

S := A

A := b E

A := a c C

C := A

C := epsilon

E := A d C

E := a A a d C

In this case, it is the two E rules that have overlapping first sets.

You want to substitute A in the first one to see if it helps?

S := A

A := b E

A := a c C

C := A

C := epsilon

E := b E d C

E := a c C d C

E := a A a d C

Ok, we can left factor the "a" off the last 2 E rules, as in:

S := A

A := b E

A := a c C

C := A

C := epsilon

E := b E d C

E := a F

F := c C d C

F := A a d C

And, presuming no mechanical errors on my part, you are correct. This

is an LL(1) grammar, and thus the language is LL(1). which shows, my

original disclaimer that I am not an LL expert. Picking up my

friendly parsing theory textbook off my desk, it turns out that the

condition requires the the parens be the same token repeated i.e. the

following grammar should work:

S := A

A := B C

B := b A d // 1 form of recursion

B := b b A a d // other form of recursion, note the slight difference

B := a c

C := A

C := epsilon

which becomes:

S := A

A := b A d C

A := b b A a d C

A := a c C

C := A

C := epsilon

then:

S := A

A := b E

A := a c C

C := A

C := epsilon

E := A d C

E := b A a d C

then:

S := A

A := b E

A := a c C

C := A

C := epsilon

E := b E d C

E := a c C d C

E := b A a d C

then:

S := A

A := b E

A := a c C

C := A

C := epsilon

E := b F

E := a c C d C

F := E d C // first={a,b}

F := A a d C // first={a,b}

then, substituting E and A into F so we can left factor

S := A

A := b E

A := a c C

C := A

C := epsilon

E := b F

E := a c C d C

F := b F d C

F := a c C d C d C

F := b E a d C

F := a c C a d C

left factoring:

S := A

A := b E

A := a c C

C := A

C := epsilon

E := b F

E := a c C d C

F := b G

F := a c C H

G := F d C // first = {a, b}

G := E a d C // first = {a, b}

H := d C d C

H := a d C

Ooops, now we've moved the problem to G. We can keep expanding and

left factoring, but the process will continue yielding grammars the

have this same issue. Thus, the language is not LL(1).

*> but As you have suggested , there is this grammar that I think its*

*> language is not an LL(k) for every k*

*>*

*> S := A*

*> S := B*

*> A := a A b*

*> A := c*

*> B := a A b b*

*> B := d*

*>*

*> This grammar shows that there are language that have LR(1) grammar*

*> ,but have not any LL(K) grammar for every k...*

This grammar shows the difference between LR(k) and LL(k) grammars.

In an LR(k) grammar, one can match multiple closing parens (the b

tokens in your case) to the same open paren (the a token in your

case), which in LL(k) grammars, each balanced paren rule must have a

unique prefix that is at most k tokens long.

Actually, I htink you have made a slight typo, and want the B rule to

recurse on B not A. As given, I think it can be rewritten to be LL(1).

First, substitute A and B in S.

S := a A b

S := c

S := a A b b

S := d

A := a A b

A := c

Now, left factor S (a A b is the common prefix to factor off):

S := a A b C

S := c

S := d

A := a A b

A := c

C := b

C := epsilon

This, grammar is LL(1). However, I'm certain the same process would

not have worked were B self-recursive, ala:

S := A

S := B

A := a A b

A := c

B := a B b b

B := d

In this grammar, you have to left factor off an indefinite string of a

tokens to disambiguate the A and B non-terminals.

Hope this helps, (and apologies for my earlier error)

-Chris

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

Chris Clark email: christopher.f.clark@compiler-resources.com

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

23 Bailey Rd voice: (508) 435-5016

Berlin, MA 01503 USA twitter: @intel_chris

------------------------------------------------------------------------------

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.