编译原理复习题

编译原理复习题一、填空题1.编译程序的工作过程一般可以划分为词法分析，语法分析，语义分析，中间代码优化，代码优化等几个基本阶段。

2.若源程序是用高级语言编写的，目标程序是汇编程序或机器语言程序，则其翻译程序称为编译程序.3.编译方式与解释方式的根本区别在于是否生成目标代码.5.对编译程序而言，输入数据是源程序，输出结果是目标程序 .7.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。

8.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格管理和出错处理。

其中，词法分析器用于识别单词。

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

12.产生式是用于定义语法成分的一种书写规则。

13.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)={x|Sx，x∈VT*}。

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

15.设G是一个给定的文法，S是文法的开始符号，如果S*⇒x(其中x∈V T*)，则称x是文法的一个句子。

16.扫描器的任务是从源程序中识别出一个个单词符号。

17.语法分析最常用的两类方法是自顶向下和自底向上分析法。

18.语法分析的任务是识别给定的终结符串是否为给定文法的句子。

19.递归下降法不允许任一非终结符是直接左递归的。

20.自顶向下的语法分析方法的关键是如何选择候选式的问题。

21.递归下降分析法是自顶向下分析方法。

22.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。

23.自底向上的语法分析方法的基本思想是：从给定的终结符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。

编译原理复习题及答案一、选择题1．一个正规语言只能对应(B)A 一个正规文法B 一个最小有限状态自动机2．文法G[A]：A→εA→aB B→Ab B→a是(A)A 正规文法B 二型文法3．下面说法正确的是(A)A 一个SLR（1）文法一定也是LALR（1）文法B 一个LR（1）文法一定也是LALR（1）文法4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A)A 必要条件B 充分必要条件5．下面说法正确的是(B)A 一个正规式只能对应一个确定的有限状态自动机B 一个正规语言可能对应多个正规文法6．算符优先分析与规范归约相比的优点是(A)A 归约速度快B 对文法限制少7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B)A 则可能存在移进/归约冲突B 则可能存在归约/归约冲突C 则可能存在移进/归约冲突和归约/归约冲突8．下面说法正确的是(A)A Lex是一个词法分析器的生成器B Yacc是一个语法分析器9．下面说法正确的是(A)A 一个正规文法也一定是二型文法B 一个二型文法也一定能有一个等价的正规文法10．编译原理是对(C)。

A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行11．用高级语言编写的程序经编译后产生的程序叫(B)A．源程序 B．目标程序C．连接程序D．解释程序12．(C)不是编译程序的组成部分。

A.词法分析程序B.代码生成程序C.设备管理程序D.语法分析程序13．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。

A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器14．源程序是句子的集合，(B)可以较好地反映句子的结构。

A. 线性表B. 树C. 完全图D. 堆栈15．词法分析器的输出结果是(D)。

A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值16．词法分析器不能(D)A. 识别出数值常量B. 过滤源程序中的注释C. 扫描源程序并识别记号D. 发现括号不匹配17．文法：G：S→xSx | y所识别的语言是(D)。

编译原理复习题一、选择题1、编译原理是对(C)。

A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行2、(A)是一种典型的解释型语言。

A．BASIC B．C C．FORTRAN D．PASCAL3、把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。

A. 编译器B. 汇编器C. 解释器D. 预处理器4、用高级语言编写的程序经编译后产生的程序叫(B)A．源程序 B．目标程序C．连接程序D．解释程序5、(C)不是编译程序的组成部分。

A.词法分析程序B.代码生成程序C.设备管理程序D.语法分析程序6、通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。

A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器7、编译程序绝大多数时间花在(D)上。

A．出错处理B．词法分析C．目标代码生成D．表格管理8、源程序是句子的集合，(B)可以较好地反映句子的结构。

A. 线性表B. 树C. 完全图D. 堆栈9、词法分析器的输出结果是(D)。

A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值10、词法分析器不能(D)A. 识别出数值常量B. 过滤源程序中的注释C. 扫描源程序并识别记号D. 发现括号不匹配11、文法：G：S→xSx | y所识别的语言是(D)。

A、xyxB、(xyx)*C、x*yx*D、x n yx n (n≥0)12、如果文法G是无二义的，则它的任何句子α(A)A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同13、正则文法(A)二义性的。

