编译原理期末考试试卷(A卷)

编译原理期末考试试题及答案一、选择题（每题2分，共20分）1. 编译器的前端主要负责以下哪项工作？A. 代码优化B. 目标代码生成C. 词法分析和语法分析D. 运行时支持2. 词法分析器的主要任务是什么？A. 识别语法结构B. 识别词法单元C. 构建语法树D. 代码优化3. 语法分析中，使用哪种方法可以避免回溯？A. 递归下降分析B. LR分析C. LL分析D. 自顶向下分析4. 下列哪个选项不是中间代码的形式？A. 三地址代码B. 四元组C. 抽象语法树D. 汇编语言5. 代码优化的目标不包括以下哪项？A. 提高代码执行速度B. 减少程序占用的内存C. 增加程序的可读性D. 减少程序的执行时间二、简答题（每题10分，共30分）1. 简述编译器的主要组成部分及其功能。

2. 解释什么是语法制导翻译，并举例说明其在编译过程中的应用。

3. 描述静态作用域规则和动态作用域规则的区别。

三、计算题（每题15分，共30分）1. 给定一个简单的算术表达式 `3 + (4 * 5) - 2`，请使用逆波兰表示法表示，并说明其转换过程。

2. 假设有一个简单的文法如下：```S -> A BA -> a A | εB -> b B | ε```请写出使用该文法生成字符串 "ab" 的所有派生树。

四、论述题（每题20分，共20分）1. 论述编译器中代码优化的重要性，并举例说明常见的优化技术。

参考答案一、选择题1. C2. B3. B4. D5. C二、简答题1. 编译器的主要组成部分包括前端、中端和后端。

前端负责词法分析和语法分析，中端进行语义分析和中间代码生成，后端则负责代码优化和目标代码生成。

2. 语法制导翻译是一种基于文法规则的翻译技术，它将源程序的语法结构映射到相应的语义操作上。

例如，在编译过程中，语法制导翻译可以用于将源代码中的条件语句转换为中间代码中的跳转指令。

3. 静态作用域规则是指变量的作用域在编译时确定，而动态作用域规则是指变量的作用域在运行时确定。

编译原理期末试卷1．给出LL(1)分析方法的总控流程图。

（5分）2．按指定类型给出下列语言的文法。

（10分）(1) L1={ ca n b m| n≥0,m>0 } 用正规文法。

S→cA A→aA|aB|a B→bB|b(2) L2={ 0n a 1n b m| n>0，m ≥0} 用二型文法。

S→0S1B|0a1 B→bB|c3．文法G[S]为：（10分）S→SdT | T T→T<G | G G→(S) | a试给出句型adT<(S)的短语、简单(直接)短语、句柄和最左素短语。

短语：a, T, (S), T<(S), adT<(S) 直接短语：a, (S) 句柄：a 最左素短语：a 4．将文法G[S] 改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。

（5分）S→[A A→B]|AS B→aB|+aS→[A A→B]A’A’→SA’|εB→aB|+a5．判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表，并写出aabbb 的分析过程。

（10分）S→aD D→STe|ε T→bM M→bH H→M|ε6．简述编译程序概念及构成。

