编译原理期末考试卷

一． 填空题（每空2分，共20分）1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。

2. 规范规约是最（3）规约。

3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。

另外还有（6）和出错处理。

4．表达式x+y*z/(a+b)的后缀式为 （7） 。

5．文法符号的属性有综合属性和 （8）。

6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址计算公式为（9）。

7．局部优化是局限于一个（10）范围内的一种优化。

二． 选择题（1-6为单选题，7-8为多选题，每问2分，共20分）1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组（ ）。

A ． 字符串B ． 产生式C ． 开始符号D ． 文法 2.程序的基本块是指（ ）。

A ． 一个子程序B ． 一个仅有一个入口和一个出口的语句C ． 一个没有嵌套的程序段D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。

A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。

A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。

A ． 四元式序列B ． 间接三元式序列C ． 二元式序列D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。

A ． 唯一的 B ． 不唯一的 C ． 可能唯一，也可能不唯一7．如果在文法G中存在一个句子，当其满足下列条件（）之一时，则称该文法是二义文法。

编译原理期末考试试卷（D卷）编译原理期末考试试卷（D 卷）⼀、单项选择题（每⼩题2分，共30分）1、编译程序是对_ _____程序进⾏翻译。

A.⾃然语⾔B.⾼级语⾔C.汇编语⾔D.机器语⾔2、描述语⾔L={ a n b n | n ≥。

3、设有⽂法G=({b},{S,B}, S, { S →bB , B →bS |ε} )，该⽂法描述的语⾔是。

A. L(G)={b n | n ≥1 } B. L(G)={ b 2n | n ≥1} C. L(G)={ b 2n+1 | n ≥0} D. L(G)={ b 2n | n ≥0} 4、下图DFA 所识别的语⾔为_______ 。

A. a 3n+1(n ≥0)B. a 2n+1(n ≥0)C. a 2n+1(n ≥1)D. a 3n+1(n ≥1) 5、下述正规式等价的是。

A.(a|b)*与a *|b *B.(ab)*与a *b *C.(a|b)*与(ab)*D.(a|b)*与(a *b *)*6、如果⽂法G 中没有形如 A →…BC …的产⽣式，其中A ，B ，C 表⽰⾮终结符，则称⽂法G 为 __________。

A.算符⽂法B.算符优先⽂法C.LR(0)⽂法D. LL(1)⽂法 7、算符优先分析法从左到右扫描输⼊串，采⽤移进-归约的⽅式，当栈顶出现___________时进⾏归约。

A. 素短语B.最左素短语C. 句柄D. 直接短语 8、LR 语法分析栈中存放的状态是识别⽂法规范句型__________的DFA 状态。

A. 句柄B.前缀C. 活前缀D. 项⽬A. S →AB A →Aa | a B →Bb | b C. S →aSb | ab D. S →aSb | ε9、中缀表达式a↑(b / d-c)的后缀式是_________。

A.abdc-/↑B. abd/c-↑C. ab/dc-↑D. abdc/-↑10、以下说法正确的是_________。

《编译原理》期末试题（四）1、 从优化的范围的角度，优化可以分哪两类？对循环的优化可以有哪三种？ 答：从优化的范围的角度，优化可以分为局部优化和全局优化两类； 对循环的优化有三种：循环不变表达式外提、归纳变量删除与计算强度削减。

2、写出表达式a=b*c+b*d 对应的逆波兰式、四元式序列和三元式序列。

答：逆波兰式： abc*bd*+:= 四元式序列：三元式序列: OP ARG1 ARG2 (1) (*， b ， c ， t 1) (1) (* b ， c ) (2) (*， b ， d ， t 2) (2) (* b ， d ) (3) (+， t1， t 2，t 3) (3) (+ (1)， (2)) (4) (:=， t3， /， a)(4) (:= (3)， a)3、对于文法G(S):）Ma L a |(L M bMb S →→→答：1） b Ma b Lb b bMb S )((⇒⇒⇒ 2） 短语: Ma)， (Ma)， b(Ma)b 直接短语: Ma) 句柄: Ma)三、 设有字母表{a ，b}上的正规式R=(ab|a)*。

