自底向上优先分析法

226 •电子技术与软件工程 Electronic Technology & Software Engineering程序设计• Program Design【关键词】语法单位 自底向上 OPG 终结符优先 优化语法分析方法中自上而下的分析是指从文法的开始符号出发，反复的选择产生式进行推导，最终推导出句型；自下而上分析是指从待分析的句型本身出发，逐步选择产生式进行归约，直至归约到文法的开始符号。

这两类分析都可以利用各种语法分析算法进行。

每种语法分析算法都有其优势和局限性，根据文法的类型，可以选择最优的语法分析算法进行语法分析。

1 OPG文法Chomsky 将文法分为短语文法、上下文有关文法、上下文无关文法和正规文法四类。

OPG 文法是上下文有关文法中的一种，该文法的特殊性在于任意两个终结符之间最多只存在<、=、>三种优先关系中的一种优先关系，文法的产生式中不会出现两个相邻的非终结符。

根据文法的特性可以推论该文法的任何句型也不会含有相邻的非终结符，这就为使用优化的OP 分析法进行句型分析奠定了基础。

2 规范归约归约与推导是一个逆过程，规范归约过程中一直本着最左的归约原则，每次分析过程中首先找到句型中的句柄，句柄是句型中的最左直接短语，之后根据产生式规则向左归约，用产生式的左部去替换产生式右部。

例如对OPG 文法G[E]：E →T|E+T T →F|T*F F →i|(E)的句型T+T*F+i 的分析如表1所示。

上述句型分析中每步都是在句型中寻找OPG 文法的语法分析优化策略文/关玉欣最左直接短语，也就是文法中某条产生式的右部。

进行最左归约实质上就是用某条产生式的左部非终结符去替换产生式的右部符号串。

根据句型的不同，归约的步骤也会有区别，但分析成功的标志就是归约到OPG 文法的开始符号，代表句型分析成功。

在上述的规范归约过程中，句型T+T*F+i 总归约次数为6。

3 优化的OP分析在自底向上的句型分析方法中，OP （Operator Priority ）分析法仅考虑句型中终结符的优先关系，从而确定每一步分析过程中的句柄。

《编译原理》课程教学大纲课程编号：（先不填）英文名称：Compiler Construction Principles课程类型：专业基础课学时/学分：40+16/3.5授课对象：本科生先修课程：高等数学，数据结构，C程序设计课程简介：本课程是计算机专业学生的一门重要专业基础课,本课程属于计算机科学与技术专业的一门重要的专业必修课。

通过本课程学习，使学生掌握编译程序的一般构造原理，包括语言基础知识、词法分析程序设计原理和构造方法。

各种语法分析技术和中间代码生成符号表的构造、代码优化、并行编译技术常识及运行时存储空间的组织等基本方法和主要实现技术。

它有一定的理论性,又有一定的实践性, 尤其是本课程的知识与计算机应用中很多领域有紧密联系与广泛应用。

了解与掌握本课程的基本内容将有利于学生提高专业素质和适应社会多方面需要的能力。

教学目的和要求：教学目的：培养学生掌握构造编译程序的基本原理与设计方法，为培养计算机语言与大型应用程序的开发人才打下良好的基础。

本课程坚持理论与实践教学并重的原则，理论上主要叙述语言和文法的形式定义、自动机理论、词法分析、语法和语义分析、优化和代码生成等环节的基本理论和方法，与此同时，通过上机实习构造简单语言的编译程序等编辑器使学生掌握开发应用程序的基本方法。

教学要求：通过本课程的学习, 学生应掌握形式语言理论与编译实现相关的基础概念, 了解与掌握编译程序构造的基本原理与技术, 从形式语言理论的角度, 进一步认识与理解程序设计语言及其与编译程序的联系。

做习题是理解课程中基本概念、培养思考能力和解题能力的重要方面, 要求学生认真做好习题, 并注意解题规范化。

