第四篇语法分析.pptVIP

第四章：语法分析 自底向上语法分析 移进归约分析法 易于实现：算符优先分析法 一般形式：LR分析法 广泛用于自动的语法分析器的生成器 第四章：语法分析：移进归约分析法 分析过程 从叶结点（底部）开始，向根节点（顶部）前进 归约过程：输入串=〉文法开始符号 在每一步归约中，如果一个字串和某个产生式右部匹配，则用该产生式的左部代替该子串 得到最右推导的逆过程 例4.21：一个输入符号串的归约过程 第四章：语法分析：移进归约分析法 句柄 非正规定义：与一个产生式右部相匹配的子串，而且把它归约为该产生式左部的非终结符代表了最右推导逆过程的一步。 若与一个产生式右部相匹配的子串，不能将输入子串最终归约为文法开始符号S，则该子串就不是句柄 第四章：语法分析：移进归约分析法 句柄 正规定义：右句型（最右推导得到的句型）γ的句柄是一个产生式A-〉β和γ的一个位置，该位置上可以得到串β，而且用A代替β可以得到γ的最右推导的前一个句型，即如果S*=〉αAw=〉αβw,那么紧跟在α后面的A-〉β是右句型γ（即αβw）的一个句柄。 句柄右侧的串w只包含终结符。 无二义文法句柄唯一。二义文法句柄不一定唯一。 把β归约为A称为“句柄裁剪” 图4-20：αβw的分析树中的句柄 例4.22: 文法（4-16）、一个最右推导和相关句柄 第四章：语法分析：移进归约分析法 句柄裁剪 通过句柄裁剪，得到最右推导的逆过程 例4.23：文法（4-16）一个输入串的归约序列 图4-21：移动归约分析器产生的归约 对照例4-22互为逆过程 第四章：语法分析：移进归约分析法 实现方式 数据结构 栈：保存文法符号及$ 输入缓冲区：保存要分析的串w及$ 4种可能的动作 移进：把下一个输入符号移进栈中 归约：语法分析器知道句柄的右端已在栈顶，在栈中确定句柄的位置，并用正确的非终结符代替句柄 接受：分析成功 出错：发现语法错误，进行错误处理 例4.24：用栈实现移进归约分析 图4-22：移进归约分析器在输入id1+id2*id3上的格局 第四章：语法分析：移进归约分析法 实现方式 特点 句柄总会出现在栈顶：右句型γ（即αβw）中w在输入缓冲中 用栈实现移进归约非常有效 两个问题 移进-归约冲突：根据栈中的内容和下一个输入符号，如何决定是移进还是归约？ 归约-归约冲突：如何定位要归约的子串?如何选取产生式？ 两种解决方法 易于实现：算符优先分析法 一般形式：LR分析法 第四章：语法分析：移进归约分析法 活前缀 定义：出现在移进归约分析器栈中的右句型的前缀集合 活前缀是右句型的前缀，而且其右部不会超过该句型的最右边句柄的未端。 作用 我们可以把终结符加到活前缀的未尾得到右句型 在给定时刻只要输入串中已分析过的那部分能归约成活前缀，就没有错误。 第四章：语法分析：移进归约分析法 冲突处理 有些文法不能用移进归约分析处理 原因：根据栈中的内容和下一个输入符号 移进归约冲突：不能决定移进还是归约 归约归约冲突：不能决定按照哪个产生式进行归约 非LR(k)类文法：4.7节 例4.25：二义性文法一定不是LR文法 移进归约冲突 解决方法：优先移进（最长匹配原则） 例4.26：id属于数组还是过程产生式? 归约归约冲突 解决方法：对不同的记号进行区分 第四章：语法分析 自底向上语法分析 移进归约分析法 易于实现：算符优先分析法 一般形式：LR分析法 第四章：语法分析：算符优先分析法 算符文法 特殊的LR文法：所有产生式的右部不存在两个或两个以上连续的非终结符 例4.27：算符文法和非算符文法 第四章：语法分析：算符优先分析法 算符优先分析的特点 根据文法构造好一种算符优先语法分析器后，可以忽略该文法，栈中的非终结符仅作为与这些非终结符相关的属性的占位符 缺点 很难处理像减号这样的记号：减号既是一元操作符又是二元操作符 不能肯定语法分析器接受的就是所期待的语言：分析的语言的文法和算符优先语法分析器本身的关系不是很紧密 优点 比较简单：用于处理表达式 第四章：语法分析：算符优先分析法 算符优先关系 三种：ab; a=b; ab 对同一语言，ab和 ab可能同时成立；（如减号） 对同一语言，ab、a=b和 ab可能同时不成立； 两种确定方法 直觉主义方法：基于习惯的操作符间的结合原则和运算优先关系 构造无二义性文法 无二义性文法在分析树上反映了结合规则和优先级 对无二义性文法，存在一种直接从该文法构造算符优先关系的机械方法 第四章：语法分析：算符优先分析法 算符优先关系 作用：界定右句型的句柄 ：句柄的左端 =：句柄的内部 ：句柄的右端 图4-23：算符优先关系 135-136页：一个归约实例 第四章：语法分析：算符优先分析法 算符优先分析 基本思想，给定栈顶的终结符a和下一个输入符号b ab或a=b：