A. 可以是B. 一定不是C. 一定是14、(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。

编译原理复习题有答案编译原理复习题及答案一、选择题1. 编译器的主要功能是什么？A. 代码格式化B. 代码优化C. 将源代码转换为机器码D. 错误检测和修复答案：C2. 词法分析阶段的主要任务是什么？A. 语法分析B. 语义分析C. 识别源程序中的词法单元D. 代码生成答案：C3. 下列哪个不是编译原理中的常见数据结构？A. 栈B. 队列C. 哈希表D. 链表答案：D4. 语法分析通常采用哪种方法？A. 递归下降分析B. 动态规划C. 贪心算法D. 深度优先搜索答案：A5. 代码优化的目的是什么？A. 增加程序长度B. 减少程序运行时间C. 提高程序的可读性D. 增加程序的复杂性答案：B二、简答题1. 简述编译过程的主要阶段。

答案：编译过程主要分为四个阶段：词法分析、语法分析、语义分析和代码生成。

词法分析负责将源代码分解成词法单元；语法分析构建语法树，检查源代码的语法结构；语义分析检查程序的语义正确性；代码生成将源代码转换成目标代码或机器码。

2. 什么是自底向上的语法分析方法？答案：自底向上的语法分析方法是一种从叶子节点开始，逐步向上构建语法树的方法。

它通常使用移进-归约分析技术，通过将输入符号与栈顶符号进行匹配，不断地将它们归约成非终结符，直到整个输入被归约为起始符号。

3. 请解释什么是中间代码，并说明其作用。

答案：中间代码是一种介于源代码和目标代码之间的代码形式，通常用于代码优化和目标代码生成。

它具有高级语言的可读性，同时又能表达程序的控制流和数据流信息。

中间代码使得编译器可以在不同的阶段对程序进行优化，提高程序的执行效率。

三、论述题1. 论述编译原理中的错误处理机制。

答案：编译原理中的错误处理机制主要包括错误检测、错误恢复和错误报告。

错误检测是指在编译过程中识别出源代码中的语法或语义错误；错误恢复是指在检测到错误后，编译器采取的措施以继续编译过程，避免因单个错误而中断整个编译；错误报告则是向程序员提供错误信息，帮助其定位和修复错误。

编译原理复习题及答案一、选择题1．一个正规语言只能对应( B )A 一个正规文法B 一个最小有限状态自动机2．文法G[A] ：A→εA→aB B→Ab B→a是( A )A 正规文法B 二型文法3．下面说法正确的是( A ) A一个SLR（1）文法一定也是LALR （1）文法B一个LR （1）文法一定也是LALR （1）文法4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL （1）文法的( A )A 必要条件B 充分必要条件5．下面说法正确的是( B )A 一个正规式只能对应一个确定的有限状态自动机B 一个正规语言可能对应多个正规文法6．算符优先分析与规范归约相比的优点是( A )A 归约速度快B 对文法限制少7．一个LR （1）文法合并同心集后若不是LALR （1）文法( B )A 则可能存在移进/归约冲突B 则可能存在归约/归约冲突C 则可能存在移进/归约冲突和归约/ 归约冲突8．下面说法正确的是( A )A Lex 是一个词法分析器的生成器B Yacc 是一个语法分析器9．下面说法正确的是( A )A一个正规文法也一定是二型文法B一个二型文法也一定能有一个等价的正规文法10．编译原理是对(C) 。

A 、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行11．(A) 是一种典型的解释型语言。

A ．BASICB ．CC．FORTRAN D．PASCAL12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B) 完成的。

A. 编译器B. 汇编器C. 解释器D. 预处理器13．用高级语言编写的程序经编译后产生的程序叫(B) A ．源程序B ．目标程序C．连接程序 D ．解释程序14．(C) 不是编译程序的组成部分。

A. 词法分析程序B. 代码生成程序C.设备管理程序D. 语法分析程序15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优目标代码生成等六个部分，还应包括(C)A ．模拟执行器B ．解释器C．表格处理和出错处理D ．符号执行器16．编译程序绝大多数时间花在(D) A ．出错处理B．词法分析C．目标代码生成D．表格管理17．源程序是句子的集A. 线性表(B) 可以较好地反映句子的结构。

编译原理（一）一、是非题1、算符优先关系表不一定存在对应的优先函。

………………………………………（）2、数组元素的地址计算与数组的存储方式有关。

