由底向上语法分析.ppt

《由底向上语法分析.ppt》由会员分享，可在线阅读，更多相关《由底向上语法分析.ppt（115页珍藏版）》请在金锄头文库上搜索。

1、2020 6 10 1 第五章自底向上的语法分析 2020 6 10 2 内容 5 1自底向上的分析方法简介5 2算符优先分析法5 3LR分析 2020 6 10 3 自底向上的分析方法简介 自底向上的语法分析器除 接受 外 一般有两种动作 移进 将一个位于输入带上的最前面的终极符移入符号栈 符号栈中可以有符号 非终极符和一些其它的状态信息 2 归约 将栈顶的符号串 利用产生式A 归约为非终极符自底向上的语法分析器有时也称为移进 规约分析器 2020 6 10 4 归约 Reduction 推导的相反过程叫归约如果S u1 u2 un 1 un是最右推导 则它的逆向过程 un un 1 u2

2、u1 S 被称为规范规约 最左归约 2020 6 10 5 规约的例子 给定文法G S aAcBeA b AbB d 句子abbcde的推导为 S S a c A B e aAbcde abbcde d A b b 规范规约为 aAbcde aAcde S a c A B e d A b b aAcBe S aAcBe aAcde abbcde b A b d a A B c S e 2020 6 10 6 自底向上的语法分析存在中的问题1 如果句型存在有多个子串与一产生式右部相匹配 该选择哪一个进行规约 选择位于句型最左边的那一个子串 Why 因为分析器是从左向右扫描的 Answer 202

3、0 6 10 7 回顾 短语与句柄 w是uAv相对于A的短语 当且仅当A w 这是一棵根为A的子树 w是uAv相对于A的直接短语 当且仅当A w 这是一棵高度为1的子树 句柄是句型的最左直接短语 设G是一个CFG uAv是G的一个句型即S uAv 那么 2020 6 10 8 句柄 是否匹配产生式右部的的最左子串一定是句柄 Answer 不 可能是 也可能不是 2020 6 10 9 句柄的例子 给定文法G S varL TL id L idT real句子varid id real的语法树如下 var id L L T S real id 看位于最左边的 id 它显然不是一个句柄 虽然它匹配

4、了产生式L id的右部 id 它是句柄吗 2020 6 10 10 问题2 如何识别句柄 试探 当子串与某个产生式的右部匹配时 将其视为句柄 如果分析失败 则回溯 对文法做一些限制 这样可以根据规则来识别句柄 例如算符优先文法 OperatorPrecedenceGrammar OPG 识别句柄是移进 规约分析器的主要任务 它可以用如下方法实现 2020 6 10 11 OPG的基本思想 每一个运算符均有其优先级 当两个运算符相邻 则优先级高的先计算 表达式中所的操作数均被运算符隔开 OPG的基本思想来源于算术表达式的计算 在算术表达式中 2020 6 10 12 运用算符优先级的例子 G E

5、 E E E E E E E E E E i 这是一个二义文法 但如规定 和 的优先级比 和 的高时 只有一棵语法树 对于句子 i i i i i 我们有如下的归约 2020 6 10 13 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 E 的优先级比 高 运用算符优先级的例子 2020 6 10 14 算符文法与算符优先文法 定义5 1若文法G的产生式右部不含两个VN符相邻的情况 则称G为算符文法 G的VT符被称为算符可以证明 算符文法不会含有两个VN符相邻的句型常见语言不一定是算符

6、文法 但可容易地对其进行改造 例PASCAL中的循环语句 for do可将其改为 for do to 2020 6 10 15 OPG定义 G中没有 产生式 如 X 也没有含连续的非终极符的产生式 对于任意的终极符对 a b 最多只有下面的一种关系a b a b a b 它们分别表示a的优先级低于 等于 高于b的优先级 一个CFGG是OPG 当且仅当 2020 6 10 16 优先性的实质 ab a比b先归约 2020 6 10 17 什么时候a b a b 当且仅当a和b同时归约于是 a和b应该是在同一个句柄中相邻 P ab orP aQb 于是有 a b当且仅当G中有产生式 形如 2020

7、 6 10 18 什么时候a b a b 当且仅当a先于b归约 a在位于b前的R的短语中 a在短语R的最右边 R aorR aQ于是a和b是邻居 R短语的根 应该是b的邻居或者b跟随于R R和b在同一个产生式中 如 P Rb 因为在OPG中没有后继的非终极符 2020 6 10 19 什么时候a b 综上所述 我们有 a b当且仅当a是b的哥哥的最小的子孙 形式地 a b当且仅当在G中有一产生式 形如 P Rb 并且R a或R aQ 2020 6 10 20 什么时候a b 同样地 我们有 a b当且仅当b是a的弟弟的最大的子孙 形式地 a b当且仅当在G中有一产生式 形如 P aR 且R b

8、 或R Qb 2020 6 10 21 优先级的总结 孩子优先 叔伯随后 兄弟一同走 ChildrenFirst UnclesLater andBrothersTogether 2020 6 10 22 a b 当且仅当在G中有一产生式 形如 P ab 或P aYb ab 当且仅当在G中有一产生式 形如 P Rb 且R a或R aQ 即 2020 6 10 23 计算a b 很容易通过扫描所有的产生式找出形如a b所有的 a b 对 如果存在有产生式P ab 或P aQb 则a b 2020 6 10 24 计算a b 我们已经知道a b 当且仅当在G中有一产生式 形如 P aR 且 1 R

