[计算机软件及应用]自下而上语法分析.ppt

自下而上语法分析 掌握自底相上分析的基本思想，基本概念 掌握算符优先关系的判定，求FIRSTVT集,LASTVT集,构造算符优先关系表，能运用算符优先分析方法进行表达式分析 掌握最左素短语、句柄的定义与判定 理解规范规约与算符优先归约的区别 LR(0)和SLR文法的理解 自下而上的语法分析 实现思想 从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功， 称为“移进-归约”方法。 从语法树的角度看：从语法树的树叶开始，逐步向上归约构造分析树，直到形成根结。是推导的逆过程。 核心 寻找可归约串(这是关键)进行规约。用不同的方法寻找可归约串，就可获得不同的分析方法。 最左推导(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-β的直接短语 位于一个句型最左边的直接短语称为句柄。 例子 下面的例子说明作为短语的两个条件缺一不可。 [例]考虑表达式文法： E ? T|E+T T ?F|T*F F ?i | (E) 对于句型i*i+i 推导 E ? E+T ? E+F ? E+i ? T+i ? T*F+T ? T*i+i ? F*i+i ? i*i+i 尽管有E ?+i+i 但是, i+i 并不是该句型的一个短语，因为不存在从E(文法开始符）到i*E的推导。 句型的短语和句柄举例 文法：S→ (T)|ε T→S|T,S|a 短语： 句型((a),S) S =* (T,S) T =+ (a) 句型((T,S),S) S =* ((T),S) T =+ T,S 句型(a,(T),(T,S))直接短语以及句柄： S =* (T,(T),(T,S)) T = a S =* (a,S,(T,S)) S =(T) S =* (a,(T),(T)) T =T,S 短语与语法树的关系 短语：语法树子树的叶子结点组成的符号串。 直接短语：语法树简单子树（只有父子两代）的叶子结点组成的符号串。 句柄：语法树最左边简单子树的叶子结点组成的符号串。 短语与语法树关系的例子 句型(a,(T),(T,S))的语法树： 用句柄对句子abbcde进行归约 用句柄对句子进行归约的过程与用移进-归约过程是一致的，使用归约的产生式及其顺序是一致的。 规范归约的定义 假定α是文法G的一个句子，如果序列： αn, αn-1, ……, α0 (=S)满足如下条件，则序列 αn, αn-1, ……, α0是一个规范归约: (1) αn =α 是给定的句子 (2) α0 =S 是文法的开始符号 (3) 对任何i, 0i?n，αi-1是从αi经把句柄替换为相应文法产生式的左部符号而得到的。 规范归约是最右推导的逆过程，规范归约又称为最左归约。 最右推导又称规范推导，由规范推导所得到的句型称规范句型，规范推导的逆过程是规范归约。 使用修剪语法树的方法来进行归约： 分析器的四种动作 移进：将下一输入符号移入栈 归约：当栈顶出现句柄，用产生式左侧的非终结符替换栈顶的句柄 接受：分析成功，是归约的一种特殊情况 出错：栈顶的内容与输入符号相悖，进行出错处理 分析成功的条件：栈顶为文法符号，输入串为空。注意，该过程并未涉及如何在栈里找可归约串。实际上，不同的找可归约串的方法，构成了不同的分析算法。 “移进-归约”分析法用栈实现的特点： 可归约串必定位于栈顶，即可归约串之后就是剩余的输入串。 栈内符号串与剩余输入串正好构成一个句型。 动作 栈 输入缓