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]


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




--

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