第6章_自底向上分析-优先分析法.ppt

1 第6章自底向上分析 优先分析法 本章介绍编译程序的第二个阶段语法分析的设计方法和实现原理 自底向上分析法的思想 简单优先分析法 算符优先分析法 2 自底向上分析 也称移进归约分析 实现思想 对输入符号串自左向右进行扫描 并将输入符逐个移入一个后进先出栈中 边移入 边分析 一旦栈顶符号串形成某个句型的句柄或可归约串时 则进行归约 重复 直到归约栈中只剩文法的开始符号时 则为分析成功 确认输入串是文法的句子 6 1自底向上分析法概述 3 例6 1有一文法G S S aAcBeA bA AbB d对输入串abbcde 进行分析 检查该符号串是否是G S 的句子 它的最右推导是 S aAcBe aAcde aAbcde abbcde由此我们可以构造它的逆过程即归约过程 4 先设一个先进后出符号栈 并且把句子左括号 号放入栈底 其分析过程如下所示 5 上述归约过程 是从输入符号串开始 自底向上地通过归约当前句型的句柄来建立语法树的 我们不难画出上述分析过程的语法树 见下图 在图中 我们仅画出与生成语法树有关的几步 从语法树看出 每一步确实都是归约当前句型的句柄 且句柄出现在符号栈栈顶 不会在栈中间 6 上述分析过程并未真正解决句柄的识别问题 对例6 1 分析进行到第 5 步 当时栈内符号串为aAb 根据该符号串 有规则A Ab和规则A b 那么 符号串Ab和b都是某条规则的右部 故都有可能被判别是句型的句柄 假如选择b作为句柄 并把b归约为A 那么 最终就达不到归约到S的目的 因而 也就无从得知输入串abbcde是一个句子了 在自底向上分析中 如何寻找确定一个句型的句柄是构造一个自左向右扫描 自底向上分析方法必须要解决的一个问题 7 6 2优先分析法概述 优先分析法分为简单优先分析法和算符优先分析法 简单优先分析法求出所有符号间的优先关系 进行规范归约 准确 规范 但分析效率低 实际使用价值不大 算符优先分析法只规定算符之间的优先关系 即只考虑终结符之间的优先关系 不是规范归约 虽不规范 但分析速度快 特别适用于表达式的分析 采取措施 克服缺点 8 6 3简单优先分析法 1 优先关系与数学中的不同 1 X Y当且仅当G中存在产生式A XY 2 XY当且仅当G中存在产生式A BD 且BX D Y 优先级高的先归约 9 文法的简单优先关系矩阵 10 例6 2若有文法G S S bAbA B aB Aa 根据上面 关系 由S bAb且A A B Aa可得 b a b B b由B Aa 且A Aa A B可得 a a a B a 11 上述关系也可以用语法树的结构表示如图 也可看出当b ba出现在某一句型中时 则 和 a 在句柄中时 b 不在句柄中 因此必须 和 a 先归约 所以 b 的优先级比 a 小 同样可以看出当 a 或 A出现在某句型中时 右边的 a A 出现在句柄中 而左边的 不被包含在句柄中 所以左边 的优先级小于右边相邻的 a 或 A 对于大于关系也可由树中看出 当ab或aa出现在某一句型中时 左边的 a 在句柄中 右边的 a 和 b 不可能在句柄中 所以有a b a a的关系存在 同样 b或 a出现在某一句型中时 在句柄中而 a b 不在句柄中 因此 先归约 则有 a b的关系 当然对含有Bb和Ba的句型 B 先归约 则有B b B a的关系 S bAbA B aB Aa 12 为了表示简洁明了我们也可以把文法符号之间的关系用矩阵表示 称作优先关系矩阵 S bAbA B aB Aa 文法的简单优先关系矩阵 13 若矩阵中元素要么只有一种关系 要么为空 元素为空时表示该文法的任何句型中不会出现该符号对的相邻关系 在分析过程中若遇到这种相邻关系出现 则为出错 也就可以肯定输入符号串不是该文法的句子 号用来表示语句括号 号的优先级 号 当然这里仅对与 号有相邻关系的文法符号而言 2 简单优先文法的定义 1 在文法符号集V中 任意两个符号之间最多只有一种优先关系成立 2 在文法中任意两个产生式没有相同的右部 14 3 简单优先分析法的操作步骤根据已知优先文法构造相应的优先关系矩阵 1 将输入符号串a1a2 an 依次逐个存入符号栈S中 直到遇到栈顶符号ai的优先性 下一个待输入符号aj为止 2 栈顶当前符号ai为句柄尾 由此向左在栈中找句柄头符号ak 即找到ak 1 ak为止 3 由句柄ak ai在文法的产生式中查找右部为ak ai的产生式 若找到则用相应的左部代替句柄 否则为出错 4 重复 1 2 3 操作直到归约完输入符号串 栈中只剩文法开始符号为止 15 6 4 算符优先分析法 自下而上分析算法模型 移进归约算符优先分析不是规范归约算符优先分析的可归约串是句型的最左素短语定义上下文无关文法G的句型的素短语是一个短语 它至少包含一个终结符 且除自身外不再包含其他素短语 处于句型最左边的素短语为最左素短语 文法G S S A 且A 则称 是句型 相对于非终结符A的短语 16 文法G 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 句型T T F i其短语有 T T F iT T FTT Fi E E T E T F F T T i 最左素短语为 T F 句型T T F的素短语为 T T E T F E 句型T T i的素短语为 i 素短语为 T F i E T T i 17 定义素短语是这样一个短语 它至少包含一个终结符号 并且 除它自身之外 不再包含其他素短语 即至少包含一个终结符号的简单短语 最左素短语是指处于句型最左边的那个素短语 算符优先文法句型的最左素短语是唯一的 形式 ai 1aj 1 句型中之间的符号串是待归约的符号串 即最左素短语 句柄和最左素短语的区别 G E E E T TT T F FF E i句型T T F i 18 19 分析程序模型 总控程序 算符优先关系表 产生式 输入串 输出 20 1 直观算符优先分析法如何确定算符优先关系 人为确定 1 i的优先级最高 1 优先级次于i 右结合 2 和 优先级次之 左结合 3 和 优先级最低 左结合 4 括号 的优先级大于括号外的运算符 小于括号内的运算符 内括号的优先性大于外括号 5 的优先性低于与其相邻的算符 文法G E E E E E E E E E E E E E i 算符优先关系表 21 2 算符优先文法的定义 定义6 1 如果不含空产生式的上下文无关文法G中没有形如A BC 的产生式 其中B C V则称G为算符文法 例 G E E E E E E E E E E E E i例 G E E E T TT T F FF P F PP E i性质1 在算符文法中任何句型都不包含两个相邻的非终结符 性质2 如Ab 或bA 出现在算符文法的句型 中 其中A V b T 则 中任何含b的短语必含有A 22 3 算符优先关系 在OG中定义6 2 算符优先关系 a bG中有形如 A ab 或A aBb 的产生式 abG中有形如 A Bb 的产生式 而B a或B aC规定若Sa 或SCa 则 23 24 定义6 3在OG文法G中 若任意两个终结符间至多有一种算符优先关系存在 则称G为算符优先文法 OPG 注意 允许b c c b 不允许b c b c b c中任两个同时存在 b c不一定c b 结论 算符优先文法是无二义的 25 E E E E E E E E E E E E i不是算符优先文法 26 4 算符优先关系表的构造 首先定义如下两个集合 FIRSTVT B b Bb 或BCb LASTVT B a B a或B aC 按如下算法计算出给定文法中任何两个终结符对 a b 之间的优先关系 27 按如下算法计算出给定文法中任何两个终结符对 a b 之间的优先关系 1 关系直接看产生式的右部 若出现了A ab 或A aBb 则a b2 关系求出每个非终结符B的FIRSTVT B 若A aB 则 b FIRSTVT B 则ab 28 计算算符优先关系 例文法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 FIRSTVT E FIRSTVT E i FIRSTVT T i FIRSTVT F i FIRSTVT P i LASTVT E LASTVT E i LASTVT T i LASTVT F i LASTVT P i 29 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 3 关系找形如 A Bb 的产生式E 则LASTVT E E 则LASTVT E T 则LASTVT T P 则LASTVT P E 则LASTVT E 2 关系找形如A aB 的产生式 E 则 FIRSTVT E T 则 FIRSTVT T F 则 FIRSTVT F F 则 FIRSTVT F E 则 FIRSTVT E 1 关系由产生式 0 和 6 得 30 表达式文法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 31 5 算符优先分析算法 算符优先文法句型的性质算符文法的任何一个句型应为如下形式 N1a1N2a2 NnanNn 1 其中Nk 1 k n 1 为非终结符或空 ak 1 k n 为终结符算符优先文法句型的最左素短语NiaiNi 1ai 1 NjajNj 1满足 ai 1 aiai ai 1 aj 1 ajaj aj 1即 ai 1aj 1 32 算符优先分析归约过程流程图 34 1k 1 S k 2repeatread下一符号到a 3ifS k Vtthenj kelsej k 1 4whileS j ado5 repeat6Q S j 7ifS j 1 Vtthenj j 18elsej j 29untilS j Q 10将S j 1 S j 2 S k 归约到某个N 11k j 1 12S k N 13 14if S j aorS j a 15then k k 1 S k a 16elseerror17untila 35 算符优先分析法小结 归约过程流程图简单 直观 有利于表达式分析 易于手工实现比规范归约快可能导致把错误的句子得到正确的归约 36 6 优先函数 简单优先分析和算符优先分析 都需要一个优先矩阵 占用大量的存储空间 如对于一个100阶的优先矩阵 它的元素共有10000个 而每一元素至少需用两个二进位表示 每个符号对间都有4种可能的状态之一 存放这样的矩阵共需20000个二进位 即2500个字节 因此很有必要寻找一种既反映符号对间的优先关系 而所需的存储空间又不太大的表示方法 37 解决方案 根据所给的优先矩阵 构造两个离散函数f和g 并用它们去代替原来的优先矩阵 此f和g把符号映射为自然数 且满足 当a b时 f a g b 当a b时 f a g b 当a b时 f a g b 把f和g分别称为入栈优先函数和比较优先函数 38 显然 在用优先分析法进行语法分析的过程中 每当需要查询一个符号对 a b 间的优先关系时 就只须比较f a 和g b 的大小即可 把记录优先关系所需的存储空间由n2个单位压缩至2n个单位 因此 我们通常把上述做法称为优先矩阵的线性化 39 1 由定义直接构造优先函数表达式文法优先函数计算过程见下图 40 2 用优先关系图构造优先函数方法1 a VT 建立两个符号fa和ga 2 若a b 则把fa和gb分在一组 3 a b VT 若a b 则从fa至gb画一条弧 若a b 则从gb至fa画一条弧 4 若图中无环 则存在优先函数 f a 和g b 等于从fa和gb出发的最长路径 或给每个结点俯一个数 此数等于从该结点出发所能到达的结点 包括结点自身在内 的个数 41 42 例 优先关系矩阵如下 与对应的优先函数表相矛盾 因此 不存在优先函数 43 7 算符优先分析法的局限性 由于算符优先分析法去掉了单非终结符之间的归约 尽管在分析过程中 当决定是否为句柄时采取一些检查措施 但仍难完全避免把错误的句子得到正确的归约 典型例题及解答例题1已知布尔表达式文法G B 为 B BoT TT TaF FF nF B t f1 G B 是算符优先文法吗 2 若G B 是算符优先文法 请给出输入串ntofat 的分析过程 44 B BoT TT TaF FF nF B t f解答 1 计算FIRSTVT和LASTVT集合 FIRSTVT B o a n t f LASTVT