编译原理第5章new.ppt

本章内容概要 自下而上分析基本问题 归约 规范归约 算符优先分析 算符优先文法 算符优先分析表的构造 LR分析法 LR分析器 LR文法 LR(0)项目集族和LR(0)分析表的构造 语法分析的方法： 自下而上分析法(Bottom-up) 自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。 递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 预测分析程序 优点：直观、简单和宜于手工实现。 5.1.1 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。 归约 所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 采用“移进－归约”思想进行自下而上分析。 实现思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分（可归约串）替换成(归约为)该产生式的左部符号。 构造语法树 例：设文法G(S)如下，试对abbcde进行“移进－归约”分析。 (1) S ? aAcBe (2) A ? b (3) A ? Ab (4) B ? d 在栈中实现“移进－归约” 文法G(S): (1) S ? aAcBe (2) A ? b (3) A ? Ab (4) B ? d 实现“移进－归约”，符号栈的变迁 移进归约分析中的问题 1) 移进-归约冲突 在分析到某一步时，既可以移进，又可以归约 2) 归约-归约冲突 存在两个可选的句柄，可对栈顶符号进行归约 各种分析方法中处理冲突的技术不同 主要分析方法 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。 LR分析法：规范归约 练习： 设文法G(E)如下，试对i*i+i进行“移进－归约”分析。 G(E)： E ? i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E 5.1.2 规范归约 定义： 有文法G，开始符号为S, 如果有S=xβy,则xβy是文法G的句型，x,y是任意的符号串。 如果有S=xAy, 且有A=β,则β是句型xβy相对于非终结符A的短语 如果有S=xAy, 且有A-β,则β是句型xβy相对于A-β的直接短语 位于一个句型最左边的直接短语称为句柄. 句型--- 短语 --- 直接短语 ---句柄 注: 每次归约的部分必须是称之为句柄的字符串(最右推导)。 关键的问题是如何识别句柄 考虑文法G(E)： E ? T | E+T T ? F | T*F F ? (E) | i 和句型i1*i2+i3： E ? E+T ? E+F ? E+i3 ? T+i3 ? T*F+i3 ? T*i2+i3 ? F*i2+i3 ? i1*i2+i3 短语： i1，i2，i3， i1*i2， i1*i2+i3 直接短语： i1，i2，i3 句柄： i1 在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有叶子结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。 最左边的两代子树的所有叶子结点从左到右排列就是句柄。 练习 ：文法G(E) 的另一个句型： E+T * F + i 其短语、直接短语、句柄分别是？ 可用句柄来对句子进行归约 句型 归约使用规则 abbcde (2) A ? b aAbcde (3) A ? Ab aAcde (4) B ? d aAcBe (1) S ? aAcBe S 定义：假定?是文法G的一个句子，我们称序列 ?n， ?n-1，? ，?0 是?的 一个规范归约，如果此序列满足： 1. ?n= ? 2. ?0为文法的开始符号，即?0=S 3. 对任何i，0 ? i ? n， ?i-1是从?i经把句柄替换成为相应产生式左部符号而得到的。 规范归约的实质 在移进过程中 ，当发现栈顶呈现句柄时就用相应产生式的左部符号进行替换。 5.1.3 符号栈的使用和分析树的表示 栈是语法分析的一种基本数据结构。‘#’作为栈底符号和输入串的