语法分析树/派生树
Howard Yin 2020-12-14 07:37:05 数学形式语言与自动机计算理论形式语言上下文无关语言上下文无关文法下推自动机
语法分析树是分析上下文无关语言的重要工具,其算法多见于各自高级语言的编译器中。
CFGG=(V,T,P,S)的语法分析树/派生树定义为:
- 每个内节点都标记为V中的一个变元
- 每个叶节点都标记为T∪{ε}中的变元、终结符或空串
- 某个内节点A的子节点从左至右分别是X1,X2,…Xn表示A→X1X2…Xn∈P
- 若有Xi=ε那么A只能有一个子节点ε,表示A→ε∈P
语法分析树的产物/结果
语法分析树的全部叶节点从左到右连接起来组成的符号串称为树的产物/结果。
若某个语法分析树的根节点是A其产物为α,则它们之间的关系记为
α/∣\A
语法分析树的子树
语法分析树中标记为A的内节点及其全部子孙节点构成的子树称为A子树。
语法分析树和上下文无关语言的等价性
对于CFGG=(V,T,P,S)且A∈V,有:
A⇒∗α⇔α/∣\A
证明:充分性和必要性都可以通过A⇒jα从j=1开始归纳证明,具体证明过程略
歧义性
如果CFGG使得有两棵不同的语法分析树产生同一个产物,那么称该CFG是歧义的。
固有歧义性
同一个CFL可以有多个CFG定义。对于某些CFL,可以设计出不歧义的CFG;而对于某些CFL,它的所有CFG都是歧义的,称这种CFL是固有歧义的。
注:“判断给定CFG是否歧义”是一个不可计算问题。
案例:固有歧义语言L={aibjck∣i=j∨j=k}
对于任何形式为anbncn的串,总存在两棵语法分析树。因此L是固有歧义的。
经典案例:四则运算表达式的语法分析树
例如,《上下文无关文法》一节中提到的四则运算表达式的案例在没有确定运算优先级时就是歧义的:
G={{E,I},{0,1,+,−,×,÷,(,)},P,E}
P=⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧EEEI→E+E∣E−E→E×E∣E÷E→(E)∣I→0∣1∣I0∣I1⎭⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎫
1+0∗10就能由两个语法分析树产生:
显然根据正常的四则运算规则,第二棵子树才是正确的计算过程。这种歧义性在程序编译的实际应用中是不能被允许的。
可以对P稍加改造使之成为无歧义的:(使×和÷父节点的子树中不存在括号外的+和−)
P=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧EEEFFFI→E+E∣E+F∣F+E∣F+F→E−E∣E−F∣F−E∣F−F→(E)∣I→F×F∣F÷F→(F)∣I→(E)→0∣1∣I0∣I1⎭⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎫
这样,1+0∗10就能由唯一的语法分析树产生: