第四章语法分析.ppt

1 22 第四章 语法分析 自底向上语法分析移进归约分析法易于实现 算符优先分析法一般形式 LR分析法广泛用于自动的语法分析器的生成器 2 22 第四章 语法分析 移进归约分析法 分析过程从叶结点 底部 开始 向根节点 顶部 前进归约过程 输入串 文法开始符号在每一步归约中 如果一个字串和某个产生式右部匹配 则用该产生式的左部代替该子串得到最右推导的逆过程例4 21 一个输入符号串的归约过程 3 22 第四章 语法分析 移进归约分析法 句柄非正规定义 与一个产生式右部相匹配的子串 而且把它归约为该产生式左部的非终结符代表了最右推导逆过程的一步 若与一个产生式右部相匹配的子串 不能将输入子串最终归约为文法开始符号S 则该子串就不是句柄 4 22 第四章 语法分析 移进归约分析法 句柄正规定义 右句型 最右推导得到的句型 的句柄是一个产生式A 和 的一个位置 该位置上可以得到串 而且用A代替 可以得到 的最右推导的前一个句型 即如果S Aw w 那么紧跟在 后面的A 是右句型 即 w 的一个句柄 句柄右侧的串w只包含终结符 无二义文法句柄唯一 二义文法句柄不一定唯一 把 归约为A称为 句柄裁剪 图4 20 w的分析树中的句柄例4 22 文法 4 16 一个最右推导和相关句柄 5 22 第四章 语法分析 移进归约分析法 句柄裁剪通过句柄裁剪 得到最右推导的逆过程例4 23 文法 4 16 一个输入串的归约序列图4 21 移动归约分析器产生的归约对照例4 22互为逆过程 6 22 第四章 语法分析 移进归约分析法 实现方式数据结构栈 保存文法符号及 输入缓冲区 保存要分析的串w及 4种可能的动作移进 把下一个输入符号移进栈中归约 语法分析器知道句柄的右端已在栈顶 在栈中确定句柄的位置 并用正确的非终结符代替句柄接受 分析成功出错 发现语法错误 进行错误处理例4 24 用栈实现移进归约分析图4 22 移进归约分析器在输入id1 id2 id3上的格局 7 22 第四章 语法分析 移进归约分析法 实现方式特点句柄总会出现在栈顶 右句型 即 w 中w在输入缓冲中用栈实现移进归约非常有效两个问题移进 归约冲突 根据栈中的内容和下一个输入符号 如何决定是移进还是归约 归约 归约冲突 如何定位要归约的子串 如何选取产生式 两种解决方法易于实现 算符优先分析法一般形式 LR分析法 8 22 第四章 语法分析 移进归约分析法 活前缀定义 出现在移进归约分析器栈中的右句型的前缀集合活前缀是右句型的前缀 而且其右部不会超过该句型的最右边句柄的未端 作用我们可以把终结符加到活前缀的未尾得到右句型在给定时刻只要输入串中已分析过的那部分能归约成活前缀 就没有错误 9 22 第四章 语法分析 移进归约分析法 冲突处理有些文法不能用移进归约分析处理原因 根据栈中的内容和下一个输入符号移进归约冲突 不能决定移进还是归约归约归约冲突 不能决定按照哪个产生式进行归约非LR k 类文法 4 7节例4 25 二义性文法一定不是LR文法移进归约冲突解决方法 优先移进 最长匹配原则 例4 26 id属于数组还是过程产生式 归约归约冲突解决方法 对不同的记号进行区分 10 22 第四章 语法分析 自底向上语法分析移进归约分析法易于实现 算符优先分析法一般形式 LR分析法 11 22 第四章 语法分析 算符优先分析法 算符文法特殊的LR文法 所有产生式的右部不存在两个或两个以上连续的非终结符例4 27 算符文法和非算符文法 12 22 第四章 语法分析 算符优先分析法 算符优先分析的特点根据文法构造好一种算符优先语法分析器后 可以忽略该文法 栈中的非终结符仅作为与这些非终结符相关的属性的占位符缺点很难处理像减号这样的记号 减号既是一元操作符又是二元操作符不能肯定语法分析器接受的就是所期待的语言 分析的语言的文法和算符优先语法分析器本身的关系不是很紧密优点比较简单 用于处理表达式 13 22 第四章 语法分析 算符优先分析法 算符优先关系三种 ab对同一语言 ab可能同时成立 如减号 对同一语言 ab可能同时不成立 两种确定方法直觉主义方法 基于习惯的操作符间的结合原则和运算优先关系构造无二义性文法无二义性文法在分析树上反映了结合规则和优先级对无二义性文法 存在一种直接从该文法构造算符优先关系的机械方法 14 22 第四章 语法分析 算符优先分析法 算符优先关系作用 界定右句型的句柄 句柄的右端图4 23 算符优先关系135 136页 一个归约实例 15 22 第四章 语法分析 算符优先分析法 算符优先分析基本思想 给定栈顶的终结符a和下一个输入符号bab 归约无优先关系 出错算法4 5 算符优先分析算法图4 24输入 输入字符串w和优先关系表输出 如果w是一个句子 则输出一个分析树 否则报告出错 16 22 第四章 语法分析 算符优先分析法 如何确定算符优先关系 启发式方法 直觉主义方法如果 1的优先级比 2高 则 1 2 2 2 2 1满足右结合律 1 例4 28 对应文法 4 17 基于启发式的算法优先关系 空白表示错误项 图4 25 17 22 第四章 语法分析 算符优先分析法 如何处理一元操作符 一元前操作符a 对于任何操作符 否则 a一元后操作符即是一元前操作符又是二元操作符 如减号 词法分析器区分一元和二元 返回不同的记号 18 22 第四章 语法分析 算符优先分析法 优先函数用两个优先函数f和g表示优先关系表 f和g把终结符映射为整数 对于符号a和b 选择f和g满足 ab f a g b 缺点无法表示不存在优先关系好在相关错误可以在调用归约时发现 没有发现句柄 并不是所有的优先关系表都能用优先函数表示例4 29 图4 25优先关系表对应的优先函数 19 22 第四章 语法分析 算符优先分析法 优先函数优先函数的构造 算法4 6输入 算符优先关系表输出 表示输入矩阵的优先函数 或指出不存在方法为每个终结符a或 创建符号fa和ga把生成的符号按下面的方式分成尽可能多的符号组 如果a b 则fa和gb在同一组 构造一个以符号组为节点的有向图 如果ab 则从fa所在组引出一条边指向gb所在组 如果上一步中构造的图中有环路 则不存在优先函数 否则将f a 设为从fa所在组开始的最长路经的长度 g a 设为从ga所在组开始的最长路经的长度 例4 30 图4 23对应的优先关系矩阵图4 26 20 22 第四章 语法分析 算符优先分析法 错误恢复处理归约错误 句柄不匹配发现的句柄不是任何产生式的右部移进归约错误栈顶的终结符和当前输入符号没有优先关系 使用优先关系表 21 22 第四章 语法分析 算符优先分析法 错误恢复处理归约错误 句柄不匹配 枚举法确定有限的终结符序列利用有向图确定所有能够弹出的字符串 当且仅当a b时 从a到b有一条边 句柄内部 沿着图上各路经的节点标记所形成的字符串就是图4 24能够弹出的字符串找到最相像的产生式右部 并给出相关诊断信息例4 31 句柄不匹配的处理图4 27 图4 25中