解：（1）（（3）对（2）得到的DFA 化简，合并状态0和2 为状态2：（4）令状态1和2分别对应非终结符B 和AG: A →aB|a|ε； B →aB|bA|a|b|ε；可化简为：G: A →aB|ε；B →aB|bA|ε四、 设将文法G 改写成等价的LL(1)文法，并构造预测分析表。

G ：S→S*a T|aT|*aT ； T →+a T|+a解：消除左递归后的文法G ’: S →aTS ’|*aTS ’S ’→*aTS ’|εT →+aT|+a提取左公因子得文法G ’’: S →aTS ’|*aTS ’S ’→*aTS ’|ε T →+aT ’T ’→T|ε Select(S →aTS ’)={a} Select(S →*aTS ’)={*}Select(S →aTS ’)∩Select(S →*aTS ’)=Ф Select(S ’→*aTS ’)={*}Select(S ’→ε)=Follow(s ’)={#}Select(S ’→*aTS ’)∩Select(S ’→ε)= Ф Select(T →+aT ’)={+}Select(T ’→T)=First(T) ={+}Select(T ’→ ε)=Follow(T ’)={*,#}Select(T ’→T)∩Select(T ’→ε)= Ф 所以该文法是LL(1)文法。

《编译原理》模拟试题一一、是非题(请在括号内，正确的划错误的划X)(每个2分，共20分)1•计算机高级语言翻译成低级语言只有解释一种方式。

(X)2.在编译中进行语法检查的目的是为了发现程序中所有错误。

(X)3.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。

(丁 )4.正则文法其产生式为A->a , A->Bb, A.BGVN , a、beVT o (X)5.每个文法都能改写为LL(1)文法。

(V)6.递归下降法允许任一非终极符是直接左递归的。

(V)7.算符优先关系表不一定存在对应的优先函数。

(X)8.自底而上语法分析方法的主要问题是候选式的选择。

(X)9.LR法是自顶向下语法分析方法。

(X)10.简单优先文法允许任意两个产生式具有相同右部。

(X)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)1.一个编译程序中，不仅包含词法分析，_____ ,中间代码生成，代码优化，目标代码生成等五个部分。

A.()语法分析B.()文法分析C.()语言分析D.()解释分析2.词法分析器用于识别_____ oA.()字符串B.()语句C.()单词D.()标识符3 •语法分析器则可以发现源程序中的______ oA.()语义错误B.()语法和语义错误C.()错误并校正D.()语法错误4.下面关于解释程序的描述正确的是。

(1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于COBOL 和FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的A. ( ) (1) (2)B. () (1)C. () (1)⑵(3)D.()⑵⑶5. _________________________________________ 解释程序处理语言时，大多数采用的是 ___________________________________ 方法。

一、填空（每空0.5分，共 10分）1、编译程序的功能是是对(高级语言)进行翻译，使之生成目标代码。

2、编译程序的工作过程一般划分为5个阶段：（词法分析）、语法分析、语义分析与中间代码生成，（代码优化）及目标代码生成。

另外还有表格管理和（出错处理）。

3、一个上下文无关文法所含四个组成部分是一组终结符号、一组（非终结符号）、一个开始符号、（一组产生式）。

4、设G是一个给定的文法，S是文法的开始符号，如果S=> x（其中x∈V*），则称x 是文法的一个（句型）。

5、规范归约中的可归约串是指句柄，算符优先分析中的可归约串是指（最左素短语）。

6、在编译过程中,可采用的中间代码形式有（）、（）、（）等。

（三元式、间接三元式、四元式、逆波兰式、抽象语法树）（任选三个即可）7、语法分析最常用的两类方法是（自上而下）和（自下而上）分析法。

8、表达式（a+b)*c的后缀表达式为（ab+c*）。

9、符号表的结构一般有（线性表）、（有序表）、（散列表或哈希表）等。

分别使用的查找方法有（顺序查找）、（折半查找）和（哈希法查找）10、代码优化的目的是（减少代码的时空开销）。

11、寄存器是CPU内部的（存储单元），其访问时间小于CPU对内存的访问时间。

12、如果一个句子存在两棵不同的语法树就说明该句子是（二义性）的。

