Re: Grammar equivalence

Christian Rinderknecht <>
30 Apr 1996 23:54:43 -0400

          From comp.compilers

Related articles
Grammar equivalence (Gabor DEAK JAHN) (1996-04-29)
Re: Grammar equivalence (Christian Rinderknecht) (1996-04-30)
Re: Grammar equivalence (1996-05-01)
Re: Grammar equivalence (1996-05-06)
| List of all articles for this month |

From: Christian Rinderknecht <>
Newsgroups: comp.compilers
Date: 30 Apr 1996 23:54:43 -0400
Organization: INRIA-Rocquencourt
References: 96-04-158
Keywords: parse, theory

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,


INRIA Rocquencourt E-mail:
(Domaine de Voluceau) Web :
BP 105 Phone : +33 (1) 39 63 53 16
F-78153 Le Chesnay Cedex Fax : +33 (1) 39 63 53 30

Post a followup to this message

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