自下而上语法分析习题（完整版）.ppt

自下而上语法分析方法习题课 第五章 本章要求 1.掌握自下而上分析的基本思想，基本概念 2.掌握算符优先文法、算符优先关系的判定 3.掌握最左素短语、句柄的定义与判定 4.掌握求FirstVT集,LastVT集,学会构造算符优先关系表,能用算符优先分析法进行表达式分析 问题的提出： ① 在构造语法树的过程中，何时归约？ 当可归约串出现在栈顶时就进行归约。 ② 如何知道在栈顶符号串中已经形成可归约串？ 如何进行归约？ 通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。 规范归约：使用句柄来定义可归约串。 算符优先：使用最左素短语来定义可归约串 规范归约的概念 有文法G，开始符号为S, 如果有S=xβy,则xβy是文法G的句型，x,y是任意的符号串 如果有S=xAy, 且有A=β,则β是句型xβy相对于非终结符A的短语 如果有S=xAy, 且有A-β,则β是句型xβy相对于A-β的直接短语 位于一个句型最左边的直接短语称为句柄. * * + * 注意: 每次归约的部分必须是句柄 (最右推导)。 关键的问题是如何识别句柄 例：考虑如下文法： 求句型 i1 * i2 + i3 的短语、直接短语和句柄。 E?T | E+T T?F | T*F F?i | (E) 从语法分析树来识别： 一棵子树是由树的某个结点连同它的所有子孙组成的。 子树的所有端末结点自左至右排列成一个相对子树根的短语。 直接短语：只有父子两代结点形成的短语。 句柄：最左子树的直接短语。 E E + T T F i3 i2 i1 T * F F 从语法树可以看出： i1, i2, i3, i1*i2, i1*i2+i3是句型i1*i2+i3的短语 直接短语有：i1, i2 , i3 句柄是： i1 E?T | E+T T?F | T*F F?i | (E) 句型i1*i2+i3的语法树如图： 练习 1、令文法G1为： E→E+T | T T→T*F | F F→(E) | i 证明E+T*F是它的一个句型，指出这个句型的所有 短语、直接短语和句柄。 E E + T T * F T*F是句型E+T*F相对于T的短语 E+T*F句型E+T*F相对于E的短语 T*F是句型E+T*F相对于T的直接短语 T*F是句柄 2 对下述文法，求句型 E+T * F + i的短语、直接短语、句柄 E?T | E+T T?F | T*F F?i | (E) E E + T F i E + T T * F 短语有：i, T * F, E+T * F, E + T * F + i 直接短语有： i, T * F 句柄是：T * F 练 习 规范归约的定义： 假定α是文法G的一个句子，如果序列： αn, αn-1, ……,α0 (=S)满足如下条件，则序列αn, αn-1, ……, α0是一个规范归约: (1) αn =α 是给定的句子 (2) α0 =S 是文法的开始符号 (3) 对任何i, 0i?n，αi-1是从αi经把句柄替换为相应文法产生式的左部符号而得到的。 规范归约是最右推导的逆过程，规范归约又称为最左归约。 最右推导又称规范推导，由规范推导所得到的句型称规范句型，规范推导的逆过程是规范归约。 句型 归约规则 abbcde (2) A?b aAbcde (3) A ? Ab aAcde (4) B ? d aAcBe (1) S ? aAcBe S (1)S ? aAcBe(2)A ? b (3)A ? Ab(4)B ? d 上述例子中句子abbcde的规范归约过程是： abbcde， aAbcde， aAcde， aAcBe，S 练 习 使用下述文法对句型i1*i2+i3进行规范规约: E?T | E+T T?F | T*F F?i | (E) i1*i2+i3 , F*i2+i3 , T*i2+i3, T*F+i3 , T + i3 , E+i3 , E + F, E + T , E E E + T T F i3 i2 i1 T * F F 2、考虑下面的表格结构文法G2： S→a | ^ | (T) T →T,