学生也应重视配合教学, 做好上机实习。

教学内容：第1章编译程序概述（2学时）1、教学内容：1)什么是编译程序2)编译过程概述3)编译程序的结构4)编译阶段的组合5)编译技术和软件工具2、教学重点：编译程序的结构3、教学难点：编译程序的结构，以及每一阶段任务第3章文法与语言（6学时）1)文法的直观概念2)符号和符号串3)文法与语言的形式定义4)文法的分类5)上下文无关文法及其语法树6)句型的分析7)有关文法实用中的一些说明2、教学重点：与编译技术密切相关的一些术语和概念。

第六章自底向上优先分析方法•教学要求：了解简单优先分折法，掌握算符优先分析法的关系表的构造以及分析过程。

•教学重点：算符优先表构造及算符优先分析法。

1自底向上分析法的基本思想•从输入串开始，朝着文法的开始符号进行最左归约，直到到达文法的开始符号为止。

•工作方式：“移进－归约”方式。

2分析程序模型1）初态时栈内仅有栈底符“＃”，读头指针在最左单词符号上。

2）语法分析程序执行的动作：a）移进读入一个单词并压入栈内，读头后移；b）归约检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号；c）识别成功移进－归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符；d）识别失败语法分析程序语法表a+b……#输出带#3例如：有文法如下（1）S→aAcBe（2）A→b（3）A→Ab（4）B→d问：语句abbcde是不是该文法的合法语句？4•例：设文法G(S)：(1) S aAcBe(2) A b(3) A Ab(4) B d 试对abbcde进行“移进－归约”分析。

bbcde bbcde b cde de deabbcde eB cA a SB A a 5成功11接受2,3,4,1＃＃S 10归约＃＃aAcBe 9移进2,3,4e ＃＃aAcB 8归约e ＃＃aAc d 7移进de ＃＃aAc 6移进2,3cde ＃＃aA 5归约cde ＃＃a Ab 4移进2bcde ＃＃aA 3归约bcde ＃＃a b 2移进bbcde ＃＃a 1移进abbcde ＃＃0动作输出带输入串栈步骤移进归约的分析过程G[S]:（1）S →aAcBe（2）A →b（3）A →Ab（4）B →d 6遇到的问题：（1）如何找出进行直接归约的简单短语？（2）找出的简单短语应直接归约到哪一个非终结符？关键：确定句柄.常用的分析方法:（1）优先分析法（2）LR分析法7b db ac eSA B A d b a c e S A B A d a c eSA B a c e A B S 没有语法树如何确定句柄？86.1 自底向上优先分析法概述•基本思想：利用文法符号中相邻符号之间的优先关系（谁先规约的优先关系）找出句柄。

第6章⾃底向上优先分析法⾃底向上分析⽅法，也称移进－归约分析法，粗略地说它的实现思想是对输⼊符号串⾃左向右进⾏扫描，并将输⼊符逐个移⼊⼀个后进先出栈中，边移⼊边分析，⼀旦栈顶符号串形成某个句型的句柄时，（该句柄对应某产⽣式的右部），就⽤该产⽣式的左部⾮终结符代替相应右部的⽂法符号串，这称为归约。

重复这⼀过程直到归约到栈顶中只剩⽂法的开始符号时则为分析成功，也就确认输⼊串是⽂法的句⼦。

本章将在介绍⾃底向上分析思想基础上，着重介绍算符优先分析法。

例6.1，设⽂法G[S]为：（1）S→aAcBe（2）A→b（3）A→Ab（4）B→d对输⼊串abbcde#进⾏分析，检查该符号串是否是G[S]的句⼦。

由于⾃底向上分析的移进－归约过程是⾃顶向下最右推导的逆过程，⽽最右推导为规范推导，⾃左向右的归约过程也称为规范归约。

容易看出对输⼊串abbcde的最右推导为：S aAcBe aAcde aAbcde abbcde由此我们可以构造它的逆过程即归约过程。

