[第四章.自下而上语法分析.ppt

第四章（2） 自下而上语法分析方法 本章要求 主要内容：自下而上语法分析的概念，规范归约，算符优先分析方法及其相关概念。 重点掌握：掌握自下而上分析的基本思想，基本概念，算符优先文法、算符优先关系的判定，最左素短语、句柄、活前缀的定义与判定，求First VT集,Last VT集,构造算符优先关系表,能用算符优先分析法进行表达式分析 例：判定输入串(i+i)*i是否是下述文法的句子？ G = ({E}, {i, +, *, (, ) } , P , E) P： E ? E + E E ? E * E E ? ( E ) E ? i 自下而上的语法分析 实现思想：“移进-归约”方法 设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时，就用左部去代替，称为归约。重复这一过程，直到栈中只剩下文法的开始符号，就确认输入串是文法的句子，分析成功，否则出错。 语法树：从树叶开始，逐步向上归约构造分析树，直到形成根结。是推导的逆过程。 核心 寻找句柄(这是关键) 进行规约。用不同的方法寻找句柄，就可获得不同的分析方法。 最左推导(Left-most Derive) 每次推导都替换当前句型的最左边的非终结符。——与最右归约对应 最右推导(Right-most Derive) 每次推导都替换当前句型的最右边的非终结符。——与最左归约(规范归约)对应，得规范句型 这种分析过程具有如下特点： 从输入串的开始依次读入单词(移进栈中) 。 一旦发现可归约串(某个产生式的右端)就立即归约。 归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进。 若最终能归约成文法的开始符号，则分析成功。 由于总是将句型的最左边的可归约串替换成非终结符，该方法与最右推导对应。 关键是如何判断可归约串？ 语法分析树的生成演示 a b b c d e 规范归约的概念 有文法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 * F + i的短语、直接短语、句柄 给定右边的文法，用句柄对符号串abbcde进行归约 用句柄对句子进行归约的过程与用移进-归约过程是一致的，使用归约的产生式及其顺序是一致的。 规范归约的定义： 假定α是文法G的一个句子，如果序列： αn, αn-1, ……,α0 (=S)满足如下条件，则序列αn, αn-1, ……, α0是一个规范归约: (1) αn =α 是给定的句子 (2) α0 =S 是文法的开始符号 (3) 对任何i, 0i?n，αi-1是从αi经把句柄替换为相应文法产生式的左部符号而得到的。 规范归约是最右推导的逆过程，规范归约又称为最左归约。 最右推导又称规范推导，由规范推导所得到的句型称规范句型，规范推导的逆过程是规范归约。 上述例子中句子abbcde的规范归约过程是： abbcde， aAbcde， aAcde， aAcBe，S 练 习 使用下述文法对句型i1*i2+i3进行规范规约: 使用修剪语法树的方法来进行归约： 规范归约分析中栈的使用 1、句型表示 动作 栈 输入缓冲区 1) 准备 # id1+id2*id3# 2) 移进 #id1 +id2*id3# 3) 归约 F→id #F +id2*id3# 4) 归约 T→F #T +id2*id3# 5) 归约 E→T #E +id2*id3# 6) 移进 #E+ id2*id3# 7) 移进 #E+id2 *id3# 8) 归约 F→id #E+F *id3# 9) 归约 T→F #E+T *id3# 10) 移进 #E+T* id3# 11) 移进