The Wikipedia article on equivalence of formal grammars defines weak and strong equivalence as follows:

In formal language theory, weak equivalence of two grammars means they generate the same set of strings, i.e. that the formal language they generate is the same. In compiler theory the notion is distinguished from strong (or structural) equivalence, which additionally means that the two parse trees are reasonably similar in that the same semantic interpretation can be assigned to both.

The article states that there are different definitions for strong equivalance but doesn't give a formal description for any of them.

Can anyone give an overview of the various definitions or at least give a formal description of the most common one, such that is can be used for an algorithm to check two parse trees for strong equivalance?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.