……………………………（）3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。

…………………………（）4、每个文法都能改写为LL(1)文法。

……………………………………………（）5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。

………………（）二、填空题1、从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。

2、扫描器的任务是从（）中识别出一个个（）。

3、所谓最右推导是指：（）。

4、语法分析最常用的两类方法是（）和（）分析法。

5、一个上下文无关文法所含四个组成部分是（）。

6、所谓语法制导翻译方法是（）。

7、符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。

8、一个过程相应的DISPLA Y表的内容为（）。

9、常用的两种动态存贮分配办法是（）动态分配和（）动态分配。

10、产生式是用于定义（）的一种书写规则。

三、名词解释1、遍－－2、无环路有向图(DAG)－－3、语法分析－－4、短语－－5、后缀式－－四、简述题1、考虑下面程序…………V ar a：integer；Procedure S(X)；V ar X：integer；Begina：＝a＋1；X：＝a＋XEnd；Begina：＝5；S(a)；Print(a)End．试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？2、画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。

3、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。

4、已知文法G(S)S→a|∧|(T)T→T，S|S写出句子((a，a)，a)的规范归约过程及每一步的句柄。

5、何谓优化？按所涉及的程序范围可分为哪几级优化？6、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？五、计算题1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。

《编译原理》复习题（看完必过）一、单项选择题1．将编译程序分成若干个“遍”是为了( B )A．提高程序的执行效率B. 使程序的结构更加清晰C．利用有限的机器内存并提高机器的执行效率D．利用有限的机器内存但降低了机器的执行效率2．不可能是目标代码的是( D )A．汇编指令代码 B．可重定位指令代码C．绝对指令代码 D．中间代码3．词法分析器的输入是( B )A．单词符号串 B．源程序C．语法单位 D．目标程序4．中间代码生成时所遵循的是( C )A．语法规则 B．词法规则C．语义规则 D．等价变换规则5．编译程序是对( D )A．汇编程序的翻译 B．高级语言程序的解释执行C．机器语言的执行 D．高级语言的翻译6．词法分析应遵循( C )A．语义规则 B．语法规则C．构词规则 D．等价变换规则7．词法分析器的输出结果是( C )A．单词的种别编码 B．单词在符号表中的位置C．单词的种别编码和属性值 D．单词属性值8．正规式M1和M2等价是指( C )A．M1和M2的状态数相等 B．M1和M2的有向弧条数相等C．M1和M2所识别的语言集相等 D．M1和M2状态数和有向弧条数相等9．词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，( B ) A．词法分析器应作为独立的一遍B．词法分析器作为子程序较好C．词法分析器分解为多个过程，由语法分析器选择使用．D．词法分析器并不作为一个独立的阶段10．如果L(M1)=L(M2)，则M1与M2( A )A ．等价B ．都是二义的C ．都是无二义的D ．它们的状态数相等 11．文法G ：S →xSx|y 所识别的语言是( C )A ．xyxB ．(xyx)* c ．x n yx n (n ≥0) d ．x *yx *12．文法G 描述的语言L(G)是指( A ) A．⎭⎬⎫⎩⎨⎧∈⇒=+*,|)(T V S G L αααB ．⎭⎬⎫⎩⎨⎧⋃∈⇒=+*)(,|)(N T V V S G L ααα C ．⎭⎬⎫⎩⎨⎧∈⇒=**,|)(T V S G L αααD ．⎭⎬⎫⎩⎨⎧⋃∈⇒=**)(,|)(N T V V S G L ααα 13．有限状态自动机能识别( C )A ．上下文无关文法B ．上下文有关文法C ．正规文法D ．短语文法14．如果文法G 是无二义的，则它的任何句子( A ) A ．最左推导和最右推导对应的语法树必定相同 B ．最左推导和最右推导对应的语法树可能不同 C ．最左推导和最右推导必定相同D ．可能存在两个不同的最左推导，但它们对应的语法树相同 15．由文法的开始符经0步或多步推导产生的文法符号序列是( C ) A ．短语 B ．句柄 C ．句型 D ．句子 16．文法G ：E →E+T|T T →T*P|P P →(E)|i则句型P+T+i 的句柄为( B )A ．P+TB ．PC ．P+T+iD ．i 17．文法G ：S →b|∧|(T) T →T ∨S|S 则FIRSTVT(T)=( C )A ．{ b ，∧，( }B ．{ b ，∧，) }C ．{ b ，∧，(，∨ }D ．{ b ，∧，），∨ } 18．产生正规语言的文法为( D )A ．0型B ．1型C ．2型D ．3型19．任何算符优先文法( D )优先函数。

一、判断题1．SLR(1)分析法是一种规范归约分析法。

（）2．算符优先文法可以是二义性文法。

（）3．每个短语都是某规则的右部。

（）4．语法分析时必须先消除文法中的左递归。

（）5．如果两个正规式是等价的，则它们所表示的正规集相同。

（）（）1.编译程序的输入是高级语言程序，输出是机器语言程序。

（）2.文法G[S]：S→iSeS|iS|i是二义文法。

（）3.若一个语言的句子有无穷多个，则对应的文法必定是递归的。

（）4.上下文无关文法可以产生语言L={a n b n a m b m | n,m≥0}。

（）5.设文法G[N]：N→ND|D，D→0|1|2|3|4|5|6|7，则句子3247的最右推导为：N=>ND=>N4=>ND4=>N74=>ND74=>N274=>D274=>3274。

（）6.每一个NFA都对应有唯一的一个最小化的DFA。

（）7.文法G[S]：S→(S)S|ε不是LL(1)文法。

（）8.若文法任一产生式的右部不含两个相继的非终结符（…QR…），则称该文法为算符文法。

（）9.优先函数是唯一的，有的优先关系矩阵不存在对应的优先函数。

（）10.在LR(1)分析法中，搜索符仅对规约项目才有意义。

1、文法规则的左部就是非终结符号。

2、乔姆斯基定义1型文法对规则的限制比2型文法对规则的限制要多一些。

3、LR（K）分析法能彻底解决冲突。

4、一个程序是正确的是指该程序的语法是完全正确的。

5、每一个编译程序都由完成词法分析、语法分析、语义分析、代码优化和代码生成工作的五部分程序组成。

6、多遍扫描的编译程序优于单遍扫描的编译程序。

7、每个句子都有规范推导；每个句型都有规范推导。

8、存在这样一些语言，它们能被确定有限自动机（DFA）识别，但不能用正规表达式表示。

9、每一个NFA都对应有唯一的一个最小化的DFA。

10、若给定文法G和某个固定的k，则G是否是LR（k）文法是可判定的。

编译原理复习题集一、基本概念1. 解释编译器的作用和基本组成。

2. 简述词法分析器、语法分析器、语义分析器、中间代码生成器、代码优化器和目标代码生成器的功能。

3. 什么是词法单元？请列举常见的词法单元类型。

4. 描述抽象语法树（AST）和具体语法树（CST）的区别。

5. 解释什么是语法制导翻译方案。

二、词法分析6. 描述词法分析的主要任务和输出。

7. 解释正则表达式和有限自动机（DFA）的关系。

8. 给出一个简单的词法分析器的实现步骤。

9. 解释词法分析中的错误处理机制。

10. 什么是词法分析的“最长匹配”规则？三、语法分析11. 简述自顶向下和自底向上的语法分析方法。

12. 解释递归下降分析法的工作原理。

13. 描述LL(1)分析器和LR分析器的设计原理。

14. 给出一个文法，并说明它是否是LL(1)文法或LR(0)文法。

15. 解释移进-规约分析法的基本思想。

四、语义分析16. 描述语义分析的主要任务。

17. 解释属性文法的概念及其在语义分析中的应用。

18. 解释类型检查的重要性及其基本步骤。

19. 给出一个简单的语义分析算法示例。

20. 解释作用域链和作用域解析的概念。

五、中间代码生成21. 简述中间代码的作用和常见类型。

22. 解释三地址代码的特点。

23. 给出一个简单的中间代码生成算法示例。

24. 解释控制流图和数据流图的概念及其在中间代码生成中的作用。

25. 描述符号表在中间代码生成中的作用。

六、代码优化26. 描述代码优化的目标和基本原则。

27. 解释局部优化和全局优化的区别。

28. 给出常见的代码优化技术示例。

29. 解释循环不变代码外提的概念及其优化方法。

30. 描述死代码消除的基本原理。

七、目标代码生成31. 描述目标代码生成的主要任务。

32. 解释寄存器分配的策略和方法。

33. 给出一个简单的目标代码生成算法示例。

34. 解释指令选择和指令调度的概念。

35. 描述目标代码优化的重要性和基本方法。

编译原理-期末复习编译原理⼀、单选题1、将编译程序分为若⼲个“遍”是为了（）。

BA.提⾼程序的执⾏效率B.使程序的结构更加清晰C.利⽤有限的机器内存并提⾼机器的执⾏效率D.利⽤有限的机器内存但降低了机器的执⾏效率2、构造编译程序应掌握（）。

DA.源程序B.⽬标语⾔C.编译⽅法D.以上三项都是3、变量应当（）。

CA.持有左值B.持有右值C.既持有左值⼜持有右值D.既不持有左值也不持有右值4、编译程序绝⼤多数时间花在（）上。

DA.出错处理B.词法分析C.⽬标代码⽣成D.管理表格5、（）不可能是⽬标代码。

DA.汇编指令代码B.可重定位指令代码C.绝对指令代码D.中间代码6、编译程序是对（）。

DA.汇编程序的翻译B.⾼级语⾔程序的解释执⾏C.机器语⾔的执⾏D.⾼级语⾔的翻译7、正规式M1和M2等价是指（）。

CA.M1和M2的状态数相等B.M1和M2的有象弧条数相等C.M1和M2所识别的语⾔集相等D.M1和M2状态数和有象弧条数相等8、如果⽂法G是⽆⼆义的，则它的任何句⼦（）。

AA.最左推导和最右推导对应的语法树必定相同。

B.最左推导和最右推导对应的语法树可能相同。

C.最左推导和最右推导必定相同。

D.可能存在两个不同的最左推导，但它们对应的语法树相同。

9、⽂法G：S→S+T|TT→T*P|PP→(S)|i句型P+T+i的短语有（）BA.i，P+TB. P，P+T，i，P+T +iB.P+T + i D. P，P+T，i10、产⽣正规语⾔的⽂法为（）。

DA.0型B.1型C.2型D.3型11、⽂法G：S→b|?|(T)T→T?S|S则FIRSTVT(T)=() CA.{b，?，(}B.{b，?，)}C.{b，?，(，?}D.{b，?，)，?}12、给定⽂法：A→bA | cc，下⾯的符号串中，为该⽂法句⼦的是（）。

A①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc可选项有：A.①B.①③④⑤C.①④D.①④⑤13、采⽤⾃上⽽下分析，必须（）。

编译原理复习题### 编译原理复习题#### 一、选择题1. 编译器的主要功能是什么？- A. 代码优化- B. 语法分析- C. 词法分析- D. 所有以上2. 词法分析器的主要任务是什么？- A. 识别关键字- B. 识别标识符- C. 将源代码分解成词素- D. 检查语法错误3. 下列哪个不是语法分析树？- A. 抽象语法树（AST）- B. 具体语法树（CST）- C. 语法分析树（GT）- D. 控制流图（CFG）4. 语义分析的主要目的是：- A. 检查类型正确性- B. 生成中间代码- C. 进行代码优化- D. 将源代码转换为目标代码5. 中间代码生成阶段通常采用哪种形式的代码？- A. 三地址代码- B. 汇编代码- C. 机器代码- D. 高级语言代码#### 二、简答题1. 简述词法分析器和语法分析器的区别。

2. 描述编译过程中的代码优化可能包括哪些方面。

3. 解释什么是抽象语法树（AST）以及它在编译过程中的作用。

#### 三、论述题1. 论述编译原理中的错误检测和恢复机制的重要性及其实现方式。

2. 分析静态和动态语义分析的区别，并讨论它们在编译过程中的作用。

#### 四、计算题1. 给定一个简单的算术表达式，如 `3 + 4 * 2 - 5`，请使用算术运算符优先级规则，描述其语法分析过程。

2. 假设有一个简单的编程语言，其语法规则如下：```S -> EE -> E + T | TT -> T * F | FF -> ( E ) | num```请写出表达式 `(3 + 4) * 5 - 6` 的语法分析树。

#### 五、案例分析题1. 考虑一个简单的C语言程序，分析其编译过程中可能遇到的常见错误类型，并讨论编译器如何处理这些错误。

以上复习题覆盖了编译原理的基本概念、关键组件以及编译过程中的一些高级主题。

通过这些题目，学生可以检验自己对编译原理的理解程度，并为进一步的学习打下坚实的基础。

《编译原理》课程复习资料一、判断题：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 型文法。

[ ]22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。

[ ]二、填空题：1. 称为规范推导。

2.编译过程可分为，，，和五个阶段。

3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是。

4.从功能上说，程序语言的语句大体可分为语句和语句两大类。

5.语法分析器的输入是，其输出是。

6.扫描器的任务是从中识别出一个个。

7.符号表中的信息栏中登记了每个名字的有关的性质，如等等。

8.一个过程相应的DISPLAY表的内容为。

9.一个句型的最左直接短语称为句型的。

10.常用的两种动态存贮分配办法是动态分配和动态分配。

<编译原理>历年试题及答案一．（每项选择2分，共20分）选择题1．将编译程序分成若干个“遍”是为了_b__。

a.提高程序的执行效率b.使程序的结构更加清晰c.利用有限的机器内存并提高机器的执行效率d.利用有限的机器内存但降低了机器的执行效率2．构造编译程序应掌握__d__。

a.源程序b.目标语言c.编译方法d.以上三项都是3．变量应当c＿。

a.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值4．编译程序绝大多数时间花在_d___上。

a.出错处理b.词法分析c.目标代码生成d.管理表格5．词法分析器的输出结果是_c___。

a.单词的种别编码b.单词在符号表中的位置c.单词的种别编码和自身值d.单词自身值6．正规式MI和M2等价是指__c__。

a.MI和M2的状态数相等b.Ml和M2的有向弧条数相等。

C.M1和M2所识别的语言集相等 d.Ml和M2状态数和有向弧条数相等7．中间代码生成时所依据的是—c。

a．语法规则b．词法规则c．语义规则d．等价变换规则8．后缀式ab+cd+/可用表达式__b_来表示。

a．a+b/c+d b．(a+b)/(c+d)c．a+b/(c+d)d．a+b+c/d9．程序所需的数据空间在程序运行前就可确定，称为____c_＿管理技术。

a.动态存储b.栈式存储c.静态存储d.堆式存储10.堆式动态分配申请和释放存储空间遵守___d____＿原则。

a.先请先放b.先请后放c.后请先放d.任意二（每小题10分，共80分）简答题1.画出编译程序的总体结构图，简述各部分的主要功能。

2.已知文法G[E]:E→ET+|T T→TF*|F F→F^|a试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.3．为正规式(a|b)*a(a|b)构造一个确定的有限自动机。

4．设文法G(S)：S→(L)|a S|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。

*编译原理复习题一．简答题：1) 什么是句子？ 什么是语言?解答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S x （其中x ∈V T *），则称x 是文法的一个句子。

语言——语言是句子的集合。

或——设G[S]是给定文法，则由文法G 所定义的语言L(G)可描述为：L(G)＝{x │Sx,x ∈V T *} 。

2) DFA 与NFA 有何区别 ?解答:DFA 与NFA 的区别表现为两个方面:一是NFA 可以有若干个开始状态，而DFA 仅只有一个开始状态。

