计算理论基础课件

1、语法分析树语法分析树 主讲：李继伟学号：2015112648指导老师：杨青老师什么是语法分析树什么是语法分析树 设G是一个上下文无关文法，字符wL(G)在G中可能有很多推导。例如：如果G是生成平衡括号语言的上下文无关文法，则字符串()()至少可以用两个不同的推导从S得到：这两个推导的过程中我们会发现这样的特点： （1）使用的规则相同（2）在中间字符串使用的它们的地点也相同（3）唯一不同的区别是使用规则的次序两个推导都可以用右边图来表示。语法分析树的概念语法分析树的概念（1）语法分析树语法分析树（如右图）（2）图中的点叫做顶点顶点。每一个顶点有一个标记，标记是V中的一个符号（3）最上面的顶点叫做

2、根根，最底层的顶点叫做树叶树叶。树叶都标记终点符终点符,也可能标记空串e.（4）从左到右链接树叶的标记得到推导出来的终结符串，称为语法分析树的结果语法分析树的结果语法分析树语法分析树的形式语法分析树的形式对于任一上下文无关文法G=(V, ,R,S),定义它的语法分析树及根，树叶和结果如下：（1） . a对于每一个a,这是一个语法分析树。它的唯一的一个顶点既是根也是树叶，它的结果是a。（2）如果Ae是R中的一个规则，则是一颗语法分析树。它的根是标记A的顶点，它的唯一一片树叶是标记e的顶点，它的结果是e。（3）如果AA1An 是R的一个规则,是n课语法树，它们的根分别标记A1An ，结果分别为y1

3、 y2,这是n=1,则是一颗语法分析树，它的根是标记A的新节点，树叶是构成语法分析树的所以树叶，结果为y1 y2 。（4）除此之外没有别的语法分析树。例3.2.1：结果为id*(id+id)的语法分析树推导直观上直观上，语法分析树是表示L(G)中字符串的推导方法，它隐蔽了由于用不同的顺序使用规则而造成的推导的人为差异。换句话说，语法分析树表示推导的等价类推导的等价类。例例3.2.2考虑生成所以平衡括号的字符串的文法G中下述三个推导D1.D2.D3有D1D2和D2 D3。但是，没有D1D3，因为这两个推导有一个以因为这两个推导有一个以上的不同字符串上的不同字符串。注意，这三个推导的语法分析树相同

4、语法分析树相同（如图）如果有序对(D,D)属于的自反对称传递闭包自反对称传递闭包，则称这两个推导D,D是相似相似的。自反相似传递闭包自反的对称的传递的等价关系相似性换句话说换句话说，如果进过一系列的变化，使用规则的次序能够把两个推导中的一个变成另一个，则这两个推导是相似的，这样的变换能够把一个推导替换成一个先于它或它先于的推导。例：例：3.2.2(续续) 语法分析树通过自然同态自然同态正好体现了上面定义的字符串推导之间的相似性的等价关系的等价类相似性的等价关系的等价类。所以以下推导：这十个推导之间的关系如图：以上十个推导都是相似的。（1）非形式地）非形式地：它们表示在字符串的同样位置应用同样的

5、规则，唯一的区别是区别是这些应用的相对次序。（2）等价地：）等价地：重复使用或的逆可以把它们中的任一关联到另一个。再没有别的推导与它们相似。对比以下两种：语法分析树有何区别呢？不相似最左最左.右推导右推导 每一个在相似性下的等价类，即每一棵语法分析树，每一棵语法分析树，有一个推导在下是极大的，极大的，即没有先于它的其他推导没有先于它的其他推导。这个推导叫做最左推导最左推导（1）最左推导最左推导：每一个语法分析树中都有一个最左推导。它可以如下得到：从根的标记A开始，按照这棵语法分析树提供的规则反复替换当前字符串最左边最左边的非终结符。（2）最右推导：最右推导：不先于与任何其他推导的推导，不先于与

6、任何其他推导的推导，它是从语法分析树经过总是替换当前字符串中的最右边的非终结符得到。（3）每一个语法分析树恰好有一个最左推导和一个最右推导，这是因为一棵语法分析树的最左推导是唯一的每一步只有一个要替换的非终结符。即最左边的终结符。例如：D1为最左推导，D10为最右推导定理定理3.2.1 设G=(V, ,R,S)是一个上下文无关文法，AV-及w*,则下述命题是等价的：（a）Aw（b）有一棵根为A结果为w的语法分析树。（c）有最左推导Aw（d）有最右推导AwL*R*歧义性歧义性 能够生产有两棵或两棵以上不同语法分析树的字符串的文法叫做歧义的。歧义的。消去歧义消去歧义 固有歧义固有歧义歧义性有两个不同的左推导有两个不同的右推导有两棵不同的语法分析树或A为起始符w为结果课后习题课后习题3.2.3习题习题3.2.3的推导过程：的推导过程：最左推导： 没有先于它的其他推导 EE+T E+id T+id T*F+id T*id+id F*id+id id*