（10分）编译程序是现代计算机系统的基本组成部分.从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序.7．设G=（V N，V T，P，<S>）是上下文无关文法，产生式集合P中任意一个产生式应具有什么样的形式？若G是正则文法呢？（10分）2型（上下文无关）：规则形式：A→βA ∈VN，β∈ (VT⋃VN)*3型（右线性）：A→aB或A→a（右线性）A→Ba或A→a （左线性）a ∈VT⋃{ε}8．为文法G[E]：（10分）V → N | N[E] E → V | V+E N → i构造递归下降识别程序E( ){ V( ); if symbol = ‘+’E( ); }V( ){ N(); if symbol = ‘[’ { E(); if symbol != ‘]’error(); }N( ){ if symbol != ‘i ’ error(); }/* 这样的写法很简化，当文法提取左公因子后，需要计算相关非终结符的Follow 集，才能确定什么时候用空串规则推导。

《编译原理》试卷A 参考答案注意事项：1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。

2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。

3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。

4. 满分100分，考试时间为120分钟。

题号一二三四总分统分人得分一、单项选择题（每小题2分共20分）1．中间代码生成所依据的是语言的（C ）。

A: 词法规则B: 语法规则C: 语义规则D: 产生式规则2．词法分析器的加工对象是（C ）。

A: 中间代码B: 单词C: 源程序D: 元程序3．同正则表达式a*b*等价的文法是（C ）。

A: G1: S aS|bS|εB: G2: S aSb|εC: G3: S aS|Sb|εD: G4: S abS|ε4．文法G[A]：A→b A→bH H H →BA B→Ab H →a 不是(B )：A: 2型文法B: 正规文法C: 0型文法D: 1型文法5．算符优先分析每次都是对（算符优先分析每次都是对（ B B B ）进行规约。

）进行规约。

A: A: 短语短语短语 B: B: B: 最左素短语最左素短语最左素短语 C: C: C: 素短语素短语素短语 D: D: D: 句柄句柄6．一个LR （1）文法合并同心集后,如果不是LALR(1)文法必定存在(B )：A: 移进-归约冲突B: 归约-归约冲突C: 识别句型D: 收集类型信息7．下列不属于类型检查范畴的描述是（C ）。

A: 运算符的分量类型的相容性B: 形参和实参类型的相容性C ：形参和实参的个数的一致性D: 赋值语句的左右部类型的相容性8．（ B B ）不是）不是DFA 的成分。

A:A:有穷字母表有穷字母表有穷字母表 B: B: B:初始状态集合初始状态集合C:C:终止状态集合终止状态集合终止状态集合 D: D: D:有限状态集合有限状态集合9．若B 为非终结符，则A α.B β为（为（ B B B ）项目。

《编译原理》考试试卷A适用专业：考试日期：闭卷所需时间：120分钟总分：100分一、填空题：（每空1分，共10分）1.解释系统与编译系统的区别在于和。

2.在编译过程中始终伴随着管理和出错处理过程。

3.语法分析的方法为和两大类。

4.LL(1)文法中不能有和。

5.词法分析器中单词的描述工具是 ,单词的识别工具。

6.算符优先语法分析，在符号栈栈顶出现时，进行规约处理。

二、单选题（每小题2分，共10分）1.词法分析器的加工对象是（）A.中间代码B.单词C.源程序D.元程序2.同正则表达式a*b*等价的文法是（）A. G1:S→aS|bS|εB. G2: S→aSb|εC. G3:S→aS|Sb|εD. G4: S→abS|ε3.文法G[A]:A→bH H→BA B→Ab H→a 不是（）A. 2型文法B. 3型文法C. 0型文法D.1型文法4.算符优先分析每次都是对（）进行规约。

A.短语B.最左素短语C.素短语D.句柄5.( )不是DFA的成分。

A.有穷字母表B. 初始状态集合C.终止状态集合D.有限状态集合三、问答题（第1,5小题每题15分，其余每小题10分，共80分）1. （15分）解释下列术语：（1）编译程序（2）句柄（3）上下文无关文法2.编译程序主要有哪些构成成分？（10分）3.给出描述语言L={a n b2n c m|n,m≥0}的cfg。

（10分）4.（10分）将下图中的DFA M最小化。

5. （15分）判断文法G[S]:S→aHH→aMd|dM→Ab|εA→aM|e是否为LL(1)文法？给出判断过程。

6. （10分）改写文法G[E]：E → E+T|TT →T*F|FF →(E)| a为无左递归文法。

7. （10分）已知文法G[S]为：S→VV→T|ViTT→F|T+FF→)V*|(请指出句型(+(i( 规范推到，并指出句型F+Fi( 中的短语、句柄和素短语。

《编译原理》考试试卷A参考答案适用专业：考试日期：闭卷所需时间：120分钟总分：100分一、填空题：（每空1分，共10分）1. 边翻译边执行和不生成目标代码。

XX大学20XX～202X学年第X学期期末考试《编译原理》试卷（A卷）一单选题 (共3题，总分值15分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。

)1. 一个正则语言只能对应？（B）（5 分）A. 一个正则文法B. 一个最小有限状态自动机C. 一个自然语言D. 一个上下文有关文法2. 一个句型中最左的（A ）称为该句型的句柄。

（5 分）A. 简单短语B. 短语C. 非终结符号D. 终结符号3. Micro语言只有三种语句：（B）、输入语句和输出语句。

（5 分）A. GOTO语句B. 赋值语句C. 条件语句D. 循环语句二填空题 (共3题，总分值15分 )4. 描述高级语言语法的常用方法有__语法图________和BNF范式。

（5 分）5. 对于编译程序而言，输入数据是 __目标程序_______ ，输出数据是 __目标程序_______ 。

（5 分）6. 给出在字母表{0,1}上的“所有以00结尾的符号串的集合”的语言的正则表达式：__（0/1）*00________。

（5 分）三简答题 (共2题，总分值20分 )7. 简述DFA与NFA有何区别。

（10 分）答：解: DFA与NFA的区别主要有两点:1是NFA可以若千个开始状态，而DFA仅只一个开始状态。

2是DFA的映象M是从KX E到K,而NFA的映象M是从KX E到K的子集，即映象 M将产生一个状态集合(可能为空集)，而不是单个状态。

8. 给出与正规式R＝（ab）*（a|b*）ab等价的NFA。

（10 分）答：四综合计算题 (共2题，总分值50分 )9. 判断分析下列文法是否具有二义性：G[P]: P→PaP|PbP|cP|Pe|f （25 分）答：10. 对于下面的文法G[Z]，构造句子(i*i+i)*i的最左和最右推导及相应的语法树。

(1)Z::=E(2)E::=T+E(3)E::=T(4)T::=F*T(5)T::=F(6)F::=(E)(7)F::=i（25 分）解：最左：Z=>E=>T=>F*T=>(E)*T=>(T+E)*T=>(F*T+E)*T=>(i*T+E)*T=>(i*F+E)*T=>(i*i+E)*T =>(i*i+T)*T=>(i*i+F)*T=>(i*i+i)*T=>(i*i+i)*F=>(i*i+i)*i最右：Z=>E=>T=>F*T=>F*F=>F*i=>(E)*i=>(T+E)*i=>(T+T)*i=>(T+F)*i=>(T*i)*i=>(F*T+i)*i =>(F*F+i)*i=>(F*i+i)*i=>(i*i+i)*iXX大学20XX～202X学年第X学期期末考试《编译原理》试卷（B卷）一单选题 (共4题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。

(5)编译过程通常为词法分析、语法分析、词法分析、语义分析与中间代码生成、优化、目标代码生成几个阶段。词法分析不用了（F）
(6) 如要依据文法G构造一个不带回溯的自上而下的语法分析器，文法G不能含有左递归，但允许文法G的部分产生式的右部候选式有公共左因子。（F）
(7) a*(b+c)的后缀表达式为abc+*。（T）
1
1
2
a
aa
bb
未简化的DFA
最小化：
分为：终态集{0,1} 非终态集{2}
{0,1}a={1}{0,1}b= {2}
所以：{0,1}= ｛0｝ ｛2｝ = ｛1｝
a
b
a
（11分）
(3)考虑以下表结构文法G[S]：
S→a|∧|(T)
T→T,S|S
(1)改写G[S]，消去G[S]的左递归。
(2)改写后的文法是否LL(1)文法？给出它的预测分析表。（12分）
a
∧
(
)
,
#
S
S→a
S→∧
S→(T)
T
T→ST’
T→ST’
T→ST’
T’
T’பைடு நூலகம்e
T’→,ST’
(4)考虑以下表结构文法G[S]：
S→a|∧|(T)
T→T,S|S
(1)给出句子(a,(a,a))的最右推导和句柄。
解：S→(T)→(T,(T))→(T,(T,S))→(T,(T,a))→(T,(S,a))
S → ·(T) （ S → a·aS → (·T)
T → ·ST’
S → ·a
S → ·∧
S → ·(T)
T
I5: ） I6:
S → (T·) S → (T)·(

3．表达式（b*5）的逆波兰式表示为。
4．文法的属性有和。
5．根据所涉与程序的范围，优化可分为局部优化、和全局优化三种。
得分
二、选择题（每小题2分，共10分）
1．描述语言{≥1}的文法为（ ）。
A．B．
C．D．ε
2．以10结尾的二进制数串为（ ）。
A．（0|1）*01B．（0|1）*10C．01（0|1）*D．10（0|1）*
()
p();
1; ;
23; p(); a .
A．2和8 B．2和9 C．7和9 D．7和8
得分
三、判断并改错(每小题2分，共10分)
1．文法的二义性和语言的二义性是两个相同的概念。
2.图中运算符，操作符可作为终端结点。
3.和所含的终态结点可以是若干个。
4.存在一个优先关系表就一定存在优先函数与之对应。
G(M)：
M →
T → |
B → | |
D → d |
4．给出赋值语句 *()的四元式表示形式。（5分)
5．设文法G(S)：(15分)
1）构造各非终结符的和集合；
2）构造优先关系表。
3）该文法是算法优先文法吗？
6．设有基本块（5分）
T1：＝2
T2：＝10
T3：＝S－R
T4：＝S＋R
A：＝T2* T4
编译原理考试试卷(A卷)
2009— 2010学年第一学期
科目：编译原理计算机系_计算机科学与技术专业_级班
题号
一
二
三
四
总分
得分
阅卷人
得分
一、填空题（每空1分，共10分）
1．编译程序的工作的过程一般可以划分为词法分析、、、、等几个基本阶段，同时还会伴有和出错处理。

编译原理期末考试试卷（A卷)一、简述编译程序的工作过程.（10)二、构造下列正规式相应的DFA（用状态转换图表示)（15）（1）1(0 ｜1)＊100（2）0*10＊10＊10＊1（3）letter（letter | digit)*三、给出下面语言的相应文法:(15）L1=｛a n b n｜n≥1｝L2={a n b m+n a m| n≥1，m≥0｝四、对下面的文法G:S→a | b | (T）T→T，S | S(1）消去文法的左递归，得到等价的文法G2;（2) 判断文法G2是否LL(1）文法，如果是，给出其预测分析表。

（15）五、设有文法G［A]：A→BCc ｜gDBB→bCDE |εC→DaB | caD→dD |εE→gAf ｜c(1)计算该文法的每一个非终结符的FIRST集和FOLLOW集；(2)试判断该文法是否为LL（1）文法。

(15）六、对表达式文法G:E →E+T ｜TT →T＊F | FF →(E) | I(1）造各非终结符的FIRSTVT和LASTVT集合；(2）构造文法的算符优先关系表。

（15）七、有定义二进制整数的文法如下:L →LB | BB →0 | 1构造一个翻译模式，计算该二进制数的值（十进制的值）。

（15）简述编译程序的工作过程。

（10）编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程,是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：①词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词;②语法分析,根据语言的语法规则,把单词符号串分解成各类语法单位；③语义分析与中间代码产生，即对各类语法单位，分析其汉一并进行初步翻译;④代码优化,以期产生更高效的代码；⑤目标代码生成,把中间代码变换成特定机器上的低级语言指令形式.二、构造下列正规式相应的DFA(用状态转换图表示）（15） （4）（5） （6）（1) (2）(3)三、给出下面语言的相应文法:（15）L1={a n b n ｜ n ≥1｝ L 2=｛a n b m+n a m ｜ n ≥1，m ≥0｝G1：A →aAb |abG1： S →ABA →aAb | abB →bBa | ε四、对下面的文法G：S→a ｜b | （T）T→T，S | S(1) 消去文法的左递归，得到等价的文法G2;(2）判断文法G2是否LL(1）文法,如果是，给出其预测分析表。

二、选择题（每题3分，共30分）1、作为编译程序的源语言不能是____________A、高级语言B、C语言C、低级语言D、Pascal语言2、正规式M1和M2等价是指__________。

A、M1和M2的状态数相等 B、M1和M2的有向边条数相等C、M1和M2所识别的语言集相等 D、M1和M2的状态数和有向边条数相等3、由文法的开始符号经0步或多步推导产生的文法符号序列是_________。

A、短语B、句柄C、句型D、句子4、设∑={0，1}，则∑上所有以1开头，后跟若干个010的字的集合对应的正规式为________。

A．1（010）* B.1（010）+ C.（010）*1 D.（010）+15、文法G(S) :S xSx|y所识别的语言是________。

A．xyx B. (xyx)* C. x n yx n(n>=0) D.x*yx*6、一个________指明了在分析过程中的某时刻所能看到的产生式多大一部分。

A．活前缀B．前缀C．项目D．项目集7、LL(1)文法的条件是______。

A.对形如U->Xl|X2|…|Xn的规则，要求FIRST(Xi)∩FIRST(Xj)=Φ，(i≠j)B.对形如U->Xl|X2|…|Xn的规则，若Xi=>*ε，则要求FIRST(Xj)∩FOLLOW(U)=ΦC．a和bD．都不是8、已知文法G[E]E->TE'E'->+TE'|εT->FT'T'->*FT'|εF一(E)|idFOLLOW(F)=______A.{*，+}B. {#，）} C．{+，#，）} D．{*，+，#,）}9、语法制导的翻译程序能同时进行__________和语义分析。

A、词法分析B、语法分析C、优化D、目标代码生成10、在LR 分析法中，分析栈中存放的状态是识别规范句型_____的DFA 状态。

8.下列文法中，_____是 LL(1)文法。( A.S->aSb|ab C.S->aS|a
9.语言分析方法中的 LR(1)分析法属于_____分析方法。( A.自左至右 B.自上而下 C.自下而上
) D.自右至左 )
10.设有语句 z=x+y，将 x+y 识别为表达式的编译阶段是_____。( A.词法分析 C.语义分析 B.语法分析 D.代码生成 )
14.设有文法的产生式：S->Aa| ，则在自上而
A.FIRST(Aa)∩FOLLOW(P)= B.FIRST(Aa)∩FIRST(P) = C.FIRST(Aa)∪FOLLOW(P)= D.上述 3 个都不是 15.设有文法 G(S 为开始符号)： S->Bp|Dq B->a|Dc D->b|B Follow(B)={_____}。 ( A.a,c B.c,c ) C.p,c,q D.其他答案
) D.8 )
6.识别各类单词的 FA（状态转化图）合并后得到的 FA_____。( A.可能是 NFA 也可能是 DFA C.一定是 NFA B.一定是 DFA D.是最小的 DFA ) D.自右至左
7.语言分析方法中的 LL(1)分析法属于_____分析方法。( A.自左至右 B.自上而下 C.自下而上 ) B.S->ab|Sab D.S->aS|b
18.算符优先分析法从左到右扫描输入串，采用移进-规约的方式，当栈顶出现 _____时进行规约。( A.最左素短语 C.句柄 ) B.素短语 D.直接短语 )
学号____________________ 姓名____________________
19.自下而上语法分析的主要分析动作是_____。( A.匹配 C.规约 B.推导 D.移进-规约 )

试卷答题时限：  分钟 考试形式：闭卷笔试得分统计表：一、单项选择题（请从 个备选答案中选择最适合的一项，每小题 分，共 分）编译程序是对（ ）✌ 汇编程序的翻译  高级语言程序的解释执行 机器语言的执行  高级语言的翻译 词法分析器的输出结果是（ ）✌．单词的种别编码 ．单词在符号表中的位置．单词的种别编码和自身值 ．单词自身值在规范规约中，用（ ）来刻画可规约串。

✌．直接短语 ．句柄 ．最左素短语 ．素短语与正规式☎♋✉ ♌✆ ✉ ☎♍  ♎✆等价的正规式是（ ）✌．♋✉ ☎♍  ♎✆  ♌☎♍  ♎✆．♋✉ ☎♍  ♎✆ ✉  ♌☎♍  ♎✆ ✉．♋✉ ☎♍  ♎✆ ♌✉ ☎♍  ♎✆ ．☎♋  ♌✆ ✉ ♍ ☎♋  ♌✆ ✉ ♎ 若项目集✋ 含有✌✹α·，则在状态 时，仅当面临输入符号♋∈☞☹☹☎✌✆时，才采取✌✹α·动作的一定是（ ）✌．☹✌☹文法 ．☹☎✆ 文法 ．☹☎ ✆文法 ． ☹☎ ✆文法 四元式之间的联系是通过（ ）实现的。

✌ 指示器  临时变量  符号表  程序变量．文法☝： ✹ ⌧ ⌧  ⍓所识别的语言是（ ）✌．⌧⍓⌧ ．☎⌧⍓⌧✆ ✉ ．⌧⏹⍓⌧⏹☎⏹≥ ✆ ．⌧✉⍓⌧✉有一语法制导翻译如下所示：✹ ♌ ✌♌ ☐❒♓⏹♦ ❽ ❾❝✌✹☎ ☐❒♓⏹♦ ❽❾❝✌✹♋ ☐❒♓⏹♦ ❽ ❾❝✹✌♋✆ ☐❒♓⏹♦ ❽ ❾❝若输入序列为♌☎☎☎♋♋✆♋✆♋✆♌，且采用自下而上的分析方法，则输出序列为（ ）✌．     ．    ．关于必经结点的二元关系，下列叙述不正确的是（ ）✌．满足自反性 ．满足传递性 ．满足反对称型 ．满足对称性 ．错误的局部化是指（ ）。

．当发现错误时，跳过错误所在的语法单位继续分析下去．当发现错误时立即停止编译，待用户改正错误后再继续编译二、判断题（每小题 分，共 分）文法☝的一个句子对应于多个推导，则☝是二义性的。

编译原理期末试题及答案一、选择题（每题2分，共20分）1. 编译器的主要功能是将（）代码转换成（）代码。

A. 高级语言，低级语言B. 高级语言，机器语言C. 汇编语言，机器语言D. 机器语言，汇编语言答案：B2. 编译过程中，词法分析的输出是（）。

A. 语法树B. 语法分析表C. 词法单元D. 抽象语法树答案：C3. 在编译原理中，语法分析通常采用（）方法。

A. 递归下降分析B. 动态规划C. 贪心算法D. 回溯算法答案：A4. 语义分析的主要任务是（）。

A. 检查语法错误B. 生成中间代码C. 检查语义错误D. 优化代码答案：C5. 编译器的优化通常发生在（）阶段。

A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D6. 编译器的前端主要负责（）。

A. 代码生成B. 代码优化C. 语法分析D. 目标代码生成答案：C7. 编译器的后端主要负责（）。

A. 代码生成B. 代码优化C. 语法分析D. 词法分析答案：A8. 编译原理中，LL(1)分析方法的特点是（）。

A. 左到右，最右推导B. 左到右，最左推导C. 右到左，最右推导D. 右到左，最左推导答案：B9. 编译原理中，LR(1)分析方法的特点是（）。

A. 左到右，最右推导B. 左到右，最左推导C. 右到左，最右推导D. 右到左，最左推导答案：B10. 编译原理中，语法制导翻译的主要思想是（）。

A. 根据语法树的结构进行翻译B. 根据词法单元进行翻译C. 根据语法分析表进行翻译D. 根据语义分析表进行翻译答案：A二、填空题（每题2分，共20分）1. 编译器中，用于表示语法规则的产生式通常由非终结符、产生符号和（）组成。

答案：产生式右侧2. 在编译原理中，一个文法是（）的，如果它的任何两个产生式都不会导致相同的句柄。

答案：无二义性3. 编译器的词法分析阶段通常使用（）算法来识别和分类词法单元。

答案：有限自动机4. 语法分析阶段，如果一个文法是左递归的，编译器需要使用（）技术来消除左递归。

得分
评卷人
七、请将如下三地址代码程序划分基本块，并作出其程序流图。 （共 10 分）
(1) I:=1; (2) Goto (4); (3) I:=I+1; (4) If I≤N goto (6); (5) Goto (9);
(6) T:=M+I; (7) M:=T; (8) Goto (3);
(9) Write M; (10) Halt
I0
E′→.E E→.aA
E I1 a I2
E′→.E E→a.A A→.cA A→.d
A d c I3 I5
A→d.
d
I4
E→aA.
A→c.A A→.cA A→.d
A
I6
A→cA.
c
(2) 因为识别文法 LR(0)活前缀的 DFA 的状态(即 LR(0)项目集)中没有任何冲突 项目，所以该文法是 LR(0)文法。 构造该文法 LR(0)分析表如下。 ACTION c d GOTO # acc R3 R1 R2 S5 R3 R1 S5 R2 S3 R3 R1 S3 R2 4 R3 R1 6 R2 E 1 A
题号 答案
1．符号串 dbb 是给定文法 G[A]：A→dBC，B→aB| ε，C→bC|b 的句子，试问其活前 缀包括 。 A. ε B. d C. db D. dbb 2．常见的自底而上语法分析方法有 A. 递归下降分析 B. 算符优先分析 。 C. LL(1)预测分析
D. LR 分析
3．已知字母表Σ=｛a ，b｝,下列________是字母表Σ上的正规式。 A. ab+a B. abc|b* C. (a|b)* D. ε 4．若 G 和 G'是两个不同的文法，如果它们是等价的，那么 。 A. G'必须超出 G 所定义语言的范围 B. G'应缩小 G 所定义语言的范围 C. G 和 G'描述的语言相同 D. G'既不超出 G 所定义语言的范围，也不缩小 G 所定义语言的范围 5．一个文法是 LR(0)文法一定也是 A. SLR(1)文法 B. LR(1)文法 。 C. LALR(1)文法

2020-2021《编译原理》期末课程考试试卷A专业： 考试日期： 时间： 总分：100分 闭卷一大题：简答题(每小题6分，共30分)1.什么是文法，按Chomsky 文法分类方法，把文法分成了哪几类？2.编译程序可以分为哪几个阶段，每个阶段的任务是什么？3. 在编译程序中，符号表的功能是什么？4. 什么是代码优化？代码优化的主要技术有哪些？5. 自底向上语法分析方法的基本思想是什么？二大题：若表达式文法G[E]为：E→ E+T|E-T |T T→ T*F | T/F | F F→ (E)|i1. 请构造句型E+T*F 对应的语法树。

(4分)2. 请写出该句型的所有的短语、直接短语、句柄和素短语。

(6分)三大题：已知如图1所示NFA M ，请将M 转换成与其等价的DFA 。

(10分)图1四大题：已知文法G[S]：S→ a | b | (T) T → ST ˊT ˊ→ ，ST ˊ| ε1. 计算该文法的FIRST 、FOLLOW 、SELECT 集合。

(10分)2. 上述文法是LL(1)文法吗?若是，则构造LL(1)分析表。

(10分)五大题：已知文法G[S]：A→ aAb | aAd | ε1. 构造该文法的识别LR(0)活前缀的DFA 。

(10分)2. 说明该文法不是LR(0)文法，是SLR(1)文法，并构造SLR(1)分析表。

(10分)六大题：根据以下的基本块：B:=3 D:=A+C E:=A*C F:=D+E G:=B*F H:=A+C I:=A*C J:=H+I K:=B*5 L:=K+J M:=L1．构造基本块对应的DAG 图。

(5分)2．若G ，M ，L 在基本块后要引用，写出优化后的代码(5分)。

院系： 专业班级： 姓名： 学号：装 订 线2020-2021《编译原理》期末课程考试试卷答案一大题：1. 答：词法分析阶段：读源程序，对字符流进行扫描和分解，识别出一个个单词。

语法分析阶段：将单词分解成各类语法短语。

期末考试试卷（A）卷一、填空题（每小题2分，共20分）1、字母表∑，用∑*表示∑上所有有穷长的串集合，∑*称为∑的①。

2、设z=abc，则z的固有头是①。

3、如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则叫①。

4、设∑＝{a,b}，∑上的正规式(a|b)(a|b) 相应的正规集为①5、NFA的映象f是从"状态×字"映射到"状态子集"，f为①值函数。

6、LR分析是按规范句型的①为可归约串。

7、结点的①属性值由该结点的兄弟结点和父结点的属性值计算。

8、如果分析树中一结点的属性b依赖于属性c，那么这个结点的属性b的语义规则的计算必须在定义属性c的语义规则的计算①。

9、对于栈式符号表，引入一个显示嵌套层次关系表- ①表，该表总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。

10、任一有向边序列n1 → n2,n2 → n3,…,nk-1 → nk为从结点n1到结点nk的一条通路。

如果n1=nk，则称该通路为①。

二、单项选择（每小题2分，共14分）1、乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。

其中3型文法也称为（）。

A．上下无关文法 B.正规文法C．上下文有关文法 D.无限制文法2、生成非0开头的正偶数集的文法是（）。

A． Z::=ABC B. Z::=ABCC::=0|2|4|6|8 C::=0|2|4|6|8B::=BA|B0|ε B::=BA|B0|0A::=1|2|3|…|9 A::=1|2|3|…|9C. Z::=ABC|2|4|6|8D. Z::=ABC|2|4|6|8C::=0|2|4|6|8 C::=0|2|4|6|8B::=BA|B0|0 B::=BA|B0|εA::=1|2|3|…|9 A::=1|2|3|…|93、简单优先分析法从左到右扫描输入串,当栈顶出现（）时进归约。

A.素短语B.直接短语C.句柄D.最左素短语4、同心集合并有可能产生新的（）冲突。

编译原理期末考试试题一、选择题（每题2分，共20分）1. 在编译原理中，词法分析器的作用是将源程序的字符序列转换为______。

A. 语法树B. 抽象语法树C. 标记D. 语义分析树2. 以下哪个不是编译器的组成部分？A. 词法分析器B. 语法分析器C. 代码生成器D. 操作系统3. 编译过程中的语义分析阶段主要完成的任务是______。

A. 检查语法结构的正确性B. 检查类型正确性C. 优化代码D. 生成目标代码4. 以下哪个是自顶向下的语法分析方法？A. LR分析B. LL分析C. CYK算法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. 词法文法二、简答题（每题10分，共30分）1. 简述编译器的五个主要阶段，并简要描述每个阶段的主要任务。

2. 解释什么是语法分析树，并说明它与抽象语法树的区别。

3. 描述代码优化的目的，并给出一个简单的代码优化示例。

三、计算题（每题25分，共50分）1. 给定一个简单的算术表达式，如“a + b * c - d”，并假设变量a, b, c, d均已在符号表中定义。

请写出一个简单的词法分析器算法，将该表达式转换为标记序列。

《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．编译程序是对高级语言程序的解释执行。

(×)2．一个有限状态自动机中，有且仅有一个唯一的终态。

(×)3．一个算符优先文法可能不存在算符优先函数与之对应。

(√)4．语法分析时必须先消除文法中的左递归。

(×)5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。

(√)6．逆波兰表示法表示表达式时无须使用括号。

(√)7．静态数组的存储空间可以在编译时确定。

(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。

(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。

(×)10．一个语义子程序描述了一个文法所对应的翻译工作。

(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。

A．()单词的种别编码B．()单词在符号表中的位置C．()单词的种别编码和自身值D．()单词自身值2．正规式M1和M2等价是指_____。

A．()M1和M2的状态数相等B．()M1和M2的有向边条数相等C．()M1和M2所识别的语言集相等D．()M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_____。

A．()xyx B．()(xyx)*C．()xnyxn(n≥0)D．()x*yx*4．如果文法G是无二义的，则它的任何句子α_____。

A．()最左推导和最右推导对应的语法树必定相同B．()最左推导和最右推导对应的语法树可能不同C．()最左推导和最右推导必定相同D．()可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握______。

A．()源程序B．()目标语言C．()编译方法D．()以上三项都是6．四元式之间的联系是通过_____实现的。