先设⼀个后进先出的符号栈，并把句⼦左括号”#”号放⼊栈底。

对上述分析过程也可看成⾃底向上构造语法树的过程，每步归约都是构造⼀棵⼦树，最后当输⼊串结束时刚好构造出整个语法树。

在上述移进－归约或⾃底向上构造语法树的过程中，考虑⼏个问题：u 何时移进？u 何时归约？u 将哪个字符串归约？当⼀个⽂法⽆⼆义性时，那么它对⼀个句⼦的规范推导是唯⼀的，规范规约也必然是唯⼀的。

因⽽每次归约时要找当前句型的句柄，也就是说，任何时候栈中的符号串和剩余的输⼊串组成⼀个句型，当句柄出现在栈顶符号串中时，则可⽤句柄归约，这样⼀直归约到输⼊串只剩结束符，⽂法符号栈中只剩开始符号。

由此可见，⾃底向上分析的关键问题是在分析过程中如何确定句柄，即如何知道何时在栈顶符号串中已形成某句型的句柄。

然⽽⾃底向上的分析算法很多，我们仅在本章和第7章介绍⽬前常⽤的算符优先分析和LR类分析法。

6.1 ⾃底向上优先分析法概述优先分析法⼜可分简单优先法和算符优先分析法。

《编译原理》-⽤例题理解-⾃底向上的语法分析，FIRSTVT，LASTVT集《编译原理》-⽤例题理解-⾃底向上的语法分析，FIRSTVT，LASTVT集上⼀篇：本笔记是对教材《编译原理》- 张晶⽼师版做学习笔记。

本篇就是第 5 章的笔记。

（⼀）⾃底向上的语法分析概述⾃底向上语法分析⾃底向上语法分析从待输⼊的符号串开始，利⽤⽂法的产⽣式步步向上归约，试图归约到⽂法的开始符号。

从语法树的⾓度看⾃底向上分析的过程是以输⼊符号串作为端末结点符号串，向着根结点的⽅向往上构造语法树，是开始符号正好是该语法树的根结点。

⾃底向上语法分析过程实际上是⼀个不断进⾏直接归约的过程移进-规约⼤意：⽤⼀个寄存符号的先进后出栈，把输⼊符号⼀个⼀个地移进到栈⾥，当栈顶符号串形成可归约串时（某个产⽣式的右部时），即把这个可归约串替换成（归约成）该产⽣式的左部的⾮终结符。

⾃底向上语法分析法基本思想⾃左向右地扫描输⼊符号串，⼀遍把输⼊符号逐个移进分析栈，⼀边检查分析栈的栈顶符号串是否已经形成了句柄（句柄就是每个产⽣式的右部），如果形成句柄就把栈顶符号串替换为相应产⽣式左部的⾮终结符号，这种替换就称规约，再根据规约后的新栈顶，继续扫描，移进，规约。

例题：移进-规约题⽬：给定⽂法 G[S]：（1）S -> aABe（2）A -> b（3）A -> Abc（4）B -> d解析：步骤： 1 2 3 4 5 6 7 8 9 10动作：进进归进进归进归进归a b (2) b c (3) d (4) e (1)执⾏时，⾸先分析栈中会存放 # 到栈底，图上没有体现出来，应该在 a 的下⾯加上 #，将余留输⼊串最左边的字符放在分析栈栈⾸，此时栈中为 a，分析上⾯ 4 句⽂法，⽂法的右部没有完全匹配的，所以没有构成句柄。

此时，继续移进第⼆个输⼊符号 b，此时栈顶的 b 与⽂法的（4）产⽣式的右部匹配，⽤ A -> b 规约，得到栈中为 aA然后移进 b，c，⽤⽂法的（3）产⽣式进⾏规约。

第6章自底向上优先分析法概述•自底向上分析法，也称移进-归约分析法，或自下而上分析。

