第6章 自底向上优先分析法

《编译原理》课程教学大纲课程编号：（先不填）英文名称：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 自底向上优先分析法概述•基本思想：利用文法符号中相邻符号之间的优先关系（谁先规约的优先关系）找出句柄。

STACK REMAINING INPUT
1
(int + int)#
2(
int + int)#
3 (int
+ int)#
4 (T
+ int)#
5 (E
+ int)#
6 (E +
int)#
7 (E + int
)#
8 (E + T
)#
9 (E
)#
10 (E)
#
11 T
#
12 E
#
13 S
#
PARSER ACTION Shift Shift Reduce: T –> int Reduce: E –> T Shift Shift Reduce: T –> int Reduce: E –> E + T Shift Reduce: T –> (E) Reduce: E –> T Reduce: S –> E
的左部而得到的
文法要求
shift-reduce or reduce-reduce 冲突（conflicts）
分析程序不能决定是shift 还是 reduce 或者分析程序归约时有多个产生式可选
例子 (dangling else) ： S –> if E then S | if E then S else S
LR分析算法
then begin pop || 项 令当前栈顶状态为S’ push GOTO[S’, A]和A(进栈)
end else if ACTION[s,a]=acc
then return (成功） else error end

一、自下而上语法分析的基本问题 1.归约: 如何判断栈顶符号的可归约性以及如何归约，是 自下而上分析的中心问题。 2.短语和句柄
如果Ｓ ⇒ αＡβ and A ⇒γ，则称γ是句型 αγβ的相对于变量A的短语 * 如果Ｓ ⇒αＡβ and A⇒γ，则称γ是句型 αγβ的相对于变量A的直接（简单）短语 最左直接短语叫做句柄
e
abbcde
一、自下而上语法分析的基本问题 (3)自下而上分析的关键问题
似乎移进-归约过程很简单,其实不然,在上面第5步,如果用 规则2(P → b)进行归约而不是用规则3(P → Pb)进行归约,结果 会怎么样呢？ 上面的归约过程是从文法的句子abbcde开始，每一步都是把最 左直接短语（句柄）替换为相应产生式的左部符号（在步骤5时 栈顶为#aPb，此时是将b归约为P还是将Pb归约为P？由于此时对 于句型aPbcde（即栈内容+输入缓冲区内容）来说Pb是句柄，故 将Pb归约为P）。也就是说，自底向上分析的关键问题是在分析 中如何确定句柄（准确地说为可归约串），即如果知道何时在 栈顶符号串中已形成了某句型的句柄，那么就可以确定何时进 行归约。对此，不同的分析方法有不同的解决办法。这里主要 介绍算符优先及LR分析方法。
例： 移进—归约分析（Shift-reduce parsing)
要点：建立符号栈，用来纪录分析的历史和现状， 并根据所面临的状态，确定下一步动作是移 进还是归约。
输入串 # 符号栈 #
S.R.P
输入串 # 符号栈 #
S.R.P
分析过程：把输入符号串按自左向右顺序一一地 移进符号栈（一次移一个），检查栈中符号，当在栈 顶的若干符号形成当前句型的句柄时，就根据规则进 行归约，将句柄从符号栈中弹出，并将相应的非终结 符号压入栈内（即规则的左部符号），然后再检查栈 内符号串是否形成新的句柄，若有就再进行归约，否 则移进符号。分析一直进行到读到输入串的右界符为 止。最后，若栈中仅含有左界符号和识别符号，则表 示分析成功，否则失败