(完整版)编译原理第一章习题解答
第一章习题解答
2．编译程序有哪些主要构成成分？各自的主要功能是什么？
编译程序的主要构成成分有：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序及出错处理程序。
（1）词法分析程序：从左到右扫描源程序，识别单词及其有关属性；
（2）语法分析程序：分析源程序的结构, 判别它是否为相应程序设计语言中的一个合法程序；
（3）语义分析程序：审查源程序有无语义错误，为代码生成阶段收集类型信息；
（4）中间代码生成程序：将源程序变成一种内部表示形式；
（5）代码优化程序：对前阶段产生的中间代码进行变换或进行改造，使生成的目标代码更为高效；
（6）目标代码生成程序：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码；
（7）表格管理程序：保存编译过程中的各种信息；
（8）出错处理程序：若编译过程中发现源程序存在错误，则报告错误的性质和错误发生的地点，有些还可以自动校正错误。
3．什么是解释程序？它与编译程序的主要不同是什么？
解释程序接受某个语言的程序并立即运行这个源程序。它的工作模式是一个个的获取、分析并执行源程序语句，一旦第一个语句分析结束，源程序便开始运行并且生成结果，它特别适合程序员交互方式的工作情况。
而编译程序是一个语言处理程序，它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序，这个二进制代码程序再机器上运行以生成结果。
它们的主要不同在于：解释程序是边解释边执行，解释程序运行结束即可得到该程序的运行结果，而编译程序只是把源程序翻译成汇编或者二进制程序，这个程序再执行才能得到程序的运行结果。（当然还有其他不同，比如存储组织方式不同）
编译原理(清华大学第2版)课后习题答案
第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题
第9题 语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12．
最新编译原理试题汇总+编译原理期末试题(8套含答案+大题集)
编译原理考试题及答案汇总一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式
编译原理第一章习题解答(可编辑修改word版)
第一章习题解答 2.编译程序有哪些主要构成成分？各自的主要功能是什么？ 编译程序的主要构成成分有：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序及出错处理程序。 （1）词法分析程序：从左到右扫描源程序，识别单词及其有关属性； （2）语法分析程序：分析源程序的结构, 判别它是否为相应程序设计语言中的一个合法程序； （3）语义分析程序：审查源程序有无语义错误，为代码生成阶段收集类型信息； （4）中间代码生成程序：将源程序变成一种内部表示形式； （5）代码优化程序：对前阶段产生的中间代码进行变换或进行改造，使生成的目标代码更为高效； （6）目标代码生成程序：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码； （7）表格管理程序：保存编译过程中的各种信息； （8）出错处理程序：若编译过程中发现源程序存在错误，则报告错误的性质和错误发生的地点，有些还可以自动校正错误。 3.什么是解释程序？它与编译程序的主要不同是什么？ 解释程序接受某个语言的程序并立即运行这个源程序。它的工作模式是一个个的获取、分析并执行源程序语句，一旦第一个语句分析结束，源程序便开始运行并且生成结果，它特别适合程序员交互方式的工作情况。 而编译程序是一个语言处理程序，它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序，这个二进制代码程序再机器上运行以生成结果。 它们的主要不同在于：解释程序是边解释边执行，解释程序运行结束即可得到该程序的运行结果，而编译程序只是把源程序翻译成汇编或者二进制程序，这个程序再执行才能得到程序的运行结果。（当然还有其他不同，比如存储组织方式不同）
编译原理作业集第七章
第七章语义分析和中间代码产生 本章要点 1. 中间语言，各种常见中间语言形式； 2. 说明语句、赋值语句、布尔表达式、控制语句等的翻译； 3. 过程调用的处理； 4. 类型检查； 本章目标 掌握和理解中间语言，各种常见中间语言形式；各种语句到中间语言的翻译；以及类型检查等内容。 本章重点 1．中间代码的几种形式，它们之间的相互转换：四元式、三元式、逆波兰表示； 3．赋值语句、算术表达式、布尔表达式的翻译及其中间代码格式； 4．各种控制流语句的翻译及其中间代码格式； 5．过程调用的中间代码格式； 6．类型检查； 本章难点 1. 各种语句的翻译； 2. 类型系统和类型检查； 作业题 一、单项选择题： 1. 布尔表达式计算时可以采用某种优化措施，比如A and B用if-then-else可解释为_______。 a. if A then true else B； b. if A then B else false； c. if A then false else true； d. if A then true else false； 2. 为了便于优化处理，三地址代码可以表示成________。 a. 三元式 b. 四元式 c. 后缀式 d. 间接三元式 3. 使用三元式是为了________：
a. 便于代码优化处理 b. 避免把临时变量填入符号表 c. 节省存储代码的空间 d. 提高访问代码的速度 4. 表达式-a+b*(-c+d)的逆波兰式是________。 a. ab+-cd+-*； b. a-b+c-d+*； c. a-b+c-d+*； d. a-bc-d+*+； 5. 赋值语句x:=-(a+b)/(c-d)-(a+b*c)的逆波兰式表示是_______。 a. xab+cd-/-bc*a+-:=；a. xab+/cd-bc*a+--:=；a. xab+-cd-/abc*+-:=；a. xab+cd-/abc*+--:=； 6. 在一棵语法树中结点的继承属性和综合属性之间的相互依赖关系可以由________来描述。 a. 抽象语法树； b. 语法规则； c. 依赖图； d. 三地址代码； 7. 按照教材中的约定，三地址语句if x relop y then L表示成四元式为。 a. (relop，x，y，L)； b. (relop，L，x，y)； c. (relop，x，L，y)； d. (L，x，y，relop)； 8. 在编译程序中，不是常见的中间语言形式。 a.波兰式； b. 三元式； c. 四元式； d. 抽象语法树； 9. 在编译程序中安排中间代码生成的目的是________。 a. 便于提高编译效率； b. 便于提高分析的正确性； c. 便于代码优化和目标程序的移植； d.便于提高编译速度； 10. 按照教材中的约定，下面不是类型表达式： a. boolean； b. type-error； c. real； d. DAG； 11. 一个Pascal函数 function f ( a, b:char ) :↑integer; …… 其作用域类型是： a. char×integer； b. char×char； c. char×pointer(integer)； d. integer×integer； 12. 因为标识符可用于多种情况，比如常量标识符、变量标识符、过程标识符等等。因此，在符号表中为了给出各个符号的标志，常给标识符引入一个属性kind，然后在相应产生式的语义动作中添加给kind属性赋值的语句。比如，在在产生式D id:T的语义动作中添加赋值语句id.kind=。 a. V AR； b. CONSTANT； c. PROC； d. FUNC； 13. 下面情况下，编译器需要创建一张新的符号表。 a. 过程调用语句； b. 标号说明语句； c. 数组说明语句； d.记录说明语句； 14. 函数function f(a,b:char):↑integer;… 所以f函数的类型表达式为： a. char×char→pointer(integer)； b. char×char→pointer； c. char×char→integer； d. char×char→integer (pointer) 15. 如果一个语言的编译器能保证编译通过的程序，在运行时不会出现类型错误，则称该语言是。 a. 静态的； b. 强类型的； c. 动态的； d. 良类型的； 一．答案：1. b；2. d；3. b；4. d；5. c；6. c.；7. a；8. a；9. c；10. d；11. b；12. a；13. d； 14. a；15. b；
编译原理_第三版_课后答案
编译 原理 课后题答案 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导:
E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/******************************** E E F T E + T F F T +i i i E E F T E -T F F T -i i i E E F T +T F F T i i i *i+i+i i-i-i i+i*i *****************/ P36-9 句子iiiei 有两个语法树： S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ???????? P36-10 /************** ) (|)(|S T T TS S →→ ***************/ P36-11 /*************** L1: ε ||cC C ab aAb A AC S →→→ L2:
编译原理复习题及答案
编译原理复习题及答案 一、选择题 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．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(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．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C) A. bba B. cab C. bca D. cba
最新编译原理复习题(经典)
编译原理复习题 一、是非题 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 3．每个文法都能改写为 LL(1) 文法。 (×) 4．算符优先关系表不一定存在对应的优先函数。 (√) 5．LR分析方法是自顶向下语法分析方法。 (×) 6．“ 用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。(× ) 7．一个句型的句柄一定是文法某产生式的右部。(√) 8．仅考虑一个基本块，不能确定一个赋值是否真是无用的。(√ ) 9．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。(× ) 10．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×) 11．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(× ) 12．递归下降分析法是自顶向下分析方法。(√ ) 13．产生式是用于定义词法成分的一种书写规则。(×) 14．在SLR(1)分析法的名称中，S的含义是简单的。(√) 15．综合属性是用于“ 自上而下” 传递信息。(× ) 16．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。(×) 17．程序语言的语言处理程序是一种应用软件。(×) 18．解释程序适用于COBOL 和FORTRAN 语言。(×) 19．一个LL(l)文法一定是无二义的。(√) 20．正规文法产生的语言都可以用上下文无关文法来描述。(√) 21．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。(×) 22．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。(√) 22．逆波兰法表示的表达式亦称后缀式。(√ ) 23．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。(√ ) 24．数组元素的地址计算与数组的存储方式有关。(√) 25．算符优先关系表不一定存在对应的优先函数。(×) 26．编译程序是对高级语言程序的解释执行。(× ) 27．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 28．一个算符优先文法可能不存在算符优先函数与之对应。(√ ) 29．语法分析时必须先消除文法中的左递归。(×) 30．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√) 31．逆波兰表示法表示表达式时无须使用括号。(√ ) 32．静态数组的存储空间可以在编译时确定。(√) 33．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(√) 34．两个正规集相等的必要条件是他们对应的正规式等价。(√) 35．一个语义子程序描述了一个文法所对应的翻译工作。(×) 36．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×) 37．确定的自动机以及不确定的自动机都能正确地识别正规集。(√) 38．词法分析作为单独的一遍来处理较好。(× ) 39．构造LR分析器的任务就是产生LR分析表。(√) 40．规范归约和规范推导是互逆的两个过程。(√) 41．同心集的合并有可能产生新的“移进”/“归约”冲突。(× )
编译原理第1章
第一章编译概述 2.典型的编译程序可划分为几部分？各部分的主要功能是什么？每部分都是必不可少的吗？ 答：编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。 各部分的主要功能如下： 词法分析程序又称扫描器。进行词法分析时，依次读入源程序中的每个字符，依据语言的构词规则，识别出一个个具有独立意义的最小语法单元，即“单词”，并用某个单词符号来表示每个单词的词性是标识符、分界符还是数； 语法分析程序的功能是：对词法分析的结果，根据语言规则，将一个个单词符号组成语言的各种语法类； 语义分析的功能是确定源程序的语义是否正确； 中间代码生成程序的功能是将源程序生成一种更易于产生、易于翻译成目标程序的中间代码； 代码优化程序的功能是将中间代码中重复和冗余部分进行优化，提高目标程序的执行效率； 目标代码生成程序的功能是将中间代码生成特定机器上的机器语言代码； 符号表管理程序的功能是记录源程序中出现的标识符，并收集每个标识符的各种属性信息； 错误处理程序的功能是应对在编译各个阶段中出现的错误做适当的处理，从而使编译能够继续进行。 编译程序的每部分都是必不可少的。 3.解释方式和编译方式的区别是什么？ 答：解释方式最终并不生成目标程序，这是编译方式与解释方式的根本区别。解释方式很适合于程序调试，易于查错，在程序执行中可以修改程序，但与编译方式相比，执行效率太低。 4.论述多遍扫描编译程序的优缺点？ 答：优点：（1）可以减少内存容量的需求，分遍后，以遍为单位分别调用编译的各个子程序，各遍程序可以相互覆盖；（2）可使各遍的编译程序相互独立，结构清晰；（3）能够进行充分的优化，产生高质量的目标程序；（4）可将编译程序分为“前端”和“后端”，有利于编译程序的移植。 缺点是每遍都要读符号、送符号，增加了许多重复性工作，降低了编译效率。
编译原理 第一章 习题解答
第一章习题解答 2．编译程序有哪些主要构成成分？各自的主要功能是什么？ 编译程序的主要构成成分有：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序及出错处理程序。 （1）词法分析程序：从左到右扫描源程序，识别单词及其有关属性； （2）语法分析程序：分析源程序的结构, 判别它是否为相应程序设计语言中的一个合法程序； （3）语义分析程序：审查源程序有无语义错误，为代码生成阶段收集类型信息； （4）中间代码生成程序：将源程序变成一种内部表示形式； （5）代码优化程序：对前阶段产生的中间代码进行变换或进行改造，使生成的目标代码更为高效； （6）目标代码生成程序：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码； （7）表格管理程序：保存编译过程中的各种信息； （8）出错处理程序：若编译过程中发现源程序存在错误，则报告错误的性质和错误发生的地点，有些还可以自动校正错误。 3．什么是解释程序？它与编译程序的主要不同是什么？ 解释程序接受某个语言的程序并立即运行这个源程序。它的工作模式是一个个的获取、分析并执行源程序语句，一旦第一个语句分析结束，源程序便开始运行并且生成结果，它特别适合程序员交互方式的工作情况。 而编译程序是一个语言处理程序，它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序，这个二进制代码程序再机器上运行以生成结果。 它们的主要不同在于：解释程序是边解释边执行，解释程序运行结束即可得到该程序的运行结果，而编译程序只是把源程序翻译成汇编或者二进制程序，这个程序再执行才能得到程序的运行结果。（当然还有其他不同，比如存储组织方式不同）
编译原理教程课后习题答案——第七章
第七章目标代码生成 7.1 对下列四元式序列生成目标代码： T=A-B S=C+D W=E-F U=W/T V=U*S 其中，V是基本块出口的活跃变量，R0和R1是可用寄存器。 【解答】简单代码生成算法依次对四元式进行翻译。我们以四元式T=a+b为例来说明其翻译过程。 汇编语言的加法指令代码形式为 ADD R, X 其中，ADD为加法指令；R为第一操作数，第一操作数必须为寄存器类型；X为第二操作数，它可以是寄存器类型，也可以是内存型的变量。ADD R,X指令的含意是：将第一操作数R与第二操作数相加后，再将累加结果存放到第一操作数所在的寄存器中。要完整地翻译出四元式T=a+b，则可能需要下面三条汇编指令： MOV R, a ADD R, b MOV T, R 第一条指令是将第一操作数a由内存取到寄存器R中；第二条指令完成加法运算；第三条指令将累加后的结果送回内存中的变量T。是否在翻译成目标代码时都必须生成这三条汇编指令呢？从目标代码生成的优化角度考虑，即为了使生成的目标代码更短以及充分利用寄存器，上面的三条指令中，第一条和第三条指令在某些情况下是不必要的。这是因为，如果下一个四元式紧接着需要引用操作数T，则第三条指令就不急于生成，可以推迟到以后适当的时机再生成。 此外，如果必须使用第一条指令，即第一操作数不在寄存器而是在内存中，且此时所有可用寄存器都已分配完毕，这时就要根据寄存器中所有变量的待用信息(也即引用点)来决定淘汰哪一个寄存器留给当前的四元式使用。寄存器的淘汰策略如下： (1) 如果某寄存器中的变量已无后续引用点且该变量是非活跃的，则可直接将该寄存器作为空闲寄存器使用。 (2) 如果所有寄存器中的变量在基本块内仍有引用点且都是活跃的，则将引用点最远的变量所占用寄存器中的值存放到内存与该变量对应的单元中，然后再将此寄存器分配给当前的指令使用。 因此，本题所给四元式序列生成的目标代码如下： MOV R0, A SUB R0, C /*R0=T*/ MOV R1, C ADD R1, D /*R1=S*/ MOV S, R1 /*S引用点较T引用点远，故将R1的值送内存单元S*/ MOV R1, E SUB R1, F /*R1=W*/ SUB R1, R0 /*R1=U*/ MUL R1, S /*R1=V*/ 7.2 假设可用的寄存器为R0和R1，且所有临时单元都是非活跃的，试将以下四元式基本
编译原理课后习题答案-清华大学-第二版
第1章引论 第1题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2） 源程序：源语言编写的程序称为源程序。 （3） 目标程序：目标语言书写的程序称为目标程序。 （4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。
目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。 注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。 第3题 何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？ 答案： 翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。 编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。 解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这条语句的功
哈工大编译原理习题及答案
1.1何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间可能有何种关系? 1.2一个典型的编译系统通常由哪些部分组成?各部分的主要功能是什么? 1.3选择一种你所熟悉的程序设计语言，试列出此语言中的全部关键字，并通过上机使用该语言以判明这些关键字是否为保留字。 1.4选取一种你所熟悉的语言，试对它进行分析，以找出此语言中的括号、关键字END以及逗号有多少种不同的用途。 1.5试用你常用的一种高级语言编写一短小的程序，上机进行编译和运行，记录下操作步骤和输出信息，如果可能，请卸出中间代码和目标代码。 第一章习题解答 1.解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序（或解释程序）将 源程序处理加工而得的另一种语言（目标语言）的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执行。 2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成 程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。 3.解：C语言的关键字有：auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。上述关键字在C语言中均为保留字。 4.解：C语言中括号有三种：{}，[]，（）。其中，{}用于语句括号；[]用于数组；（）用于函数（定 义与调用）及表达式运算（改变运算顺序）。C语言中无END关键字。逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。 5.略 第二章前后文无关文法和语言 21设有字母表A1={a,b,…,z}，A2={0,1,…,9}，试回答下列问题： (1) 字母表A1上长度为2的符号串有多少个? (2) 集合A1A2含有多少个元素? (3) 列出集合A1 (A1∪A2)*中的全部长度不大于3的符号串。
编译原理教程课后习题答案——第四章
第四章语义分析和中间代码生成 4.1 完成下列选择题： (1) 四元式之间的联系是通过实现的。 a. 指示器 b. 临时变量 c. 符号表 d. 程序变量 (2) 间接三元式表示法的优点为。 a. 采用间接码表，便于优化处理 b. 节省存储空间，不便于表的修改 c. 便于优化处理，节省存储空间 d. 节省存储空间，不便于优化处理 (3) 表达式(┐A∨B)∧(C∨D)的逆波兰表示为。 a. ┐AB∨∧CD∨ b. A┐B∨CD∨∧ c. AB∨┐CD∨∧ d. A┐B∨∧CD∨ (4) 有一语法制导翻译如下所示： S→bAb {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 【解答】 (1) b (2) a (3) b (4) b 4.2 何谓“语法制导翻译”？试给出用语法制导翻译生成中间代码的要点，并用一简例予以说明。 【解答】语法制导翻译(SDTS)直观上说就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并且在语法分析的同时执行这些子程序。也即在语法分析过程中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。 用语法制导翻译(SDTS)生成中间代码的要点如下： (1) 按语法成分的实际处理顺序生成，即按语义要求生成中间代码。 (2) 注意地址返填问题。 (3) 不要遗漏必要的处理，如无条件跳转等。 例如下面的程序段： if (i>0) a=i+e-b*d; else a=0; 在生成中间代码时，条件“i>0”为假的转移地址无法确定，而要等到处理“else”时方可确定，这时就存在一个地址返填问题。此外，按语义要求，当处理完(i>0)后的语句(即“i>0”为真时执行的语句)时，则应转出当前的if语句，也即此时应加入一条无条件跳转指令，并且这个转移地址也需要待处理完else之后的语句后方可获得，就是说同样存在着地址返填问题。对于赋值语句a=i+e-b*d，其处理顺序(也即生成中间代码顺序)是先生成i+e的代码，再生成b*d的中间代码，最后才产生“-”运算的中间代码，这种顺序不能颠倒。 4.3 令S.val为文法G[S]生成的二进制数的值，例如对输入串101.101，则S.val= 5.625。按照语法制导翻译方法的思想，给出计算S.val的相应的语义规则，G(S)如下： G[S]: S→L.L|L
编译原理课后习题答案+清华大学出版社第二版
第 1 章引论 第1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。
编译原理：学习指导与典型题解析
(1)——不是NFA的成分o A．有穷字母表B．初始状态集合 c．终止状态集合D．有限状态集合 (北京航天航空大学研究生入学考试试题 (2)——不是编译程序的组成部分0 A．词法分析程序B．代码生成程序 c．设备管理程序D．语法分析程序 (北京航天航空大学研究生入学考试试题 解答 (1)B，(2)C 例题2．2 给出下面描述的正规表达式 (1)以0l结尾的二进制数串； (2)能被5整除的十进制整数； (3)包含奇数个t或奇数个0的二进制数串 解题思路 (1)分析题意，要求的是二进制串，即由0和1构成的串，并且必须以ot结尾，所以 本题可以分两部分去完成，一部分实现由o和1构成的任意串，一部分即01，然后将它们连接到一起就可以了，所以本题的解答是：(1|0)*01 (2)分析题意，本题要求是十进制整数，也就是由o09这10个数字组成的字符串， 并且不能以o开头(整数“o”除外)，要求能被5整除，则该串必须以0或者5结尾0根据我们的分析，可以把本题分成两种情况考虑：一种情况是该整数只有1位，则该整数有0 和5两种可能；另外一种情况是该整数有多位，则该整数可以分成3部分考虑，一是第l 位必须不为0，二是最后1位必须为0或5，三是中间部分可有可无，并且可以由0…9之间任意数字构或，所以本题的正规表达式为：(1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)*(0|5)| (0|5) (3)本题求二进制串，并且要求包含奇数个0或奇数个1，由于o和1都可以在二进制串 中任何地方出现，所以本题只需要考虑一种情况，另外一种情况也可以类似求得0考虑包含奇数个0的字符串：由于只关心0的个数的奇偶数，我们可以把二进制串分成多段来考虑，第1段为二进制串的开始到第1个0为止，这一段包含1个o，并且0的前面有0个或多个l，对于剩下的二进制串按照每段包含两个0的方式去划分，即以o开始，以0结尾，中间可以有0个或多个1，如果一个二进制串被这样划分完后，剩下的部分如果全部是全1串(这些全1串在前面划分的串之间或最后)，则该二进制串就具有奇数个o，所以该二进制串可以这样描述：以第1段(1‘o)开始．后面由全1串(1‘)以及包含两个o的串(ol0o)组成，所以包含奇数个0的正规表达式为：100(1[ol’o]‘，本题的解答则是：1*0(1|01*0)*|0*1(0|10*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．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(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．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n(n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C)