•自底向上分析的移进-归约过程是自顶向下最右推导的逆过程，而最右推导为规范推导，自左向右的归约过程也称规范归约。

例6.1 G[S]：(1) S→aAcBe (2) A→b (3) A→Ab (4) B→d 对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。

容易看出对输入串abbcde的最右推导是：S=>aAcBe=>aAcde => aAbcde => abbcde 。

它的逆过程即归约过程。

基本问题•如何找出进行直接归约的简单短语？•将找到的简单短语归约到哪个非终结符号？基本方法•基本都采用移入-归约方法。

•使用一个栈来存放归约得到的符号。

•在分析的过程中，识别程序不断地移入符号。

移入的符号暂时存放在一个栈中。

一旦在已经移入的（和归约得到的）符号串中包含了一个句柄时，将这个句柄归约成为相应的非终结符号。

基本方法（续）•归约中的动作有4类–移入：读入一个符号并把它归约入栈。

–归约：当栈中的部分形成一个句柄（栈顶的符号序列）时，对句柄进行归约。

–接受：当栈中的符号仅有#和识别符号的时候，输入符号也到达结尾的时候，执行接受动作。

–当识别程序觉察出错误的时候，表明输入符号串不是句子。

进行错误处理。

例 子i *i+ii*i+i i E::=i E *i+iE*i+i E* i+iE*i+i E*i +iE*i+i i E::=i E*E +iE*E+i E*E E::=E*E E +iE+i E+iE+i i E::=i E+EE+E E+E E::=E+EE 文法G E [E]: E::=E+E|E*E|(E)输入符号串：i*i+i已处理 未处理 句型 句柄 规则例子的解释•当栈中的符号的栈顶部分还不能形成句柄时，进行移入操作。

•一旦发现栈顶部分形成了句柄的时候，对该句柄进行归约。

第五章语法分析——自下而上分析要紧内容:[1]自下而上分析的大体问题[2]算符优先分析法[3]算符优先分析表和优先函数的构造[4]LR分析器的大体原理大体要求:[1]明白得自下而上分析法的大体思想[2]明白得有关归约、短语、句柄、标准归约等概念[3]把握算符优先分析法[4]了解算符优先表和优先函数的构造技术[5]了解LR 分析器大体原理和工作方式教学要点：本章介绍自下而上语法分析方式。

所谓自下而上分析法确实是从输入串开始，慢慢进行“归约”，直至归约到文法的开始符号；或说，从语法树的结尾开始，步步向上“归约”，直到根结。

讲义摘要：5.1 自下而上分析大体问题自下而上分析法的大体思想：从输入串开始，慢慢进行“归约”，直到文法的开始符号。

即从树结尾开始，构造语法树。

所谓归约，是指依照文法的产生式规那么，把产生式的右部替换成左部符号。

自上而下分析的核心问题是：如何判定符号串的可归约性，和如何归约。

即，识别可归约串的问题。

归约自下而上分析法事实上确实是一种“移进－归约”法，即，采纳“移进－归约”思想进行。

实现思想是：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，（该句型对应某产生式的右部，即栈顶生成了某产生式的右部的文法符号串），就将栈顶的这一部份替换成 (归约为) 该产生式的左部符号，这称为归约。

重复这一进程直到归约到栈中只剩文法的开始符号时那么为分析成功，也就确认输入串是文法的句子。

现举例说明。

例1：设文法G[S]为：(1) S→aAcBe(2) A→b(3) A→Ab(4) B→d试对abbcde进行“移进－归约”分析。

步骤: 1 2 3 4 5 6 7 8 9 10解：动作: 进a 进b 归(2) 进b 归(3) 进c 进d 归(4) 进e 归(1)表1符合栈的转变进程自下而上语法分析的进程也可看成自底向上构造语法树的进程，每步归约都是构造一棵子树，最后当输入串终止时恰好构造出整个语法树，如图1所示。