15 Aug 2004 22:20:29 -0400

From: | "SLK Parsers" <parsersinc@earthlink.net> |

Newsgroups: | comp.compilers |

Date: | 15 Aug 2004 22:20:29 -0400 |

Organization: | SLK Parser Generator |

References: | 04-08-046 |

Keywords: | parse, theory |

Posted-Date: | 15 Aug 2004 22:20:28 EDT |

I am not sure what you are trying to show, but you may be interested in the

following argument that was made some years ago.

Clearly the following productions are all equivalent.

A --> a B C

A --> a B epsilon C

A --> a B epsilon C epsilon

A --> a epsilon B epsilon C epsilon

A --> epsilon a epsilon B epsilon C epsilon

and so a context free grammar can be expressed as

A --> epsilon a B C

B --> epsilon b

B --> epsilon e

C --> epsilon c D

D --> epsilon d

without changing its meaning from

A --> a B C

B --> b

B --> e

C --> c D

D --> d

Now this LL(1) grammar can be thought of as an LL(0) grammar with a single

conflict between productions 2 and 3, that conflict being on the empty

string. The resolution is to look ahead one symbol, which is the standard

method of LL(1) construction. So the strong LL(k) grammars can be fully

described in terms of conflict resolution, and the method is orthogonal down

to the case where k=0.

http://home.earthlink.net/~slkpg/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.