Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the empty string)

"SLK Parsers" <parsersinc@earthlink.net>
15 Aug 2004 22:20:29 -0400

          From comp.compilers

Related articles
Question re the (non-)equivalence of Z -> z and Z -> z e (e the empty dhalitsky@cumulativeinquiry.com (2004-08-09)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em kwheinri@bsr2.uwaterloo.ca (Kenn Heinrich) (2004-08-10)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em k301x@yahoo.com (dtf) (2004-08-10)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em dhalitsky@cumulativeinquiry.com (2004-08-11)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em cppljevans@cox-internet.com (Larry Evans) (2004-08-11)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em kwheinri@bsr2.uwaterloo.ca (Kenn Heinrich) (2004-08-13)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em dhalitsky@cumulativeinquiry.com (2004-08-13)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em parsersinc@earthlink.net (SLK Parsers) (2004-08-15)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em dhalitsky@cumulativeinquiry.com (2004-08-23)
Re: Question re the (non-)equivalence of Z -> z and Z -> z e (e the em parsersinc@earthlink.net (SLK Parsers) (2004-09-03)
| List of all articles for this month |

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.