另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。

3) 自顶向下的语法分析方法的基本思想是什么?解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。

4) 自底向上的语法分析方法的基本思想是什么?解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。

5) 一个上下文无关文法G 包括哪四个组成部分？解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。

6) 在自底向上的语法分析方法中，分析的关键是什么？解答:关键是寻找句柄。

7)在自顶向下的语法分析方法中，分析的关键是什么？解答:关键是选择候选式。

8）什么是属性文法？答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。

在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。

一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。

其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。

9）语法制导翻译语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。

编译原理期末考试复习题（含答案）一、选择题1.代码生成阶段的主要任务是（C）。

A.把高级语言翻译成汇编语言B.把高级语言翻译成机器语言C.把中间代码变换成依赖具体机器的目标代码D.把汇编语言翻译成机器语言2.文法G 所描述的语言是（ C ）的集合。

A.文法G 的字母表V 中所有符号组成的符号串B.文法G 的字母表V 的闭包V* 中的所有符号串C.由文法的开始符号推出的所有终结符串D.由文法的开始符号推出的所有符号串3.语言是（C）。

A.终结符与非终结符的符号串的集合B.非终结符符号串的集合C.终结符符号串的集合D.产生式的集合4.常用的中间代码形式不含（D）。

A.三元式B.四元式C.逆波兰式D.语法树5.四元式之间的联系是通过（B）实现的。

