东 北 大 学
秦 皇 岛 分 校
课程名称： 编译原理 试卷： (B )答案 考试形式： 闭卷
授课专业： 计算机科学与技术 考试日期： 年 月 日 试卷：共 2 页
题号 一 二 三 四 总分
得分 阅卷人
一、填空题（每空2分，共30分）
1、编译程序的整个过程可以从逻辑上划分为词法分析、 语法分析 、语义分析、中间代码生成、 代码优化 和目标代码生成等几个阶段，另外还有两个重要的工 作是 理 和出错处理。表格管
2、规范规约中的可归约串是 句柄 ，算符优先分析中的可归约串是 最左素短语 。
3、语法分析方法主要可分为 自顶向下 和 自底向上 两大类。
4、LR （0）文法的项目集中不会出现 移进-归约 冲突和 归约-归约 冲突。
5、数据空间的动态存储分配方式可分为 栈式 和 堆式 两种。
6、编译程序是指能将 源语言 程序翻译成 目标语言 程序的程序。
7、确定有穷自动机DFA 是 NFA 的一个特例。 8、表达式 (a+b)*c 的逆波兰表示为 ab+c* 。
二、选择题（每题2分，共20分）
1、LR 语法分析栈中存放的状态是识别 B 的DFA 状态。
A 、前缀
B 、可归前缀
C 、项目
D 、句柄 2、 D 不可能是目标代码。
A 、汇编指令代码
B 、可重定位指令代码
C 、绝对机器指令代码
D 、中间代码 3、一个控制流程图就是具有 C 的有向图
A 、唯一入口结点
B 、唯一出口结点
C 、唯一首结点
D 、唯一尾结点 4、设有文法G[S]：S →b|bB
B →bS ，则该文法所描述的语言是
C 。
A 、L （G ）={b i |i ≥0}
B 、L （G ）={b 2i |i ≥0}
C 、L （G ）={b 2i+1|i ≥0}
D 、L （G ）={b 2i+1|i ≥1}
5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。
A 、编译器
B 、汇编器
C 、解释器
D 、预处理器 6、在目标代码生成阶段，符号表用于 D 。
A 、目标代码生成
B 、语义检查
C 、语法检查
D 、预处理器地址分配0
7、规范归约是指 B 。
A 、最左推导的逆过程
B 、最右推导的逆过程
C 、规范推导
D 、最左归约逆过程 8、使用 A 可以定义一个程序的意义。
A 、语义规则
B 、词法规则
C 、语法规则
D 、左结合规则 9、经过编译所得到的目标程序是 D 。
A 、三元式序列
B 、四元式序列
C 、间接三元式
D 、机器语言程序或汇编语言程序 10、在一个基本块内进行的代码优化是 B 。
A 、全局优化
B 、局部优化
C 、循环优化
D 、代码外提
三、简答题（3小题，共30分） 1、已知文法G[S]：S →Ac|aB
A →ab
B →bc
证明该文法具有二义性（本题6分）
证明：因为该文法的句型abc 存在如下两棵语法树：
装
订
线
装 订 线 内 不 要 答 题
学 号
姓 名
班 级
所以，该文法具有二义性
3、若有文法G[S]：S →bAb A →（B|a B →Aa ）。构造该文法的简单优先关系矩阵。
（10分） 解：
4、构造正规表达式（a|b ）* b 的DFA 并化简。（14分）
解：先构造其NFA 如下：
确定化为DFA ：
将其最小化如下：
四、综合题（20分）
设有文法G[S]：S →BA
A →BS|d
B →aA|bS|c
（1） 证明文法G 是LL （1）文法。 （2） 构造LL （1）分析表。 （3） 写出句子adccd 的分析过程。 解：（1）
可见，文法G 是是LL （1）文法。 （2） （3）
备注: 学生不得在试题纸上答题(含填空题、选择题等客观题
装
订
线
装 订 线 内 不 要 答 题
学 号
姓 名
班 级
一、填空题（每空1分，共20分）
1．编译过程一般分为、、中间代码生成、
和目标代码生成五个阶段。
2．语法分析最常用的两类方法是和分析法。
3．确定的有穷自动机是一个，通常表示为。
4．所谓最右推导是指。
5．语法分析器的任务是。
6．如果一个文法的任何产生式的右部都不含有的非终结符，则这种文法称为文法。
7．进行确定的自上而下语法分析要求语言的文法是无和
的。
8．LR分析法是一种的语法分析方法。
9．根据优化对象所涉及的程序范围，代码优化分为、和等。
10．常用的优化技术包括：、、强度削弱、复写传播、等。
二、是非题（下列各题，你认为正确的，请在题后的括号内打“ √”，错的打“×”。
每题2分，共20分）
1．正规文法产生的语言都可以用上下文无关文法来描述。……………………
( )
2．仅考虑一个基本块，不能确定一个赋值是否真是无用的。………………………（）3．如果一个文法是递归的，则其产生的语言的句子是无穷个。…………………（）4．四元式之间的联系是通过符号表实现的。…………………………………………（）5．文法的二义性和语言的二义性是两个不同的概念。……………………… …（）6．一个LL( l)文法一定是无二义的。…………………………………………… … ( ) 7．在规范规约中用最左素短语来刻划可归约串。………………… …………… ( ) 8．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。…………… ( ) 9．编译程序是对汇编程序的翻译。……………………………………（）10．逆波兰法表示的表达式亦称前缀式。…………………………………………… ( )
三、简答题（每题5分，共15分）
1、简述栈式存储管理策略；
2、何谓DAG；
3、何谓文法的二义性；
四、给出下述文法对应的正规式（7分）
S→ 0A| 1B
A→1S | 1
B→0S | 0
五、已知文法G(E)：
E→T | E+T | E-T
T→F | T*F | T/F
F→(E) | i
证明E+T*F是该文法的一个句型，并指出该句型的所有短语、直接短语和句柄。（8分）
六、设有文法G[S]：
S→aBc|bAB
A→aAb|b
B→b|ε
构造其LL(1)分析表，并分析符号串baabbb是否是该文法的句子. (10分)
七、设有文法G[E]:
E (E) |ε
试判断该文法是否为SLR(1)文法，若不是，请说明理由；若是请构造SLR(1)分析表。(10分)
八、假设可用寄存器为R0和R1，试写出下列四元式序列对应的目标代码。（10
分）
T1=B-C
T2=A*T1
T3=D+1
T4=E-F
T5=T3*T4
参考答案
一、填空题(1X20=20分)
1．词法分析、语法分析、代码优化
2．自上而下、自下而上
3．五元组、DFA=(K ,∑, M, S, Z)
4．任何一步都是对中最右非终结符进行替换
5．分析一个文法的句子结构
6．相邻、算符
7．左递归、公共左因子
8．自下而上
9．局部优化、循环优化、局部优化
10．删除公共子表达式、代码外提、变换循环控制条件、合并已知量、删除无用赋值（任选3个）
二、是非题（2X10=20分）
1、×
2、√
3、√
4、×
5、√
6、√
7、×
8、√
9、×10、×
三、简答题（见书中相应部分）（5X3=15分）
四、解：首先得正规式方程组：
S=0A+1B
A=1S+1
B=0S+0
求解该方程组得：
S=(01|10)(01|10)* （8分）
五、解（2分）
是文法G[S]的句型。
短语：E+T*F, T*F （2分）
直接短语：T*F （2分）
句柄：T*F （2分）
六、解：
、因为FOLLOW(B)=FIRST(c)∪FOLLOW(S)={c,#}(2分),所以构造文法G[S]的LL（1）分析表（5）如下：
a B c#
S aBc bAB
A aAb b
B bεε
符号串baabbb是该文法的句子(3分)（分析过程略）。
七(2分)
所以该文法为SLR(1)文法。其分析表如下：(8分)
状态ACTION GOTO
()#E 0S2r2r21
1acc
2S2r2r23 3S4
4r1r1
八、目标代码为：(10分)
LD R0,B
SUB R0,C
LD R1,A
MUL R1,R0
LD R0,D
ADD R0,1
ST R1,M
LD R1,E
SUB R0,F
MUL R0,R1
LD R1,M
DIV R1,R0
ST R1,W
东 北 大 学 秦 皇 岛 分 校 课程名称： 编译原理 试卷： (B )答案 考试形式： 闭卷 授课专业： 计算机科学与技术 考试日期： 年 月 日 试卷：共 2 页 题号 一 二 三 四 总分 得分 阅卷人 一、填空题（每空2分，共30分） 1、编译程序的整个过程可以从逻辑上划分为词法分析、 语法分析 、语义分析、中间代码生成、 代码优化 和目标代码生成等几个阶段，另外还有两个重要的工 作是 理 和出错处理。表格管 2、规范规约中的可归约串是 句柄 ，算符优先分析中的可归约串是 最左素短语 。 3、语法分析方法主要可分为 自顶向下 和 自底向上 两大类。 4、LR （0）文法的项目集中不会出现 移进-归约 冲突和 归约-归约 冲突。 5、数据空间的动态存储分配方式可分为 栈式 和 堆式 两种。 6、编译程序是指能将 源语言 程序翻译成 目标语言 程序的程序。 7、确定有穷自动机DFA 是 NFA 的一个特例。 8、表达式 (a+b)*c 的逆波兰表示为 ab+c* 。 二、选择题（每题2分，共20分） 1、LR 语法分析栈中存放的状态是识别 B 的DFA 状态。 A 、前缀 B 、可归前缀 C 、项目 D 、句柄 2、 D 不可能是目标代码。 A 、汇编指令代码 B 、可重定位指令代码 C 、绝对机器指令代码 D 、中间代码 3、一个控制流程图就是具有 C 的有向图 A 、唯一入口结点 B 、唯一出口结点 C 、唯一首结点 D 、唯一尾结点 4、设有文法G[S]：S →b|bB B →bS ，则该文法所描述的语言是 C 。 A 、L （G ）={b i |i ≥0} B 、L （G ）={b 2i |i ≥0} C 、L （G ）={b 2i+1|i ≥0} D 、L （G ）={b 2i+1|i ≥1} 5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。 A 、编译器 B 、汇编器 C 、解释器 D 、预处理器 6、在目标代码生成阶段，符号表用于 D 。 A 、目标代码生成 B 、语义检查 C 、语法检查 D 、预处理器地址分配0 7、规范归约是指 B 。 A 、最左推导的逆过程 B 、最右推导的逆过程 C 、规范推导 D 、最左归约逆过程 8、使用 A 可以定义一个程序的意义。 A 、语义规则 B 、词法规则 C 、语法规则 D 、左结合规则 9、经过编译所得到的目标程序是 D 。 A 、三元式序列 B 、四元式序列 C 、间接三元式 D 、机器语言程序或汇编语言程序 10、在一个基本块内进行的代码优化是 B 。 A 、全局优化 B 、局部优化 C 、循环优化 D 、代码外提 三、简答题（3小题，共30分） 1、已知文法G[S]：S →Ac|aB A →ab B →bc 证明该文法具有二义性（本题6分） 证明：因为该文法的句型abc 存在如下两棵语法树： 装 订 线 装 订 线 内 不 要 答 题 学 号 姓 名 班 级
1．一个句型中最左的（D）称为该句型的句柄。 A、短语 B、非终结符号 C、终结符号 D、直接短语 2．设文法为：S→SA|A，A→a|b，则对句子aba，下面（D）是规范推导。 A、S?SA?SAA?SAa?Sba?Aba?aba B、S?SA?SAA?AAA?aAA?abA?aba C、S?SA?SAA?AAA?AAa?Aba?aba D、S?SA?Sa?SAa?Sba?Aba?aba 3．最左简单子树的末端结点构成的符号串称为（B） A、简单短语 B、句柄 C、最左素短语 D、素短语 * ? 4．设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*）,则称x是文法G的一个（D）。 A、产生式 B、单词 C、候选式 D、句型 5．若一个文法是递归的，则它产生的句子个数是（B） A、有限个 B、无穷个 C、可能有限个 D、以上均不对 6．乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中2型文法是（B）。 A、正则文法 B、上下文无关文法 C、上下文有关文法 D、短语文法 7．文法G[E]：E→T∣E＋T ，T→F∣T﹡F，F→a∣（E）该文法句型E＋F﹡（E＋T）的简单短语是下列符号串中的。①（E＋T）②E＋T ③F ④F﹡（E＋T）可选项有（C） A、②和③ B、③ C、③和④ D、①和③ 8．若a为终结符，则A→α·aβ为（C）项目。 A、待约 B、接受 C、移进 D、归约 9．下面哪种不是自底向上的语法分析文法？（C） A、LR（1） B、SLR（1） C、LL（K） D、算符优先法 10．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的（C）。 A、无关系 B、充分必要条件 C、必要条件 D、充分条件 11、一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组（B）。 A、单词 B、产生式 C、句型 D、句子 12．下面哪个不是单词的描述工具？（D） A、正规式 B、正规文法 C、有穷自动机 D、下推自动机 13．正规式M1和M2等价是指（D）。 A、M1和M2的有向弧条数相等 B、M1和M2的状态数相等 C、M1和M2状态数和有向弧条数相等 D、M1和M2所识别的语言集相等 14．编译程序中语法分析器接收以（C）为单位的输入。 A、句子 B、表达式 C、单词 D、产生式 15．表达式A*（B-C*（C/D））的逆波兰式是（C） A、ABC-*CD/* B、ABC-CD/* C、ABCCD/*-* D、a,b,c均不正确 16．后缀式ab+cd+/可用表达式来表示。 A、a+b/c+d B、（a+b）/（c+d） C、a+b/（c+d） D、a+b+c/d 17．一个句型中的可归前缀为（C） A、短语 B、句柄 C、规范前缀，且句柄位于该规范前缀的后端 D、简单短语
一、填空题: 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.语法分析最常用的两类方法是自上而下和自下而上分析法。 4-02.语法分析的任务是识别给定的终极符串是否为给定文法的句子。 4-03.递归下降法不允许任一非终极符是直接左递归的。 4-04.自顶向下的语法分析方法的关键是如何选择候选式的问题。 4-05.递归下降分析法是自顶向上分析方法。 4-06.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 5-02.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行直接归约，力求归约到文法的开始符号。 5-03.简单优先方法每次归约当前句型的句柄，算符优先方法每次归约当前句型的最左素短语，二者都是不断移进输入符号，直到符号栈顶出现可归约串的尾，再向前找到可归约串的头，然后归约。
第一章 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.若源程序是用高级语言编写的，目标程序是______，则其翻译程序称为编译程序。 2.词法分析和语法分析本质上都是对源程序的______进行分析。 3.如果源语言(编写源程序的语言)是高级语言，而目标语言是某计算机的汇编语言或机器语言，则这种翻译程序称为_____。 4.对编译程序而言，输入数据是_______,输出结果是________。 5. ______，是构成语言文法的单词，是语法成分的最小单位。 6.由PL／0的EBNF可知，PL／0语言可看成是PASCAL语言的子集，它的编译程序是一个__________。 7.由于PL／0编译程序采用_________，所以语法分析过程BLOCK是整个编译过程的核心。 8.用语法图描述语法规则的优点是______、________。 9.每个非终结符是一个语法成分，在书写语言程序时并不出现，它是由_________和_________、或终结符串定义的。 10.PL／0的目标程序为假想栈式计算机的汇编语言，与具体计算机______。 11.PL／0的编译程序和目标程序的解释执行程序都是用_______书写的，因此PL／0语言可在配备_________的任何机器上实现。 12.PL／0编译程序是用PASCAL语言书写的，整个编译程序(包括主程序)是由______个嵌套及并列的过程或函数组成 13.当源程序编译正确时，PL／0编译程序自动调用__________，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果。 14.由于对某些非终结符可以递归定义，这就使得_________可用有穷的文法描述。 15. ______的任务是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规则。 16. PL／0编译程序的语法分析采用了____________。 17.语法分析程序除总控外主要有两大部分的功能，即_________和__________. 18.PL／0的词法分析程序GETSYM，是一个独立的过程，其功能是为_________提供单词用的，是______的基础，它把输入的字符串形式的源程序分割成一个个单词符号。 19.每个过程应有过程首部以定义局部于它自己过程的常量、变量和过程标识符，也称_____。 20.词法分析程序GETSYM将完成的任务有:______, 识别保留字；_______,拼数,拼复合词,输出源程序. 21.如果一个PL／0语言的单词序列在整个语法分析中，都能逐个得到匹配，直到_________，这时就说所输入的程序是正确的。 22.若要构造程序设计语言的编译程序，则首先要对程序设计语言本身有较为精确的描述。而关于程序设计语言的描述，将涉及_____、语义和______三个方面。 23.凡是具有某种特殊性质的客体的聚合，都可称为______。 24.如果集合中元素个数为零，即集合中不含有任何元素，这样的集合称为_______，记为φ。 25.设有集合A和B，如果A和B有相同的元素，则称这两个集合是_______. 26.设A、B为任意两个集合，由所有属于集合A或属于集合B的元素组成的集合，叫做集合A与B的_______． 27. 设A、B为任意两个集合，由所有用于集合A且属于集合B的元素组成的集合，称为集合A与B的_______.
P36-6 L （G 1）是0~9组成的数字串 编译 原理课后题答案 第二章 01DD 012D 0127 N ND DD 3D 34 N ND NDD DDD 5DD 56D 568 最右推导： N ND N7 ND 7 N27 ND 27 N127 N ND N4 D4 34 N ND N8 ND 8 N68 D68 568 N ND NDD NDDD D127 ⑵ 最左推导: DDDD 0DDD 0127 P36-7 G(S) O 1|3|5|7|9 2|4|6|8|O 0|N O|AO AD|N P36-8 文法: T E T|E F T* F|T/ F (E)|i 最左推导： T T* i*( i T) i*(i F) i *( i T i i*( E) i) T* F i F* F i i *( E T) i*( T i* F T) i i * i i*( F T) 最右推导：
E E T E T* F E T*i E F*i E i*i T i *i F i*i i i*i *****************/ P36-9 P36-10 /************** S TS|T (S)|() ***************/ P36-11 /*************** L1: AC aAb | ab cC | L2:F*( E T) F*( E F) F*( E i) T F i E T F*T F * F F*(E) i+i+i i-i- i i+i*i 句子iiiei 有两个语法树: ? 巳
AB aA| bBc|bc L3: AB aAb| aBb| L4: A| B 0A1| 1B0| A ***************/ 第二章习题参考答案P64 — 7 1(01) 101 确定化:
华东师范大学试卷及答案（A ） 学生姓名：_____________ 学号：___________________ 学生系别：_____________ 专业：______________ 年级___________班级_____________ 课程名称：编译原理 课程性质：专业必修 一、问答题 1. 设G=（V N ，V T ，P ，）是上下文无关文法，产生式集合P 中任意一个产生式 应具有什么样的形式？若G 是正则文法呢？（5％） 答：一般形式为
答： + 4. 试将下述程序段翻译成三地址形式的中间代码表示。（8％） 答：三地址代码如下： 100: t:=a+b 101: if t 第1 题 已知文法 A→aAd|aAb|ε 判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。 答案： 文法： A→aAd|aAb|ε 拓广文法为G′，增加产生式S′→A 若产生式排序为： 0 S' →A 1 A →aAd 2 A →aAb 3 A →ε 由产生式知： First (S' ) = {ε,a} First (A ) = {ε,a} Follow(S' ) = {#} Follow(A ) = {d,b,#} G′的LR(0)项目集族及识别活前缀的DFA 如下图所示 在I0 中： A →.aAd 和A →.aAb 为移进项目，A →.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。 在I0、I2 中： Follow(A) ∩{a}= {d，b，#} ∩{a}= 所以在I0、I2 中的移进-归约冲突可以由Follow 集解决，所以G 是SLR(1)文法。 构造的SLR(1)分析表如下： 对输入串ab#的分析过程: 第2 题 若有定义二进制数的文法如下： S→L·L|L L→LB|B B→0|1 (1) 试为该文法构造LR 分析表，并说明属哪类LR 分析表。 (2) 给出输入串101.110 的分析过程。 答案： 文法： S→L.L|L L→LB|B B→0|1 拓广文法为G′，增加产生式S′→S 若产生式排序为： 0 S' →S 1 S →L.L 2 S →L 3 L →LB 4 L →B 5 B →0 6 B →1 由产生式知： First (S' ) = {0,1} First (S ) = {0,1} First (L ) = {0,1} First (B ) = {0,1} Follow(S' ) = {#} Follow(S ) = {#} Follow(L ) = {.,0,1,#} Follow(B ) = {.,0,1,#} G′的LR(0)项目集族及识别活前缀的DFA 如下图所示： 在I2 中： B →.0 和 B →.1 为移进项目，S →L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。 在I2、I8 中：Follow(s) ∩{0，1}= { #} ∩{0，1}= 所以在I2 、I8 中的移进-归约冲突可以由Follow 集解决，所以G 是SLR(1)文法。 构造的SLR(1)分析表如下： 编译原理试题 一、填空题 1、汇编程序将________翻译成________；编译程序将________翻译成________。 2、编译程序工作工程可以划分为______、______、______、______和______等5个基本阶段，同时还会伴有______和______。 3、对编译程序而言，输入数据是______，输出数据是______。 4、已知文法G［E］：E—>T|E+T｜E—F，T－〉F|T*F｜T/F，F->(E）｜I，(“，”是间隔符号，不是文法中的符号）。该文法的开始符号(识别字符）是______,终结符号集合V T是______，非终结符号结合V N是______，句型T+T＊F+i的短语有____________。该文法消除直接左递归，改写后的文法为E－>________,T －>________，F－〉________。 5、Chomsky定以来寺中形式语言的文法分别为:________文法(又称________文法）、________文法（又称________文法)、________文法（又称________文法）、________文法（又称________文法)。 6、编译过程中扫描器所完成的任务是从________中识别出一个个具有________。 7、确定的有穷自动机是一个________，通常表示为________. 8、LL(k）分析中，第一个L的含义是________，第二个L的含义是________，“k"的含义是________。 9、LL(1）分析中，第一个L的含义是________，第二个L的含义是________，“1”的含义是________. 10、LR（0）分析中，“L"的含义是________，“R”的含义是________，“0”的含义是________。 11、SLR(1）分析中，“L”的含义是________，“R”的含义是________，“1”的含义是________。 12、LR(1）分析中,“L"的含义是________,“R”的含义是________，“1”的含义是________。 13、算术表达式：a*(—b+c)的逆波兰式表示为：________。 14、算术表达式：a＋b*（c+d/e）的逆波兰式表示为:____________。 15、在编译程序中安排中间代码生成的目的是__________和___________。 16、语法制导的翻译程序能同时进行________分析和________分析. 17、根据所涉及的程序范围,优化可分为________、________、________三种. 二、简答题 1、有人认为编译程序的词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成五个组成部分是缺一不可的,这种看法正确吗？说明理由。 2、多边扫描的程序是高质量的编译程序，优于单遍扫描的编译程序,对吗?为什么？ 3、LR分析器与优先分析器在识别被归约串时的主要异同时什么？ 三、给出生成下述语言的上下文无关的文法 {1n0m1m0n｜n，m>=0｝ ｛WaW r|W属于{0｜1｝*，W r表示W的逆｝ 四、给出生成下列语言的三型文法： ｛a n|n〉=0｝ ｛a n b m|n，m〉0｝ {a n b m c k｜n，m,k〉=0｝ 一、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。每题1分,共5分) 1、算符优先关系表不一定存在对应的优先函数。√ 2、数组元素的地址计算与数组的存储方式有关。√ 3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。√ 4、每个文法都能改写为LL(1)文法。× 5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。× 6、一个LL(1)文法一定是无二义的。 7、逆波兰法表示的表达式亦称前缀式。 8、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 9、正规文法产生的语言都可以用上下文无关文法来描述。 10、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 二、选择题： 1.编译原理是对（c ）。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 2.词法分析器的输出结果是（ d ）。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 3. 若文法G定义的语言是无限集，则文法必然是（ c ） A.前后文无关文法 B.正规文法 C.二义性文法 D.递归文法 4.文法：G：S→xSx | y所识别的语言是（ d ）。 A、x n yx m B、(xyx)* C、x*yx* D、xnyxn（n≥0） 1 ．文法G 产生的⑴ 的全体是该文法描述的语言。d A ．句型B. 终结符集C. 非终结符集D. 句子 2 ．若文法G 定义的语言是无限集，则文法必然是⑵ ：a A ．递归的 B 前后文无关的 C 二义性的 D 无二义性的 3 ．Chomsky 定义的四种形式语言文法中，0 型文法又称为⑶ 文法；1 型文法又称为⑷ 文法；2 型语言可由⑸ 识别。 A ．短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正规文法 E 图灵机 F 有限自动机 G 下推自动机 4 ．一个文法所描述的语言是⑹ ；描述一个语言的文法是⑺ 。 A ．唯一的 B 不唯一的 C 可能唯一，好可能不唯一 5 ．数组的内情向量中肯定不含有数组的⑻ 的信息 A．维数B.类型C.维上下界D.各维的界差 6 ．在下述的编译方法中，自底向上的方法有⑼ ，自顶向下的分析方法有⑽ 。 ①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR（K）分析 ⑥ SLR（k）分析⑦ LL（k）分析⑧LALR（K）分析 A.③④⑦ B. ③④⑧ C.①②⑧ D.③④⑤⑥⑦ E.①②⑤⑥⑦ F. ①②⑤⑥⑧ ⑴ D ⑵ A ⑶ A ⑷ C ⑸ G. ⑹ A ⑺ B ⑻ A ⑼ F ⑽ A 1、编写一个计算机高级语言的源程序后，到正式上机运行之前，一般要经过__B____这几步 ①编辑②编译③连接④运行 A、①②③④ B、①②③ C、①③ D、①④ 2、使用高级语言进行编程时，首先可以通过编译程序发现源程序的所有___A__错误和部 分___B__错误 A、语法 B、语义 C、语用 D 运行 3、乔姆斯基定义的四种形式语言文法分别为：__（1）_文法（又称_（2）___文法）、（3） ___文法（又称_（4）___文法）、__（5）_文法（又称_（6）___文法）、_（7）__文法（又称__（8）__文法） （1）0型（2）短语文法（3）1型（4）上下文有关文法（5）2型（6）上下文无关文法（7）3型（8）正则 4、巴科斯—诺尔范式（即BNF）是一种广泛采用的__C__工具 A、描述规则 B、描述语言 C、描述文法 D、描述句子 给定文法A ®bA|cc,下面的符号串为该文法句子的是_A 一、填空题（每空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___实现的。 A．指示器B．临时变量C．符号表D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧ C．AB∨┐CD∨∧D．A┐B∨∧CD∨ 8. 优化可生成__D___的目标代码。 A．运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱B．删除归纳变量C．删除多余运算D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x 编译原理习题答案 习题1 1.1翻译程序：把用某种程序设计语言（源语言）编写的程序（源程序）翻译成与 之等价的另一种语言（目标语言）的程序（目标程序）。 编译程序：一种翻译程序，将高级语言编写的源程序翻译成等价的机器语言或汇编语言的目标程序。 1.2词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成1.3词法分析：根据语言的词法规则对构成源程序的符号进行扫描和分解，识别出 一个个的单词。 语法分析：根据语言的语法规则，把单词符号串分解成各类语法单位。 语义分析及中间代码生成：对语法分析识别出的语法单位分析其含义，并进行初步翻译。 代码优化：对中间代码进行加工变换，以产生更高效的目标代码。 目标代码生成：将中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或会变指令代码。 以上5个阶段依次执行。 习题2 2.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|e 2.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|bb 2.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→CD D→0|1|2|3|4|5|6|7|8|9 2.8证明：E=>E+T=>E+T*F 短语：T*F E+T*F 直接短语：T*F 句柄：T*F 答题时限：120 分钟考试形式：闭卷笔试 一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分，共20 注意：须将本题答案写在下面的表格中，写在其它地方无效 1. 编译程序是对（） A. 汇编程序的翻译 B. 高级语言程序的解释执行 C. 机器语言的执行 D. 高级语言的翻译 2. 词法分析器的输出结果是（） A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 3.在规范规约中，用（）来刻画可规约串。 A．直接短语B．句柄C．最左素短语D．素短语 4. 与正规式(a* | b)* (c | d)等价的正规式是（） A．a* (c | d) | b(c | d) B．a* (c | d) * | b(c | d) * C．a* (c | d)| b* (c | d) D．(a | b) * c| (a | b) * d 5. 若项目集I K含有A→α·，则在状态K时，仅当面临输入符号a∈FOLLOW(A)时，才采取A→α·动作的一定是（） A．LALR文法B．LR(0) 文法C．LR(1)文法D．SLR(1)文法 6.四元式之间的联系是通过（）实现的。 A. 指示器 B. 临时变量 C. 符号表 D. 程序变量 7．文法G：S → x Sx | y所识别的语言是（） A．xyx B．(xyx) *C．x n yx n(n≥0) D．x*yx* 8.有一语法制导翻译如下所示： S → b Ab {print “1”} A→(B {print “2”} A→a {print “3”} B→Aa) {print “4”} 若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为（）A．32224441 B. 34242421 C．12424243 D. 34442212 9．关于必经结点的二元关系，下列叙述不正确的是（） A．满足自反性B．满足传递性C．满足反对称型D．满足对称性 10．错误的局部化是指（）。 A．把错误理解成局部的错误B．对错误在局部范围内进行纠正 C．当发现错误时，跳过错误所在的语法单位继续分析下去 D．当发现错误时立即停止编译，待用户改正错误后再继续编译 1分，共5分） 1.文法G的一个句子对应于多个推导，则G是二义性的。（×） 2. 动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（√） 3. 算符优先文法采用“移进－规约”技术，其规约过程是规范的。（×） 4. 删除归纳变量是在强度削弱以后进行。（√） 5. 在目标代码生成阶段，符号表用于目标代码生成。（×） 5分，共15分） 1. 构造正规式(0∣1)*00相应的正规式并化简。（共5分） （1）根据正规式，画出相应的NFA M（2分） （ 一． 填空题（每空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 ． 可能唯一，也可能不唯一 (完整word版)《编译原理》考试试题及答案《编译原理》考试试题及答案（附录） 一、判断题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。( X ) 2.一个句型的直接短语是唯一的。( X ) 3.已经证明文法的二义性是可判定的。（X ） 4.每个基本块可用一个DAG表示。（√） 5.每个过程的活动记录的体积在编译时可静态确定。（√） 6.2型文法一定是3型文法。（x ） 7.一个句型一定句子。( X ) 8.算符优先分析法每次都是对句柄进行归约。(应是最左素短语) ( X ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。（√） 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。( x ) 11.一个优先表一定存在相应的优先函数。( x ) 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.语法分析是依据语言的（）规则进行。中间代码产生是依据语言的（）规则进行的。 《编译原理》期末试题（五） 一、单项选择题(共10小题，每小题2分，共20分） 1．语言是 A．句子的集合B．产生式的集合 C．符号串的集合D．句型的集合 2．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化 3．一个句型中称为句柄的是该句型的最左 A．非终结符号B．短语C．句子D．直接短语 4．下推自动机识别的语言是 A．0型语言B．1型语言 C．2型语言D．3型语言 5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即A．字符B．单词C．句子D．句型 6．对应Chomsky四种文法的四种语言之间的关系是 A．L0L1L2L3 B．L3L2L1L0 C．L3=L2L1L0D．L0L1L2=L3 7．词法分析的任务是 A．识别单词B．分析句子的含义 C．识别句子D．生成目标代码 8．常用的中间代码形式不含 A．三元式B．四元式C．逆波兰式D．语法树 9．代码优化的目的是 A．节省时间B．节省空间 C．节省时间和空间D．把编译程序进行等价交换 10．代码生成阶段的主要任务是 A．把高级语言翻译成汇编语言 B．把高级语言翻译成机器语言 C．把中间代码变换成依赖具体机器的目标代码 D．把汇编语言翻译成机器语言 二、填空题(本大题共5小题，每小题2分，共10分） 1．编译程序首先要识别出源程序中每个(单词）,然后再分析每个(句子)并翻译其意义。 2．编译器常用的语法分析方法有(自底向上)和（自顶向下)两种. 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的（分析）,中间代码生成、代码优化与目标代码的生成则是对源程序的(综合）。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类,即（静态存储分配)方案和（动态存储分配）方案。 5．对编译程序而言，输入数据是(源程序）,输出结果是（目标程序）。 三、名词解释题(共5小题，每小题4分，共20分) 1．词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号,按照词法规则编译原理第七章 习题参考答案
编译原理试题及答案
(完整word版)编译原理(选择、填空、简答)题
(完整word版)编译原理期末考试题目及答案 (2)(word文档良心出品)
(完整word版)编译原理_课后习题答案_杨明
(完整word版)郑州大学编译原理期末考试试卷(word文档良心出品)
编译原理期末考试试卷及答案
(完整word版)《编译原理》考试试题及答案
(完整word版)编译原理期末试题(8套含答案+大题集)
相关主题
文本预览