二、选择题（每题1分，共10分）1、文法的开始符号经多步推导产生的文法符号序列(仅包含终结符)是文法的（D ）。

A.短语B.句柄C.句型D.句子2、构造编译程序应掌握（D）。

A.源程序B.目标语言C.编译方法D.以上三项都是3、不属于循环优化的主要方法的是（B）。

A.强度削弱B.删除无用赋值C.删除归纳变量D.代码外提4、使用（A）可以定义一个程序的含义。

A.语义规则B.词法规则C.产生规则D.左结合规则5、优化可生成（D）的目标代码。

A ．运行时间较短B ．占用存储空间较小C ．运行时间短但占用内存空间大D ．运行时间短且占用存储空间小6、有文法G ：E →E*T|T ， T →T+i|i ,则输入串1+2*8+6按该文法G 归约,其值为（B ）。

编译原理期末考试试题（卷）（C卷）编译原理期末考试试卷（ C 卷）⼀、单项选择题（每⼩题2分，共30分）1、编译程序是对_ _____程序进⾏翻译。

A. ⾃然语⾔B. 汇编语⾔C. ⾼级语⾔D. 机器语⾔2、描述语⾔L={ a m b n | m ≥1。

3、设有⽂法G=({b},{S,B}, S, { S →bB , B →bS |ε} )，下列哪个符号串不是该⽂法的句⼦。

A. bB. bbC. bbbD. bbbbb 4、下图DFA 所识别的语⾔为_______ 。

A. 含有偶数个0偶数个1的⼆进制串 B. 含有偶数个0奇数个1的⼆进制串 C. 含有奇数个0偶数个1的⼆进制串 D. 含有奇数个0奇数个1的⼆进制串 5、下述正规式等价的是。

A.(a|b)*与(a *b *)*B.(ab)*与a *b *C.(a|b)*与(ab)*D. (a|b)*与a *|b *6、设有⼀个LR(1)项⽬集I ={ X →α.bB,a B →α.,a }则该项⽬集 __________。

A.不含冲突项⽬B. 含有移进-归约冲突C.含有归约-归约冲突D. 含有移进-待约冲突 7、LR 语法分析栈中存放的状态是识别⽂法规范句型__________的DFA 状态。

A. 句柄B.前缀C. 活前缀D. 项⽬A. S →ABA →Aa | aB →Bb | b C. S →aSb | ab D. S →aSb | ε8、有⽂法如S → r DD → D,i | i则FIRSTVT(D)=_________。

A.{ i }B. {i ,}C. { i r }D. { i r ,}9、有⽂法如 S → r DD → D,i | i则 i 和，的优先关系是_________。

A.没有优先关系B. 等于C. 低于D. ⾼于10、算符优先分析法从左到右扫描输⼊串，采⽤移进-归约的⽅式，当栈顶出现___________时进⾏归约。

A. 素短语B.C.D. 直接短语11、局部优化是局限于⼀个_________范围内的⼀种优化。

编译原理期末试题及答案一、选择题（每题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. 语法分析阶段，如果一个文法是左递归的，编译器需要使用（）技术来消除左递归。

编译原理期末考试试题一、选择题（每题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均已在符号表中定义。

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

1、试为表达式 w+（a+b)＊（c+d/(e-10）+8) 写出相应的逆波兰表示。

2、写出表达式a＋b＊(c-d)/e的逆波兰式和三元序列。

3、写出表达式a:=（b+c)＊e+(b+c)/f的逆波兰式和三元序列。

