等价（形式语言）

在形式语言理论中，两个语法的弱等价意味着它们生成相同的字符串集，也就是说，它们生成的形式语言是相同的。在编译器理论中，这个概念与强等价（或结构性）区分开来，强等价另外意味着两个解析树是合理相似的，即同样的语义解释可以被分配给两者。Vijay-Shanker和Weir（1994）证明了线性索引语法、组合分类语法、树状连接语法和头部语法是弱等价的形式主义，因为它们都定义相同的字符串语言。另一方面，如果两个语法产生相同的派生树集（或更一般的，相同的抽象句法对象集），那么这两个语法就是强等价的。

然而，第二种语法的具体语法树总是反映通常的运算顺序，而xxx种语法的树则不需要。以后缀顺序评估该树将产生正确的值7。相反，左边图片部分显示了xxx种语法对该字符串的一个解析树；以后缀顺序评估将产生9。生成能力在语言学中，一个语法的弱生成能力被定义为由它生成的所有字符串的集合，而一个语法的强生成能力是指由它生成的结构描述的集合。因此，如果两个语法的弱生成能力相吻合，则被认为是弱等价的；对于强等价也是如此。