ch6-自底向上优先分析方法.ppt

1 第六章自下而上优先分析法 自下而上分析方法 移进 归约分析 基本思想 用一个寄存文法符号的先进后出栈 将输入符号按从左到右扫描顺序逐个移入栈中 边移入边分析 一旦栈顶符号串形成某个句型的句柄或可归约串时 对应于某条规则右部 就进行一次归约 即用该规则左部非终结符替换相应规则右部符号串 重复这一过程直到整个输入串分析完毕 最终若栈中剩下句子右界符 和文法的开始符号 则所分析的输入符号串是文法的正确句子 否则就不是正确的句子 报告错误 2 例 文法G S 见右面部分 对输入串abbcde 进行语法分析 检查该符号串是否是该文法的正确句子 S aAcBeA bA AbB d abbcde aAbcde aAcde aAcBe S 输入串分析过程 3 S aAcBeA bA AbB d 分析过程可以看成自底向上构造语法树的过程 每步归约都是构造一颗子树 当输入串结束时 整个语法树构造完成 自底向上构造语法树 4 可以看出 一个句型中当含有多个子串可以匹配不同产生式的右部时 将有不同的归约过程 究竟应该对谁先归约呢 答案 句柄 使用句柄归约 在分析过程中 如何确定句柄呢 5 6 1自下而上优先分析法概述 优先分析法有两种 简单优先分析法 规范归约 对文法按一定原则求出所有文法符号的优先关系 以确定归约过程中的句柄 算符优先分析法 不规范归约 规定算符之间的优先关系 即终结符之间的优先关系 在归约过程中只要找到可归约串就归约 并不考虑归约到那个非终结符号 6 6 1自下而上优先分析法概述 简单优先分析法 准确 规范 但分析效率较低 实际使用价值不大 算符优先分析法 分析速度快 适用于表达式分析 但归约不规范 7 6 2简单优先分析法 简单优先分析法是按照文法符号的优先关系确定句柄 1 优先关系 1 X Y当且仅当G中存在产生式规则A XY 2 X XB 且B Y 3 X Y当且仅当G中存在产生式规则A BD 且B X和D Y 关键 确定文法符号间的优先关系 8 举例说明文法符号的优先关系 9 文法符号间的优先关系采用语法树结构表示 语法树结构 10 注 矩阵元素为空时表示该文法的任何句型中不会出现该符号对的相邻关系 在分析时若遇到它们相邻 则说明出错 也就肯定输入符号串不是该文法的句子 优先关系矩阵 11 2 简单优先文法若一个文法满足 1 在文法符号集V中 任意两个符号之间最多只有一种关系成立 2 在文法中任意两个产生式没有相同的右部 则这样的文法为简单优先文法 简单优先文法 12 3 简单优先分析法 优先分析算法 1 根据优先文法构造优先关系矩阵 2 存储文法产生式 并设符号栈S 3 将输入符号串a1a2 an 依次逐个存入符号栈S中 直到遇到栈顶符号ai的优先性 下一个待输入符号aj时为止 4 栈顶当前符号ai为句柄尾 由此向左在栈中找句柄的头符号ak 即找到ak 1 ak为止 5 由句柄ak ai在文法的产生式中查找右部为ak ai的产生式 若找到则用相应左部代替句柄 若找不到则为出错 这时可断定输入串不是该文法的句子 6 重复 3 5 直至归约完输入串 栈中只剩下文法的开始符号为止 优先分析算法 13 6 3算符优先分析法 算符优先分析法只考虑算符 广义为终结符 之间的优先关系 14 6 3 1方法概述 算符优先分析法是一种自下而上的语法分析方法 它是依据算术表达式的四则运算过程而设计的一种方法 算符优先分析法的基本思想 首先确定算符 确切地说是终结符 之间的优先关系和结合性质 然后借助这种关系 比较相邻算符之间的优先级来确定句型的可归约串 并进行归约 注意 算符优先分析过程是自下而上的归约过程 但它的可归约串未必是句柄 也就是说 算符优先分析过程不是一种规范归约 15 任何两个相邻终结符a和b之间的优先关系有三种 aba的优先级高于ba ba的优先级等于b 1 相邻终结符号的优先关系 注意 优先关系与出现的左右次序有关 aaa b不一定有b a 16 例如 表达式文法 二义文法 17 2 优先关系矩阵 优先关系表 优先表 一个文法的终结符号之间的优先关系可用一个矩阵来表示 矩阵的每一行每一列都是文法的终结符 矩阵元素是两终结符之间可能的优先关系 算符优先分析法就是借助优先关系矩阵寻找句型的可归约串 18 表达式运算符的优先关系表 19 6 3 2算符优先文法 1 算符文法的定义设有文法G 若它的任一规则的右部都不含两个相邻的非终结符 即不含形如 U VW 的规则 则称该文法为算符文法 也称OG OperatorGrammar 文法 使用算符优先分析法的条件 文法必须是算符优先文法 20 性质1 在算符文法中 任意句型都不含两个相邻的非终结符 证明 用归纳法设 是句子 S 即S 0 1 n 1 n 推导长度是n 归纳起点n 1时 S 0 1 即S 必存在一个规则S 而由算符文法的定义 文法的规则中无相邻的非终结符 满足性质1 假设n 1 n 1满足性质1 若 n 1 A A为非终结符 由假设的 的尾符号和 的首符号都不是非终结符 否则与假设矛盾 又若A 是文法的规则 则有 n 1 n 而A 是文法的规则 它不含两个相邻非终结符 所以 也不含两个相邻的非终结符 满足性质1 算符文法的性质 21 性质2 若Ab或bA出现在算符文法的句型 中 其中A VN b VT 则 中任何含b的短语必包含A 证明 用反证法 由算符文法的性质1可知 S bA 若存在B b 这时b和A不同时归约 分属于不同的短语 则必有S BA 这样在句型BA 中 存在相邻的非终结符 所以与性质1矛盾 故 中任何含b的短语必包含A 证毕 注意 含b的短语必含A 含A的短语不一定含b 22 2 终结符号间的优先关系设G是一个算符文法 对于任何终结符a b 算符优先关系定义如下 a b当且仅当G中含有形如P ab 或P aQb 的规则 ab 或R Qb a b当且仅当G中含有形如P Rb 的产生式 而R a或R aQ 23 由语法树来说明优先关系 1 a b则存在语法子树 a a和b在同一句柄中同时归约 所以优先级相同 2 ab则存在语法子树 c a和b不在同一句柄中 a先归约 所以b的优先级小于a 为 或非终结符 24 设有一个不含 规则的算符文法G 如果任何终结符对 a b 至多只满足下述关系之一 a b a b a b 则称G是一个算符优先文法 也称OPG文法 OPG OperatorPrecedenceGrammar 3 算符优先文法的定义 25 例 文法G E E E E E E E i 所有规则中都没有相邻的非终结符 所以它是算符文法OG文法 由于E E E和E E E 所以有 运算符 和 之间存在两种不同的优先关系 所以该文法不是算符优先文法OPG 文法G E E E T TT T F FF E i该文法是算符优先文法 OPG 26 6 3 3算符优先关系表的构造 由定义直接构造 对任意的文法非终结符A 给出集合FIRSTVT A 和LASTVT A 的定义 FIRSTVT A a A a 或A Ba a VT而B VN LASTVT A a A a或A aB a VT而B VT 查看右部形如 ab 或 aBb 的产生式 则有a b若产生式右部是 aA 且 b FIRSTVT A 则必有优先关系 ab 由上述定义有 27 计算表达式文法的算符优先关系 28 计算表达式文法的算符优先关系 29 表达式文法的算符优先关系表 30 构造FirstVT A 的规则 若有规则A a 或A Ba 则a FirstVT A 若a FirstVT B 且有产生式A B 则a FirstVT A 构造优先关系表的算法 1 构造FirstVT与LastVT算法依据的规则 构造LastVT A 的规则 若有产生式A a或P aB 则a LastVT A 若a LastVT B 且有产生式A B 则a LastVT A 31 主程序 BEGINFOR每一个非终结符A和终结符aDOF A a FALSE FOR每个形如A a 或A Ba 的产生式DOINSERT A a WHILESTACK非空DOBEGIN把STACK的顶项记为 B a 托出去FOR每个形如A B 产生式DOINSERT A a ENDEND ProcedureINSERT A a IFNOTF A a THENBEGINF A a TRUEPUSH A a ONTOSTACKEND 计算FIRSTVT A 的算法 F A a 是一个布尔数组其值为真当且仅当a FIRSTVT A 32 举例说明 求表达式文法中每个非终结符的FIRSTVT集合 33 举例说明 求表达式文法中每个非终结符的FIRSTVT集合 34 按同样方法 求每个非终结符的LASTVT A 的集合 35 for 每条产生式A x1x2 xn for i 1 ixi 1 2 构造分析表的算法 36 对于算符优先文法 可以引入一个新的文法开始符号S S S 可以看成是句子的括号 所以 对FirstVT S 中的所有b 置 置 关于输入结束符号 的解释 37 对E求FIRSTVT E 和LASTVT E 按构造规则 E E T 则 FIRSTVT E 又E T T T F 则 FIRSTVT E 又E T T F F E 则 FIRSTVT E 又E T T F F i 则i FIRSTVT E 故 FIRSTVT E i 类似地 LASTVT E i 例 表达式文法G E 构造该文法的算符优先关系表 E E T TT T F FF E i 首先构造每个非终结符的FirstVT和LastVT 38 按步骤构造如下 1 逐条扫描产生式 因有产生式F E 则有 2 寻找终结符在左边 非终结符在右边的符号对有E E T T则 T T FT 则LastVT F F E E 则LastVT E 3 例 续 构造该文法的算符优先关系表 39 算符优先关系表 40 6 3 4算符优先分析算法的设计 算符优先分析方法是一种自下而上分析方法 但它不是一种规范归约的分析方法 其原因是在算符优先分析中 仅在终结符之间定义优先关系 而不考虑非终结符之间的优先关系 从而无法使用优先关系表去识别由单个非终结符组成的可归约串 也就是说 算符优先分析法不是用句柄来刻画可归约串 而是用最左素短语来刻画可归约串 41 1 最左素短语的定义 所谓素短语是指这样的一个短语 它至少含有一个终结符 并且除它自身之外不再含有其它素短语 最左素短语是指处于句型最左边的那个素短语 最左素短语是算符优先分析算法的可归约串 例 考虑表达式文法G E 的句型T T F id的素短语和最左素短语 T F和id是素短语 T F是最左素短语T是句柄 但不是素短语 42 如果aNb 或ab 出现在句型r中 则a和b之间有且只有一种优先关系 即 1 若ab则在r中必含有a而不含b的短语存在 3 若a b则在r中含有a的短语必含有b 反之亦然 算符优先分析句型的性质 43 2 识别句型最左素短语的方法 一个算符优先文法G的一般句型可写成 N1a1N2a2 NnanNn 1 其中ai是终结符 Ni是可有可无的非终结符 也就是说 在算符优先文法的一般句型中 任何两个终结符之间至多只有一个非终结符 任何句型都没有相邻的两个非终结符 44 由最左素短语的定义 一个算符优先文法G的任何句型 N1a1N2a2 NnanNn 1 的最左素短语是满足下列条件的最左子串NiaiNi 1ai 1 NjajNj 1 ai 1aj 1也就是说 NiaiNi 1ai 1 NjajNj 1已经和某个产生式的右端匹配 即已形成可归约串 可以对它进行归约 2 识别句型最左素短语的方法 续 45 例 考虑表达式文法G E 的句型T T F id的最左素短语 T T F id N1a1N2a2N3a3a4 N2a2N3是最左素短语 46 3 算符优先分析算法 算符优先分析方法是从句子开始 从左到右扫描 找出其中的最左素短语进行归约 已扫描或归约后的串与未扫描的串连接在一起是某时刻的句型 继续对句型进行归约 直至输入串扫描结束 句型为 S 为止 47 最左素短语中的终结符号具有相同的优先关系 最左素短语中的符号是当时最先要归约的串 如果当前栈顶的终结符输入符号 表示已找到最左素短语的尾 再从栈顶开始 按优先关系在栈内向左寻找最左素短语的头 然后归约最左素短语 如果出现两个终结符之间不存在优先关系 则表示语法错误 进行出错处理 3 算符优先分析算法 续 48 归约成功的标志是 读入符号为 S栈中为 N 49 k 1 S k REPEAT把下一个输入符号读进a中 IFS k VTTHENj kELSEj k 1 WHILES j aDOBEGINREPEATQ S j IFS j 1 VTTHENj j 1ELSEj j 2UNTILS j Q 把S j 1 S k 归约成某个串N k j 1 S k N ENDOFWHILE IFS j aORS j aTHENBEGINk k 1 S k a ENDELSEERRORUNTILa 使用一个符号栈S 既用它寄存终结符 也用它寄存非终结符 用k代表符号栈S的使用深度 50 1 由于算符优先分析过程不考虑非终结符 所以任何归约都可以归约到同一个非终结符N 2 甚至非终结符根本就可以不入栈 只要在归约时知道去执行哪个语义子程序就可以了 这样还可以节省栈空间 算法分析 51 例 对输入串i i 的算符优先分析过程 52 句子的算符优先分析过程中 没有考虑非终结符 也就是说 最左素短语中包含的非终结符是什么对归约来说无关紧要 解释 编译程序可以不必关心符号名字 而只关心与终结符和非终结符相联系的语义信息 如与非终结符或运算对象相关的类型 存储地址等 也就是说 对E T归约时执行的语义子程序只关心素短语中有无符号 而不关心 左右是E T还是F 算符优先分析过程跳过了许多形如P A的规则 所以算符优先分析过程的效率较高 算符优先分析过程 规范分析过程 53 6 3 5优先函数的构造 在算符优先分析法中 文法终结符之间的优先关系是用矩阵表示的 这样需要大量的内存空间 当文法有n个终结符时 就需要 n 1 2个内存单元 包括 实际实现中使用优先函数来代替优先矩阵表示优先关系 对具有n个终结符的文法 它只需2 n 1 个内存单元存放优先函数 可以节省大量存储空间 54 把每个终结符a与两个自然数f a 和g a 相对应 使得 若ab则f a g b 若a b则f a g b f与g称为优先函数 1 优先函数的定义 55 对应的优先函数如下 56 2 构造优先函数的方法方法一 逐次加一法 Floyd方法 确定初值 对所有终结符a 包括 令f a g b 0 也可为其它任意整数 对所有终结符a和b若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 重复执行 2 直到过程收敛 重复过程中 若f a 或g b 大于2n 则表明该优先关系表不存在对应的优先函数 输入关系表输出优先函数 57 例 已知优先关系分析表 构造函数f和g 第一步 置初值 不考虑 第二步 迭代1次 第三步 迭代2次 第四步 迭代3次 迭代过程收敛 58 文法的优先关系表对应的优先函数不唯一 对优先函数每个元素的值都增加一个常数 仍为原优先关系表的优先函数 不会影响终结符之间的关系 2 59 也有一些优先关系表不存在对应的优先函数 若假定它存在优先函数f和g 则应有f a g a f a g b f b g a f b g b 从而f a g b f b g a f a f a f a 矛盾因而不存在对应的优先函数 60 第一步 置初值 第二步 迭代1次 第三步 迭代2次 第四步 迭代3次 第N 1步 迭代N次 永远不能收敛 61 对于每个终结符a 包括 令其对应两个符号fa和ga 画一张以所有符号fa和ga为节点的方向图 如果a b或a b 则从fa画一箭弧至gb 如果a b或a b 则从gb画一箭弧至fa 对每个节点赋一个值 该数等于从该节点出发所能达到节点 包括出发节点自身在内 的个数 检查所构造出来的函数f和g与原优先关系表是否矛盾 若无矛盾 则所求即为优先函数 反之 则不存在优先函数 2 构造优先函数的方法方法二 Bell有向图法 输入关系表输出优先函数 62 例 已知优先关系分析表 构造函数f和g 63 使用优先函数表对符号串的分析过程类似于优先关系表的过程 另外对 符号有如下规定 f g 其中x VN VT 64 例 设有文法G S S a b T T T S S 1 计算每个非终结符的FIRSTVT和LASTVT 2 构造算符优先关系分析表 3 文法G S 是算符优先文法吗 如果是 给出优先函数 并给出串 a a a 的算符优先分析过程 1 FIRSTVT S a b LASTVT S a b 2 FIRSTVT T a b LASTVT T a b 算符优先关系分析表 文法G S 是算符优先文法 65 优先关系分析表对应的bell有向图 66 串 a a a 的分析过程 0 a a a 移进预备 1 a a a 用S a归约 4 S a a 用S a归约 8 S S a 用S a归约 11 S T 用T T S归约 12 S T