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

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/

Return to the comp.compilers page.
Search the comp.compilers archives again.