Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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: | macrakis@osf.org (Stavros Macrakis) |
| Newsgroups: | comp.compilers |
| Date: | 1 May 1996 23:21:57 -0400 |
| Organization: | OSF Research Institute |
| References: | 96-04-158 96-04-163 |
| Keywords: | parse, theory |
Christian Rinderknecht <Christian.Rinderknecht@inria.fr> writes:
...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....
"Undecidable" means that the problem cannot be solved _in general_.
However, it does _not_ mean that particular instances cannot be
solved. How difficult the original problem is depends on what sorts
of "simplifications" and "changes" are involved. I admit that even
the "simple" cases are likely to be combinatorially difficult, but
sometimes that is still tractable. For that matter, it may be good
enough for the original problem to produce some sort of "diff" of the
two grammars, reducing a large number of rules to compare to a small
number.
-s
--
Return to the
comp.compilers page.
Search the
comp.compilers archives again.