《编译原理》考试试卷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→aH
H→aMd|d
M→Ab|ε
A→aM|e
是否为LL(1)文法？给出判断过程。
6. （10分）改写文法G[E]：
E → E+T|T
T →T*F|F
F →(E)| a
为无左递归文法。
7. （10分）已知文法G[S]为：
S→V
V→T|ViT
T→F|T+F
F→)V*|(
请指出句型(+(i( 规范推到，并指出句型F+Fi( 中的短语、句柄和素短语。
《编译原理》考试试卷A参考答案
适用专业：考试日期：闭卷
所需时间：120分钟总分：100分
一、填空题：（每空1分，共10分）
1. 边翻译边执行和不生成目标代码。
2. 表格。
3. 自上而下和自底向上。
4. 左递归和回溯。
5. 正则式或正规文法, 有穷自动机。
6. 最左素短语。
二、单选题（每小题2分，共10分）
1-5：CCBBB
三、问答题（每小题10分，共80分）
1.
（1）编译程序
一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的程序
（2）句柄
一个句型的最左直接短语称为该句型的句柄
（3）上下文无关文法
对任一产生式α→β，α为非终结符，β为终结符和非终结符组成的符号串。
2.
编译程序一般由词法分析程序，语法分析程序，语义分析程序，中间代码生成程序，目标代码生成程序，代码优化程序，符号表管理程序和错误处理程序等成分构成。
3.
G[S]:
S→AB
A→aAbb|ε
B→cB|ε
4.
初始划分：I1={1,2,3,4},I2={5,6,7}
因为
move(I1,a)={6,1,7,4}→move({1,2},a)={6,7} move({3,4},a)={1,4}
所以第二次划分：I1={1,2},I2={3,4},I3={5,6,7}
又因为
move({3,4},a)={1,4}→ move({3},a)={1}, move({4},a)={4}
所以，将{3,4}划分为集合：{3}，{4}
move({5,6,7},a)={4,7}→move({5},a)={7}, move({6,7},a)={4} 所以将集合{5,6,7}划分为：{5}，{6,7}
最终划分结果：I1={1,2},I2={3},I3={4},I4={5},I5={6,7}
产生式的Select集交集都为空集，所以该文法是LL(1)文法。6. G[ E]: (1) E →TE’ (2) E’ →+TE’
(3) E’ →ε (4) T →FT’
(5) T’ →*FT’ (6) T’ →ε
(7) F → (E) (8) F →a
7.
S → V → ViT→ViF→Vi(→Ti(→T+Fi(→T+(i(→F+(i(→(+(i( 句型F+Fi(
短语：F,F+F,(,F+Fi( 句柄：F
素短语：F+F，（
《编译原理》考试试卷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→aH H→aMd|d M→Ab|ε A→aM|e 是否为LL(1)文法？给出判断过程。 6. （10分）改写文法G[E]： E → E+T|T T →T*F|F F →(E)| a 为无左递归文法。 7. （10分）已知文法G[S]为： S→V V→T|ViT T→F|T+F F→)V*|( 请指出句型(+(i( 规范推到，并指出句型F+Fi( 中的短语、句柄和素短语。
编译原理试题A 一、单项选择题（每题1分，共20分） 1、哪个不是编译系统的组成部分（C ） A．词法分析器 B. 代码生成器 C．设备管理程序 D. 语法分析器 2. 设有表达式a*b-c，将其中a*b识别为表达式的编译阶段是什么 （ B ） A．词法分析 B. 语法分析 C．语义分析 D. 代码生成 3. 下面不能用于对文法进行描述的是（A ） A．源语言 B. EBNF C．BNF D. 语法图 4. 设有文法G[S]: S→S1|S0|Sa|Sc|a|b|c，下列符号串中不是该文法的句子的是 （A ） A．ab0 B. a0c01 C．aaa D. bc10 5. 文法G[S]: S→aA A→bB B→a|aS ,则L(G)为（C ）A．{(ab)n a|n≥1} B. {a (ba)n|n≥1} C．{(aba)n|n≥1} D. {(aba)n|n≥0} 6. 哪个不是DFA的构成成分（B ） A．有穷字母表 B. 初始状态集合 C．终止状态集合 D. 有限状态集合 7.词法分析器的输入是（B ） A．单词符号串 B.源程序C．语法单位 D.目标程序 8.在词法分析阶段不能识别的是（C ）A．标识符 B. 运算符C．四元式 D. 常数 9.设有一段C语言程序 while(i&&++j) { c=2.19; j+=k;
i++; } ,经过词法分析后可以识别的单词个数是（B ）A．19 B.20 C．21 D.23 10．自上而下语法分析的主要动作是（B ）A．移进 B. 推导C．规约 D. 匹配 11.下面不属于LL(1)分析器的组成部分是（D ）A．LL(1)总控程序 B. LL(1)分析表 C．分析栈 D.源程序串 12.设有文法G[S]为 S→AB|bC，A→ε|b，B→ε|aD，C→AD|b，D→aS|c 则FOLLOW(A)为（A ）A．{a,c,#} B.{c,#} C．{a,#} D.{#} 13.设有文法G[S]: S→Ap|Bq，A→a|cA，B→b|dB，则FIRST(Ap)为（ C ）A．{p,q} B. {b,d} C．{a,c} D. 其他 14.自下而上语法分析的主要分析动作是（D ）A．推导 B. 规约C．匹配 D. 移进-规约 15.算法优先分析中，可规约串是（C ）A．句柄B．活前缀C．最左素短语D．素短语16. 设有文法G={{S},{a},{S→SaS|ε},S}，该文法是（B ） A．LL(1)文法B．二义性文法 C．SLR(1)文法D．算法优先文法 17、中间代码生成时所以据的是（C ）A．语法规则B．词法规则C．语义规则 D．等价变换规则 18、给定文法G: E→E+T|T，T→T*F|F，F→i|(E) 则L(G)中的一个句子i+i+(i*i)*i的逆波兰表示为（C）A．iii*i++B．ii+iii**+ C．ii+ii*i*+ D．其他 19．在编译程序中与生成中间代码的目的无关的是（B）A．便于目标代码优化B．便于存储空间的组织 C．便于目标代码的移植D．便于编译程序的移植
课程测试试题（04A卷） I、命题院（部）：数学与计算机科学学院 II、课程名称：编译原理 III、测试学期：2006－2007 学年度第1 学期 IV、测试对象：数计、国交学院计科专业2004 级1、2、国交班 V、问卷页数（A4）：3 页 VI、答卷页数（A4）：4 页 VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚） VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号） 一、填空题（共30分，30个空，每空1分） 1、典型高级程序设计语言编译系统的工作过程一般分为六个阶段，即词法分析、语法分析、语义分析、中间代码生成、、目标代码生成。编译阶段的两种组合方式是组合法和按遍组合法，这两种组合方式的主要参考因素都是的特征。 2、Chomsky将文法按其所表示语言的表达能力，由高往低分为四类：0型，1型，2型，3型文法。其中，2型文法也称，它的所有规则α→β 都满足：α∈，β∈ ((V N∪V T) *且，仅当β= ε时例外。 3、现代编译系统多采用方法，即在语法分析过程中根据各个规则所相联的或所对应的语义子程序进行翻译的办法。该方法使用为工具来说明程序设计语言的语义。 4、构造与NFA M等价的正规文法G的方法如下：（1）对转换函数f(A，a)=B或f(A，ε)=B，改成形如或的产生式；（2）对可识别终态Z，增加一个产生式：。 5、代码生成要考虑的主要问题：充分利用的问题、选择的问题、选择的问题。 6、设有穷自动机M=(K，∑，f，S，Z)，若当M为时，满足z0∈f(S，α)且z0∈Z，或当M为时，满足f(S，α)=P∈Z，则称符号串α∈∑*可被M所。 7、符号表中每一项对应一个多元组。符号表项的组织可分为组织、组织、组织等。 8、对于A∈∀ＶN 定义A的后续符号集：FOLLOW(A)={a|S=*>uAβ，a∈ＶT，且a∈，u∈ＶT*，β∈Ｖ+;若，则#∈FOLLOW(A)。也可以定义为：FOLLOW(A)={a|S=*>…Aa…，a∈ＶT}。若有，则规定#∈FOLLOW(A)。 9、基本块的定义：一个基本块是指程序中一个执行的语句序列，其中只有一个入口和一个出口。入口是程序第一个语句或转移语句的目标语句，或转移语句的后继第一个语句。出口是程序或转移语句。在基本块范围内的优化称为。 10、预测分析器由预测分析表、先进后出栈（用来存放分析过程的语法符号）和三部分组成。其中预测分析表是一个二维矩阵，其形式为M[A，a]，其中A∈V N，a∈V T或#。若有产生式A→α，使得a∈，则将A→α填入M[A，a]中。(书写时，通常省略规则左部，只填→α)。对所有的M[A，a]标记为出错。 二、简述题（共20分，4个小题，每小题5分） 1、简述将NFA转换为最小化DFA的步骤。 2、简述静态存储分配、栈式存储分配和堆式存储分配的特点和主要用途。 3、以表达式 a:=b*(-c)+b/(-d)为例，简述常用的三种中间代码表示形式。 4、简述判别文法Ｇ是否为LL(1)文法的步骤和将一个非LL(1)文法转换为LL(1)文法的方法。 三、应用题（共50分） 1、有文法G[S]：(12分)
华中科技大学武昌分校 《编译原理》试卷A 专业班级：_________学号：_________姓名：__________总分 一、单项选择题(共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 ．L 0?L 1?L 2?L 3 B ．L 3?L 2?L 1?L 0 C ．L 3=L 2?L 1?L 0 D ．L 0?L 1?L 2=L 3 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．词法分析 2．LL(1)文法 3．语法树 4．LR(0)分析器 5．语言和文法 四、简答题(共4小题，每小题5分) （题分 20分） 1．编译程序和高级语言有什么区别? 2．编译程序的工作分为那几个阶段? 3．简述自下而上的分析方法。 4．简述代码优化的目的和意义。 五、综合应用题(共3小题，每小题10分) （题分 30分） 1．证明下述文法G ： S →aSbS|aS|d 是二义性文法。 2．对于文法G[S]：S →AB ，A →Aa|bB ，B →a|Sb 求句型baSb 的全部短语、直接短语和句柄？ 得分 得分 得分 得分
期末考试试卷〔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.正规文法 2、生成非0开头的正偶数集的文法是〔〕。 A． Z::=ABC B. Z::=ABC C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|ε B::=BA|B0|0 A::=1|2|3|…|9 A::=1|2|3|…|9 C. Z::=ABC|2|4|6|8 D. Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8
东北师范大学2021年9月《编译原理》基础作业考核试题及答案参考 1. 若消除文法中的ε-产生式，将会改变文法所定义的语言，故不能消除ε-产生式。( ) A.错误 B.正确 参考答案：A 2. 算符优先分析法每次都是对( )进行归约 A.句柄 B.最左素短语 C.素短语 D.简单短语 参考答案：B 3. 类型检查技术不能用于捕捉多种安全漏洞。( ) A.正确 B.错误 参考答案：B 4. 对于LR(0)分析法，语法分析栈中存放的状态是识别规范句型( )的DFA状态。 A.前缀 B.活前缀 C.LR(0)项目 D.句柄 参考答案：B 5. 算符优先分析法只能识别由算符优先文法描述的句子。( ) A.错误 B.正确 参考答案：B
6. ( )是描述语言的语法结构的形式规则。 A.文法 B.语义 C.词法 D.语法 参考答案：A 7. Chmosky的3型语言是这样一种语言，其产生式限制为什么?( ) A.A∷=α B.A∷=a，A∷=Ab C.α∷=β D.αAβ∷=απβ 参考答案：B 8. 在JavaScript中，下面变量的声明和赋值语句错误的是( )。 A.x=10 B.int x=10 C.var x=10 D.var x，y，x=10 参考答案：B 9. 有时不需要将一个布尔表达式从头算到尾，而只需计算它的一个子表达式，便能确定整个布尔表达式的真假值。( ) A.错误 B.正确 参考答案：B 10. 上下文无关文法可以用( )来描述。 A.正则表达式 B.正规文法 C.扩展的BNF D.翻译模式
参考答案：C 11. 一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。( ) A.错误 B.正确 参考答案：A 12. 1型文法也称为( )。 A.短语文法 B.上下文有关文法 C.右线性文法 D.左线性文法 参考答案：B 13. 下面关于解释程序的描述正确的是( )。(1)解释程序的特点是处理程序时不产生目标代码(2)解释程序适用于COBOL和FORTRAN语言(3)解释程序是为打开编译程序技术的僵局而开发的 A.(1)(2) B.(1) C.(1)(2)(3) D.(2)(3) 参考答案：B 14. 一个文法，如果能为它构造出所有条目都唯一的LR分析表，就说它是LR文法。( ) A.正确 B.错误 参考答案：A 15. 有文法G=({S}，{a}，{S→SaS，S→e}，S)，该文法是哪一类文法?( ) A.LL(1)文法
编译原理试卷A 选择题(每空2分,共20分) 1.一个正规语言只能对应( B ) A 一个正规文法; B 一个最小有限状态自动机; 2.文法G[A]:A→ε A→aB B→Ab B→a是( B ): A 正规文法 B 二型文法 3.下面说法正确的是( A ): A 一个SLR(1)文法一定也是LALR(1)文法 B 一个LR(1)文法一定也是LALR(1)文法 4.一个上下文无关文法消除了左递归,提取了左公共因子后是满足LL(1)文法的( A ): A 必要条件 B 充分必要条件 5. ( D )不是NFA的成分. A 由穷字母表 B 初始状态集合 C 终止状态集合 D 有限状态集合 6.(C )不是编译程序的组成部分 A 词法分析程序 B 代码生成程序 C 设备管理程序 D 语法分析程序 7.有文法G=({S},{a},{S→SaS, S→ε},S),该文法是( B ). A. LL(1)文法 B. 二义性文法C 算符优先文法D SLR(1)文法 8 给定文法A→bA|cc,则符号串①cc②bcbc③bcbcc④bccbcc⑤bbbcc中,是该文法句子的是( D ) A ① B ③④⑤ C ②④ D ①⑤ 9 表达式A*(B-C*(C/D))的逆波兰表示为( B ) A. ABC-CD/** B. ABCCD/*-* C. ABC-*CD/* D. 前三个选项都不对 10 LR(1)文法都是( A ) A 无二义性且无左递归 B 可能有二义性但无左递归 C 无二义性但可能有无左递归 D 可以既有二义性又有左递归 问答题 第1题(10分)将文法G[S] 改写为等价的G′[S],使G′[S]不含左递归和左公共因子. G[S]: S→bSAe | bA A→Ab | d 答:文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为: S→bB B→SAe | A A→d A' A' →bA' | ε 第2题(10分) 给出与正规式R=(ab)*(a|b*)ba等价的NFA. 答: 与正规式R=(ab)*(a|b*)ba 等价的NFA如下图 第3题(10分)将下图的NFA确定化为DFA. 答:用子集法确定化如下表 用子集法对所给图的确定化 I
《计算机编译原理》试卷A1参考答案 一、单项选择题（每小题1分，共25分） 1、语言是＿＿＿A＿＿＿ A、句子的集合 B、产生式的集合 C、符号串的集合 D、句型的集合 2、编译程序前三个阶段完成的工作是＿＿＿C＿＿＿ A、词法分析、语法分析和代码优化 B、代码生成、代码优化和词法分析 C、词法分析、语法分析、语义分析和中间代码生成 D、词法分析、语法分析和代码优化 3、一个句型中称为句柄的是该句型的最左＿＿＿D＿＿＿ A、非终结符号 B、短语 C、句子 D、直接短语 4、下推自动机识别的语言是＿＿＿C＿＿＿ A、0型语言 B、1型语言 C、2型语言 D、3型语言 5、扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即＿＿＿B＿＿＿ A、字符 B、单词 C、句子 D、句型 6、对应Chomsky四种文法的四种语言之间的关系是＿＿＿B＿＿＿ A、L0⊂L1⊂L2⊂L3 B、L3⊂L2⊂L1⊂L0 C、L3=L2⊂L1⊂L0 D、L0⊂L1⊂L2=L3 7、词法分析的任务是＿＿＿A＿＿＿ A、识别单词 B、分析句子的含义 C、识别句子 D、生成目标代码 8、常用的中间代码形式不含＿＿＿D＿＿＿ A、三元式 B、四元式 C、逆波兰式 D、语法树 9、代码优化的目的是＿＿＿C＿＿＿ A、节省时间 B、节省空间 C、节省时间和空间 D、把编译程序进行等价交换 10、代码生成阶段的主要任务是＿＿＿C＿＿＿ A、把高级语言翻译成汇编语言 B、把高级语言翻译成机器语言 C、把中间代码变换成依赖具体机器的目标代码 D、把汇编语言翻译成机器语言 11、一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个开始符号，以及一组＿＿＿B＿＿＿。 A、字符串 B、产生式 C、数字符号 D、文法 12、程序的基本块是指＿＿＿D＿＿＿。 A、一个子程序 B、一个仅有一个入口和一个出口的语句 C、一个没有嵌套的程序段 D、一组顺序执行的程序段，仅有一个入口和一个出口 13、高级语言编译程序常用的语法分析方法中，递归下降分析法属于＿＿＿B＿＿＿分析方法。 A、自左向右 B、自顶向下 C、自底向上 D、自右向左 14、在通常的语法分析方法中，＿＿＿A＿＿＿特别适用于表达式的分析。 A、算符优先分析法 B、LR分析法 C、递归下降分析法 D、LL（1）分析法 15、经过编译所得到的目标程序是＿＿＿D＿＿＿。 A、四元式序列 B、间接三元式序列
华东师范大学试卷及答案（A ） 学生姓名：_____________ 学号：___________________ 学生系别：_____________ 专业：______________ 年级___________班级_____________ 课程名称：编译原理 课程性质：专业必修 一、问答题 1. 设G=（V N ，V T ，P ，）是上下文无关文法，产生式集合P 中任意一个产生式 应具有什么样的形式？若G 是正则文法呢？（5％） 答：一般形式为
答： + 4. 试将下述程序段翻译成三地址形式的中间代码表示。（8％） 答：三地址代码如下： 100: t:=a+b 101: if t 2003－2004学年第二学期 韶关学院计算机系《编译原理》期末考试试卷（A 卷答案） 年级：00 专业：计算机科学技术 班级： 学号： 姓名： 题号 一 二 三 四 五 总分 签名 得分 注：1、共120分钟，总分100分 。 2、此试卷适用专业：计算机本科 一 得 分 阅卷教师 一、判断题：（每小题1分，共5分） 1、每个文法都能改写为LL(1)文。 （×） 2、符号表是上下文语义的合法性检查的依据之一。 （√） 3、函数backpatch(p,t)的功能是指将字符p 后退t 格。 （×） 4、算符优先关系表不一定存在对应的优先函。 （√） 5、“把所有语言中的符号都组织在一张符号表中”是用得最多的一种对符号表的总体组织方法中。 （×） 二 得 分 阅卷教师 二、填空题(每空1分，共20分) 1、编译过程一般分为：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段。 2、词法分析的任务是：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描，从而识别出一个个单词。 3、语法分析最常用的两类方法是 自顶向下分析法 和自底向上分析法。 4、一个上下文无关文法包含非终结符集、终结符集、产生式集和开始符号四个组成部分是。 5、在有穷自动机中，两类状态s 和t 等价的条件是：一致性条件和蔓延性条件。 6、程序设计语言的语义分为：静态语义和动态语义两类。 7、乔姆斯把文法分成 0型文法（短语文法）、1型文法（上下文有关文法）、2型文法（上下文无关文法）和3型文法（正规文法）四种类型。 三 得 分 阅卷教师 ——————————————装————————————————订————————————————线————————— 贵州大学计算机科学与信息学院 2011-2012 学年第二学期考试试卷 A 《编译原理》 注意事项： 1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。 2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。 3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。 4. 满分100分，考试时间为120分钟。 一、 填空题(每空1分, 共20分) 1. 有穷自动机接受的语言是 语言。 2. ∑={a, b}，则∑上所有以字符a 开头的字符串的正规式为： 。 3. 活前缀是指规范句型的一个前缀，其中不含 之后的任意符号。 4. 编译程序的整个过程从逻辑上依次分为词法分析、 、语义分析、中间代码生成、 代码优化和 等几个阶段。另外还有两个重要工作是 和出错处理。 5. 语法分析方法可以分为 和 两大类。 6. 数据空间的动态存储分配方式可分为 和 两种。 7. 表达式a+b*(c-d)的逆波兰式为： 。 8. LR(0)文法中，不会出现 冲突和 冲突。 9.LL(1)文法应该消除和。 10.嵌套过程静态作用域的实现方式通常有两种，一种是为每个活动记录增加一个称为访问链的指 针，还有一种则是通过使用一个称为的指针数组来实现非局部名字的访问。 11.已知如下程序段，采用传值的方式进行参数传递时，程序输出结果为，采用传地址 的方式进行参数传递时，程序输出结果为，采用传值结果的方式进行参数传递时，程序输出结果为，采用传名的方式进行参数传递时，程序输出结果为。 主程序子程序 A:=2; B:=3; P(X,Y,Z); P(A+B, A, A); {Y:=Y+1; print A Z:=Z+X; } 二、单选题(每题2分, 共20分) 1.Chomsky定义的四种形式语言文法中，上下文无关文法是()。 A. 0型文法 B. 1型文法 C. 2型文法 D. 3型文法 2.设有文法G(S):S→b|bB B→bS，则该文法所描述的语言是()。 A. L(G)={b2i+1|i≥0} B. L(G)={b2i+1|i≥1} C. L(G)={b2i|i≥0} D. L(G)={b2i|i≥1} 3.经过编译所得到的目标程序是()。 A. 三元式序列 B. 四元式序列 C. 间接三元式 D. 机器语言程序或汇编语言程序 4.中间代码生成所依据的是（）。 A. 词法规则 B. 语法规则 C. 语义规则 D. 产生式规则 5.词法分析器加工处理的对象是（）。 A. 单词 B. 源程序 C. 中间代码 D. token串 6.与正则表达式a*b*等价的文法是（）。 A. G1：S→abS|ε B. G2：S→aS|Sb|ε C. G3：S→aSb|ε D. G4：S→aS|bS|ε 华东交通大学2010—2011学年第二学期考试卷 试卷编号： （ A ）卷 编译原理（E ） 课程 课程类别：必修课 考生注意事项：1、本试卷共 7 页，总分 100 分，考试时间 120 分钟。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 一、简答题 (每题 5 分，共 20 分) 1． 简述编译程序与解释程序的主要差异？ 【答】 编译程序产生中间代码，且效率高； 解释程序不产生中间代码，且效率低。 2． 文法的二义性与语言的二义性是两个相同的概念吗？请说明理由。 【答】这两个概念是不相同的。文法的二义性指的是文法所描述的语言中至少存在一个句子，而该句子对应两棵不同的语法树（或最左（右）推导）；而语言的二义性是指描述该语言的全部文法都是二义性的。 由于描述同一个语言的文法可以有多个，一个二义性文法也可能找到一个等价的无二义性文法，所以一个文法是二义性的，其描述的语言不一定就是二义性的。 3． 简述在句型分析中的自上而下与自下而上两类分析方法的主要差异？ 【答】自上而下的分析方法是从文法的开始符号出发，反复使用推导技术，试图把要分析的句型推导出来；自下而上的分析方法是从要分析的句型出发，反复使用归约技术，试图最终归约出文法的开始符号。 4．为什么说“素短语是包含有终结符的直接短语”的论断是错误的？并针对文法G[E]：(1) E→E+T | T (2) T→T*F | F (3) F→i 中的句型T+T+F，举一个反例加以进一步说明。 【答】在一个文法的句型中，其素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。而不是说是一个直接短语。 例如：文法G[E]中的句型T+T+F，其一个素短语为：T+T，而T+T 是素短语，但不是直接短语。 二、形式文法与自动机题(共20 分) L={ a i b j a j b i| i＞0，j≥1 } 【答】描述该语言的文法G[S]为： S→aAb |εA→bAa | ba 2.对文法 G[E] : E→A│E+A │E–A A→B│A*B B→(E)│a 写出句型B-(E)*a 的短语、直接短语和句柄。（5分） 【答】该句型的对应的语法树如下： 故其短语、直接短语和句柄分别为： 短语：B；(E)；a；(E)*a；B-(E)*a 直接短语：B；(E)；a 句柄：B 湖北第二师范学院2014－2015学年度第二学期 《编译原理》课程考试答案(A卷) 院系：计算机学院专业班级： 学生姓名：学号： 考试方式：闭卷……………………………………………………………………………………………………………… 一、填空题（每空1分，共10分） 1．词法分析程序是逐个识别（字符），形成单词级别的（字符）串，词法分析程序输出 的数据是（2 ）个，它们分别是（种别编码 ）和（自身值）。 2．语法分析程序是逐个识别（单词），形成语句级别的（单词）串。 3．一遍扫描的编译方法，是以语法分析程序为主，调用（词法分析）程序、语义分析程序，再由语义程序调用中间代码生成、中间代码优化等。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即（静态存储分配）方案和（动态存储分配）方案。 二、综合题（共90分） 1．（5分）将下面文法改写成3型文法： G=（｛S,A,B｝,{a,b,c,d,e},P,S） 其中：P={S→abcA|edB,A→beB,B→d} 答案：改写后的3型文法是（5分） G=（｛S,A,B,C,D,E,F｝,{a,b,c,d,e},P,S） 其中：P={S→aC|eF, C→bD,D→cA,A→bE,E→eB,F→dB,B→d} 2．（5分）给出下面表达式的四元式形式： a*b+(c-d)/e 答案：四元式形式（5分） （*，a，b，t1） （-，c，d，t2） （/，t2，e，t3） （+，t1，t3，t4） 3．（30分）给定文法 G[E] ： E → E+T | E-T | T T → T*F | T/F | F F → (E) | i 该文法是 LL(1) 文法吗？为什么？不是的能否改造为LL（1）文法，如果能够改造，给出改造后的文法，并给出改造后文法是LL（1）文法的证明过程。无论改造前还是改造后的文法，如果是LL（1）文法，则给出（i+i）*i的分析过程（要求给出详细过程，并给出LL（1）的分析表）答案：（1）该文法不是LL（1）文法，因为文法的产生式含有左递归（2分）（2）该文法可改造为LL（1）文法，即消除左递归，改造后的文法是（3分） E → TE’ E’→ +TE’ | -TE’ | ε T → FT’ T’→ *FT’ | /FT’ |ε F → (E) | i 证明改造后的文法是LL（1）文法的过程 A.求可达ε的非终结符（1分） 可达的是E’,T’ B.求每个非终结符的First集合（3分） First(E)={ (,i} First(E’)={+,-} First(T)={ (,i} First(T’)={*,/} First(F)={ (,i} C.求每个产生式右部字符串的First集合（3分） First(TE’)={ (,i} First(+TE’)={+} First(-TE’)={-} First(FT’)={ (,i} First(*FT’)={*} First(/FT’)={/} First((E))={ ( } First(i)={ i } First(ε)={ ε} D.求每个非终结符的Follow集合（3分） Follow(E)={$,)} Follow(E’)= Follow(E)={$,)} Follow(T)=First(E’) ∪ Follow(E)={$,+,-,)} Follow(T’)= Follow(T)={$,+,-,)} Follow(F)= First(T’) ∪ Follow(T)={$,+,-, *,/,)} E.求每个非终结符的Select集合（5分） Select(E → TE’)=First(TE’)={ (,i } Select(E’→ +TE’)=First(+TE’)={ + } Select(E’→ -TE’)=First(-TE’)={ - } 编译原理期末试卷 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|c 3．文法G[S]为：（10分） S→SdT | T T→T 6．简述编译程序概念及构成。（10分） 编译程序是现代计算机系统的基本组成部分.从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序. 7．设G=（V N，V T，P， 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)|i 1. 请构造句型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:=L 1．构造基本块对应的DAG 图。(5分) 2．若G ，M ，L 在基本块后要引用，写出优化后的代码(5分)。 院系： 专业班级： 姓名： 学号： 装 订 线 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分 ) （1） 我们把右部仅含一个非终结符号的产生式，称为什么产生式()。 •A无用 •B有用 •C奇 •D单 正确答案:D （2） 编译过程的核心部分是什么()。 •A语法结构 •B语法分析 •C源程序 •D单词符号 正确答案:B （3） 所谓NFA的确定化，是指对任给的NFA，都能相应地构造一DFA，使它们有相同的什么()。 •A状态集 •B符号集 •C接受集 •D结点集 正确答案:C （4） 正则式的“|”读作什么()。 •A并且 •B或者 •C连接 •D闭包 正确答案:B （5） 对于自底向上的语法分析而言，须着重解决的问题是什么()。 •A如何确定一个规范句型的句柄 •B应将句柄归约为哪个非终结符号 •C如何确定一个规范句型的句柄，以及应将句柄归约为哪个非终结符号•D以上都不是 正确答案:C （6） 已知文法G定义为：S→WZ,W→X|Y,X→x|xX,Y→y|yY,Z→z|zZ，与该文法描述相同语言的正规表达式是哪个()。 •A xx*|yy*|zz* •B(xx*|yy*)zz* •C xx*(yy*|zz*) •D(xx|yy)*zz* 正确答案:B （7） 设d是结点n的必经结点(即有d DOM n)，若在流程图中，存在着从结点n到d 的有向边，则称此有向边为流程图中的一条什么()。 •A环路 •B环边 •C回路 •D回边 正确答案:D （8） 文法Z→ABb|c，A→Ba，B→Za中含有什么样的非终结符号()。 •A直接左递归 •B直接右递归 •C间接左递归 •D间接右递归 正确答案:C （9） LL(1)分析表可用一个二维数组表示，它的每一行与文法的一个什么符号相关联()。 •A非终结符号 •B终结符号 •C界符#号 •D开始符号 正确答案:A （10） 局部优化是局限于什么范围内的一种优化()。 •A一个程序块 •B一个基本块 •C一个循环 •D一个语句 正确答案:B （11） 语言L={ambn|m≥0，n≥1}的正规表达式是什么()。 •A a*bb* •B aa*bb* •C aa*b* •D a*b* 正确答案:A （12） 在文法中，由于有些符号不需要进一步定义，故通常将它们称为什么()。 •A终结符号 •B非终结符号 •C开始符号 •D基本符号 正确答案:A （13） 在BNF表示方法中，“|”表示什么()。[03_04(2)]《编译原理》00本科班A卷(答案)
编译原理试卷A
编译原理2010-2011试卷---A(答案)
编译原理(A卷)答案
编译原理考试试卷+答案A卷
）是上下文无关文法，产生式集合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(); }2020-2021《编译原理》期末课程考试试卷A(含答案)
XX大学20XX～202X学年第X学期期末考试《编译原理》试卷
编译原理试卷
相关主题
文本预览