9、b orR Qb 于是我们定义符合条件 1 的所有终极符如下Firstvt R b R b orR Qb 如果对每一个终极符R求出了Firstvt R 则如果存在有产生式P aR 那么对于Firstvt R 中的任意的终极符b都有有a b 如何计算Firstvt R 2020 6 10 25 计算Firstvt 在定义中包括了 由此我们可以想到 这是闭包计算 如果有产生式 R b 或R Qb 则b Firstvt R 如果R T 则对于任意的a Firstvt T 将a加入Firstvt R 2020 6 10 26 计算a b 定义Lastvt R 为 a R a或R aQ 存在有产生式 R

10、 a或R aQ 则a Lastvt R 如果R T 则对于任意的a Lastvt T 将a加入Lastvt R 集合 如果有产生式P Rb 则对于Lastvt R 中的每个a 有a b 2020 6 10 27 计算优先关系的例子 设文法G E E T TT T F FF P F PP E id 首先计算Firstvt E Firstvt T 于是有 Firstvt E id Firstvt T id Firstvt F id Firstvt T Firstvt F Firstvt F Firstvt P Firstvt P id 同样地可得到 Lastvt E id Lastvt T id

11、Lastvt F id Lastvt P id 2020 6 10 28 于是我们可得到所有非终极符的优先级 例如 对E E T和Lastvt E 有 id 运算符的优先级 2020 6 10 29 运算符的优先级 id id 右 左 2020 6 10 30 算符优先分析的算法 栈顶符号输入符号 找到栈中句柄 并用左部替代它 0 用栈来比较优先级 1 初始化栈顶为 2 读入输入符号 比较栈顶符号和输入符号的优先级 当 3 重复步骤2 直到所有的输入符号都已处理且栈中只有开始符号为止 2020 6 10 31 OP分析的例子 给定算术表达式 id id id其自底向上的分析过程如下 有限状态控

12、制 栈 输入带 id id id id Push id id id id id ReducebyE id id E E Push E id id id Push id E id id id ReducebyE id E id E Push E E id id Push id E E id id ReducebyE id id E E ReducebyE E E E E E ReducebyE E E E E Hi thestringisacceptedsuccessfully Doyouseeitsstructureontheright E E E E E E id 2020 6 10 32

13、StackPrecedenceRelationInputStringAction id id id Shift id id id Reduce P id id Shift P id id Shift P id id Reduce P P id Shift P P id Shift P P id Reduce P P P Reduce P T Reduce E Accept 2020 6 10 33 StackInputStringAction id id id Shift id id id ReduceP id P id id ReduceP F F id id ReduceF T T id

14、id ReduceE T E id id Shift E id id Shift E id id ReduceP id id id id的规范规约 2020 6 10 34 E P id ReduceF P E F id ReduceF T E T id Shift E T id Shift E T id ReduceP id E T P ReduceF id E T F ReduceT F E T ReduceE E T E Accept 2020 6 10 35 OPG与规范归约的比较 id id id 的语法树 E P T id P P id id id id id 的分析框架 2020

15、 6 10 36 在算符优先文法中 由于优先关系仅定义于VT符中 所以当句柄仅由一个VN符构成时 无法通过优先关系识别出 在扫描句型时 利用两个VT符之间的关系 我们总能找出一个被归约的子串 不一定是句柄 称为最左素短语 由于被归约的子串 最左素短语 不一定是句柄 甚至不一定是产生式的右部 因此 归约时可能无完全一致的产生式可用 解决的办法 在P中找形为A UjajUj 1aj 1 UiaiUi 1的产生式 其中 Ui与Ni不一定相同 但每个ai必须相同 若存在这样的产生式 则用其归约 否则分析报错 2020 6 10 37 素短语 PrimePhrase 实际上 OPG中归约的不是句柄 因为

16、它忽略了A B这样的推导 例如 右边语法树的归约为 id P P P T其中 P P 是短语但不是句柄 我们称其为素短语 一个素短语是包含至少一个终极符 并且如自身外不再包含其它素短语的短语 2020 6 10 38 素短语 算符优先分析的句型具有形式w N1a1N2a2 NnanNn 1 其中 ai VT Ni VN 素短语 1 是一个短语 2 它至少含有一个VT符 3 满足 1 2 的最小短语 寻找最左素短语的方法 从左到右扫描w 找到第一个ai ai 1时 记下ai 再回扫 找到第一个aj 1 aj 此时 NjajNj 1aj 1 NiaiNi 1就是应被子归约的最左素短语 2020 6 10 39 素短语的例子 在右图中 有多少个素短语 有两个素短语 T Fid其中 T F 是最左素短语 2020 6 10 40 有关素短语更多说明 引入形如是为了定义终级符的优先级 在得到优先级后 可以将这些产生式删除 实际上 如果事先已经定义了终极符的优先级 则可不需要引入形如A B的产生式 2020 6 10 41 算符优先函数 是否可以将优先级的比较变为数的比较 由此引入了优先函数 20