等价(形式语言)

编辑
本词条由“匿名用户” 建档。
在形式语言理论中,两个语法的弱等价意味着它们生成相同的字符串集,也就是说,它们生成的形式语言是相同的。在编译器理论中,这个概念与强等价(或结构性)区分开来,强等价另外意味着两个解析树是合理相似的,即同样的语义解释可以被分配给两者。Vijay-Shanker和Weir(1994)证明了线性索引语法、组合分类语法、树状连接语法和头部语法是弱等价的形式主义,因为它们都定义相同的字符串语言。另一方面,如果...

等价(形式语言)

编辑

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

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

内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/163878/

(2)
词条目录
  1. 等价(形式语言)

轻触这里

关闭目录

目录