编译原理习题答案
1、正规文法又称 D
A、0型文法
B、1型文法
C、2型文法
D、3型文法
2、对于无二义性的文法，规范归约是 B
A. 最左推导
B. 最右推导的逆过程
C.最左归约的逆过程
D.最右归约的逆过程。
3、扫描器的任务是从源程序中识别出一个个单词符号。
4、程序所需的数据空间在程序运行前就可确定，称为 A 管理技术。
A 静态存储
B 动态存储
C 栈式存储
D 堆式存储
5、编译过程中，语法分析器的任务是（B）。
①分析单词是怎样构成的
②分析单词串是如何构成语句和说明的
③分析语句和说明是如何构成程序的
④分析程序的结构
A、②③
B、②③④
C、①②③
D、①②③④
6、文法G：E→E+T|T T→T*P|P P→ (E)| i
则句型P+T+i的句柄和最左素短语分别为 B 。
A、P+T和i
B、P和P+T
C、i和P+T+i
D、P和P
7、四元式之间的联系是通过B实现的
A.指示器
B.临时变量
C.符号表
D.程序变量
8、程序语言的单词符号一般可以分为保留字、标识符、常数、运算符、界符等等。
9、下列 B 优化方法是针对循环优化进行的。
A．删除多余运算B．删除归纳变量C．合并已知量D．复写传播
10、若文法G 定义的语言是无限集，则文法必然是 A
A、递归的
B、前后文无关的
C、二义性的
D、无二义性的
11、文法G 产生的D的全体是该文法描述的语言。
A、句型
B、终结符集
C、非终结符集
D、句子
12、Chomsky 定义的四种形式语言文法中，0 型文法又称为 A文法；1 型文法又称为 C 文法。
A.短语文法
B.上下文无关文法
C.上下文有关文法
D.正规文法
A.短语文法
B.上下文无关文法
C.上下文有关文法
D.正规文法
13、语法分析最常用的两类方法是自顶向下和自底向上分析法。
14、一个确定的有穷自动机DFA是一个 A 。
A 五元组（K，∑，f, S, Z）
B 四元组（V N，V T，P，S）
C 四元组（K，∑，f，S）
D 三元组(V N,V T,P)
A、语法
B、语义
C、代码
D、运行
15、 B不属于乔姆斯基观点分类的文法。
A、上下文无关文法
B、算符优先文法
C、上下文有关文法
D、正规文法
16、一个文法所描述的语言是A ；描述一个语言的文法是 B 。
A.唯一的
B.不唯一的
C.可能唯一,可能不唯一
A.唯一的
B.不唯一的
C.可能唯一,可能不唯一
17、语法分析是依据语言的语法规则进行的，中间代码产生是依据语言的等价变换规则进行的。
18、 B 不属于乔姆斯基观点分类的文法。
A上下文无关文法B算符优先文法C上下文有关文法D正规文法
19、过程调用时参数传递方式有 A
(1)传地址(2)传值(3)传标识符(4)得结果(5)传名(6) 返回值
可选项有：
A、(1)(2)(4)(5)
B、(1)(2)(5)(6)
C、(1)(2)(3) (6)
D、(2)(3)(4)(6)
20、过程调用时参数传递方式有
(1)传地址(2)传值(3)传标识符(4)得结果(5)传名(6) 返回值
可选项有：
A、(1)(2)(4)(5)
B、(1)(2)(5)(6)
C、(1)(2)(3) (6)
D、(2)(3)(4)(6)
21、下列代码中 D 不可能是目标代码。
A、汇编指令代码
B、可重定位指令代码
C、绝对指令代码
D、中间代码
22、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。B B。
A.正确
B.不正确
23、有限自动机能识别 C
A．上下文无关文法B．上下文有关文法
C．正规文法D．短语文法。
24、汇编程序是将 B 程序改造成目标语言程序的翻译程序。
A机器语言B汇编语言C高级语言D低级语言
25、LR(k)文法___B____二义性的。
A、都是
B、都不是
C、不一定都是
26、乔姆斯基方法的2型语言是这样一种语言，其产生式限制为 A
A、A→α
B、A→a，A→aB
C、α→β(| α | ≤ | β|)
D、α→β
27、局部优化是局限于一个 C 范围内的一种优化。
A.循环
B.函数
C.基本块
D.整个程序
28、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 A 。
A.正确
B.不正确
29、乔姆斯基方法的3型语言是这样一种语言，其产生式限制为 B
A A→α
B A→a或A→aB Cα→β(| α | ≤ | β|) D α→β
30、运算符与运算对象类型不符属于 A 。
A、语法错误
B、语义错误
C、语用错误
D、规则集合
31、词法分析器的输入是 B 。
A、词法记号
B、源程序
C、语法单位
D、目标程序
32、在下述的编译方法中，自底向上的方法有F，自顶向下的分析方法有 A 。
①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR（K）分
析⑥SLR（k）分析⑦LL（k）分析⑧LALR（K）分析
A.③④⑦
B. ③④⑧
C.①②⑧
D.③④⑤⑥⑦
E.①②⑤⑥⑦
F. ①②⑤⑥⑧
A.③④⑦
B. ③④⑧
C.①②⑧
D.③④⑤⑥⑦
E.①②⑤⑥⑦
F. ①②⑤⑥⑧
33、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。 B 。
A.正确
B.不正确
34、算符优先分析法每次都是对 C 进行归约。
A 句柄B短语C最左素短语D素短语
35、编译时能进行的类型检查称为 C 。
A、错误检查
B、动态检查
C、静态检查
D、随机检查
36、规范推导的每一步总是用产生式右边符号串替换句型中B位置的非终结符号
A、最左
B、最右
C、最中
D、任意
37、语法分析器的输入是单词符号流，其输出是分析树的某种表示
38、每个文法都能改写为LL(1)文法。 B
A.正确
B.不正确
39、对于无二义性的文法，规范推导是 C
A 最左推导
B 最右推导的逆过程
C 最左归约的逆过程
D 最右归约的逆过程。
40、描述语言L= { a m b n| n≥m≥1 } 的文法为 D 。
A、Z→A bb A→aA | a B→bB | b
B、Z→AB | b A→Aa | a B→aBb | b
C、Z→Ab A→aAb | a
D、Z→aAb A→Ab | aAb | ε
41、间接三元式表示法的优点为
A、采用间接码表，便于优化处理
B、节省存储空间，不便于表的修改
C、便于优化处理，节省存储空间
D、节省存储空间，不便于优化处理
42、编译时能进行的类型检查称为 C
A错误检查B动态检查C静态检查D随机检查
43、文法G[S]：S→ xSx | y所识别的语言是 A 。
A、x n yx n(n≥0)
B、(xyx)*
C、xyx
D、x*yx*
44、项目A→α·称为 B ，其中A∈V N，A不是开始符。
A、移进项目
B、归约项目
C、出错项目
D、接受项目
45、设有文法G[S]: S-> S*S | S+S | (S) | a, 该文法___A__二义性文法。
A、是
B、不是
C、不一定
46、高级语言编译程序常用的语法分析方法中，LL分析法属于 B 分析方法。
A、自左至右
B、自顶向下
C、自底向上
D、自右至左。
47、有文法G：E→E*T|T T→T＋i|i句子2＋5*3＋3按该文法G归约，其值为 B
A 23 B42 C30 D 17
48、高级语言编译程序常用的语法分析方法中，LL分析法属于 B 分析方法。
A 自左至右
B 自顶向下
C 自底向上D自右至左。
49、形如A→α·Bβ的项目为 A 项目。
A、待约
B、移进
C、接受
D、规约
50、活动记录的连接数据不包括 A 。
A、形参单元
B、动态链（老SP）
C、返回地址
D、全局Display地址
51、高级语言编译程序常用的语法分析方法中，lALR分析法属于 C 分析方法。
A、自左至右
B、自上而下
C、自下而上
D、自右至左
52、设a、b、c是文法的终结符，且满足优先关系a=?b和b=?c，则 D 。
A.必有a=?c
B.必有c=?a C 必有b=?a D 答案A~C都不一定成立
53、词法分析器的输出是 A 。
A、词法记号流
B、源程序
C、语法单位
D、目标程序
54、对一个基本块来说， A 是正确的。
A、只有一个入口语句和一个出口语句
B、有一个入口语句和多个出口语句
C、有多个入口语句和一个出口语句
D、有多个入口语句和多个出口语句
55、词法分析所依据的是 B 。
A 语义规则
B 构词规则
C 语法规则
D 等价变换规则
56、句型是由 D 推导出的符号串。
A、非终结符
B、终结符
C、任何符号
D、开始符号
57、如果文法G是无二义的，则它的任何句子α A 。
A、最左推导和最右推导对应的语法树必定相同
B、最左推导和最右推导对应的语法树可能不同
C、最左推导和最右推导必定相同
D、可能存在两个不同的最左推导，但它们对应的语法树相同
58、算符优先文法与算符优先函数的关系的描述中正确的是（B）。
A、一个算符优先文法一定存在优先函数与之对应
B、一个算符优先文法可能存在多个优先函数与之对应
C、一个算符优先文法一定存在多个优先函数与之对应
D、一个算符优先文法一定存在有限对优先函数与之对应
59、一个句型中称为句柄的是该句型的最左 D 。
A 非终结符
B 短语
C 句子
D 直接短语
60、描述一个语言的文法是（B ）
A、唯一的
B、不唯一的
C、可能唯一，也可能不唯一
61、下列 C 优化方法不是针对循环优化进行的。
A、强度削弱
B、删除归纳变量
C、删除多余运算
D、代码外提
62、更动一张 A 表很困难。
A 三元式
B 间接三元式
C 四元式
D 三元式和四元式
63、栈式存储分配申请和释放存储空间遵守BC 原则。
A、先申请先释放
B、先申请后释放
C、后申请先释放
D、任意
64、所谓自上而下分析法是指。
65、所谓语法制导翻译方法是。
66、确定的有穷自动机是一个五元组，通常表示为M=(S ,∑,f,s0,Z ) 。
素短
左素
短
最左67、规范归约中的可归约串是指句柄；算符优先分析中的可归约串是指最
语。
语
分析
析、语义分析、中间代码
语法
法分
68、编译程序在逻辑上由词法分析、语
生成、代码优化和目标代码生成六部分组成。
69、
A、汇编语言模块
B、可重定位目标模块
C、可执行目标模块
D、中间代码
70、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。
71、一个名字的属性包括继承属性和综合属性。
72、正规式的“*”读作星闭包。
73、编译程序在逻辑上由、、语义分析、中间代码生成、代码优化和目标代码生成六部分组成。
74、编译程序的各个阶段的工作都涉及到符号表管理和错误处理
75、文法用来描述语言的语法结构，它由如下4个部分组成：文法终结符集合、文法非终结
符集合、 D 和文法开始符号。
A、单词集合
B、字母数字串
C、文法句子集合
D、文法产生式的集合
76、确定的有穷自动机是一个元组，通常表示为。
77、已知文法G[E]：
E→E + T | T
T→T * F | F
F→（E）| id
该文法终结符集合V T= ，文法非终结符集合V N= ，该文法在乔姆斯基（Chomsky）文法分类属于 2 文法。
78、编译程序的各个阶段的工作都涉及到和。
79、假设G是一个文法，S是文法开始符号，如果S *>x，则称x是该文法的一。
80、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是。
81、优化时，节省一条指令MOV R i，M，节省的指令代价为 C
A、0
B、1
C、2
D、3
82、采用LL(1) 语法分析时，必须消除文法的左递归。
83、在状态转换图中，结点代表状态，用圆圈表示。
84、若源程序是高级语言编写的，目标程序是机器语言或汇编语言的程序，则相应的翻译程序称为编译程序。
85、常用的两种动态存贮分配办法是栈式分配和堆式分配。
86、翻译方案和语法制导定义不同的是它的语义动作（而不叫语义规则）放在括号{ }内，并且可以插在产生式右部的任何地方
87、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是。
88、所谓最左推导是指：。
89、上下文无关文法的可以用四元组表示，其形式为 G=(V N,V T,S,P) 。
90、后缀式ab+c+d*e- 所表达的式子为（a+b+c）*d-e 。
91、常用的两种动态存贮分配办法是分配和分配。
92、LL(K)文法中，第一个L表示从左到右扫描输入串，第二个L表示产生最左推导，K表示在决定语法分析器每步动作时向前看K 个输入符。
93、一个上下文无关文法所含四个组成部分是文法终结符集合文法非终结符集合
开始符号产生式有限集合。
94、对于文法G，仅含终结符号的句型称为句子。
95、设有文法G[E]：
E→E + T | E – T | T
T→T * F | T/F | F
F→（E）| i
该文法句型E + T * F 的句柄是T * F 。
96、后缀式ab+c+d*e- 所表达的式子为。
97、文法符号的属性有两种，一种称为继承属性，另一种称为综合属性，S属性定义是指仅使用综合属性的语法制导定义。
98、LR(0)项目和LR(1)项目的区别在于是否有搜索符。
99、紧跟在条件转移语句后面的语句是基本块的入口语句。
100、若二个正规式所表示的DFA（或正规集）相同，则认为二者是等价的。101、仅含终结符的句型称为。
102、编译方式与解析程序的根本区别在于是否生成目标代码。( F )
103、规范归约和规范推导是互逆的两个过程。( T ) 104、一个上下文无关文法的开始符号可以是终结符或非终结符。( F ) 105、逆波兰表示法表示表达式时无需使用括号。( T )
106、符号表由词法分析程序建立，由语法分析程序使用。( F ) 107、逆波兰法表示的表达式亦称前缀式。( F )
108、代码生成器的输入包括中间代码和符号表中的信息。( T )
109、孤立地考虑一个基本块常常不能确定一个赋值是否真是无用的。( T ) 110、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。( T ) 111、无左递归的文法是LL(1)文法。( F )
112、一个句型的直接短语语是唯一的。( F ) 113、正规文法产生的语言都可以用上下文无关文法来描述。(F ) 114、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。( F )
115、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。( F ) 116、一个上下文无关文法的开始符号可以是终结符或非终结符。( F ) 117、一个文法所有句子的集合构成该文法定义的语言。( T )
118、优化实质上是对代码进行等价变换，变换后的代码结构不同但运行结果相同。( T ) 119、算符优先分析法是一种规范归约分析法。( F ) 120、非终结符可以有综合属性，但不能有继承属性。( F )
121、所有LR分析器的总控程序都是一样的，只是分析表各有不同。( T ) 122、因名字都是用标识符表示的，故名字与标识符没有区别(F ) 123、空符号串的集合{ε}={}=?。( F )
124、非终结符可以有综合属性，但不能有继承属性。( F ) 125、终结符可以有综合属性，也可以有继承属性。( F ) 126、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。( )
127、若一个句型中出现了某一产生式的右部，则此右部一定是该句型的句柄。( F ) 129、DAG是一个可带环路的有向图。( F ) 130、设有符号串x和y，把y的符号写在x的符号之后所得的符号串，叫做x与y的连接，记为xy。( T ) 131、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。( F ) 132、对任何正规表达式e，都存在一个DFA M，满足L(M)＝L(e)。( T)
133、运行时的DISPLAY表的内容是什么？它的作用是什么？
答：内容：1、过程R的现行活动记录的地址（sp的现值）2、R的外层Q的最新活动记录的地址3、Q的外层即主程序P的活动记录的地址
作用：跟踪每个外层的最新活动记录的位置
134、何谓局部优化、循环优化和全局优化？优化工作在编译的哪个阶段进行？
答：局部优化：在基本快内的优化。循环优化：对循环中的代码进行优化。全局优化：整个程序范围内的优化。在中间代码优化阶段。
135、常见的存储分配策略有几种？它们都适合于什么性质的语言？
答：1、静态分配策略适用于无动态申请内存、无可变体积数组、无递归调用的程序语言（如Fortran）
2、动态分配策略
2.1栈式动态分配2.1.1简单栈式分配适用于没有分程序结构、不允许程序嵌套定义但允许过程递归调用、允许过程含可变数组的语言 2.1.2嵌套过程语言的栈式分配适用于没有分程序结构、允许程序嵌套定义和过程递归调用、允许过程含可变数组的语言
2.2堆式动态分配适用于允许程序为变量在运行时动态申请和释放存储空间的语言
136、下面文法是否是二义文法？试说明理由。
G[S]：S → SaS| ε
答：二义
137、已知文法G(E)
E→T|E＋T
T→F|T * F
F→(E)|i
(1) 给出句型(T * F＋i)的最右推导及画出语法树；
(2) 给出句型(T * F＋i)的短语、素短语。
1）E→E＋T→E+i→T+i→T*F+I 树略
2）短语：T*F+i T*F i
素短语：T*F i
138、把算术表达式－(a+b)*(b+c)翻译成：
(a) 后缀表示ab+bc+*@
(b) 语法树图略
(c) 有向无环图图略
(d) 四元式三地址代码
四地址代码：
（+, a ，b，t1）
（+，b，c，t2）
（*，t1，t2，t3）
（@，t3，-，t4）
139、DFA与NFA的区别？
答：1、DFA弧上不允许有ε出现，NFA允许
2、DFA中每个状态S和输入符号a最多有一条边离开S，NFA有多条
3、NFA可以有多个初态，DFA只有一个
140、设已构造出文法G(S)：
S→S(S)
S→ε
的LR分析表如下
假定输入串为( )( )，请给出LR分析过程(即状态，符号，输入串的变化过程)。
步骤状态符号输入串
141、对符号表的基本操作有几种，分别是什么？
答：5类。1、填写名称2、查找名字3、访问信息4、填写修改信息5、删除（或者：4类。建立、插入、查找、删除）
142、给定代码段如下，求出按四种不同方式进行参数传递后，变量a的值
…
procedure P(w,x,y,z);
begin
y := y*w;
z := z+x;
end
begin
a := 5;
b := 3;
P(a+b,a-b,a,a);
write(a);
end
传值: 5
传地址: 42
得结果: 7
传名: 77
143、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？
答：1、汇编语言2、机器语言又可分为a可立即执行的机器语言b可重定位的机器语言需要考虑：1.、如何使生成的目标代码最短2、如何分配寄存器的使用
144、下面的推导S ?rm… ? rmγ A b w ? rmγ l β b w中，最后一步用的是A→lβ，分别指出LL（1）方法和LR（1）方法在扫描到此句型的什么位置决定用此产生式？(5分) P79
答：LL(1)扫描到l的时候决定用此产生式；LR(1)扫描到b的时候决定使用次产生式
145、构造一个最简DFA，它接受正规式ab (a|b)*。
给出文法G[S]：S→SaA|A
A→AbB|B
B→cSd|e
(1)证实AacAbcBaAdbed是文法G[S]的一个句型；
(2)请写出该句型的所有短语、素短语以及句柄。
答：1）这里用最右推导表示，省略树S→SaA→SaB→SacSd→SacAd→SacAbBd→SacAbed→SacAbBbed→SacAbcSdbed
→SacAbcSaAdbed→SacAbcAaAdbed→SacAbcBaAdbed →AacAbcBaAdbed
2）短语：AacAbcBaAdbed cAbcBaAdbed AbcBaAdbe AbcBaAd cBaAd BaA e A 素短语：BaA e 句柄：A
146、写出表达式a+b*(c-d)对应的逆波兰表示、三元式三地址代码序列和抽象语法树。
147、什么是活动记录？它主要由哪些内容构成？
148、对下列四元式序列生成目标代码(10分)
T=A-B
S=C+D
W=E-F
U=W/T
V=U*S
其中，V是基本块出口的活跃变量，R0和R1是可用寄存器。
答MOV R0 ，A
SUB R0 ，B
MOV R1 ，A
ADD R1 ，D
MOV S ，R1
MOv R1 ，E
SUB R1 ，F
DIV R1 ，R0
MUL R1 ，S
149、设有如下的三地址码(四元式)序列：
Read N
I∶=N
J∶=2
————————
L1：if I≤J goto L3
————————
L2：I∶=I-J
if I>J goto L2
————————
if I=0 goto L4
————————
J∶=J+1
I∶=N
goto L1
————————
L3：Print ′YES′
Return
————————
L4：Print ′NO′
Return
（1）、对题中代码划分基本块，并给每个基本块一个序号
（2）、画出基本块集合的控制流图，每个基本块就用（1）小题中的序号表示。
（3）、若有循环的话，列出构成每个循环的结点。
150、已知文法G(V)：V →N | N [E]
E→V | V+E
N→i
(1)给出与G(V)等价的LL(1)文法G'(V)；
V →NV’V’→[E]|εE→VE’E’→+E|εN→i
(2)求文法G'(V)的每个非终结符的FIRST集合和FOLLOW集合；
First(V)={i} First(V’)={[ , ε}
First(E)={i} First(E’)={ + ,ε} First(N)={i}
Follow(V)={$,+,]} Follow(V’)={$,+,]} Follow(E)={]} Follow(E’)={]} Follow(N)={[ , $ , + }
(3)构造文法G'(V)的LL(1)分析表。
151、考虑下面的三地址语句序列： b := 1 b := 2 if w <= x goto L2 ———————— e := b goto L2 ———————— L1: goto L3 ———————— L2: c := 3 b := 4 c := 6
———————— L3: if y <= z goto L4 ———————— goto L5 ———————— L4: g := g + 1 h := 8 goto L1 ———————— L5: h := 9
（1）、在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。 （2）、画出该代码的控制流图，每个基本块就用（1）小题中的序号表示。 （3）、若有循环的话，列出构成每个循环的结点。
152、对于文法G(S)：
)
Ma L a |(L M bMb S →→→ (1) 写出句型b(Ma)b 的最右推导并画出分析树。 S →bMb →b(Lb →b(Ma)b
(2) 写出上述句型的短语，直接短语和句柄。 短语：b(Ma)b (Ma) Ma) 句柄：Ma) 153、LL(1)分析法对文法有哪些要求？
对文法中任意A→α|β型产生式需满足：
First(α)∩First(β)=空集
若β=>ε则First(α)∩Follow(A)=空集
154、写出语句a:=b*(-c)+b*(-c)的后缀式、抽象语法树、DAG图、四元式三地址代码和三元式三地址代码。
155、设有文法G[A]： A →iB*e
B →SB | ε
S →[eC] | . i
C →eC | ε
判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否则说明理由。(20分) First(A)={i} First(B)={[ , ε , . } First(S)={ [ , . } First(C)={e, ε}
Follow(A)={$} Follow(B)={*} Follow(S)={*} Follow(C)={]}
对产生式B →SB | ε
First(SB)=First(S)= { [ , . } First(ε)={ ε} 所以First(SB)∩First(ε)=空集
First(SB)∩Follow(B)=空集
对产生式S →[eC] | . i
First([eC])= { [} First(. i)={ . i } 所以First([eC])∩First(. i)=空集
对产生式C →eC | ε
First(eC) { e } First(ε)={ ε} 所以First(eC)∩First(ε)=空集
First(eC)∩Follow(C)=空集
156、构造一个DFA，它接受∑={0，1}上能被5整除的二进制数。
157、正规式(0 | 1)* 和( (ε | 0) 1* )*是否等价，说明理由。
158、写出字母表∑ = {a, b}上语言L = {w | w的最后两个字母是aa或bb}的正规式，并画出接受该语言的最简DFA。
(a|b)*aa|bb
159、文法G(S)及其LR分析表如下，请给出串baba$的分析过程。
(1) S →DbB (2) D →d (3) D→ε
(4) B →a (5) B →Bba (6) B →ε
LR分析表
160、已知文法G(A)：A→aABl | a
B→ Bb | d
(1)消除文法中的左递归，提取公共左因子，给出与G(A)等价的LL(1)文法G'(A)；
(2)求文法G'(A)的每个非终结符的FIRST集合和FOLLOW集合；
(3)构造文法G'(A)的LL(1)分析表。
答：1）A→aA’A’→ABl|εB→ d B’B’→b B’ |ε
2) First(A)={a} First(B)={d} First(A’)={a, ε} First(B’)={b, ε}
Follow(A)={$,d} Follow(B)={l} Follow(A’)={$,d} Follow(B’)={l}
161、设文法G(S)：
S→S+aF | aF | +aF
F→*aF | *a
(1) 消除左递归和回溯；
(2) 计算每个非终结符的FIRST和FOLLOW；
(3) 构造预测分析表。
答
1、S→+aFS’| aFS’
S’→+aFS’|ε
F→*aF’
F’→F|ε
2、Fist(S)={a,+} Fist(S’)={+,ε} Fist(F)={*} Fist(F’)={*, ε}
Follow(S)={$} Follow(S’)={$} Follow(F)={$,+} Follow(F’)={$,+}
162、构造下面文法的LL（1）分析表。
D → TL
T → int | real
L → id R
R → , id R | ε(10 分)
163、已知文法G(S):
S→a | (T)
T→T，S | S
给出该文法的优先关系表，并计算出该优先关系表所对应的优先函数。
答：(算符优先的大于小于等于都带点，在此省略)
Firstvt(S)={ a , ( } Firstvt(T)={，, a , (}
Lastvt(S)={a , )} Lastvt(T)={，, a , )}
画表
T—>T，S ，< Firstvt(S) Lastvt(T) > ，
T—>T，S —>S，S Lastvt(S) > ，
S—>(T) ( < Firstvt(T) Lastvt(T) > )
S—>(T)—>(S) ( < Firstvt(S) Lastvt(S) > )
164、处于/* 和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。(10分)
165、已知文法G(S)
S→a|∧|(T)
T→T，S|S
写出句子((a，a)，a)的移进-归约分析过程及每一次归约的句柄。(10分)
初始状态如下，请接着往下进行分析。
栈输入动作句柄
166、接受文法
S → A a | b A c | d c | b d a
A → d
活前缀的DFA见下图。请根据这个DFA来构造该文法的SLR(1)分析表，并说明该文法为什么不是SLR(1)文法。(10分)
0）S ‘→S
1）S → A a
2）S →b A c
3）S → d c
4）S → b d a
5）A → d
考察既含有归约项目又含有移进项目的项目集如I4
S → d .c 移进项目
A → d . 归约项目
Follow(A)={a , c}∩{c}≠空集所以此文法不是SLR(1)文法
编译原理课后习题答案(第三版)
精品文档 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************
(完整版)编译原理课后习题答案
第一章 1．典型的编译程序在逻辑功能上由哪几部分组成？ 答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。 2. 实现编译程序的主要方法有哪些？ 答：主要有：转换法、移植法、自展法、自动生成法。 3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？ 答：编译法、解释法。 4. 编译方式和解释方式的根本区别是什么？ 答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快； 解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。
第二章 1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关 系如何？ 答：1）0型文法、1型文法、2型文法、3型文法。 2） 2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。 答： Z→SME | B S→1|2|3|4|5|6|7|8|9 M→ε | D | MD D→0|S B→2|4|6|8 E→0|B 3. 设文法G为： N→ D|ND D→ 0|1|2|3|4|5|6|7|8|9 请给出句子123、301和75431的最右推导和最左推导。 答：N?ND?N3?ND3?N23?D23?123 N?ND?NDD?DDD?1DD?12D?123 N?ND?N1?ND1?N01?D01?301 N?ND?NDD?DDD?3DD?30D?301 N?ND?N1?ND1?N31?ND31?N431?ND431?N5431?D5431?75431 N?ND?NDD?NDDD?NDDDD?DDDDD?7DDDD?75DDD?754DD?7543D?75431 4. 证明文法S→iSeS|iS| i是二义性文法。 答：对于句型iiSeS存在两个不同的最左推导： S?iSeS?iiSes S?iS?iiSeS 所以该文法是二义性文法。 5. 给出描述下面语言的上下文无关文法。 （1）L1={a n b n c i |n>=1,i>=0 } （2）L2={a i b j|j>=i>=1} （3）L3={a n b m c m d n |m,n>=0} 答： （1）S→AB A→aAb | ab B→cB | ε （2）S→ASb |ab
编译原理复习题及答案
编译原理复习题及答案 一、选择题 1．一个正规语言只能对应(B) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A]：A→εA→aB B→Ab B→a是(A) A 正规文法 B 二型文法 3．下面说法正确的是(A) A 一个SLR（1）文法一定也是LALR（1）文法 B 一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A) A 必要条件 B 充分必要条件 5．下面说法正确的是(B) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是(A) A 归约速度快 B 对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8．下面说法正确的是(A) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9．下面说法正确的是(A) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 11．(A)是一种典型的解释型语言。
A．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 13．用高级语言编写的程序经编译后产生的程序叫(B) A．源程序 B．目标程序C．连接程序D．解释程序 14．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C) A. bba B. cab C. bca D. cba
编译原理复习题及参考答案
中南大学网络教育课程考试复习题及参考答案 编译原理 一、判断题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。 ( ) 3.已经证明文法的二义性是可判定的。 ( ) 4.每个基本块可用一个DAG表示。 ( ) 5.每个过程的活动记录的体积在编译时可静态确定。 ( ) 6.2型文法一定是3 型文法。 ( ) 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 ( ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 ( ) 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 ( ) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成 LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个 LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是 2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( ) 二、填空题： 1.( )称为规范推导。 2.编译过程可分为（），（），（），（）和（）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。 4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。 5.语法分析器的输入是（），其输出是（）。 6.扫描器的任务是从（）中识别出一个个（）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。 8.一个过程相应的DISPLAY表的内容为（）。 9.一个句型的最左直接短语称为句型的（）。 10.常用的两种动态存贮分配办法是（）动态分配和（）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（），（）和（）。 13.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。 14.语法分析的方法大致可分为两类，一类是（）分析法，另一类是（）分析法。 15.预测分析程序是使用一张（）和一个（）进行联合控制的。 16.常用的参数传递方式有（），（）和（）。 17.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。 18.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。 19.语法分析是依据语言的（）规则进行。中间代码产生是依据语言的（）规则进行的。 20.一个句型的最左直接短语称为句型的（）。 21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（）文法。 22.对于数据空间的存贮分配， FORTRAN采用( )策略， PASCAL采用( )策略。
编译原理课后答案
第二章 2.3叙述由下列正规式描述的语言 (a) 0(0|1)*0 在字母表{0, 1}上,以0开头和结尾的长度至少是2的01 串 (b) ((ε|0)1*)* 在字母表{0, 1}上,所有的01串,包括空串 (c) (0|1)*0(0|1)(0|1) 在字母表{0, 1}上,倒数第三位是0的01串 (d) 0*10*10*10* 在字母表{0, 1}上,含有3个1的01串 (e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 在字母表{0, 1}上,含有偶数个0和偶数个1的01串 2.4为下列语言写正规定义 C语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀（本身除外）不以 */ 结尾。 ［解答］ other → a | b | … other指除了*以外C语言中的其它字符 other1 → a | b | … other1指除了*和/以外C语言中的其它字符 comment → /* other* (* ** other1 other*)* ** */ (f) 由偶数个0和偶数个1构成的所有0和1的串。 ［解答］由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况： x 偶数个0和偶数个1（用状态0表示）； x 偶数个0和奇数个1（用状态1表示）； x 奇数个0和偶数个1（用状态2表示）； x 奇数个0和奇数个1（用状态3表示）；所以， x 状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0和奇数个1（状态1） x 状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态3（奇数个0和奇数个1）读入0，则0和1的数目变为：偶数个0和奇数个1（状态1） 因为，所求为由偶数个0和偶数个1构成的所有0和1的串，故状态0既为初始状态又为终结状态，其状态转换图： 由此可以写出其正规文法为： S0 → 1S1 | 0S2 | ε S1 → 1S0 | 0S3 | 1 S2 → 1S3 | 0S0 | 0 S3 → 1S2 | 0S1 在不考虑S0 →ε产生式的情况下，可以将文法变形为： S0 = 1S1 + 0S2 S1 = 1S0 + 0S3 + 1 S2 = 1S3 + 0S0 + 0 S3 = 1S2 + 0S1 所以： S0 = (00|11) S0 + (01|10) S3 + 11 + 00 (1) S3 = (00|11) S3 + (01|10) S0 + 01 + 10 (2) 解(2)式得： S3 = (00|11)* ((01|10) S0 + (01|10)) 代入(1)式得： S0 = (00|11) S0 + (01|10) (00|11)*((01|10) S0 + (01|10)) + (00|11) => S0 = ((00|11) + (01|10) (00| 11)*(01|10))S0 + (01|10) (00|11)*(01|10) + (00|11) => S0 = ((00|11)|(01|10) (00|11)*(01|10))*((00|1
编译原理课后习题答案-清华大学-第二版
第1章引论 第1题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2） 源程序：源语言编写的程序称为源程序。 （3） 目标程序：目标语言书写的程序称为目标程序。 （4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。
目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。 注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。 第3题 何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？ 答案： 翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。 编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。 解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这条语句的功
编译原理习题及答案(整理后)
第一章 1、将编译程序分成若干个“遍”就是为了。 a．提高程序得执行效率 b．使程序得结构更加清晰 c．利用有限得机器内存并提高机器得执行效率 d．利用有限得机器内存但降低了机器得执行效率 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法d．以上三项都就是 3、变量应当。 a．持有左值b．持有右值 c．既持有左值又持有右值d．既不持有左值也不持有右值 4、编译程序绝大多数时间花在上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 5、不可能就是目标代码。 a．汇编指令代码b．可重定位指令代码 c．绝对指令代码d．中间代码 6、使用可以定义一个程序得意义。 a．语义规则b．语法规则 c．产生规则d．词法规则 7、词法分析器得输入就是。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循得就是- 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序就是对。 a．汇编程序得翻译b．高级语言程序得解释执行 c．机器语言得执行d．高级语言得翻译 10、语法分析应遵循。 a．语义规则b．语法规则 c．构词规则d．等价变换规则 二、多项选择题 1、编译程序各阶段得工作都涉及到。 a．语法分析b．表格管理c．出错处理 d．语义分析e．词法分析 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成 d．语义检查e．目标代码生成 三、填空题 1、解释程序与编译程序得区别在于。 2、编译过程通常可分为5个阶段，分别就是、语法分析、代码优化与目标代码生成。 3、编译程序工作过程中，第一段输入就是，最后阶段得输出为程序。
编译原理课后习题答案
第1 章 1、编译过程包括哪几个主要阶段及每个 阶段的功能。 答案：编译过程包括词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成5 个阶段。词法分析的功能是对输入的高级语言源程序进行词法分析，识别其中的单词符号，确定它们的种类，交给语法分析器，即把字符串形式的源程序分解为单词符号串形式。语法分析的功能是在词法分析结果的基础上，运用语言的语法规则，对程序进行语法分析，识别构成程序的各类语法范畴及它们之间的层次关系，并把这种层次关系表达成语法树的形式。词义分析和中间代码生成的功能是在语法分析的基础上，对程序进行语义分析，“理解”其含义，产生出表达程序语义的内部表达形式（中间代码）。优化的功能是按照等价变换的原则，对语义分析器产生的中间代码序列进行等价变换，删除其中多余的操作，对耗时耗空间的代码进行优化，以期最后得到高效的可执行代码。目标代码生成的功能是把优化后的中间代码变换成机器指令代码，得到可在目标机器上执行的机器语言程序。 第2 章 1、写一上下文无关文法G，它能产生配 对的圆括号串（如：(),(()),()(())等，甚至 包括0 对括号） 文法为：S→(L)|LS|L L→S| ε 2 、已知文法G ：E→E+T|E-T|T T→T*F|T/F|F F→(E) |i （1）给出i+i*i,i*(i-i)的最左推导，最右推导以及语法树。 （2）i-i+i 哪个算符优先。 【解答】 （1）最左推导：E?E+T?T+T? F+T ? i+T ? i+T*F ? i+F*F ?i+i*F ?i+i*i E?T?T*F? F*F ? i*F ? i*(E) ? i*(E-T) ? i*(T-T) ? i*(F-T) ? i*(i-T) ? i*(i-F) ?i*(i-i) 最右推导：E?E+T?E+T*F? E+T*i ? E+F*i ? E+i*i ? T+i*i ? F+i*i ? i+i*i E?T?T*F? T*(E) ? T*(E-T) ? T*(E-F) ? T*(E-i) ? T*(T-i) ? T*(F-i) ?T*(i-i) ? F*(i-i) ?i*(i-i) i+i*i 以及i*(i-i)的语法树如下所示： （2）i-i+i 的语法树如下图所示。 从上图的语法树可知：“-”的位置位 于“+”的下层，也就是前面两个i 先进 行“-”运算，再与后面的i 进行“+” 运算，所以“-”的优先级高于“+”的 优先级。 3 、文法G: E→ET+|T T→TF*|F F→FP↑|P P→E|i （1）试证明符号串TET+*i↑是G 的一 个句型(要求画出语法树). （2）写出该句型的所有短语,直接短语和句柄. 【解答】（1）采用最右推导： E?T?F? FP↑? Fi↑? Pi↑? Ei↑ ? Ti↑? TF*i↑? TP*i↑? TE*i↑? TET+*i↑ 语法树如下图所示。 从文法G 的起始符号出发，能够推导 出符号串TET+*i↑，所以给定符号串是文法G的句型。 (2) 该句型的短语有： ET+,TET+*,i ,TET+*i↑ 直接短语有：ET+, i 句柄是：ET+ 4、已知文法G：S→iSeS|iS|i ，该文法 是二义文法吗？为什么？ 【解答】该文法是二义文法。 因为对于句子iiiei 存在两种不同的最 左推导： 第 1 种推导：S? iSeS? iiSeS? iiieS? iiiei 第2种推导：S?iS?iiSeS?iiieS?iiiei 第3 章 1、用正规式描述下列正规集： （1）C 语言的十六进制整数； （2）以ex 开始或以ex 结束的所有小写字母构成的符号串； （3）十进制的偶数。 【解答】 （1）C 语言十六进制整数以0x 或者0X 开头，所以一般形式应该为（+|-|ε） (0x|0X)AA*，其中前面括号表示符号， 可以有正号、负号，也可以省略（用ε表示）默认是正数，A 表示有资格出现在十六进制整数数位上的数字，AA*表示一位或者多位（一个或者多个数字的
编译原理第三版课后习题与答案
目录 P36-6 (2) P36-7 (2) P36-8 (2) P36-9 (3) P36-10 (3) P36-11 (3) P64–7 (4) P64–8 (5) P64–12 (5) P64–14 (7) P81–1 (8) P81–2 (9) P81–3 (12) P133–1 (12) P133–2 (12) P133–3 (14) P134–5 (15) P164–5 (19) P164–7 (19) P217–1 (19) P217–3 (20) P218–4 (20) P218–5 (21) P218–6 (22) P218–7 (22) P219–12 (22) P270–9 (24)
P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************
编译原理课后习题答案+清华大学出版社第二版
第 1 章引论 第1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。
编译原理复习题及答案
编译原理复习题及答案一、选择题 1．一个正规语言只能对应( B ) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A]：A→εA→aB B→Ab B→a是( A ) A 正规文法 B 二型文法 3．下面说法正确的是( A ) A 一个SLR（1）文法一定也是LALR（1）文法 B 一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的( A ) A 必要条件 B 充分必要条件 5．下面说法正确的是( B ) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是( A ) A 归约速度快 B 对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法( B ) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8．下面说法正确的是( A ) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9．下面说法正确的是( A ) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行
11．(A)是一种典型的解释型语言。 A．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 13．用高级语言编写的程序经编译后产生的程序叫(B) A．源程序?B．目标程序C．连接程序D．解释程序14．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序? C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器?C．表格处理和出错处理 ??? D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n(n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C)
编译原理(清华大学 第2版)课后习题答案
第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题
第9题 语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12．
(完整版)编译原理及实现课后习题答案
编译原理及实现课后习题解答 2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5 以及A+和A*. x0=(aaa)0=ε| x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪ …. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…} A* = A0 ∪A1 ∪A2 ∪…. ∪A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…} 2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语 法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a*
S S S * S S + a a a 2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。 Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101 2.5已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc , 写出该文法描述的语言。 A∷=aA︱ε描述的语言: {a n|n>=0} B∷=bBc︱bc 描述的语言：{b n c n|n>=1} L(G[S])={a n b m c m|n>=0,m>=1} 2.6已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。 开始符号：E V t={+, - , * , / ,（, ）, i} V n={E , F , T}
最新编译原理小题答案
《编译原理》常见题型 一、填空题 1.编译程序的工作过程一般可以划分为词法分析，语法分析，中间代码生成，代码优化(可省) ，目标代码生成等几个基本阶段。 2.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序. 3.编译方式与解释方式的根本区别在于是否生成目标代码. 5.对编译程序而言，输入数据是源程序，输出结果是目标程序. 7.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。 8.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。 10.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。 12.产生式是用于定义语法成分的一种书写规则。 13.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S=>*x,x∈VT*} 。 14.设G是一个给定的文法，S是文法的开始符号，如果S * ?x（其中x∈V*），则称x是 文法的一个句型。 15.设G是一个给定的文法，S是文法的开始符号，如果S * ?x(其中x∈V T*)，则称x是文 法的一个句子。 16.扫描器的任务是从源程序中识别出一个个单词符号。 17.语法分析最常用的两类方法是自上而下和自下而上分析法。 18.语法分析的任务是识别给定的终结符串是否为给定文法的句子。 19.递归下降法不允许任一非终结符是直接左递归的。 20.自顶向下的语法分析方法的关键是如何选择候选式的问题。 21.递归下降分析法是自顶向下分析方法。 22.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 23.自底向上的语法分析方法的基本思想是：从给定的终结符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 24.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地 向上进行直接归约，力求归约到文法的开始符号。 26.在LR（0）分析法的名称中，L的含义是自左向右的扫描输入串，R的含义是最 左归约，0 的含义是向貌似句柄的符号串后查看0个输入符号。 31.终结符只有综合属性，它们由词法分析器提供。
编译原理及实现课后习题答案 孙悦红
2.1 设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*. x0=(aaa)0=ε | x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪…. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…} A* = A0 ∪A1 ∪ A2∪…. ∪ A n∪…={ε,a,aa,aaa,aaaa,aaaaa…} 2.2 令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a* 2.4 已知文法G[Z]：Z∷=U0∣V1 、 U∷=Z1∣1 、 V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。 Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101 2.5 已知文法G[S]： S∷=AB A∷=aA︱ε B∷=bBc︱bc , 写出该文法描述的语言。 A∷=aA︱ε描述的语言: {a n|n>=0} B∷=bBc︱bc描述的语言：{b n c n|n>=1} L(G[S])={a n b m c m|n>=0,m>=1} 2.6 已知文法E∷=T∣E+T∣E-T 、 T∷=F∣T*F∣T/F 、 F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。 开始符号：E V t={+, - , * , / ,（ , ）, i} V n={E , F , T}
编译原理第三版课后答案
编译原理课后题答案 第二章 P36-6 (1) L G () 1是0~9组成的数字串 (2) 最左推导: 最右推导: P36-7 G(S) P36-8 文法： 最左推导: 最右推导: 语法树：/******************************** *****************/ P36-9 句子iiiei有两个语法树： P36-10 /************** ***************/ P36-11 /*************** L1: L2: L3: L4: ***************/ 第三章习题参考答案P64–7 (1)
最小化： P64–8 (1) (2) (3) P64–12 (a) a a,b a 0
给状态编号： a a a b b b 最小化： a a b b a b (b) 已经确定化了, 进行最小化 最小化： P64 –14 (1) 0 1 0 (2): (|)*010 1 εε 0 0 0 Y Y
最小化： 0 1 1 1 0 0 第四章 P81–1 (1) 按照T,S 的顺序消除左递归 递归子程序： procedure S; begin if sym='a' or sym='^' then abvance else if sym='(' then begin advance;T; if sym=')' then advance; else error; end else error end; procedure T; begin S; T end;
procedure 'T; begin if sym=',' then begin advance; S;'T end end; 其中: sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序 (2) FIRST(S)={a,^,(} FIRST(T)={a,^,(} FIRST('T)={,,ε} FOLLOW(S)={),,,#} FOLLOW(T)={)} FOLLOW('T)={)} 预测分析表 是LL(1)文法 P81–2 文法： (1) FIRST(E)={(,a,b,^} FIRST(E')={+,ε} FIRST(T)={(,a,b,^} FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F')={*,ε} FIRST(P)={(,a,b,^} FOLLOW(E)={#,)} FOLLOW(E')={#,)} FOLLOW(T)={+,),#} FOLLOW(T')={+,),#} FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#} (2)