A.指示器B.临时变量C.符号表D.程序变量6．词法分析器的输出结果是（ C ）。

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．下推自动机识别的语言是（ C ）A．0型语言 B．1型语言C．2型语言 D．3型语言9. 在规范归约中，用（B）来刻画可归约串。

A．直接短语 B．句柄C．最左素短语 D．素短语10．词法分析器用于识别（ C）。

A．字符串 B．语句 C．单词 D．标识符11．一个句型中称为句柄的是该句型的最左（D）A．非终结符号 B．短语 C．句子 D．直接短语12.文法 G[E] ：E→T∣E＋TT→F∣T * FF→a∣（E）该文法句型 E ＋ F * (E ＋ T) 的简单短语是下列符号串中的（B）。

①（E＋T）②E＋T ③F ④ F * (E＋T)A．①和③B．②和③C．③和④D．③13.通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括（C）。

一、单选题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.句柄11.在自上而下的语法分析方法中，分析的关键是（）。

A.寻找句柄B.寻找句型C.消除递归D.选择候选式12.在自下而上的语法分析方法中，分析的关键是（）。

A.寻找句柄B.寻找句型C.消除递归D.选择候选式13.一个句型中的（）称为该句型的句柄。

A.最左直接短语B.最右直接短语C.终结符D.非终结符14.在规范归约中，用（）来刻画可归约串。

