第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 ⾃底向上优先分析法概述优先分析法⼜可分简单优先法和算符优先分析法。l 简单优先分析法的基本思想是对⼀个⽂法按⼀定原则求出该⽂法所有符号（即终结符和⾮终结符）之间的优先关系，按照这种关系确定归约过程中的句柄，它的归约过程实际上是⼀种规范规约。l 算符优先分析法的基本思想则是只规定算符之间的优先关系，即只考虑终结符之间的优先关系，由于算符优先分析不考虑⾮终结符之间的优先关系，在归约过程中只要找到句柄就归约，并不考虑归约到那个⾮终结符名，因⽽算符优先归约不是规范归约。
编译原理教程第五版课后答案
第一章：引言
问题1
答：编译器是一种将高级编程语言源代码转换为目标机器代码的软件工具。它由多个阶段组成，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成等。
问题2
答：编译器的主要任务包括以下几个方面： - 词法分析：将源代码划分为词法单元，如标识符、关键字、操作符等。 - 语法分析：根据语法规则，将词法单元组成语法树。 - 语义分析：对语法树进行语义检查，如类型匹配、变量声明等。 - 中间代码生成：将语法树转换为中间代码表示形式。 - 代码优化：对中间代码进行优化，以提高程序的效率。 - 代码生成：将优化后的中间代码转换为目标机器代码。
第二章：词法分析
问题1
答：词法单元是编译器在词法分析阶段识别的最小的语法单位，它由一个或多个字符组成。常见的词法单元包括关键字、标识符、常量和运算符等。
问题2
答：识别词法单元的方法包括以下几种： - 正则表达式：通过正则表达式匹配字符串，识别出各类词法单元。 - 有限自动机：构建有限状态自动机，根据输入字符的不同状态转移，最终确定词法单元。 - 递归下降法：使用递归下降的方式，根据语法规则划分出词法单元。
第三章：语法分析
问题1
答：语法分析是编译器的一个重要阶段，它的主要任务是根据给定的语法规则，将词法单元序列转换为语法树。语法分析有两个主要的方法：自顶向下的分析和自底向上的分析。 问题2
答：自顶向下的分析是从文法的起始符号开始，根据语法规则逐步向下展开，直到生成最终的语法树。常见的自顶向下的分析方法包括LL(1)分析和递归下降分析。
问题3
答：自底向上的分析是从输入串开始，逐步合并词法单元，最终生成语法树。常见的自底向上的分析方法包括LR分析和LALR分析。
第四章：语义分析
问题1
答：语义分析的主要任务是对语法树进行语义检查和类型推断。语义分析阶段会检查变量的声明和使用是否合法，以及类型是否匹配等。
简单优先和算符优先分析方法
简单优先分析（Simple Precedence Parsing）和算符优先分析（Operator Precedence Parsing）是两种常用的自底向上的语法分析方法。它们是基于符号优先级的理念，通过比较符号之间的优先级关系，来进行语法分析。
1.简单优先分析
简单优先分析是一种自底向上的语法分析方法，它利用一个优先级表来确定符号之间的优先关系。简单优先分析的算法如下：
（1）将输入串和符号栈初始化为空。
（2）从输入串中读入第一个输入符号a。
（3）将a与栈顶的符号进行比较：
a.如果a的优先级大于栈顶符号的优先级，将a推入符号栈，并读入下一个输入符号。
b.如果a的优先级小于栈顶符号的优先级，将栈中的符号做规约操作，直到栈顶的符号优先级不小于a。然后，将a推入符号栈。
c.如果a和栈顶符号优先级相等，栈顶的符号出栈，并将a推入符号栈。
（4）重复步骤（3）直到输入串为空。
（5）如果符号栈中只有一个符号且为文法的开始符号，则分析成功。
简单优先分析的优先级表一般由语法规则和符号之间的优先关系组成。我们可以通过构造优先级关系表来实现简单优先分析。 2.算符优先分析
算符优先分析是一种自底向上的语法分析方法，它也是基于符号优先级的理念，但是相对于简单优先分析，算符优先分析更加灵活，并且允许处理左递归的文法。算符优先分析的算法如下：
（1）将输入串和符号栈初始化为空。
（2）从输入串中读入第一个输入符号a。
（3）将a与栈顶的符号进行比较：
a.如果a的优先级大于栈顶符号的优先级，将a推入符号栈，并读入下一个输入符号。
b.如果a的优先级小于栈顶符号的优先级，将栈中的符号做规约操作，直到栈顶的符号优先级不小于a。然后，将a推入符号栈。
c.如果a和栈顶符号优先级相等，根据符号栈中符号的类型执行相应的操作（如归约、移进等）。
（4）重复步骤（3）直到输入串为空。
（5）如果符号栈中只有一个符号且为文法的开始符号，则分析成功。
1、给出算符优先文法的定义，算符优先表是否都存在对应的优先函数？给出优先函数的定义。
设有一不含ε产生式的算符文法G，如果对任意两个终结符对a，b之间至
多只有、和h三种关系的一种成立，则称G一个算符优先文法。
算符优先关系表不一定存在对应的优先函数
优先函数为文法字汇表中
2、考虑文法G[T]：
T→T*F|F
F→F↑P|P
P→（T）|i 证明T*P↑（T*F）是该文法的一个句型，并指出直接短语和句柄。
首先构造T*P↑（T*F）的语法树如图所示。
句型T*P↑（T*F）的语法树
由图可知，T*P↑（T*F）是文法G[T]的一个句型。
直接短语有两个，即P和T*F；句柄为P。3、文法G[S]为：
S→SdT | TT→T
G→(S) | a
试给出句型(SdG)
句型(SdG)
短语：(SdG)
简单(直接)短语：G 、a
句柄：G 最左素短语：SdG
4、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？
三种形式：可立刻执行的机器语言代码；汇编语言程序；待装配的机器语言代码
模块
考虑的问题包括：
每一个语法成分的语义；
目标代码中需要哪些信息，怎样截取这些信息。
5、符号表的作用是什么？符号表的查找的整理技术有哪几种?作用：登记源程序中出现的各种名字及其信息，以及编译各阶段的进展状况。主要技术：线性表，对折查找与二叉树，杂凑技术。
1、实现高级语言程序的途径有哪几种？它们之间的区别？
计算机执行用于高级语言编写的程序主要有两种途径：解释和编译。
在解释方式下，翻译程序并不对高级语言进行彻底的翻译，而是读入一条语句，
就解释其含义并执行，然后再读入下一条语句，再执行。
在编译方式下，翻译程序先对高级语言进行彻底的翻译并生成目标代码，然后再
对目标代码进行优化，即对源程序的处理是先翻译后执行。
从速度上看，编译方式下，源程序的执行比解释方式下快，但在解释方式下，有利于程序的调试。
2、文法G[S]为：
S->Ac|aB
A->ab
B->bc 该文法是否为二义的？为什么？
