《编译原理》复习题
82．在自上而下的语法分析中，应从（ C ）开始分析。
A．句型 B．句子 C．文法开始符号 D．句柄
83．赋值语句X:=-(a+b)/(c-d)-(a+b*c)的逆波兰表示是（ C ） E. Xab+cd-/-bc*a+-:= F. Xab+/cd-bc*a+--:= G. Xab+-cd-/ a bc* +-:= H. Xab+cd-/abc* +--:= 84．编译程序不能检查、处理的错误是程序中的_______B_________。
A．静态语义检查 B．动态语义检查 C．语法错误 D．词法错误
85．在LR（0）的ACTION子表中，如果某一行中有标记为“rj”的栏，则_______C__________。A．该行既有rj又有Sj B．其它行也有rj C．该行一定填满rj D．该行未填满rj
86．同正规式（a|b）+等价的正规式是_________B________________。
A．（a|b）* B．（a|b）（a|b）* C．（ab）*（ab） D．（a|b）|（a|b）* 87.在规范归约中，用______B______来刻画可归约串。
A．直接短语 B．句柄 C．素短语 D．短语 88．若a为终结符，则A→α·aβ为_______B______项目。 A．归约 B．移进 C．接受 D．待约 89．一个文法G，若________C____________，则称它是LL（1）文法。 A．G中不含左递归 B．G无二义性 C．G的LL（1）分析表中不含多重定义的条目 D．G中产生式不含左公因子 90．LR分析器的核心部分是一张分析表，该表由_______D___________组成。
A．ACTION表 B．GOTO表 C．预测分析表 D．ACTION表和GOTO表 91．构造编译程序应该掌握_______D__________。
A．源程序 B．目标语言 C．编译方法 D．以上三项都是 92．在递归子程序方法中，若文法存在左递归，则会使分析过程产生___D__________。 A．回溯 B．非法调用 C．有限次调用 D．无限循环 93．最左简单子树的叶结点，自左至右排列组成句型的________C____________。 A．短语 B．句型 C．句柄 D．间接短语
94．如果一个正规式所代表的集合是无穷的，则它必含有的运算是__________C___________。 A．连接运算“· ” B．或运算“|” C．闭包运算“* ” D．括号“（”和“）” 95．同正规式a*b*等价的文法是________C___________。
A．G1：S→aS|bS|ε B．G2：S→aSb|ε C．G3：S→ aS|Sb|ε D．G4： S→ abS|ε
9
《编译原理》复习题
96．由文法的开始符号出发经过若干步（包括0步）推导产生的文法符号序列称为______B________。 A．语言 B．句型 C．句子 D．句柄
97．四元式之间的联系是通过 _______B____________实现的。 A．指示器 B．临时变量 C．符号表 D．程序变量 98．编译程序的语法分析器必须输出的信息是________A____________。
A．语法错误信息 B．语法规则信息 C．语法分析过程 D．语句序列
99．LL（1）分析法中“1”的含义是在输入串中查看一个输入符号，其目的是_______C___________。 A．确定最左推导 B．确定句柄 C．确定使用哪一个产生式进行展开 D．确定是否推导 100．称正规式R1和R2 等价是指__________C_______________。 A．R1和R2都是定义在同一个字母表上的正规式 B．R1和R2使用的运算符相同 C．R1和R2代表同一个正规集 D．R1和R2代表不同的正规集
二、填空题 概述部分：
1．编译程序的开发常常采用自编译、 交叉编译 、 自展 和移植等技术实现。 2．解释程序和编译程序的区别在于 是否生成目标程序 。
3．如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为3个阶段： 编译阶段 、 汇编阶段 和 运行阶段 。
4．编译程序工作过程中，第一阶段输入是 源程序 ，最后阶段的输出为 目标程序 。
5．编译过程通常可分为5个阶段 词法分析阶段 、 语法分析阶段 、 语义分析和中间代码生成阶段 、优化阶段和目标代码生成阶段。
6．如果编译阶段生成的目标程序是某特定计算机系统的机器代码程序，则源程序的执行分为两大阶段： 编译阶段 和 运行阶段 。
7．对编译程序而言，输入数据是 源程序 ，输出结果是 目标程序 。
10
《编译原理》复习题
8．贯穿于编译程始终的工作有 符号表处理 和出错处理。
词法分析部分：
1．词法分析的工作是将源程序中的 字符串 变换成 单词符号流 的过程，所遵循的是语言的 构词规则 。
2．若两个正规式所表示的 正规集 相同，则认为二者是等价的。 3．若两个正规式所表示的正规集相同，则认为二者是 等价 的。
4．正规式R1和R2等价是指_______表示相同的正规集 。
5．词法分析器的输入是源程序字符串，输出结构是 二元式（单词种别， 单词自身的值） 。词法分析所遵循的是语言的 构词 规则。
6．确定的有限自动机是一个五元组，包含的五个元分别是：状态集合、 字母表、初态、终态集、状态转换函数集合 。
7．有限自动机是更一般化的状态转换图，它分为 确定的有限自动机DFA 和 非确定的有限自动机NFA 两种。
8．NFA和DFA的区别主要有两点：其一是 NFA可以有若干个初始状态，而DFA仅有一个初始状态 ；其二是 NFA的状态转换函数f不是单值函数，而是一个多值函数 。 语法分析部分：（基本概念、LL（1）、LR（0）、SLR（1）、递归下降子程序） 1． 语法分析的方法通常分为两类： 自上而下分析方法 和 自下而上分析方法 。 2．文法中的终结符集和非终结符集的交集是 空集 。
3．一个句型的最左直接短语称为该句型的___句柄________________。 4．规范归约是 最右推导 的逆过程。
5．自下而上语法分析中分析器的动作有_移进 、____归约 、__接受_ 、__报错 __。 6．自上而下语法分析中分析器的动作有___匹配终结符____、__展开非终结符_、__分析成功、报错__。 7．常用的自上而下语法分析方法有递归下降子程序方法和预测分析表方法（LL（1）方法）。 8．常用的自下而上语法分析方法有算符优先分析法和LR分析法。
11
《编译原理》复习题
9．一个LL(1)分析器由 一张LL(1)分析表（预测分析表） 、 一个先进后出分析栈 和一个 控制程序（表驱动程序）组成。
10．一个LR分析器由 分析栈 、 分析表 和总控程序三个部分组成。
11．LR(0)分析法的名字中，“L”表示 自左至右分析输入串 ，“R”表示 采用最右推导的逆过程即最左归约 。“0”表示 向右查看0个字符 。
12．LL(1)分析法中，第一个L的含义是 从左到右扫描输入串 ；第二个L的含义是 分析过程中采用最左推导 ；“1”的含义是 只需向右查看一个符号就可以决定如何推导 。
13．LR(1)文法的含义是：L表明_____自左至右扫描输入串__，R表明___采用最右推导的逆过程（最左归约）方法进行分析__。
14．一个上下文无关文法是LL(1)文法的充分必要条件是：对每一个非终结符A的任何两个不同产生式A→α|β，有下面的条件成立：（1） FIRST(α)∩FIRST(β) = ? ；（2）假若???，则有 FIRST(α) ∩ FOLLOW(A) = ? 。
15．对于LL（1）文法中的任何产生式A→α|β，则需要满足__First(_α)∩First(β)= Φ 、 _若_β=>*ε,则_ First(_α) ∩__Follow(A)=_ Φ_。
16．LR分析器的核心部分是一张分析表，该表包括 动作（ACTION）表 和 状态转换（GOTO）表 等两个子表。
17．关于非终结符A的直接左递归产生式：A→Aα|β，其中α、β是任意的符号串且β不以A开头，则可以将A的产生式改写为右递归的形式为： A→βA’ , A’→αA’|ε 。
18．在消除回溯，提取公共左因子时，关于A的产生式A → δβ1 | δβ2 | … | δβi | βi+1 | …| βj，可以改写为： A → δA’ | βi+1 | …| βj ， A’ →β1 | … |βi 。
19．设G[S] 是一文法，如果符号串x是从识别符号推导出来的，即有S?x，则称x是文法G[S]的____
*S?x,x?VT句型__，若x仅由终结符号组成，即，则称x为文法G[S]的__句子 。
**20．已知文法G[S]:
S→eT|RT T→DR|ε R→dR|ε D→a|bd
求FIRST(S)={e，d，a，b，ε}______；FOLLOW(D)=_{d，#} 。
12