6 May 1996 23:10:29 -0400

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) |

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.