正则树语法

在理论计算机科学和形式语言理论中，正则树语法是一种描述一组有向树或术语的形式语法。正则词语法可以被看作是一种特殊的正则树语法，描述的是一组单路径树。

正规树状语法G是由元组定义的g=（n，σ，z，p）。其中N是一个有限的非端点集合，Σ是一个有等级的字母表（即。Σ是一个与N不相连的字母表（即其符号有一个相关的算数），Z是起始非终端，Z∈N，P是一个形式为A→t的产品的有限集合，A∈N，t∈TΣ(N)，其中TΣ(N)是相关的术语代数，即由所有树组成的集合。即由Σ∪N中的符号根据其算数组成的所有树的集合，其中非终结符被认为是空的。树的派生语法G隐含地定义了一个树集：任何可以用规则集P从Z派生出来的树都被说成是由G描述的，这个树集被称为G的语言。更正式地说，关系⇒G对集合TΣ(N)的定义如下。如果有一个上下文S和一个生产（A→t）∈P，那么一棵树t1∈TΣ(N)可以在一个步骤中派生为一棵树t2∈TΣ(N)（简而言之：t1⇒Gt2），这样。这里，语境指的是一棵树，其中正好有一个洞；如果S是这样的语境，S[t]表示将树t填入S的洞中的结果。由G生成的树语言是语言L(G)={t∈TΣ|Z⇒G*t}。这里，TΣ表示由Σ的符号组成的所有树的集合，而⇒G*表示⇒G的连续应用。由某种规则树语法生成的语言被称为规则树语言。

让G1=（N1,Σ1,Z1,P1），其中N1={Bool,BList}是我们的非终端集合，Σ1={true,false,nil,cons(.,.)}是我们的排序字母表，它是一棵树的树（主图），而词语法中的派生树是一棵字符串的树（左上表）。G1生成的树状语言是所有布尔值的有限列表的集合，也就是说，L(G1)刚好等于TΣ1。语法G1对应于代数数据类型声明（在标准ML编程语言中）。数据类型Bool=false|true数据类型BList=nil|Bool*BList的consL(G1)的每个成员都对应于一个BList类型的标准-ML值。

再举个例子，让G2=(N1,Σ1,BList1,P1∪P2)，使用上面的非终端集和字母表，但用P2扩展生产集，由以下生产组成。BList1→cons(true,BList)BList1→cons(false,BList1)语言L(G2)是所有布尔值的有限列表的集合，其中至少包含一次true。L(G2)这个集合在标准ML中没有对应的数据类型，在任何其他函数式语言中也没有对应的数据类型。它是L(G1)的一个适当的子集。上面的例子术语也恰好在L(G2)中，正如下面的推导所示。BList1⇒cons(false,BList1)⇒cons(false,cons(true,BList))⇒cons(false,cons(true,nil))。语言特性如果L1，L2都是正则树语言，那么树集L1∩L2，L1∪L2，以及L1L2也是正则树语言，并且L1⊆L2，以及L1＝L2都是可判定的。

正则树语法是正则词语法的概括。正则树语言也是自下而上的树自动机和非确定性自上而下的树自动机所识别的语言。RajeevAlur和ParthasarathyMadhusudan将正则二叉树语言的一个子类与嵌套词和可见的推倒语言联系起来。应用正则树语法的应用包括。编译器代码生成中的指令选择以平等（=）和集合成员（∈）为xxx谓词的公式的一阶逻辑理论的决策程序解决关于数学集合的约束关于有限代数的一阶逻辑中可表达的所有真理的集合（它总是一种正则树语言）图形搜索