A．直接短语B．句柄C. 最左素短语D. 素短语15.已知文法G[S]：S → eT∣RTT → DR∣εR → dR∣εD → a ∣bd求FIRST(S)=( )。

A．{e} B.{e,d,a,b}C.{e,d}D.{e,d,a,b,ε}16. 已知文法G[S]：S → eT∣RTT → DR∣εR → dR∣εD → a ∣ bd求FOLLOW(D)=( )。

编译原理复习题⼀、单项选择题概述部分1．构造编译程序应掌握。

D A. 源程序 B. ⽬标语⾔ C. 编译⽅法 D. 以上三项都是 2．编译程序绝⼤多数时间花在上。

DA. 出错处理B. 词法分析C. ⽬标代码⽣成D. 表格管理 3．编译程序是对。

DA. 汇编程序的翻译B. ⾼级语⾔程序的解释执⾏C. 机器语⾔的执⾏D. ⾼级语⾔的翻译 4. 将编译程序分成若⼲“遍”，是为了。

BA. 提⾼程序的执⾏效率B. 使程序的结构更为清晰 C 利⽤有限的机器内存并提⾼机器的执⾏效率 D. 利⽤有限的机器内存但降低了机器的执⾏效率词法分析部分1．DFA M(见图1-1)接受的字集为。

