参考答案 一、单项选择题(共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．词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则 从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位， 并转换成统一的内部表示(token)，送给语法分析程序。 2．LL(1)文法 若文法的任何两个产生式A→α |β都满足下面两个条件： （1）FIRST(α)?FIRST(β ) = φ； （2）若β?* ε，那么FIRST(α) ?FOLLOW( A ) =φ。 我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左 向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步 动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一 些明显的性质，它不是二义的，也不含左递归。 3．语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。 给定文法G=(V N，V T，P，S)，对于G的任何句型都能构造与之关联的 语法树。这棵树具有下列特征：
《编译原理》考试试卷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．便于编译程序的移植
西安邮电学院2007 —2008 学年第二学期 《编译原理》课程期中考试卷（A） 考核形式：闭卷班级：姓名：学号： 一、填空题（30分，每空2分） 1．由文法开始符号经0步或多步推导产生的文法符号序列是__句型__。 2．编译器通常经历___词法分析______、____语法分析_______、__语义分析和中间代码生成___、____优化___、__目标代码生成___等几个阶段；其中第一个阶段是以__源程序__为输入，_单词符号_为输出；最后一阶段是以_中间代码_为输入，_机器语言程序或汇编语言程序__为输出。同时_表格管理_和_出错处理_贯穿编译器的各个阶段。 3．解释器与编译器的主要区别是：____编译程序生成目标代码，而解释程序不生成目标代码____。 4．高级语言到低级语言的翻译过程称为__编译__。汇编语言到机器语言的翻译过程称为__汇编__。 二、单项选择题（20分，每小题2分） 1．正规表达式(ε|a|b)2表示的集合是（ D ）。 A．{ε，ab，ba，aa，bb} B．{ab，ba，aa，bb} C．{a，b，ab，aa，ba，bb} D．{ε，a，b，aa，bb，ab，ba} 2．分析树的内部结点仅由（C ）组成。 A．开始符号和非终结符号B．终结符号和非终结符号 C．非终结符号D．终结符号 3．文法 S→(L)|a L→L，S|S 的终结符号是（C）。 A．S B．S L C．a , ( ) D．a , ( ) | 4．NFA M所识别的语言是（ D ）。 A．0型语言B．上下文有关语言 C．上下文无关语言D．正规语言 5．同正规式a*b*等价的文法是（C ）。 A．S→aS|bS|εB．S→aSb|ε C．S→aS|Sb|εD．S→abS|ε 6．对LR分析表的构造，不可能存在( C )动作冲突。 A．移进/归约B．归约/归约C．移进/移进 D.以上都不对 7．LR分析模式中，改变格局变化的动作不包括（ B ）。 A．移进B．匹配终结符 C．归约D．接受 8．如果一个文法G是二义文法，则必存在某个句子X∈L（G），该句子（）。 A．存在两个不同的最右推导和一个最左推导
课程测试试题（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分)
《计算机编译原理》试卷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、间接三元式序列
华东交通大学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
编译原理试题 一、填空题 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．给出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， 编译原理试卷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 期末考试试卷〔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 《编译原理》考试试题及答案（附录） 一、判断题： 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.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。 2023编译原理试题及参考答案 编译原理试题一、是非题 (请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1.词法分析器的输出结果是_____。 A.( ) 单词的种别编码 B.( ) 单词在符号表中的位置 C.( ) 单词的种别编码和自身值 D.( ) 单词自身值 2. 正规式 M 1 和 M 2 等价是指_____。 A.( ) M1和M2的状态数相等 B.( ) M1和M2的有向边条数相等 C.( ) M1和M2所识别的语言集相等 D.( ) M1和M2状态数和有向边条数相等 3. 文法G：SxSx|y所识别的语言是_____。 A.( ) xyx B.( ) (xyx)__ C.( ) xnyxn(n0) D.( ) x__yx__ 4.如果文法G是无二义的，则它的任何句子_____。 A.( )最左推导和最右推导对应的语法树必定相同 B.( ) 最左推导和最右推导对应的语法树可能不同 C.( ) 最左推导和最右推导必定相同 D.( )可能存在两个不同的最左推导，但它们对应的语法树相同 5.构造编译程序应掌握______。 A.( )源程序 B.( ) 目标语言 C.( ) 编译方法 D.( ) 以上三项都是 6.四元式之间的联系是通过_____实现的。 A.( ) 指示器 B.( ) 临时变量 C.( ) 符号表 D.( ) 程序变量 7.表达式(┐AB)(CD)的逆波兰表示为_____。 A. ( ) ┐ABCD B.( ) A┐BCD C.( ) AB┐CD D.( ) A┐BCD 8. 优化可生成_____的目标代码。 A.( ) 运行时间较短 B.( ) 占用存储空间较小 C.( ) 运行时间短但占用内存空间大 D.( ) 运行时间短且占用存储空间小 9.下列______优化方法不是针对循环优化进行的。 A. ( ) 强度削弱 B.( ) 删除归纳变量 C.( ) 删除多余运算 D.( ) 代码外提 10.编译程序使用_____区别标识符的作用域。 A. ( ) 说明标识符的过程或函数名 B.( ) 说明标识符的过程或函数的静态层次 C.( ) 说明标识符的过程或函数的动态层次 D. ( ) 标识符的行号 编译原理测试题及其答案 1.一个上下文无关文法的开始符，可以是终结符或非终结符。[判断题]* 对 错(正确答案) 2.一个句型的直接短语是唯一的。[判断题]* 对 错(正确答案) 3.已经证明文法的二义性是可判定的。[判断题]* 对 错(正确答案) 4.每个基本块可用一个DAG表示。[判断题]* 对(正确答案) 错 5.每个过程的活动记录的体积在编译时可静态确定。[判断题]* 对(正确答案) 错 6.2型文法一定是3型文法[判断题]* 对 错(正确答案) 7.一个句型一定句子。[判断题]* 对 错(正确答案) 8.算符优先分析法每次都是对句柄进行归约。[判断题]* 对 错(正确答案) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。[判断题]* 对(正确答案) 错 10.编译过程中，语法分析器的任务是分析单词是怎样构成的[判断题]* 对 错(正确答案) 11.一个优先表一定存在相应的优先函数。[判断题]* 对 错(正确答案) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。[判断题]* 对(正确答案) 错 13.递归下降分析法是一种自下而上分析法。[判断题]* 对 错(正确答案) 14.并不是每个文法都能改写成LL(1)文法。[判断题]* 对(正确答案 错 15.每个基本块只有一个入口和一个出口。[判断题]* 对(正确答案) 错 16.一个LL(1)文法一定是无二义的。[判断题]* 对(正确答案) 错 17.逆波兰法表示的表达试亦称前缀式。[判断题]* 对 错(正确答案) 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。[判断题]* 对(正确答案 错 19.正规文法产生的语言都可以用上下文无关文法来描述。[判断题]* 对(正确答案) 错 20.一个优先表一定存在相应的优先函数。[判断题]* 对 错(正确答案) 21.3型文法一定是2型文法。[判断题]* 对(正确答案) 错 试卷 答题时限：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）用子集法将NFA确定化（2分) 将所有子集重命名,得到转换矩阵： 《编译原理》模拟题 一.单选题 1.()是两类程序语言处理程序. A.高级语言程序和低级语言程序 B.解释程序和编译程序 C.编译程序和操作系统 D.系统程序和应用程序 [答案]:B 2.解释程序处理语言时,大多数采用的是()方法. A.源程序命令被逐个直接解释执行 B.先将源程序转化为中间代码,再解释执行 C.先将源程序解释转化为目标程序,再执行 D.以上方法都可以 [答案]:A 3.()是一种典型的解释型语言. A.BASIC B.C C.FORTRAN D.PASCAL [答案]:A 4.与编译系统相比,解释系统(). A.比较简单,可移植性好,执行速度快 B.比较复杂,可移植性好,执行速度快 C.比较简单,可移植性差,执行速度慢 D.比较简单,可移植性好,执行速度慢 [答案]:D 5.编译程序是一种(). A.汇编程序 B.翻译程序 C.解释程序 D.目标程序 [答案]:B 6.编译程序是对(). A.汇编程序的翻译 B.高级语言程序的解释执行 C.机器语言的执行 D.高级语言的翻译 [答案]:D 7.用高级语言编写的程序经编译后产生的程序叫(). A.源程序 B.目标程序 C.连接程序 D.解释程序 [答案]:B 8.将编译程序分成若干个“遍”是为了(). A.提高程序的执行效率 B.使程序的结构更加清晰 C.利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 [答案]:B 9.构造编译程序应掌握(). A.源程序 B.目标语言 C.编译方法 D.以上三项都是 [答案]:D 10.通常一个编译程序中,不仅包含词法分析,语法分析,中间代码生成,代码优化,目标代码生成等五个部分,还应包括(). A.模拟执行器 B.解释器 C.表格处理和出错处理 D.符号执行器 [答案]:C 11.编译程序绝大多数时间花在()上. A.出错处理 B.词法分析 C.目标代码生成 D.管理表格 [答案]:D 12.程序的基本块是指(). A.一个子程序 B.一个仅有一个入口和一个出口的语句 C.一个没有嵌套的程序段 D.一组顺序执行的程序段,仅有一个入口和一个出口 [答案]:D 13.变量应当().）是上下文无关文法，产生式集合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(); }编译原理试卷A
编译原理期末考试试卷及答案
《编译原理》考试试题及答案
2023大学_编译原理试题及参考答案
编译原理测试题及其答案
编译原理期末考试试卷A卷
编译原理试题及答案
相关主题
文本预览