Re: Grammar equivalence

Gabor DEAK JAHN wrote:
> Is there a program somewhere to compare two grammars (not Yacc but
> EBNF, if possible) for equivalence? I have an original grammar and a
> derived one with many productions renamed, changed, simplified, left
> factored and so on, and I would like to check whether they still
> describe the same language.


> [Sounds intractable to me. -John]


I published last year a Tech. Report on a huge grammar transformation
(It was the ASN.1 specification language for network protocols). It
took me over 50 pages in TeX to write down the whole stuff and I
wondered if it was possible to show that, given two grammars (the
first and the last), they describe the same language. The answer it
NO. It is an undecidable problem. See. A. AHO & J. ULLMAN. Theory of
parsing, Translation and Compiling, vol. 1 (Parsing) in Automatic
Computation, Prentice Hall, 1972, chap. 2.6.3, p199. The only
solution that remains it to show step by step that you keep invariant
the language described by the resulting grammar, and at last, if
necessary, you make some proof upon the last grammar (in my case I
proved it to be LL(1)). The best way is to define as I did a group of
regular (ie gentle ;-)) transformations and to compose them.


The world of grammar is very tough!


I hope this helps,


Best regards,


Christian


----------------------------------------------------------------------------
INRIA Rocquencourt E-mail: Christian.Rinderknecht@inria.fr
(Domaine de Voluceau) Web : http://pauillac.inria.fr/~rinderkn
BP 105 Phone : +33 (1) 39 63 53 16
F-78153 Le Chesnay Cedex Fax : +33 (1) 39 63 53 30
--

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