下载文档原格式
编译原理试题及答案一、选择题1. 编译器的主要功能是什么？A. 程序设计B. 程序翻译C. 程序调试D. 数据处理答案：B2. 下列哪一项不是编译器的前端处理过程？A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D3. 在编译原理中，词法分析器的主要作用是什么？A. 识别程序中的关键字和标识符B. 将源代码转换为中间代码C. 检查程序的语法结构D. 确定程序的运行环境答案：A4. 语法分析通常采用哪种方法？A. 自顶向下分析B. 自底向上分析C. 正则表达式匹配D. 直接解释执行答案：B5. 语义分析的主要任务是什么？A. 检查程序的语法结构B. 检查程序的类型安全C. 识别程序中的变量和常量D. 将源代码转换为机器代码答案：B二、简答题1. 简述编译器的工作原理。
答案：编译器的工作原理主要包括以下几个步骤：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。
词法分析器将源代码分解成一系列的词素；语法分析器根据语法规则检查词素序列是否合法；语义分析器检查程序的语义正确性；中间代码生成器将源代码转换为中间代码；代码优化器对中间代码进行优化；最后，目标代码生成器将优化后的中间代码转换为目标机器代码。
2. 什么是词法分析器，它在编译过程中的作用是什么？答案：词法分析器是编译器前端的一个组成部分，负责将源代码分解成一个个的词素（tokens），如关键字、标识符、常量、运算符等。
它在编译过程中的作用是为语法分析器提供输入，是编译过程的基础。
三、论述题1. 论述编译器中的代码优化技术及其重要性。
答案：代码优化是编译过程中的一个重要环节，它旨在提高程序的执行效率，减少资源消耗。
常见的代码优化技术包括：常量折叠、死代码消除、公共子表达式消除、循环不变代码外提、数组边界检查消除等。
代码优化的重要性在于，它可以显著提高程序的运行速度和性能，同时降低程序对内存和处理器资源的需求。
四、计算题1. 给定一个简单的四则运算表达式，请写出其对应的逆波兰表达式。
1、正规文法又称 DA、0型文法B、1型文法C、2型文法D、3型文法2、对于无二义性的文法，规范归约是 BA. 最左推导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和iB、P和P+TC、i和P+T+iD、P和P7、四元式之间的联系是通过B实现的A.指示器B.临时变量C.符号表D.程序变量8、程序语言的单词符号一般可以分为保留字、标识符、常数、运算符、界符等等。
9、下列 B 优化方法是针对循环优化进行的。
A．删除多余运算B．删除归纳变量C．合并已知量D．复写传播10、若文法G 定义的语言是无限集，则文法必然是 AA、递归的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不属于乔姆斯基观点分类的文法。
第一章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、编译程序工作过程中，第一段输入就是，最后阶段得输出为程序。
4、编译程序就是指将程序翻译成程序得程序。
单选解答1、将编译程序分成若干个“遍”就是为了使编译程序得结构更加清晰，故选b。
2、构造编译程序应掌握源程序、目标语言及编译方法等三方面得知识，故选d。
3、对编译而言，变量既持有左值又持有右值，故选c。
4、编译程序打交道最多得就就是各种表格，因此选d。
5、目标代码包括汇编指令代码、可重定位指令代码与绝对指令代码3种，因此不就是目标代码得只能选d。
第2章形式语言基础2.2 设有文法G[N]: N -> D | NDD -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(1)G[N]定义的语言是什么?(2)给出句子0123和268的最左推导和最右推导。
解答：(1)L(G[N])={(0|1|2|3|4|5|6|7|8|9)+} 或L(G[N])={α| α为可带前导0的正整数}(2)0123的最左推导：N ⇒ ND ⇒ NDD ⇒ NDDD ⇒ DDDD ⇒ 0DDD ⇒ 01DD ⇒ 012D ⇒ 0123 0123的最右推导：N ⇒ ND ⇒ N3 ⇒ ND3 ⇒ N23 ⇒ ND23 ⇒ N123 ⇒ D123 ⇒ 0123268的最左推导：N ⇒ ND ⇒ NDD ⇒ DDD ⇒ 2DDD ⇒ 26D ⇒ 268268的最右推导：N ⇒ ND ⇒ N8 ⇒ ND8 ⇒ N68 ⇒ D68 ⇒ 2682.4 写一个文法，使其语言是奇数的集合，且每个奇数不以0开头。
解答：首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。
如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。
分别用3个非终结符来产生句子的第1位、中间部分和最后一位。
引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。
N -> 1 | 3 | 5 | 7 | 9 | BNB -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B02.7 下面文法生成的语言是什么？G1：S->ABA->aA| εB->bc|bBc G2：S->aA|a A->aS解答：B ⇒ bcB ⇒ bBc⇒ bbccB ⇒ bBc⇒ bbBcc ⇒ bbbccc……A ⇒εA ⇒ aA ⇒ aA ⇒ aA ⇒ aaA ⇒ aa……∴S ⇒ AB ⇒ a m b n c n , 其中m≥0,n≥1即L(G1)={ a m b n c n | m≥0,n≥1} S ⇒ aS ⇒ aA ⇒ aaS ⇒ aaaS ⇒ aA ⇒ aaS ⇒ aaaA ⇒aaaaS ⇒ aaaaa ……∴S ⇒ a2n+1 , 其中n≥0即L(G2)={ a2n+1 | n≥0}2.11 已知文法G[S]: S->(AS)|(b)A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。
一、填空题:1-01.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，之间代码生成,代码优化等几个基本阶段,同时还会伴有表格处理和出错处理.1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序,则其翻译程序称为编译程序.1-03.编译方式与解释方式的根本区别在于是否生成目标代码.1-04.翻译程序是这样一种程序,它能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序. 1-05.对编译程序而言,输入数据是源程序,输出结果是目标程序.1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段: 编译阶段和运行阶段.如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段: 编译阶段, 汇编阶段和运行阶段.1-07.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。
1-08.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。
其中，词法分析器用于识别单词。
1-09.编译方式与解释方式的根本区别为是否生成目标代码。
2-01.所谓最右推导是指：任何一步αβ都是对α中最右非终结符进行替换的。
2-02.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。
2-03.产生式是用于定义语法成分的一种书写规则。
2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈V T*} 。
2-05.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法的一个句型。
2-06.设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V T*),则称x是文法的一个句子。
3-01.扫描器的任务是从源程序中识别出一个个单词符号。
4-01.语法分析最常用的两类方法是自上而下和自下而上分析法。
本书习题可分为思考题和必做题，这里仅给出必做题的参考答案。
习题11-1至1-11均为思考题。
习题22-1至2-14均为思考题。
习题33-1至3-13均为思考题。
习题44-1至4-4均为思考题。
4-5 解：上下文有关文法（1型文法），产生的语言L（G）{=a i b i c i | i≥1,i为整数} 4-6 解：3型文法，L（G）={a i | i≥1,i为奇数}4-7 解：2型文法，L（G）={a i b i | i≥1,i为整数}4-8 解：1型文法，L（G）={a i b i c i | i≥1,i为整数}4-9 解：1. 最左推导最右推导S⇒ (A) ⇒ (B) ⇒(SdB) S⇒ (A) ⇒ (B) ⇒ (SdB)⇒ ((A)dB) ⇒ ((B)dB) ⇒ (SdS) ⇒ (Sda)⇒ ((S)dB) ⇒ ((b)dB) ⇒ ((A)da ⇒ ((B)da)⇒ ((b)dS) ⇒ ((b)da) ⇒ ((s)da⇒ ((b)da)2. 语法树4-10解：1. 因为存在推导S ⇒ SbF ⇒ SbP ⇒ Sbc ⇒ Fbc ⇒ FaPbc所以FaPbc是文法G (S) 的一个句型。
2. 语法树4-11解：因为串aaabaa可有下列两棵不同的语法树所以文法G (S)是二义文法。
4-12解：因为串i (*可有下列两棵不同的语法树4-13解：假定所设计的语言面向的机器为一般通用机。
按照题目给出的问题，如果不考虑输入和输出语句，那么所要设计的语言仅包含字符串数据类型和赋值语句。
语言设计如下：<程序>→<分程序><分程序>→begin<语句说明表>；<执行语句>end<说明语句表>→<说明语句>|<说明语句表>；<说明语句><说明语句>→<变量说明><变量说明>→string<变量表>说明：string是变量的类型，表示变量为字符串。
编译原理课后习题答案编译原理习题答案习题11.1翻译程序：把⽤某种程序设计语⾔（源语⾔）编写的程序（源程序）翻译成与之等价的另⼀种语⾔（⽬标语⾔）的程序（⽬标程序）。
编译程序：⼀种翻译程序，将⾼级语⾔编写的源程序翻译成等价的机器语⾔或汇编语⾔的⽬标程序。
1.2词法分析、语法分析、语义分析和中间代码⽣成、代码优化、⽬标代码⽣成1.3词法分析：根据语⾔的词法规则对构成源程序的符号进⾏扫描和分解，识别出⼀个个的单词。
语法分析：根据语⾔的语法规则，把单词符号串分解成各类语法单位。
语义分析及中间代码⽣成：对语法分析识别出的语法单位分析其含义，并进⾏初步翻译。
代码优化：对中间代码进⾏加⼯变换，以产⽣更⾼效的⽬标代码。
⽬标代码⽣成：将中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或会变指令代码。
以上5个阶段依次执⾏。
习题22.1 （1）有穷⾮空的符号集合（2）利⽤产⽣是规则A->v将A替换为v时与A的上下⽂⽆关。
（3）略（4）推导是把句型中的⾮终结符⽤⼀个产⽣是规则的右部开替代的过程；直接推导是将⾮终结符的替代结果只⽤了⼀次产⽣式规则。
（5）略（6）⼀个句型的最左直接短语（7）如果⼀个⽂法存在某个句⼦对应两棵不同的语法树或有两个不同的最左（右）推导，则称这个⽂法是⼆义的。
2.2（1）VN =｛Z,A,B｝ VT ={a,b,c,d,e}（2）abbcde,abbbcde是，acde不是。
2.3 （1）L[G]={d|n≥1,m≥0}（2）2.4 （1） A=>B=>c=>fAg=>fBg=>fCg=>feg（2）A=>AaB=>AaC=>Aae=>Bae=>BcCae=>Bceae=>Cceae=>eceae（3）A=>B=>BcC=>BcfAg=>BcfAaBg=>BcfAaCg=>BcfAaeg=>BcfBaeg =>BcfCaeg=>Bcfeaeg=>Ccfeaeg=>ecfeaeg（3）中题⽬有错应为C fCg|e2.5L[G]=｛a?b?c?|aab,n≥2｝2.6 (1)Z→AB A→Aa|ε B→Bb|ε(2)Z→aZb|ab(3)Z→aAb A→aAb|b(4)Z→AB A→aAb|ab B→cB|ε(5)Z→aaAb|ab Z→aaBb|bb A→aaAb|ab B→aaBb|bb2.7 ⼀位数：Z→2|4|6|8两位数：Z→AB A→1|2|3|4|5|6|7|8|9 B→0|2|4|6|8三位以上：Z→ACB A→1|2|3|4|5|6|7|8|9 B→0|2|4|6|8 C→CDD→0|1|2|3|4|5|6|7|8|92.8证明：E=>E+T=>E+T*F短语：T*F E+T*F 直接短语：T*F 句柄：T*F2.9 语法树： E 短语：E*T , (E*T) , F↑(E*T) ，F ,E* F↑(E*T)E *F 直接短语：E*T , FT ↑ F 句柄：FF ( E )E * T2.10（1）语法树（2）直接短语：a , ZZ 句柄：Z( L )L , ZZ ( L )Za2.11最左推导：Z=>ZaB=>BaB=>B+AaB=>A+AaB=>(+)Z*aB=>(+)ZaB*aB =>(+)+aB*aB=>(+)+aA*aB=>(+)+a(*aB=>(+)+a(*aA=>(+)+a(*a(直接短语：（，+句柄：(2.12(1) S=>iSeS=>iiSeS=>iiIeS=>iiIeIS=>iS=>iiSeS=>iiIeS=>iiIeI(2) S=>SaS=>cSaS=>cfaS=>cfafS=>cS=>cSaS=>cfaS=>cfaf(3) E=>EOE=>EOEOE=>iOEOE=>i+EOE=>i+iOE=>i+i-E=>i+i-iE=>EOE=>iOE=>i+E=>i+EOE=>i+iOE=>i+i-E=>i+i-i2.13 Z→aABZ|cCACdA→bAB|aZA|cCCB→bAB|CzbC→cZ|c习题33.1(1)确定的有限⾃动机(2)不确定的有限⾃动机(3)正规集是⼀类特殊的单词集合，正规式是正规集的描述⼯具 3.2 (1) (1|2|3|4|5|6|7|8|9|0)*(1|3|5|7|9) (2) 11(0|1)*00 3.3 证明：b *(a|b)+=｛a,b,ab,ba,aa,bb …｝ (a|b)+=｛a,b,ab,ba,aa,bb …｝ 3.4 (1)(2)DDDD3.5(1) (2)(3)3.6(1) (01|10) *(01|10)(2) (0(1|00)*)|003.7(1) Z →1AB (2)Z →ABA →(0|1)A A →0A|εA →0|1B →(0|1)B|ε B →0B B →ε3.8 r=a(a|b )*bb3.9 Z →1BB →0Z|0 Z →0Z|ε3.10 3.11DDD习题44.1 (1)若⽂法G[Z]满⾜①⽂法不含左递归②③(2)4.2(1) First(S)={a,d} First(B)={a,d,c,ε}First(A)={a,d,e,c} First(D)={a,d,ε}Follow(S)={#,a,b,d,e} Follow(B)={a,d}Follow(A)={b} Follow(D)={e,a,d,b}(2) 不是4.3 (1) 证明： First(Z)={a,b,c} Follow(S)={#,a,b,c,d} First(A)={a,b,c,d} Follow(A)={ #,a,b,c,d }First(B)={a,d,c} Follow(B)={ a,b,c,d } 是LL(1)⽂法。
第一章练习题（绪论）一、选择题1．编译程序是一种常用的软件。
A) 应用B) 系统C) 实时系统D) 分布式系统2．编译程序生成的目标代码程序是可执行程序。
A) 一定B) 不一定3．编译程序的大多数时间是花在上。
A) 词法分析B) 语法分析C) 出错处理D) 表格管理4．将编译程序分成若干“遍”将。
A)提高编译程序的执行效率；B)使编译程序的结构更加清晰，提高目标程序质量；C)充分利用内存空间，提高机器的执行效率。
5．编译程序各个阶段都涉及到的工作有。
A) 词法分析B) 语法分析C) 语义分析D) 表格管理6．词法分析的主要功能是。
A) 识别字符串B) 识别语句C) 识别单词D) 识别标识符7．若某程序设计语言允许标识符先使用后说明，则其编译程序就必须。
A) 多遍扫描B) 一遍扫描8．编译方式与解释方式的根本区别在于。
A) 执行速度的快慢B) 是否生成目标代码C) 是否语义分析9．多遍编译与一遍编译的主要区别在于。
A)多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部分只执行一遍；B)一遍编译是对源程序分析一遍就立即执行，而多遍编译是对源程序重复多遍分析再执行；C)多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直接分析执行；D)多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调用执行完成。
10．编译程序分成“前端”和“后端”的好处是A)便于移植B)便于功能的扩充C)便于减少工作量D)以上均正确第二章练习题（文法与语言）一、选择题1．文法 G 产生的 (1) 的全体是该文法描述的语言。
A.句型B. 终结符集C. 非终结符集D. 句子2．若文法 G 定义的语言是无限集，则文法必然是 (2) A递归的 B 上下文无关的 C 二义性的 D 无二义性的3． Chomsky 定义的四种形式语言文法中， 0 型文法又称为(A)文法；1 型文法又称为(C)文法；2 型语言可由(G) 识别。
A 短语结构文法B 上下文无关文法C 上下文有关文法D 正规文法E 图灵机F 有限自动机G 下推自动机4．一个文法所描述的语言是(A)；描述一个语言的文法是(B)。
第一章1、将编译程序分成若干个“遍”是为了。
b．使程序的结构更加清晰2、构造编译程序应掌握。
a．源程序b．目标语言c．编译方法3、变量应当。
c．既持有左值又持有右值4、编译程序绝大多数时间花在上。
d．管理表格5、不可能是目标代码。
d．中间代码6、使用可以定义一个程序的意义。
a．语义规则7、词法分析器的输入是。
b．源程序8、中间代码生成时所遵循的是- 。
c．语义规则9、编译程序是对。
d．高级语言的翻译10、语法分析应遵循。
c．构词规则二、多项选择题1、编译程序各阶段的工作都涉及到。
b．表格管理c．出错处理2、编译程序工作时，通常有阶段。
a．词法分析b．语法分析c．中间代码生成e．目标代码生成三、填空题1、解释程序和编译程序的区别在于是否生成目标程序。
2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。
3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。
4、编译程序是指将源程序程序翻译成目标语言程序的程序。
一、单项选择题1、文法G：S→xSx|y所识别的语言是。
a. xyxb. (xyx)*c.x n yx n(n≥0) d. x*yx*2、文法G描述的语言L(G)是指。
a. L(G)={α|S+⇒α , α∈V T*}b. L(G)={α|S*⇒α, α∈V T*}c. L(G)={α|S*⇒α,α∈(V T∪V N*)} d. L(G)={α|S+⇒α, α∈(V T∪V N*)}3、有限状态自动机能识别。
a. 上下文无关文法b. 上下文有关文法c.正规文法d. 短语文法4、设G为算符优先文法，G 的任意终结符对a、b有以下关系成立。
a. 若f(a)>g(b)，则a>bb.若f(a)<g(b)，则a<bc. a~b都不一定成立d. a~b一定成立5、如果文法G是无二义的，则它的任何句子α。
a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同6、由文法的开始符经0步或多步推导产生的文法符号序列是。
编译原理考试题及答案一、选择题（每题5分，共20分）1. 编译器的主要功能是什么？A. 代码优化B. 代码翻译C. 代码调试D. 代码运行答案：B2. 下列哪个选项不属于编译器的前端部分？A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D3. 在编译原理中，文法的产生式通常表示为：A. A -> αB. A -> βC. A -> γD. A -> δ答案：A4. 下列哪个算法用于构建语法分析树？A. LL(1)分析B. LR(1)分析C. SLR(1)分析D. LALR(1)分析答案：A二、填空题（每空5分，共20分）1. 编译器的前端通常包括词法分析、语法分析和________。
答案：语义分析2. 编译器的后端主要负责________和目标代码生成。
答案：代码优化3. 编译器中的词法分析器通常使用________算法来识别单词。
答案：有限自动机4. 语法分析中，________分析是一种自顶向下的分析方法。
答案：递归下降三、简答题（每题10分，共30分）1. 简述编译器的作用。
答案：编译器的主要作用是将高级语言编写的源代码转换成计算机能够理解的低级语言或机器代码，以便执行。
2. 解释一下什么是语法制导翻译。
答案：语法制导翻译是一种翻译技术，它利用源语言的语法信息来指导翻译过程，使得翻译过程能够更好地理解源代码的语义。
3. 什么是词法分析器？答案：词法分析器是编译器前端的一部分，它的任务是将源代码文本分解成一系列的标记（tokens），这些标记是源代码的最小有意义的单位。
四、计算题（每题10分，共30分）1. 给定一个简单的文法G(E)：E → E + T | TT → T * F | FF → (E) | id请计算文法的非终结符号E的FIRST集和FOLLOW集。
答案：E的FIRST集为{(, id}，FOLLOW集为{), +, $}。
2. 假设编译器在进行语法分析时，遇到一个语法错误的代码片段，请简述编译器如何处理这种情况。
第2章形式语言基础2.2 设有文法G[N]: N -> D | NDD -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(1)G[N]定义的语言是什么?(2)给出句子0123和268的最左推导和最右推导。
解答：(1)L(G[N])={(0|1|2|3|4|5|6|7|8|9)+} 或L(G[N])={α| α为可带前导0的正整数}(2)0123的最左推导：N ⇒ ND ⇒ NDD ⇒ NDDD ⇒ DDDD ⇒ 0DDD ⇒ 01DD ⇒ 012D ⇒ 0123 0123的最右推导：N ⇒ ND ⇒ N3 ⇒ ND3 ⇒ N23 ⇒ ND23 ⇒ N123 ⇒ D123 ⇒ 0123268的最左推导：N ⇒ ND ⇒ NDD ⇒ DDD ⇒ 2DDD ⇒ 26D ⇒ 268268的最右推导：N ⇒ ND ⇒ N8 ⇒ ND8 ⇒ N68 ⇒ D68 ⇒ 2682.4 写一个文法，使其语言是奇数的集合，且每个奇数不以0开头。
解答：首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。
如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。
分别用3个非终结符来产生句子的第1位、中间部分和最后一位。
引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。
N -> 1 | 3 | 5 | 7 | 9 | BNB -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B02.7 下面文法生成的语言是什么？G1：S->ABA->aA| εB->bc|bBc G2：S->aA|a A->aS解答：B ⇒ bcB ⇒ bBc⇒ bbccB ⇒ bBc⇒ bbBcc ⇒ bbbccc……A ⇒εA ⇒ aA ⇒ aA ⇒ aA ⇒ aaA ⇒ aa……∴S ⇒ AB ⇒ a m b n c n , 其中m≥0,n≥1即L(G1)={ a m b n c n | m≥0,n≥1} S ⇒ aS ⇒ aA ⇒ aaS ⇒ aaaS ⇒ aA ⇒ aaS ⇒ aaaA ⇒aaaaS ⇒ aaaaa ……∴S ⇒ a2n+1 , 其中n≥0即L(G2)={ a2n+1 | n≥0}2.11 已知文法G[S]: S->(AS)|(b)A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。
解答：S( A S ) ( a )( b ) 因为S 不能⇒ (a),所以(a)不是文法的句型。
没有短语、直接短语和句柄。
S( A S )( A S ) ( S a A ) ( b ) 因为S ⇒ (AS) ⇒(A(AS)) ⇒ (A((SaA)S)) ⇒(A((SaA)(b))),所以(A((SaA)(b)))是文法的句型。
短语：(A((SaA)(b)))，((SaA)(b))，(SaA)，(b)直接短语：(SaA)，(b)句柄：(SaA)第3章自动机基础3.1 构造下列正规式相应的DFA。
(2) (a|b)*(aa|bb)(a|b)*解答：NFA：NFA化为DFA：a b{1} {1,3} {1,4} + {1}{1,3} {1,2,3} {1,4} {2}{1,4} {1,3} {1,2,4} {3}{1,2,3} {1,2,3} {1,2,4} - {4}{1,2,4} {1,2,3} {1,2,4} - {5}a+ a a③ b -b最小化DFA：初始划分：{1,2,3},{4,5} 最终划分：{1},{2},{3},{4,5} 这样，状态4与状态5等价，将4和5合并：+b3.2 将下图中的(a)和(b)分别确定化和最小化。
解答：(a) NFA 化为DFA ： a b {0} {0,1} {1}+-{1} {0,1} {0,1} {1} - {2} {1} {0}{3}a±① b 最小化DFA ：{1,2},{3}(b) 本身为DFA ，最小化DFA ： {0,1},{2,3,4,5} {0,1},{2,4},{3,5}3.4 给出文法G[S]，构造相应最小的DFA 。
S->aS|bA|b A->aS解： 原文法等价于：S->aS|bA|bB A->aS B->ε NFA ：令 ①-S, ②-A, ③-B③-NFA 化为DFA ：a b{1} {1} {2,3} +{1} {2,3} {1} - {2}(a)-(b)a a②-3.6 给出与下图中的NFA 等价的正规文法G 。
解：G(A)：A → aB | bD B → bCC → aA | bD | ε D → aB | bD| ε补充题1：构造与正规式(a|b)*c +|ab 等价的DFA (1) 与之等价的NFA 为+--(2) 消除ε边后的NFA 为+--a-得到的DFA为：--第5章语法分析4.3 设有文法G[S]:S->AA->B | AiBB->C | B+CC-> )A* | ((1) 将文法G[S]改写为LL(1)文法。
(2) 构造改写后的文法的递归子程序(给出流程图即可) 。
(3) 求经改写后的文法的每个非终结符的FIRST集和FOLLOW集。
(4) 构造相应的LL(1)分析表，并给出输入串(+)(*# 的分析过程。
解答：(1) 原文法有左递归，利用A->Aβ|α可以化为A->αA`A`->βA`|ε可以得到，原文法可以化为G`(S)：S->AA->BA`A`->iBA`|εB->CB`B`->+CB`|εC->)A*|((2) 扩展文法，增设一个产生式S`->S，作为主程序，得到的递归下降子程序的流程如下：主程序子程序S：子程序A：子程序A`：子程序B：子程序B`：子程序C：(3)其中，follow(B)=first(A`)∪follow(A)= first(A`)∪{*}∪follow(S)={i}∪{*}∪{#}(4) 为产生式编号：S->A ①A->BA`②A`->iBA`③|ε④B->CB`⑤B`->+CB`⑥|ε⑦C->)A*⑧|(⑨根据每个非终结符的FIRST集和FOLLOW集，可以得到各产生式的select集如下：select(①)=first(A) ={), (}select(②)= first(B) ={), (}select(③)=first(iBA`)={i}select(④)=first(ε)∪follow(A`)={#,*}select(⑤)=first(C)= {), (}select(⑥)=first(+CB`)={+}select(⑦)= first(ε)∪follow(B`)={i,#,*}select(⑧)=first()A*)={)}select(⑨)=first(()={(}根据以上select集，可以得到LL(1)分析表：根据以上LL(1)4.9 设文法G[S]为:S->rDD->D,i | i(1) 构造文法的句柄识别器。
(2) 该文法是LR(0)文法吗？请说明理由。
(3) 该文法是SLR(1)文法吗？若是，构造它的SLR(1)分析表，并给出符号串ri,i# 的分析过程。
解答：(1)扩展文法：S`->S (0)S->r D (1)D->D , i (2)| i (3)构造的文法的句柄识别器为：(2)由上图可以看出，在③状态处存在移进和规约冲突，即{,4}和{r(1)}，因此，不是LR(0)文法。
(3)对以上移进和规约冲突{,4}和{r(1)}，(1)号产生式为S->r D，follow(S)∩{,}={#}∩{,}=Φ，因此，是SLR(1)文法。
分析表如下：符号串ri,i# 的SLR(1)4.10 考虑文法S->aA | bBA->0A |1B->0B |1(1) 构造文法的句柄识别器。
(2) 判断该文法是否为LR(0)文法，若是，请构造LR(0)分析表，并给出符号串a001# 的分析过程；若不是，请说明理由。
解答：(1) 扩展文法：S`->S (0)S->a A (1)| b B (2)A->0 A (3) |1(4)B->0 B (5) |1 (6)构造的文法的句柄识别器为：(2) 从以上句柄识别器中可以看出，没有任何状态存在移进和规约冲突，因此，是LR(0)文符号串a001# 的LR(0)分析过程如下：附加题1：已知文法G[A]为：A->aAB1|aB->Bb|d(1) 给出与G[A]等价的LL(1)文法G'[A];(2) 构造G'[A]的预测分析表;(3) 给出输入串aad1#的分析过程;解答：(1) 将递归和公因子处理后，得到的文法G'[A]为：A->aA'A'->A B1|εB->dB'B'->bB'|ε(3) 输入串aad1#第6章中间代码及其翻译【习题1】写出下列语句的四元式序列：(1) if(x>0) x=(a-b/2)*c；(2) while (a∨b) b=2*a/5;(3) a1: y=2*x-6; …; goto a1;解答：(1)四元式序列：(1) ( > x 0 t1 )(4) ( -(7) ( ie(2)四元式序列：(1) (wh_ _ _ )∨a b t1 )(3)四元式序列：(1) ( lb _ _ a1 )(2) (* 2 x t1 )(3) ( - t1 6 t2 )(4) ( = t2 _ y )......(8) ( gt _ _ a1 )【习题2】表达式E的“值”描述如下：产生式语义动作(1) S`->E {print E.val}(2) E->E(1)+E(2){E.val=E(1).val+E(2).val}(3) E->E(1)*E(2){E.val=E(1).val*E(2).val}(4) E->(E(1)) {E.val=E(1).val}(5) E->n {E.val=n}如采用LR分析法，给出表达式(5*4+8)*2的语法树并在各结点注明语义值val。
