Re: Grammar equivalence

ikastan@alumnae.caltech.edu (Ilias Kastanas)
6 May 1996 23:10:29 -0400

          From comp.compilers

Related articles
Grammar equivalence deakjahn@ludens.elte.hu (Gabor DEAK JAHN) (1996-04-29)
Re: Grammar equivalence Christian.Rinderknecht@inria.fr (Christian Rinderknecht) (1996-04-30)
Re: Grammar equivalence macrakis@osf.org (1996-05-01)
Re: Grammar equivalence ikastan@alumnae.caltech.edu (1996-05-06)
| List of all articles for this month |

From: ikastan@alumnae.caltech.edu (Ilias Kastanas)
Newsgroups: comp.compilers
Date: 6 May 1996 23:10:29 -0400
Organization: Caltech Alumni Association
Expires: May 13, 1996
References: 96-04-158 96-04-163
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]


You cannot find an algorithm to test L(G1) = L(G2) for arbitrary CFG's
G1 and G2, that is a fact. But there might well be a successful test
for _your_ G1 and G2. The Halting Problem is unsolvable too, but by
restricting language constructs, or using
invariants/assertions/conditions etc. we do prove termination and
correctness for a lot of programs.


Symbolic integration is unsolvable as well. Yes, in spite of MA*.
Once function arguments x, pi*x, m/n (or something like that) and
combinations are allowed, one can actually embed the integers and then
proceed as usual! It is a paper in the Journal of Symbolic Logic.
However, the less fancy versions actually computable seem to cover
most practical needs. (J.S.L. may have actually triggered reverse
psychology: one of the developers of MACSYMA stated during a talk,
with obvious relish: "X conjectured it could not be done... Y proved
it could not be done... and I did it!").




Good luck!


Ilias




--


Post a followup to this message

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