4、已知文法G(S)及相应翻译方案S→aAb ｛print “1”}S→a {print “2”｝A→AS {print “3”｝A→c ｛print “4"｝输入acab, 输出是什么？5、已知文法G（S)S→bAaA→(B | aB→A a)写出句子b（aa）b的规范归约过程.6、已知文法G［S］S→S*aF | aF ｜＊aFF→+aF | +a消除文法左递归。

1、设文法G（S）：S→^ ｜ a | （T）T→T,S ｜ S⑴ 消除左递归;⑵ 构造相应的FIRST和FOLLOW集合;⑶ 构造预测分析表2.语句 if E then S(1）改写文法，使之适合语法制导翻译；（2）写出改写后产生式的语义动作。

4。

设某语言的for语句的形式为for i：＝E（1) to E（2) do S其语义解释为i：＝E(1）LIMIT:＝E（2）again: if i＜＝LIMIT thenBeginS；i：＝i＋1goto againEnd；（1）写出适合语法制导翻译的产生式;（2)写出每个产生式对应的语义动作。

7。

已知文法G(S)S→a ｜ ^ | （T）T→T，S ｜ S（1) 给出句子(a，（a,a))的最左推导;（2) 给出句型（(T,S），a）的短语, 直接短语，句柄。

8。

对于 C 语言do S while E语句(1）改写文法，使之适合语法制导翻译;(2）写出改写后产生式的语义动作.9。

已知文法G(S）S→aAcBeA→Ab｜ bB→d（1)给出句子abbcde的最左推导及画出语法树；（2）给出句型aAbcde的短语、素短语。

10。

设文法G（S）:S→（T) | aS | aT→T,S ｜ S⑴消除左递归和提公共左因子；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表。

编译原理试题计算机学院2001级班学号姓名一选择题（12分）【】1．词法分析器的输入是。

A．符号串B．源程序C．语法单位D．目标程序【】2．两个有穷自动机等价是指它们的。

A．状态数相等B．有向弧数相等C．所识别的语言相等D．状态数和有向弧数相等【】3．文法G：S → xSx | y 所识别的语言是。

A．xy*x B．(xyx)* C．xx*yxx* D．x*yx*【】4．设a,b,c为文法的终结符，且有优先关系a≡b和b≡c，则。

A．必有a≡c B．必有c≡aC．必有b≡a D．选项A、B和C都不一定成立【】5．若状态k含有项目“A→α.”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A →α”归约的语法分析方法是。

A．ALR分析法B．LR(0)分析法C．LR(1)分析法D．SLR(1)分析法【】6．生成中间代码时所依据的是。

A．语法规则B．词法规则C．语义规则D．等价变换规则【】7．表达式（┐a∨b）∧（c∨d）的逆波兰表示为。

A．┐ab∨∧cd∨B．a┐b∨cd∨∧C．ab∨┐cd∨∧D．a┐b∨∧cd∨【】8．基本块。

A．只有一个入口语句和一个出口语句B．有一个入口语句和多个出口语句C．有多个入口语句和一个出口语句D．有多个入口语句和多个出口语句二判断题（6分。

认为正确的填“T”，错的填“F”）【T】1．同心集的合并有可能产生“归约/归约”冲突。

【T】2．一个文法所有句子的集合构成该文法定义的语言。

【】3．非终结符可以有综合属性，但不能有继承属性。

【T】4．逆波兰表示法表示表达式时无需使用括号。

【】5．一个有穷自动机有且只有一个终态。

【】6．若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。

三填空题（8分）1．最常用的两类语法分析方法是自顶向下和自低向上分析法。

2．对于文法G[E]：E→T|E+T T→F|T*F F→P↑F|P P→(E)|i,句型T+T*F+i 的直接短语为，句柄为。

一、填空题（每空2分，共20分）1．编译程序首先要识别出源程序中每个单词,然后再分析每个句子并翻译其意义.2．编译器常用的语法分析方法有自底向上和自顶向下两种。

3．通常把编译过程分为分析前端与综合后端两大阶段。

词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合.4．程序设计语言的发展带来了日渐多变的运行时存储管理方案,主要分为两大类，即静态存储分配方案和动态存储分配方案。

5．对编译程序而言，输入数据是源程序，输出结果是目标程序.1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译.2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。

4．一个LL（1）分析程序需要用到一张分析表和符号栈。

5．后缀式abc-/所代表的表达式是a/（b—c）。

二、单项选择题（每小题2分，共20分）1．词法分析器的输出结果是__C。

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

A．M1和M2的状态数相等 B．M1和M2的有向边条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_C____.A．xyx B．（xyx）* C．xnyxn（n≥0）D．x*yx*4．如果文法G是无二义的，则它的任何句子α_A____.A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。

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