|Grammar equivalence firstname.lastname@example.org (Gabor DEAK JAHN) (1996-04-29)|
|Re: Grammar equivalence Christian.Rinderknecht@inria.fr (Christian Rinderknecht) (1996-04-30)|
|Re: Grammar equivalence email@example.com (1996-05-01)|
|Re: Grammar equivalence firstname.lastname@example.org (1996-05-06)|
|From:||email@example.com (Ilias Kastanas)|
|Date:||6 May 1996 23:10:29 -0400|
|Organization:||Caltech Alumni Association|
|Expires:||May 13, 1996|
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!").
Return to the
Search the comp.compilers archives again.