D A. 以0开头的⼆进制数组成的集合B. 以0结尾的⼆进制数组成的集合C. 含奇数个0的⼆进制数组成的集合D. 含偶数个0的⼆进制数组成的集合2．词法分析器的输出结果是。

CA. 单词的种别编码B. 单词在符号表中的位置C. 单词的种别编码和⾃⾝值D. 单词⾃⾝值 3．正规式M1和M2等价是指。

C A. M1和M2的状态数相等 B. M1和M2的有向边条数相等 C. M1和M2所识别的语⾔集相等 D. M1和M2状态数和有向边条数相等 4．词法分析器的加⼯对象是。

C A ．中间代码 B ．单词 C ．源程序 D ．元程序 5．同正规式（a|b ）*等价的正规式为。

D A ．(a|b)+ B ．a*|b* C ．(ab)* D ．(a*|b*)+ 6. 两个DFA 等价是指：。

D A.这两个DFA 的状态数相同B. 这两个DFA 的状态数和有向弧条数都相等C. 这两个DFA 的有向弧条数相等D. 这两个DFA 接受的语⾔相同7. 下列符号串不可以由符号集S ＝{a,b}上的正闭包运算产⽣的是：（A ） A. ε B. a C. aa D. ab 8．称有限⾃动机A1和A2等价是指________。

D A ．A1和A2都是定义在⼀个字母表上的有限⾃动机 B ．A1和A2状态数和有向边数相等图1-11C．A1和A2状态数或有向边数相等D．A1和A2所能识别的字符串集合相等9．同正规式（a|b）+等价的正规式是_______。