第四部分 第五-七章(语法分析).ppt

第四部分语法分析 第四部分内容 4 1自顶向下分析方法 第5章 4 2递归下降分析 递归子程序法 第5章 4 3LL 1 分析方法 第5章 4 4自底向上分析方法 第6章 4 5算符优先分析法 第6章 4 6LR分析方法 第7章 一 语法分析是编译过程的核心部分语法分析的任务 按照文法 从源程序符号串中识别出各类语法成分 同时进行语法检查 为语义分析和代码生成做准备 语法分析程序的定义 执行语法分析任务的程序称为语法分析程序 也称为语法分析器 它是编译程序的主要部分之一 语法分析方法的分类 分成两大类 自顶向下分析和自底向上分析 二 语法分析的数学模型 下推自动机 1 下推机的逻辑结构PDA的读 写 状态转移动作决定于以下三个因素 当前所处状态读头所指符号下推栈栈顶符号一个输入串能为PDA所接受 仅当输入串读完 下推栈变空 或者输入串读完 控制器到达某些终态 2 下推机的定义下推自动机是一个七元组M Q H q0 z0 F 其中 Q是控制器的有限状态集 是输入字母表 H是下推栈内字母表 是Q H到Q H 的有限子集映射 q0 Q是控制器的初始状态 z0 H是下推栈的栈初始符 F为Q的子集 是控制器的终态集 3 说明映射函数 描述PDA动作与状态的变化 q a z q1 1 q2 2 qn n 其中q qi 1 i n Q a z H含义 控制器当前状态为q 下推栈栈顶符号为z 输入符号为a 可为空 情况下 状态转换到序偶集 qi i qi为下一状态 i为代替z的栈顶符号串 映射函数 不是单值映射 且下推机有两种接受状态 串读完进入终态和串读完栈空 例子 LL 1 语法分析器与PDA的对应关系设CFGG VN P S 构造一个不确定的PDAM Q H q0 z0 F 其中Q F q0 H VN z0 S 映射关系的构造方法如下 对于形如A 产生式 有 q A q q a a q 其中a 4 1自顶向下分析方法 4 1 1带回溯的自顶向下的分析方法4 1 2存在的问题及解决方法 4 1 1带回溯的自顶向下的分析方法 思路 对任一输入符号串 通过一切可能的办法 从树根结点 识别符号 出发 根据文法自上而下地为输入串建立一棵语法树 或者说 从识别符号开始 根据文法试图为输入串建立一个推导序列 特点 是自顶向下分析的一般方法 分析过程的本质是一种试探过程 以上文法没有左递归 且有以下两个特点 1 每个产生式的右部都由终结符号开始 2 如果两个产生式有相同的左部 那么它们的右部由不同的终结符开始 举例 1 确定的自顶向下分析 以上文法没有左递归 且有以下特点 1 产生式的右部不全是由终结符开始 2 如果两个产生式有相同的左部 其右部是由不同的终结符或非终结符开始 3 文法中无空产生式 以上推导过程的特点 在第二步到第三步的推导中 即abAS abS时 因为当前输入符号为d 而最左非终结符A的产生式右部的开始符号集合都不包含d 但A可以推出空 所以d的匹配任务就只能依赖于A后面的符号 所以选用产生式 A 空 进行推导 句型中紧跟A后面的符号为S S产生式右部的开始符号中包含了d 所以可匹配 假定有文法G S 1 S cAd 2 A ab a对输入串w cad 要求自上而下地构造w的语法树 解决过程 2 非确定的自顶向下分析 分析 通过上述解答过程可以看出 自顶向下地为输入符号串w建立语法树的过程实际上就是设法建立w的一个最左推导序列 比如对于上例中的输入串w可以通过如下的推导过程将其推导出来 S cAd cad由于对输入串是自左向右扫描的 因此用最左推导 只有用最左推导 才能保证按扫描顺序去匹配输入串 问题 缺陷 不能处理左递归文法 教材P88图5 6 图5 7 缺点 存在回溯 算法效率低 另 更多例子参阅教材P91 4 1 2存在的问题及解决方法 一 左递归问题 直接左递归 间接左递归二 回溯问题实现不带回溯的自顶向下分析的条件 文法非左递归 首符号集不相交 一 左递归问题 P88 直接左递归自顶向下分析方法不能处理具有左递归性的文法的原因 例如 规则U U 是一条左递归规则 为了实现用U 匹配输入串 又会遇到要用U去匹配 故又要启用上述规则的右部符号串U 来完成匹配工作 如此循环下去而无法终止 方法 用第二章中介绍的重复和选择表示法 扩充的BNF表示 去改写左递归规则 例如 规则 E E T T改写为 E T T 规则 T T F T F F改写为 T F F F 改写后的文法消除了直接左递归 且改写前后的文法是等价的 将直接左递归规则转换成使用重复表示法的等价规则的处理原则 1 规则1 提取因子 当出现规则U xy xw xz时 用规则U x y w z 代替 其中 圆括号是元符号 特例 对规则U x xy 则转换为U x y 其中 是空符号 2 规则2令U x y z Uv是一组规则 它具有一个直接左递归右部且位于最后 该规则表明 语法类U的成员是由x或y或 或z其后随有零个或多个v组成的 因此 可以把这组规则等价变换成U x y z v 算法 使用规则1 通过提取因子将规则改写成满足以下要求的形式 相对于某个非终结符号 至多只有一个直接左递归的右部 使用规则2 将规则改写为不含直接左递规的扩充的BNF形式 以消除直接左递归 例题 1 规则 E E T T 1 变形为 E T E T 2 由规则2 改写为 E T T 2 规则 T T F T F F 1 规则1 改写为 T F T F F 2 规则2 改写为 T F F F 3 删去圆括号为 T F F F 间接左递归要求 1 文法没有回路 即没有形如A A的推导 2 不存在形如 A 的规则 则可以按下述算法消除文法的左递归性 消除左递归算法 1 把G的非终结符整理成某种顺序A1 A2 An fori 1step1untilndobeginforj 1step1untili 1do把每个形如Ai Ajr的规则替换成Ai 1r 2r kr 其中Aj 1 2 k是当前的全部Aj规则 消除Ai规则中的直接左递归end 化简由 所得的文法 删除所有多余规则 例题 有文法G S S Qc cQ Rb bR Sa a解 该文法有间接左递归 例如有S Qc Rbc Sabc 即S Sabc 1 首先将非终结符号排列成 R Q S的顺序 2 将R代入Q得 Q Sab ab b将Q代入S得 S Sabc abc bc c消除S的直接左递归 S abc bc c abc 3 处理后的文法为 S abc bc c abc Q Sab ab bR Sa a化简后的文法为 S abc bc c abc 消除左递归算法 2 1 设G是一上下文无关文法 Vn X1 X2 Xn 对每个形如Xi 1 2 m的产生式 根据 的开始符号作如下等价变换 1 将 表示成 表示成 2 以非终结符号Xi引导的 i表示成 Xi i 3 以终结符号引导的所有 i之 和 看成常数项 表示成 i变形后的产生式为 Xi X1 1i X2 2i Xn ni i 如产生式不含有以Xi打头的候选式 则相应的系数 为 产生式集可表示为 11 12 1n 21 X1 X2 Xn X1 X2 Xn 1 2 n n1 nn即 X XA B 且其通解为 X BA 化简X BA 1 j蒋立源 编译原理 M 西北工业大学出版社 P91 94 消除左递归算法 2 设 z11z12z1n z21 A Z I zn1znn 则可得以下矩阵方程组 X BZZ I AZ解以上方程组并化简即可得到不含左递规的文法例题 S Sa Ab aA Sc 二 回溯问题 P91 1 消除回溯的理由前面介绍的带回溯的自顶向下的分析方法实际上采用了一种穷尽一切可能的选择试探法 三种回溯情形举例 教材P91 回溯需要记住每一步分析的现场 浪费时间和空间 因此 效率低 代价高 要构造一个行之有效的自顶向下的语法分析程序 就必须消除回溯 2 消除回溯的思路为了避免回溯 要求对文法的任何非终结符号 主要是对那些规则右部有多个选择 候选式 的非终结符号 当要用它去匹配输入串时 能够根据所面临的输入符号准确地选用一个候选式去执行匹配任务 并且工作的结果应是确定的 即若此选择匹配输入串成功 那么这种匹配一定正确无误 若此选择无法完成匹配任务 则任何其他的选择也肯定无法完成 3 消除回溯的方法 预测与提左因子1 预测预测就是根据读入的符号选择满足一定条件的候选式 使其第一个符号与读头下的符号相同 或该候选式可推导出的第一个符号与读头下符号相同 所以 对文法有如下要求 令G是一个不含左递归的文法 对每条规则中的每个候选式 定义它的终结首符集First a a a VT 设A VN 且A 如当前用A去匹配输入串 且输入符号为a时 对A的候选式的选择可以分成以下四种情况 当A不能推出 时 1 若a First 而a First 选A 2 若a First 而a First 选A 3 若a First 而a First 输入有错 4 若a First 同时a First 终结符首集两两相交 则需要改写文法 2 改造文法方法 提取公共左因子 a 假定关于非终结符A的产生式是 A 1 2 n那么可改写成两条规则 A A A 1 2 n b 一般情况 若有关A的产生式是 A 1 2 3 4 则可写成 A A A A 1 2A 3 4 结论 即当规则右部具有n个选择 从每一个选择出发 都可以推导出一个以上的终结符号串 为了避免回溯 就要保证当用非终结符号A去匹配输入串时 能够根据当前读入的符号准确地选用它的一个候选式执行任务 即对文法的要求是 对任意一个非终结符号 当对应的规则右部有多个选择时 由各个选择所推出的终结符号串的首符号集合要两两不相交 当文法不满足避免回溯的条件时 可以改写文法 对规则右部反复提取左因子 例题 规则 U xV xW 1 改写为 U x V W 2 引入一个新的非终结符号Y 则规则变换成 U xYY V W改写后的文法中 非终结符号U的右部只有一个选择 而引入的新非终结符号Y具有两个选择V或W 且这两个选择所推出的终结符号串所组成的头符号集合不相交 总结 为了实现不带回溯 确定 的自顶向下分析 对文法来说 需要满足下述两个条件 文法是非左递归的 对文法的任一非终结符号 若对应的规则右部有多个候选式时 那么 各选择所推出的终结符号串的头符号集合要两两不相交 4 2递归下降分析 递归子程序法 一 基本思路对文法中每个非终结符号U 分别代表一种语法成分 都编出一个子程序 以完成该非终结符号所对应的语法成分的分析和识别任务 二 非终结符号的语法分析子程序的功能用该非终结符号的规则的右部符号串去匹配输入串 分析过程 按文法规则自左向右地逐个处理每个文法符号 处理方法如下 1 对规则中的终结符号直接与输入匹配 2 非终结符号则调用该符号的分析子程序来完成匹配 即当编译程序根据文法和当前的输入符号预测到下一个语法成分为U时 即预测到待匹配的输入符号串可以和U推导出的符号串相匹配时 就确定U为子目标 并调用分析和识别U的子程序来完成该子目标的分析匹配工作 三 特点在分析和识别某个语法成份的过程中 有可能还要确立其它子目标并调用相应的分析子程序 只有在被调用的分析和识别某语法成分的子程序匹配输入串成功并正确返回后 该语法成分的分析才能继续进行 并最终完成分析任务 所以该分析方法具有明显的预测性特征 并在分析过程中向下确立多级子目标 所以 该方法也被称为面向预测和目标的分析方法 Predictiveparser 四 例题Z U aUbU dZ Ud eProcedureZ ifCLASS thenbeginnextsym U ifCLASS thennextsymelseerrorend elseifCLASS a thenbeginnextsym U ifclass b thennextsymelseerrorend elseerror ProcedureU 首先要消除左递归 U dZ e d ifCLASS d thenbeginnextsym Z whileCLASS d donextsymend elseifCLASS e thenbeginnexteym whileCLASS d donextsymendelseerror 4 3LL 1 分析方法 基本思路 相应的语法分析将按自左至右的顺序扫描输入符号串 并在此过程中产生一个句子的最左推导 其中第一个L表示从左向右扫描输入符号串 第二个L表示生成最左推导 括号中的 1 则表示在分析过程中 每进行一步推导 只要向前查看一个输入符号 便能确定当前所应选用的产生式 规则 4 3 1LL 1 分析器的逻辑结构及工作过程 一 逻辑结构 1 LL分析器的数学模型设CFGG VN P S 构造PDA如下 M Q H q0 z0 F 其中Q F q0 H VN z0 S 映射关系的构造方法如下 对于形如A 产生式 有 q A q 对于a q a a q 2 LL分析器的逻辑结构一个LL 1 分析器由一个总控程序 一张分析表和一个分析栈组成 其中 输入 即待分析的符号串 分析表M用一个矩阵 或二维数组 来表示 它概括了相应文法的全部信息 矩阵的每一行与文法的一个非终结符号 终结符号或 相关联 而每一列则与文法的一个终结符号或 相关联 分析表元素M A a 指示分析器应采取的动作 其中A Vt Vn a Vt 二 工作过程第一步 分析开始时 首先将符号 及文法的开始符号S依次置于分析栈的底部 并把各指示器调整至起始位置 即初始格局为然后 反复执行第二步的操作 第二步 设在分析的某一步 分析栈及余留的输入符号串处于如下的格局 其中 X1 X2 Xm为分析过程中所产生的文法符号 此时 可视栈顶符号Xm的不同情况 分别进行如下操作 若Xm VN 则以Xm及ai组成符号对 Xm ai 查分析表M 设M Xm ai 为一产生式 譬如说Xm UVW 此时将Xm从分析栈中退出 并将UVW按反序推入栈中 即用该产生式推导 从而得到新的格局但若M Xm ai ERROR 则调用出错处理程序进行处理 若Xm ai 则表明栈顶符号已与当前正扫描的输入符号匹配 此时应将Xm 即ai 从栈中退出 并将输入符号指示器向前推进一个位置 若Xm ai 则表明输入串已完全得到匹配 此时即可宣告分析成功而结束分析工作 分析流程如下 举例 原始文法 消除左递归 4 3 2LL 1 分析表的构造方法 LL 1 分析算法对不同的LL 1 文法都相同 即总控部分相同 仅仅是分析表不同 而且总控程序十分简单 容易实现 所以 LL 1 分析方法的核心是构造LL 1 分析表 一 定义符号串 的首符号集假定 是文法G的任一符号串 即 VT VN 定义 FIRST a a a VT 特别是 若 则规定 FIRST 即FIRST 是从 可能推导出的所有开头终结符号或可能的 二 定义非终结符的尾符号集假定S是文法的开始符号 对于G的任何非终结符A 定义 FOLLOW A a S Aa a VT 特别是 若S A 则规定 FOLLOW A 即FOLLOW A 是所有句型中能够紧接A之后的终结符或 三 定义SELECT集 教材P78 对文法的产生式X 如 则SELECT X FIRST 如 则SELECT X FIRST FOLLOW X 四 构造First集的算法1 定义法若X VT 则FIRST X X 若X VN 对形如X a 的产生式 a VT 或形如X 的产生式 把a或 加进FIRST X 设G中有形如X Y1Y2 Yk的产生式 若Y1 VN 则把FIRST Y1 中的一切非 的符号加进FIRST X 对于一切2 i k 若Y1 Y2 Yi 1均为非终结符 且 FIRST Yj 1 j i 1 则将FIRST Yi 中的一切非 的符号加进FIRST X 若对一切1 j k 均有 FIRST Yj 则将 加进FIRST X 关系图法 1 首先求出能推出 的非终结符号 2 然后按照下面步骤求解 对于文法G的任一符号串 X1X2 Xn可按如下的步骤构造相应的FIRST 置FIRST 把FIRST X1 中的一切非 符号加进FIRST 依次进行下述操作 若 FIRST X1 将FIRST X2 中的一切非 的符号加进FIRST 若 属于FIRST X1 及FIRST X2 将FIRST X3 中一切非 的符号加进FIRST 以此类推 最后 若对于1 i n FIRST Xi 则将 加进FIRST 五 构造Follow集的算法1 定义法对于文法的开始符号 令 FOLLOW S 若G中有形如A B 的产生式 且 则将FIRST 中的一切非 符号加进FOLLOW B 即FOLLOW不含 若G中有形如A B或A B 的产生式 且 FIRST 则FOLLOW A 中的全部元素均属于FOLLOW B 2 关系图法 六 构造分析表的算法分析表M是一个二维表 每一行对应一个文法符号 每一列对应一个终结符号 元素的赋值规则如下 1 对规则A FRIST 中的每一终结符a 置M A a POP PUSH 其中 为 的倒置 若 FIRST 则对属于FOLLOW A 的每一终结符号b或 置M A b A 2 把M中所有M a a 置为 POP NEXTSYM 3 把M中所有不能按以上规则定义的元素均置为 ERROR 出错 简化表示 可以省略分析表中所有终结符号对应的行 定义 一个文法G 若它的分析表M不含多重定义元素 则称它是一个LL 1 文法 一个LL 1 文法是无二义的 它所定义的语言恰好就是它的分析表M所能识别的全部句子 可以证明 一个文法G是LL 1 文法 当且仅当对于G的每一个非终结符A的任何两条不同规则A 下面的条件成立 1 FIRST FIRST 即由 和 推导不出以同一终结符a为首字符的符号串 且不应该都能推出空字符 2 假若 则FIRST FOLLOW A 即若 则 所能推出的串的首符号不应在FOLLOW A 中 教材P78 即SELECT A 与SELECT A 不相交 且两者不能同时推出 主要结论 任何LL 1 文法都是无二义性的 若一文法中含有左递归的非终结符号 则它必然是非LL 1 文法 存在一种算法 它能判定任一文法是否为LL 1 文法 存在一种算法 它能判定任意两个LL 1 文法是否产生相同的语言 不存在这样的算法 它能判定任意上下文无关语言能否由LL 1 文法产生 非LL 1 语言是存在的 一 非LL 1 文法的改造 四种改造情形举例 教材P85 二 非LL 1 文法 4 4自底向上分析方法 一 基本思路自底向上的分析方法 也称为 移进 归约 法 这种方法的一般过程是 设置一个寄存符号的先进后出栈 称为符号栈 用来记录分析的历史和指示分析的下一步动作 二 分析过程在分析进行时 把输入符号一个个地按扫描顺序移进栈里 当栈顶符号串形成一个句柄 为某条规则的右部 时 就进行一次归约 把栈顶构成句柄的那个符号串用相应规则左部的非终结符号来代替 接着再检查在栈顶是否又出现了新的句柄 若出现新的句柄 就再进行归约 若没有形成新的句柄 则再从输入符号串移进新的符号 如此继续直到整个输入符号串处理完毕 最终如栈底为识别符号 则所分析的输入符号串为合法的句子 报告成功 否则 是不合法的符号串 报告错误 例1 有文法G S 1 S aAcBe 2 A b 3 A Ab 4 B d分析符号串abbcde abbcde的移进 归约过程 abbcde语法树的构造过程 三 关键问题在自底向上分析中 如何寻找或确定一个句型的句柄 是构造一个自左向右扫描 自底向上分析方法必须要解决的一个关键问题 下面介绍较为常用的两种方法 1 算符优先分析方法 2 LR分析法 4 5算符优先分析法 4 5 1方法概述4 5 2直观算符优先分析法4 5 3算符优先分析法的进一步讨论 4 5 1方法概述 思路 算符优先分析法是仿照算术式的四则运算过程而设计的一种语法分析方法 该方法首先要规定运算符之间的优先关系和结合性质 然后利用这种关系 通过比较相邻运算符的优先顺序来确定句型的 句柄 和进行归约 特点 简单直观 最适用于表达式分析 宜于手工实现 例 有文法G E E E E E E E E E E E i试分析句子i i i i i 根据运算符优先顺序和结合原则的规定对句子i i i i i 进行归约 归约过程为 i i i i i E i i i i E E i i i E i i i E E i i E E E i E E E E E E E E E E E E 11 E 该归约过程是唯一的 在上述的整个归约过程中 起决定作用的是相邻两个终结符的优先关系 所以应用算符优先分析法自底向上地分析句子 解决了前面提到的问题 即 1 可以只根据相邻运算符的优先关系 就能方便地并且唯一地确定归约的 句柄 2 同时还可以发现 该方法可以用来分析二义性文法所产生的语言 上述文法是二义性的 但用算符优先法分析其句子时 其归约过程是唯一的 我们所规定的运算符之间的优先顺序和左结合的原则 就是避免二义性的充分条件 4 5 2直观算符优先分析法 1 算符优先分析的关键在于定义任何两个可能相邻的终结符a和b之间的优先关系要求对于任何两个可能相继出现的终结符a和b具有形式 ab 或 aQb Q VN 定义a b之间有3种关系 1 a ba的优先级低于b 2 a ba的优先级等于b 3 a ba的优先级高于b如果a和b在任何情况下不可能相继出现 则a b之间不可比 即无关系 要与算术中的 区分 a b并不意味着b a 比如栈内的 大于栈外 同时栈内 也大于栈外 优先关系矩阵示例 2 直观算符优先分析法的基本步骤使用两个工作栈OPTR 寄存运算符 和OPND 存放 操作数 和 运算结果 开始 将OPTR栈底置为 输入串尾设置右界符 OPND初始为空 令 代表OPTR现行栈顶符号 a存放新输入的符号 则分析算法的基本步骤如下 1 把下一个输入符号读至a中 2 若a为运算数i 则把它压入OPND 转 1 3 若 a 则调用 的处理程序 处理子表达式E 1 E 2 同时 把 从OPTR栈顶弹出 然后重新进入 3 4 若 a 则按优先关系表有两种可能 a 此时弹出OPTR顶的 放弃a中的 然后转 1 a 结束 5 若 a 把a移进OPTR栈 转 1 6 与a不存在优先关系 则输入串有错 4 5 3算符优先分析法的进一步讨论 一 算符优先文法定义1 设有一文法G 如果G中没有形如U VW 的规则 其中V和W是非终结符号 那么 就称G为算符文法 OG文法 定义2设G是一OG文法 并令a和b是任意两个终结符号 U V W是非终结符号 终结符号的优先关系定义如下 1 a b 当且仅当文法中有形如U ab 或U aVb 的规则 a b同时归约 2 a b 当且仅当文法中有形如U aW 的规则 其中W b 或W Vb b归约在前 3 a b 当且仅当文法中有形如U Wb 的规则 其中W a或W aV a归约在前 三种优先关系和归约的先后顺序的图形解释 参见教材P108 定义3设有一OG文法 如果在任意两个终结符号之间 在 和 中至多只有一种关系成立 那么 这样的OG文法称为算符优先文法 OPG文法 二 构造优先关系矩阵定义1非终结符号U的FIRSTVT集合FIRSTVT U a U a 或U Va 定义2非终结符号U的LASTVT集合LASTVT U a U a或U aV 1 构造FIRSTVT算法 LASTVT的构造算法与此类似 ProcedureInsert U b ifnotF U b thenBeginF U b TRUE Push U b 把 U b 下推进STACKEnd 主程序 F为2维数组 如b FIRSTVT U 则F U b TRUE BEGINFor每个非终结符号U和终结符号bdoF U b FALSE 初始化为0 For每个形如U b 或U Vb 的规则doInsert U b WhileSTACK非空doBeginPop V b 记STACK栈顶为 V b 弹出 For每条形如U V 的规则doInsert U b EndofWhile END 例子 给定如下表达式文法G E 0 E E 1 E E T 2 E T 3 T T F 4 T F 5 F P F P 6 P E 7 P i非终结符号的FIRSTVTLASTVT如右 2 用图形法求FIRSTVT的算法 教材P105 图形法求解结果如右图所示 3 构造优先关系表算法For每条规则U x1x2 xnDOFori 1TOn 1DOBEGINIFxi和xi 1均为终结符号THEN置xi xi 1 IFxi为终结符号而xi 1为非终结符THEN置xi xi 2 IFxi为终结符号而xi 1为非终结符THENForFIRSTVT xi 1 中的每个bDO置xi b IFxi为非终结符号而xi 1为终结符THENForLASTVT xi 中的每个aDO置a xi 1 End 例 设文法G S 的产生式为 S aAcBeA Ab bB d FIRSTVT S a FIRSTVT A b FIRSTVT B d LASTVT S e LASTVT A b LASTVT B d 三 算符优先分析算法设计定义4文法句型的素短语是满足以下条件的一个短语 它至少包含一个终结符号 并且除它自身之外 不再包含其他素短语 定理1一个OPG句型的最左素短语是满足下列条件的最左子串Njaj NiaiNi 1aj 1 ajaj aj 1 aj 1 aj 2 ai 2 ai 1 ai 1 aiai ai 1出现在aj左端或ai右端的非终结符号一定属于这个素短语 举例 P116图6 6 图6 7 例子 P110 与规范归约的比较 继续往前扫描寻找素短语尾 找到素短语尾 往栈底搜索找素短语头 找到素短语头 S为分析栈 k为栈顶指针 注意 1 在查找所应归约的最左素短语的过程中 没有用到非终结符号 因此 在符号栈中放不放相应的非终结符号 对分析过程中寻找最左素短语没有影响 2 与归约为某个非终结符号相对应 语义程序分配一个工作单元来存放该子表达式的运算结果 所以 对语义处理程序来说 也不需要知道真正的非终结符号的名字 算符优先函数及其构造方法 为什么要构造优先函数 对具有n个终结符号 包括句子界符 的算符优先文法 其优先关系矩阵需要n2的存储空间 是否可能将空间消耗控制在n的线性复杂度范围内 算符优先函数及其构造方法 把每一个终结符 与一对整数f g 联系在一起 其中f 为终结符 在栈内时的优先数 g 为终结符 在栈外的优先数 1 f 与g 的值应满足如下关系若 1 2则f 1 g 2 2个优先函数所需空间为2n 2 优先表与优先函数的关系1 优先函数并不等价于优先表 在优先表中没有关系的终结符对存在优先函数 2 有些优先表不存在对应的优先函数f和g 3 如果存在一对优先函数 则存在无穷多对优先函数 根据不同的算法从优先表转换推演出优先函数时也可能得到不同的结果 3 从优先表转换为优先函数的算法算法一 逐次加1法1 对所有终结符a 包括 令f a g a c2 对所有终结符 若a b且f a g b 则f a g b 1若a b且f a g b 则g b f a 1若a b且f a g b 则f a g b max f a g b 3 重复步骤 2 直至f a g b 不再改变为止 如果f a 或g b 的任一值 2n c而步骤 2 还没结束 表示优先函数不存在 例 由G E 文法的优先表构造优先函数的过程 P118 第1步 f 与g g g 比较 按算法调整对应的f g值 第2步 f 与g g g 比较 按算法调整对应的f g值 第n步 f 与g g g 比较 按算法调整对应的f g值 以上优先函数的计算迭代三次收敛 不难看出对优先函数每个元素的值都增加同一个常数 优先关系不变 所以同一个文法的优先关系矩阵对应的优先函数可以不唯一 但是也有一些优先关系矩阵中的优先关系是唯一的 却不存在优先函数 例如下面的优先关系矩阵 构造算法二 Bell有向图方法1 对每个终结符a 包括 令其对应两个节点fa和ga 画一张以所有fa和ga为节点的有向图 如果a b或a b 就从fa画一弧指向gb 若a b或a b 则从gb画一弧指向fa 2 令f a 等于节点fa可达的节点数 包括自身 令g a 等于节点ga可达的节点数 包括自身 3 检查构造出来的f a 和g a 若与优先表符合则优先函数存在 否则不存在 Bell有向图举例 4 6LR分析方法 4 6 1概述4 6 2LR 0 分析器4 6 3SLR 1 分析器4 6 4规范LR 1 分析器4 6 5规范LALR 1 分析器4 6 6语法分析程序的自动生成工具 YACC 基本思路 LR K 分析器从左到右扫描所给定的输入串 并以相反的方向构造该输入串的最右推导 Right mostDerive即规范推导 LR K 分析器根据分析栈的内容以及向前查看输入串中K个符号来决定分析动作 特点 1 分析器对源程序中错误的诊断灵敏 2 分析器对文法适应性强 文法分析能力强 3 分析器结构复杂 K越大 相应的分析器愈复杂 当K 0时 表示在确定分析动作时不需向前查看符号 LR 0 分析器是LR分析器中最简单的一种 LR 0 分析器分析能力弱 实用性差 一般仅作为构造更复杂的LR分析器的基础 LR分析器的逻辑结构和工作原理 LR分析器的数学模型是下推自动机 该下推机具有一个输入机构 一个分析栈和一个有穷的控制系统 一般来说 其控制系统是一个具有多状态的有穷状态机 4 6 1概述 1 下推自动机的定义M R q0 Z0 F 有穷状态集 堆栈字母表 输入字母表R 转换关系 q0 初态Z0 初始堆栈 符号Z0 F 为 的子集 是控制器的终态集 2 有穷自动机状态的分类有穷状态集 中的状态分成3类 读状态 当读一个终结符或非终结符时 发生由一个状态到另一状态的状态转移 归约状态 识别出当前句型的活前缀的句柄部分 处于归约状态时 检测出来的句柄将归约为一个非终结符号 识别状态 输入串被分析器成功识别 3 LR 0 分析栈的结构LR 0 分析器的分析栈是一个符号对偶栈 对偶的第一个元素是文法符号 对偶的第二个元素是分析器扫描一个文法符号时所进入的状态 4 LR 0 分析过程LR 0 分析器由总控程序和分析表两部分组成 分析开始时 栈内的初始状态为S0 即与分析器有关的有穷控制的开动状态 1 当分析器处于读状态时 它将当前扫描到的符号压入堆栈 并执行由所读符号所指示的状态转移 并将该后继状态也压入栈内 2 当分析器处于归约状态时 将对偶栈中与句柄对应的部分弹出进行归约 然后执行读操作 读入归约后的符号并压入堆栈 如果归约到的符号为识别符号 则分析器接受所给定的符号串并停机 否则 归约生成的左部符号和当前栈顶状态将确定下一个状态转移 一 初始情况 二 一般过程 1 Ifaction sm ai si shiftsi then分析格局变为 2 Ifaction sm ai ri Reducei then表示用第i个产生式A Xm k 1 Xm进行归约 分析格局变为 然后查goto表 Ifgoto sm k A sithen格局变为 3 Ifaction sm ai accthen分析成功 5 举例 P124 文法G S S aAcBeA bA AbB d 注意 分析中只需要状态栈信息1 因为分析器的有穷控制是确定的 所以文法符号可不必压入栈内 2 当到达一归约状态时 与该状态对应的句柄是确定的 4 6 2LR 0 分析器 LR 0 分析器是最简单的分析器 无需向前查看输入符号即可确定分析器的动作 如下面的分析表 栈顶状态为0 2 3 5 7时采取移进操作 状态4 6 8 9时采取归约操作 不需要查看输入符号 LR 0 分析器是构造其它更为复杂的分析的基础 LR分析器为一个输入串构造一个最左归约序列 即逆向构造最右 规范 推导 最右推导序列的特征分析 考虑文法G 其开始符号为S 对于输入串x 其规范推导序列为 S 1 2 m 1 m x在推导序列中的每一步都具有形式 Bt t式中 i Bt B 是所使用的产生式 t Vt 定义 规范句型的活前缀对于规范句型 t 表示句柄 如果 u1u2 ur 那么称符号串u1u2 ui 其中1 i r 是句型 t的活前缀 其中包含了完整句柄的活前缀称为可归前缀 其它称为子前缀 P125 注意 由定义可知所有活前缀都不包括句柄右边的任何符号 即t中的任何符号 要建立输入串的最左归约序列 分析器的一个基本的功能就是要能检测当前规范句型的句柄 即能够识别出每一步规范推导 Bt t中的 即规范句型的所有活前缀 例子 文法G S P126 0 S S 1 S aAcBe 2 A b 3 A Ab 4 B d分析符号串abbcde a活前缀为 aab 规则2归约 可归前缀 ab 句柄为 baAb 规则3归约 可归前缀 aAb 句柄为 AbaAc活前缀为 aAcaAcd 规则4归约 可归前缀 aAcd 句柄为 daAcBe 规则1归约 可归前缀 aAcBe 句柄为 aAcBe以上规范归约对应的最右推导如下 S aAcBe aAcb e aA cde aAb cde aA bcde ab bcde abbcde 识别活前缀的NFA 化简NFA引入共同的初态结点X 用 弧联结得到图7 3 化简后得到图7 4 例子文法G E T E T E TT i E 引入一个新的开始符号S 得到拓广文法G S E E T E T E TT i E 其中符号 为文法G所产生的终结符号串的右界符 考察句型 E i i 建立其规范推导如下 S E T E E E E T E E i E T i E i i 根据定义 E E E E i均为该句型的活前缀 E i为可归前缀 拓展文法的目的 使文法只有一个以识别符号作为左部的产生式 从而使构造出来的分析器有唯一的接受状态 i为句柄 活前缀及可归前缀的一般计算方法 P128 定义规范句型中非终结符号A的左串集合为LC A 推论 如文法中有产生式B A 则有 根据以上推论和文法列出前缀集合方程 0 S S 1 S aAcBe 2 A b 3 A Ab 4 B d 求解前缀集合方程 一 LR 0 项目LR 0 项目定义文法G的一个项目是一个在右部符号串中标有一圆点的产生式 其形式为 A 1 2其中A 1 2为G的一个产生式 对空产生式A 其LR 0 项目只有一个为A 项目的意义在于它可以表示分析的进程 圆点是项目中标识分析进度的一种记号 圆点前面的部分是已经分析过的内容 后面的部分表示下面将要分析的内容 显然圆点后面的部分带有明显的预期特征 根据项目的特点 可以将LR 0 项目划分成三种类型 1 A 1 a 2其中a Vt称为移进项目 2 A 1 X 2其中X Vn称为待约项目 3 A 称为归约项目 举例 一般情况下 一个产生式可以有几个项目 例如 产生式E E T有下面四个项目 E E TE E TE E TE E T 二 有效性LR分析器的有穷控制机构的任务是识别规范句型的句柄 因此 只有包含在规范句型中的LR 0 项目才是合法有效的 一个项目A 1 2对于某个规范句型 1 2t的活前缀 1是有效的 当且仅当存在某个最右推导 S At 1 2t其中t是终结符号串 举例 一般来说 活前缀与有效项目是多对多关系 例如 具有如下产生式的LR 0 文法S E E T E T E TT i E 项目E E T T i和T E 对活前缀E 全都是有效的 即一个活前缀对应多个有效项目 如最右推导 S E E T 证明项目E E T对E 是有效的 最右推导 S E E T E i 证明项目T i对E 也是有效的 最右推导 S E E T E E 证明项目T E 对E 是有效的 请举出一个有效项目对应多个活前缀的例子 三 LR 0 分析器实现思路LR分析器的基本功能是识别当前句型的句柄 LR 0 项目刻画了当前句型的句柄被分析的程度 句柄完全在分析栈外 句柄的一部分已经进入分析栈 句柄全部进入分析栈 通过建立LR 0 项目集与分析器的每个状态之间的联系 构造LR 0 分析器的有穷控制机构 识别活前缀的有限自动机构造方法 方法1 直接法P131 1 求出文法的所有LR 0 项目 2 按照一定规则构造NFA1 确定状态结点每一个LR 0 项目都是结点 且为活前缀识别状态 圆点在最右的项目为句柄识别状态 2 生成转移弧线 3 将NFA确定化得到DFA例子 P131 图7 7 7 8 四 LR 0 项目集规范族的构造 识别活前缀的有限自动机构造方法2 首先 将项目S 将作为有穷状态控制的开始状态 其中S为文法的开始符号 项目S 反映了此时分析器还没有识别任何 非空 活前缀 然后 需要对项目集中的该初始项目进行闭包 closure 运算 为了获得一个项目A 1 X 2的闭包 X为非终结符号 应该将形式为X 的项目添加到该项目集中 一 闭包 closure 运算定义设I为一项目集 定义CLOSURE I 如下 1 I中的每一个项目都属于CLOSURE I 2 如项目A 1 X 2属于CLOSURE I 且X为非终结符号 则将形式为X 的项目添加到CLOSURE I 中 3 重复 1 和 2 直到CLOSURE I 封闭为止 二 后继项目定义令项目A X 是对应某个状态U的项目集中的一个项目 则称项目A X 为其后继项目 其中X为文法字汇表中的任一符号 三 状态转移当扫描一输入符号或者分析器处于归约状态时 则在LR分析器的有穷控制中将发生状态转移 在分析器的构造过程中 读操作是建立新状态的一种手段 因为项目A X 的后继项目A X 将与机器中另一状态V相联系 所以 读操作对所扫描的符号X将定义由状态U到状态V的状态转移 举例 具有如下产生式的LR 0 文法S E E T E T E TT i E 初态 C0 S E E T E E T E E T T i T E 以下是初态0到其它后继状态的转移图 例题中分析器的每个状态所对应的项目集 状态0 C0 S E E T E E T E E T T i T E 状态1 C1 S E E E T E E T 状态2 C2 E T 状态3 C3 T i 状态4 C4 T E E T E E T E E T T i T E 状态5 C5 S E 状态6 C6 E E T T i T E 状态7 C7 E E T T i T E 状态8 C8 E E T 状态9 C9 E E T 状态10 C10 T E E E T E E T 状态11 C11 T E 五 构造分析器有穷状态控制的三条规则 开始操作 令S 是文法中的一条规则 其中S表示该文法的开始符号 则与开始状态有关的项目为S 核项目 在一般情况下 开始状态最终将包含有多个项目 闭包运算 ifA X 是状态U的一个项目 X是非终结符号 则每个形式为X 的项目均是状态U的项目 扩展项目 闭包项目 闭包运算一直要进行到再没有新项目产生时为止 读操作 在状态U的项目A X 中 令X是一个字汇表中的符号 则项目A X 是状态U的后继状态V中的一个项目 核项目 注意U和V可以是同一个状态 例子 1 LR 0 项目集规范族C I0 I1 I10 如下 2 由LR 0 构造如下DFA M C V GO I0 C 六 算法1构造LR 0 项目集 给定一文法G 该文法的开始符号为S 算法为给定文法G生成LR 0 分析器的有穷控制 该机器包含有下列项目集 C C0 C1 Cm 其中C0是开始项目集 该LR 0 分析器的状态是 0 1 m 其中每个状态j是由项目集Cj得到的 本算法将生成项目集C 1 生成开始项目集 赋给开始项目集一个下标 即0 然后将项目S 放入集合C0 对该项目集执行闭包运算 即找到在圆点之后的非终结符X 将形式为X 的项目放置到集合中 其中X 是文法G的一个产生式 该闭包运算也要对所有导出的新项目进行 2 生成LR 0 项目集规范族C 重复第3到第4步 直到再没有新的项目集出现 3 在一个项目集上执行读操作 在一个项目上进行读操作 生成一个新的项目集 如果该项目集已经存在 则忽略不计 否则 得到一个新的基本项目集 4 对新的基本项目集进行闭包运算 七 算法2构造LR 0 分析表 1 构造状态转移表 即GOTO表 2 构造动作表 即ACTION表 例子 八 总结1 在LR 0 分析器中有两类状态 即 读状态和归约状态 包括接受状态 其中归约状态对应的项目集的模式特征为 在项目集中 所有项目中圆点均位于项目的右端 这样的状态表示已经发现句柄 2 采用两张表描述LR 0 分析器 其中一张表用来表示分析器的执行动作 如接受 归约 进栈和出错 另一张表用来指示从一个状态到另一个状态的转移 4 6 3SLR 1 分析器 LR 0 分析器的问题观察以下文法例子1 P137 构造其LR 0 分析表和DFA如下 歧义 问题分析 该项发生移进归约冲突 例子2 P139 给定如下拓广文法 求LR 0 分析表0 1 2 3 4 5 6 id I0 E E E E TE TT T FT FF E F id E I1 E E E E T T I2 E T T T F F I3 T F I4 F E E E TE TT T FT FF E F id id I5 F id I6 E E TT T FT FF E F id I7 T T FF E F id E I8 F E E E T T F id T I9 E E T T T F F id F I10 T T F I11 F E id I12 E E LR 0 分析表的冲突分析 状态2 9为不完全状态 出现移进归约冲突 I2 E T T T F I9 E E T T T F SLR规则基本思路 利用非终结符号的follow集信息帮助判断是采取 归约 动作还是 移进 动作 例1中冲突的解决办法 P138 求非终结符S的FOLLOW集 FOLLOW S 例子1改造之后的分析表如下 例2中冲突的解决办法 0 1 2 3 4 5 6 id求非终结符E的FOLLOW集FIRST F id FIRST T id FIRST E id FOLLOW E FOLLOW T FOLLOW F si表示移进到状态i ri表示用i号产生式归约 例子2改造之后的分析表如下 follow E follow E 采用改造后的分析表对句子i i i的分析 SLR 1 分析器可用一对函数F和G表示 F函数和G函数将确定下推机的有限控制结构 1 函数F 动作函数 是状态和当前符号到下列动作的映射 移进 缩写为s 归约k k是产生式编号 缩写成rk 接受 缩写为A 出错E 用空项表示 函数F 状态 当前输入 rk s A E 2 函数G 状态转移函数 G函数是状态和字汇表V中的符号到下列项目的映射 一个状态 出错E 用空项表示 函数G 状态 字汇表符号 状态 出错 算法SLR 1 CONSTRUCTOR 给定由项目集的集合表示的LR 0 机器C C0 C1