计算理论基础重点分析.ppt

语法分析树 主讲：李继伟 学号：2015112648 指导老师：杨青老师 语法分析树的概念 语法分析树的形式 最左.右推导 课后习题3.2.3 习题3.2.3的推导过程： * * 什么是语法分析树 设G是一个上下文无关文法，字符w∈L(G)在G中可能有很多推导。 例如：如果G是生成平衡括号语言的上下文无关文法，则字符串()()至少可以用两个不同的推导从S得到： 这两个推导的过程中我们会发现这样的特点： （1）使用的规则相同 （2）在中间字符串使用的它们的地点也相同 （3）唯一不同的区别是使用规则的次序 两个推导都可以用右边图来表示。 转换图 （1）语法分析树（如右图） （2）图中的点叫做顶点。每一个顶点有一个标记，标记是V中的一个符号 （3）最上面的顶点叫做根，最底层的顶点叫做树叶。树叶都标记终点符,也可能标记空串e. （4）从左到右链接树叶的标记得到推导出来的终结符串，称为语法分析树的结果 语法分析树 对于任一上下文无关文法G=(V, ∑,R,S),定义它的语法分析树及根，树叶和结果如下： （1） . a 对于每一个a∈∑,这是一个语法分析树。它的唯一的一个顶点既是根也是树叶，它的结果是a。 （2）如果A e是R中的一个规则，则 是一颗语法分析树。它的根是标记A的顶点，它的唯一一片树叶是标记e的顶点，它的结果是e。 （3）如果A→A1…An 是R的一个规则, 是n课语法树，它们的根分别标记A1…An ，结果分别为y1… y2,这是n=1,则是一颗语法分析树，它的根是标记A的新节点，树叶是构成语法分析树的所以树叶，结果为y1… y2 。 （4）除此之外没有别的语法分析树。 例3.2.1： 结果为id*(id+id)的 语法分析树 推导 直观上，语法分析树是表示L(G)中字符串的推导方法，它隐蔽了由于用不同的顺序使用规则而造成的推导的人为差异。换句话说，语法分析树表示推导的等价类。 例3.2.2考虑生成所以平衡括号的字符串的文法G中下述三个推导D1.D2.D3 有D1﹤D2和D2 ﹤D3。但是，没有D1﹤D3，因为这两个推导有一个以上的不同字符串。注意，这三个推导的语法分析树相同（如图） 如果有序对(D,D′)属于＜的自反对称传递闭包，则称这两个推导D,D′是相似的。 自反相似 传递闭包 自反的 对称的 传递的 等价关系 相似性 换句话说，如果进过一系列的变化，使用规则的次序能够把两个推导中的一个变成另一个，则这两个推导是相似的，这样的变换能够把一个推导替换成一个先于它或它先于的推导。 例：3.2.2(续) 语法分析树通过自然同态正好体现了上面定义的字符串推导之间的相似性的等价关系的等价类。所以以下推导： 这十个推导之间的＜关系如图： 以上十个推导都是相似的。 （1）非形式地：它们表示在字符串的同样位置应用同样的规则，唯一的区别是区别是这些应用的相对次序。 （2）等价地：重复使用＜或＜的逆可以把它们中的任一关联到另一个。再没有别的推导与它们相似。 对比以下两种： 语法分析树 有何区别呢？ 不相似 每一个在相似性下的等价类，即每一棵语法分析树，有一个推导在＜下是极大的，即没有先于它的其他推导。这个推导叫做最左推导 （1）最左推导：每一个语法分析树中都有一个最左推导。 它可以如下得到：从根的标记A开始，按照这棵语法分析树提供的规则反复替换当前字符串最左边的非终结符。 （2）最右推导：不先于与任何其他推导的推导，它是从语法分析树经过总是替换当前字符串中的最右边的非终结符得到。 （3）每一个语法分析树恰好有一个最左推导和一个最右推导，这是因为一棵语法分析树的最左推导是唯一的每一步只有一个要替换的非终结符。即最左边的终结符。 例如：D1为最左推导，D10为最右推导 定理3.2.1 设G=(V, ∑,R,S)是一个上下文无关文法，A∈V-∑及w∈∑*,则下述命题是等价的： （a）A→w （b）有一棵根为A结果为w的语法分析树。 （c）有最左推导A→w （d）有最右推导A→w L* R* * 歧义性 能够生产有两棵或两棵以上不同语法分析树的字符串的文法叫做歧义的。 消去歧义 固有歧义 歧义性 有两个不同的左推导 有两个不同的右推导 有两棵不同的 语法分析树 或 A为起始符 w为结果 最左推导： 没有先于它的其他推导 E→E+T →E+id →T+id →T*F+id →T*id+id →F*id+id →id*id+id E→E+T →T+T →