第一章 引 论
第一章 引论
1.1 1.1 什么叫编译程序
什么叫编译程序编译程序编译程序:
:是指这样的程序，它能够把某种语言的程序转换成另一种语言的程序，而后者与前者在逻辑上是等价的。如果源语言是诸如源语言是诸如FORTRAN FORTRAN FORTRAN、、Pascal Pascal、、C 、Ada Ada、、Smalltalk Smalltalk或或Java Java这样的
这样的“高级语言”，而目标语言如汇编语言之类的“低级语言”这样的翻译程序则称之为编译程序。 本课程主要介绍设计和构造编译程序本课程主要介绍设计和构造编译程序的基本原理和方法。
编译程序又简称为“编译器”?第一个编译器是20世界50年代的后期出现的FORTRAN语言编译器。
?同样，解释程序又简称为“解释器”，但是在概念上与编译器有明显区别：
编译程序是源转换系统，而解释程序是源程序的一个执行系统。
编译程序的结果是得到等价源程序的某种目标机程序，而解释程序的结果是得到源程序的执行结果，即它相当于执行源程序的抽象机。
第一章引论
注意编译程序与解释程序的区别，一个语言的解释程序是这样的程序：它以该语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。
术语“编译”的内涵是实现从源语言表示的 术语
算法向目标语言表示的算法的等价变换。
第一章引论
高级语言分类及其编译：
过程式语言：FORTRAN Pascal Ada C （特点：面向驱动，面向语句，由系列的语句组成）函数式语言：LISP ML ASL
（注重程序表示的功能，而不是一个语句接一个语句的执行）从已有的函数出发构造更复杂的函数。
逻辑式语言：PROLOG
（检查一定的条件，当满足时，则执行适当的动作。）对象式语言：SMALLTALK C++
（封装性、继承性、多态性）
第一章引论
这里主要研究过程式语言的编译
高级语言分类及其编译：
过程式语言：FORTRAN Pascal ADA C
函数式语言：LISP ML ASL
逻辑式语言：PROLOG
对象式语言：SMALLTALK C++
函数式语言与逻辑式语言，特别是逻辑式语言，其编译技术与过程式语言的差别比较大；因对象式语言的载体基本上是过程式的，所以其编译程序也不难理解。
第一章引论
编译过程概述
1.2 编译过程概述
1.2
编译程序的工作，从输入源程序开始 编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非
常复杂的。
掌握编译过程的五个基本阶段，是我 掌握编译过程的五个基本阶段，是我们学习编译原理课程的基本内容，把编译的五个基本阶段与英译中的五个步骤相比较，有利于对编译过程的理解：
第一章引论
英译与编译的比较
1。识别出句子中的一个个单字
2。分析句子的语法结构3。初步翻译句子的含意4。译文修饰
5。写出最后译文1。词法分析
2。语法分析
3。语义分析中间代码生成
4。优化
5。目标代码生成
第一章引论
源程序是以文本文件方式存在注意：程序总是以字符串的方式存在。
第一章引论
1.2.1 词法分析
输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词（也称单词符号，或简称符号）
在词法分析阶段工作所依循的是语言的词法规则。描述词法规则的有效工具是正规式和有限自动机。
第一章引论
1.2.1 词法分析
什么是单词
–逻辑上相连的一组字符，从语法的角度来看，这些字符所具有的集体含义已不能再
区分了，通常包括：保留字、标识符、界
符、算符和常量等
第一章引论
例. 考虑下面的一段源程序var area, radius:real;
begin
read(radius);
area:=3.1415926*radius*radius;
end.
保留字： var， begin， end， read，real 运算符： *， :=
界符：‘(’，‘)’，‘; ’，‘.’
标识符： radius， area
第一章引论
有关术语
?词法分析(lexical analysis or scanning) --The stream of characters making up a
source program is read from left to right
and grouped into tokens,which are sequences of characters that have a
collective meaning.
?单词---token
?保留字---reserved word
?标识符 ---identifier(user-defined name)
第一章引论
1.2.2语法分析
语法分析的任务：在词法分析的基础上，根据语言的语法规则，把单词符号分解成各类语法单位（语法范畴），如“短语”、“句子”、“子句”、“程序段”等。
语法规则通常用上下文无关文法描述。
?例. 对赋值语句area:=3.1415926*radius*radius进行语法分析
第一章引论
术语
?语法分析(syntax analysis or parsing)
The purpose of syntax analysis is to determine the source program’s phrase structure.This process is also called parsing.The source program is parsed to check whether it conforms to the source language’s syntax,and to construct a suitable representation of its phrase structure.
?语法树(推导树)(parse tree or derivation
tree)
第一章引论
1.2.3语义分析与中间代码的产生
对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
这一阶段通常包括两方面的工作首先对各种语法范畴进行静态语义检查（如：变量是否定义，类型是否正确等），如果正确则进行另一方面的工作，即进行中间代码的翻译。
通常使用属性文法描述语义规则
第一章引论
1.2.3语义分析与中间代码的产生
?什么是中间代码
–是将源程序转变成的一种内部表现形式，是一种结构简单、含义明确的记号系统
–中间代码的两种性质
?容易生成这种中间代码
?容易将它翻译成目标代码
–主要形式
?四元式、三元式、间接三元式、逆波兰式等
第一章引论
术语
?语义分析(semantic analysis)
The parsed program is further analyzed to determine whether it conforms to the source language’s contextual constraints:scope rules, type rules
e.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration.
第一章引论
1.2.4 优化
优化的任务在于对前段产生的中间代码进行加工，以期在最后阶段产生更为高效（省时间和空间）的代码
优化所依循的原则是程序的等价变换规则
其方法有：公共子表达式的提取、循环优化、删除无用代码等。
第一章引论
第1 章 1、编译过程包括哪几个主要阶段及每个 阶段的功能。 答案：编译过程包括词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成5 个阶段。词法分析的功能是对输入的高级语言源程序进行词法分析，识别其中的单词符号，确定它们的种类，交给语法分析器，即把字符串形式的源程序分解为单词符号串形式。语法分析的功能是在词法分析结果的基础上，运用语言的语法规则，对程序进行语法分析，识别构成程序的各类语法范畴及它们之间的层次关系，并把这种层次关系表达成语法树的形式。词义分析和中间代码生成的功能是在语法分析的基础上，对程序进行语义分析，“理解”其含义，产生出表达程序语义的内部表达形式（中间代码）。优化的功能是按照等价变换的原则，对语义分析器产生的中间代码序列进行等价变换，删除其中多余的操作，对耗时耗空间的代码进行优化，以期最后得到高效的可执行代码。目标代码生成的功能是把优化后的中间代码变换成机器指令代码，得到可在目标机器上执行的机器语言程序。 第2 章 1、写一上下文无关文法G，它能产生配 对的圆括号串（如：(),(()),()(())等，甚至 包括0 对括号） 文法为：S→(L)|LS|L L→S| ε 2 、已知文法G ：E→E+T|E-T|T T→T*F|T/F|F F→(E) |i （1）给出i+i*i,i*(i-i)的最左推导，最右推导以及语法树。 （2）i-i+i 哪个算符优先。 【解答】 （1）最左推导：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?T*F? T*(E) ? T*(E-T) ? T*(E-F) ? T*(E-i) ? T*(T-i) ? T*(F-i) ?T*(i-i) ? F*(i-i) ?i*(i-i) i+i*i 以及i*(i-i)的语法树如下所示： （2）i-i+i 的语法树如下图所示。 从上图的语法树可知：“-”的位置位 于“+”的下层，也就是前面两个i 先进 行“-”运算，再与后面的i 进行“+” 运算，所以“-”的优先级高于“+”的 优先级。 3 、文法G: E→ET+|T T→TF*|F F→FP↑|P P→E|i （1）试证明符号串TET+*i↑是G 的一 个句型(要求画出语法树). （2）写出该句型的所有短语,直接短语和句柄. 【解答】（1）采用最右推导： E?T?F? FP↑? Fi↑? Pi↑? Ei↑ ? Ti↑? TF*i↑? TP*i↑? TE*i↑? TET+*i↑ 语法树如下图所示。 从文法G 的起始符号出发，能够推导 出符号串TET+*i↑，所以给定符号串是文法G的句型。 (2) 该句型的短语有： ET+,TET+*,i ,TET+*i↑ 直接短语有：ET+, i 句柄是：ET+ 4、已知文法G：S→iSeS|iS|i ，该文法 是二义文法吗？为什么？ 【解答】该文法是二义文法。 因为对于句子iiiei 存在两种不同的最 左推导： 第 1 种推导：S? iSeS? iiSeS? iiieS? iiiei 第2种推导：S?iS?iiSeS?iiieS?iiiei 第3 章 1、用正规式描述下列正规集： （1）C 语言的十六进制整数； （2）以ex 开始或以ex 结束的所有小写字母构成的符号串； （3）十进制的偶数。 【解答】 （1）C 语言十六进制整数以0x 或者0X 开头，所以一般形式应该为（+|-|ε） (0x|0X)AA*，其中前面括号表示符号， 可以有正号、负号，也可以省略（用ε表示）默认是正数，A 表示有资格出现在十六进制整数数位上的数字，AA*表示一位或者多位（一个或者多个数字的
第二章 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 ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************
目录 P36-6 (2) P36-7 (2) P36-8 (2) P36-9 (3) P36-10 (3) P36-11 (3) P64–7 (4) P64–8 (5) P64–12 (5) P64–14 (7) P81–1 (8) P81–2 (9) P81–3 (12) P133–1 (12) P133–2 (12) P133–3 (14) P134–5 (15) P164–5 (19) P164–7 (19) P217–1 (19) P217–3 (20) P218–4 (20) P218–5 (21) P218–6 (22) P218–7 (22) P219–12 (22) P270–9 (24)
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 ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************
第一章 1．典型的编译程序在逻辑功能上由哪几部分组成？ 答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。 2. 实现编译程序的主要方法有哪些？ 答：主要有：转换法、移植法、自展法、自动生成法。 3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？ 答：编译法、解释法。 4. 编译方式和解释方式的根本区别是什么？ 答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快； 解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。
第二章 1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关 系如何？ 答：1）0型文法、1型文法、2型文法、3型文法。 2） 2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。 答： Z→SME | B S→1|2|3|4|5|6|7|8|9 M→ε | D | MD D→0|S B→2|4|6|8 E→0|B 3. 设文法G为： N→ D|ND D→ 0|1|2|3|4|5|6|7|8|9 请给出句子123、301和75431的最右推导和最左推导。 答：N?ND?N3?ND3?N23?D23?123 N?ND?NDD?DDD?1DD?12D?123 N?ND?N1?ND1?N01?D01?301 N?ND?NDD?DDD?3DD?30D?301 N?ND?N1?ND1?N31?ND31?N431?ND431?N5431?D5431?75431 N?ND?NDD?NDDD?NDDDD?DDDDD?7DDDD?75DDD?754DD?7543D?75431 4. 证明文法S→iSeS|iS| i是二义性文法。 答：对于句型iiSeS存在两个不同的最左推导： S?iSeS?iiSes S?iS?iiSeS 所以该文法是二义性文法。 5. 给出描述下面语言的上下文无关文法。 （1）L1={a n b n c i |n>=1,i>=0 } （2）L2={a i b j|j>=i>=1} （3）L3={a n b m c m d n |m,n>=0} 答： （1）S→AB A→aAb | ab B→cB | ε （2）S→ASb |ab
《编译原理》课后习题答案第一章 第 1 章引论 第 1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第 2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程 序的总体结构图。 答案： 一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语 义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式 的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的 各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源
作为考研课程中最难的科目，编译原理的复习一直以来困扰着无数的计算机考研者，特别是本科期间没有认真学习这门课程或者专业外的人士。由sodme写作的这一系列文章将主要以陈火旺院士的编译原理教材为主线，对编译原理的复习重点和复习思路进行归纳和总结，以帮助大多数朋友尽快入门。由于绝大多数的本科编译教材，都是在围绕着原理性方面的知识进行介绍和展开，所以，本总结也适合于使用其它教材的朋友。anyway，希望使用各种不同教材的朋友都能从中受益并有所感悟。 与数据结构的总结类似，对于编译的总结都是采用我自己认为比较容易理解的语言进行描述，绝不对书上的概念和算法进行原原本本的照搬，这里，在多数情况下讲的都是我自己的学习经验和学习心得。So，其行文写作的style可能有些朋友不太适应，but，I promise：这个总结绝不会平庸、泛泛无奇。 Ok，now，let’s go. 一、编译原理的章节结构及重点构成 第1章引论：本章属非重点章节，简单介绍了编译的基本知识。出题分值不会太多，如果出题（很多情况是不出题，^_^），其分值比例一般情况下不会超过5%. 第2章高级语言及其语法描述：本章属重要章节，在本章逐步引出了编译的若干基础概念和术语。如果出题，其分值比例一般在5%-20%. 第3章词法分析：重难点章节。本章是难点章节之一，同时又是编译原理最重要的章节和多数学校的必考章节之一，通常作为大题中的先行题考查。分值比例各有侧重，一般在10%~20%不等。 第4章语法分析－自上而下分析：重难点章节。本章的难度要高于词法分析一章，与词法分析一章一样，同属编译原理最重要的章节之一，是多校学校的必考章节之一，通常作为大题考查。如果出题，其分值在10%~20%不等（如果同一试卷中既出现词法分析又出现语法分析，语法分析题目的分值一般比词法分析的分值要大）。 第5章语法分析－自下而上分析：重难点章节。属多数学校的必考章节之一，其重要性描述同上，通常作为大题考查。一般情况下，在同一学校的同一张编译试卷内，多数不会同时考自上而下分析和自下而上分析两种语法分析方法，各学校会根据自身题目的难度定位选择考查自上而下的还是自下而上的。自下而上的分析要难一点。如果本章出题，其分值比例约为：10%~20%. 第6章属性文法和语法制导翻译：重难点章节。属多数学校的必考章节之一。多数与语义分析一章联合出题，通常作为大题考查。如果出题，本章的分值比例约为：10%~20%左右。第7章语义分析和中间代码生成：重难点章节，常考内容之一，报考名校的同学应该多留意本章节内容。如果出题，本章分值约为：10%左右。 第8章符号表：非重点章节，本章介绍的是编译过程中的辅助内容，并未紧密联系编译的主体思想。多数学校在本章不出题，如果出题，其分值比例约为：5%左右。 第9章运行时存储空间组织：常考内容之一。本章多数会联系实际语言进行考查，如果出题，其分值比例约为：10%左右。 第10章优化：常考内容之一。分值比例约为：10%左右。 第11章目标代码生成：较少考查，即使考查，分数比例一般在5%左右。 第12章并行编译基础：很少考查，只作了解，了解其基本概念即可。 关于重要性标识的几点说明： “必考内容”：是针对于多校学校一般的出题规律而言，本章极易被考到。或者说，作为
第6章 属性文法和语法制导翻译 7. 下列文法由开始符号S 产生一个二进制数，令综合属性v al 给出该数的值： 试设计求S.val 的属性文法，其中，已知B 的综合属性c, 给出由B 产生的二进位的结果值。例如，输入101.101时，S.val=5.625，其中第一个二进位的值是4，最后一个二进位的值是0.125。 【答案】 11. 设下列文法生成变量的类型说明： (1) 构造一下翻译模式，把每个标识符的类型存入符号表；参考例6.2。 【答案】
第7章 语义分析和中间代码产生 3. 请将表达式－(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。 【答案】 间接码表：(1)→(2)→(3)→(4)→(1)→(5)→(6) 4. 按7.3节所说的办法，写出下面赋值句A:=B*(－C+D ) 的自下而上语法制导翻译过程。给 出所产生的三地址代码。 【答案】
5. 按照7.3.2节所给的翻译模式，把下列赋值句翻译为三地址代码： A[i, j]:=B [i, j] + C[A [k, l]] + d [ i+j] 【答案】 6. 按 7.4.1和7.4.2节的翻译办法，分别写出布尔式A or ( B and not (C or D) )的四元式序列。 【答案】 用作数值计算时产生的四元式： 用作条件控制时产生的四元式： 其中：右图中(1)和(8)为真出口，(4)(5)(7)为假出口。 7. 用7.5.1节的办法，把下面的语句翻译成四元式序列： While A 编译 原理 课后题答案 第二章 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: 第二章2.3叙述由下列正规式描述的语言 (a) 0(0|1)*0 在字母表{0, 1}上,以0开头和结尾的长度至少是2的01串(b) ((ε|0)1*)* 在字母表{0, 1}上,所有的01串,包括空串(c) (0|1)*0(0|1)(0|1) 在字母表{0, 1}上,倒数第三位是0的01串(d) 0*10*10*10* 在字母表{0, 1}上,含有3个1的01串 (e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 在字母表{0, 1}上,含有偶数个0和偶数个1的01串 2.4为下列语言写正规定义 C语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀（本身除外）不以 */ 结尾。 ［解答］ other → a | b | … other指除了*以外C语言中的其它字符 other1 → a | b | … other1指除了*和/以外C语言中的其它字符 comment → /* other* (* ** other1 other*)* ** */ (f) 由偶数个0和偶数个1构成的所有0和1的串。 ［解答］由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况： x 偶数个0和偶数个1（用状态0表示）； x 偶数个0和奇数个1（用状态1表示）； x 奇数个0和偶数个1（用状态2表示）； x 奇数个0和奇数个1（用状态3表示）；所以， x 状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0和奇数个1（状态1） x 状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态3（奇数个0和奇数个1）读入0，则 0和1的数目变为：偶数个0和奇数个1（状态1） 因为，所求为由偶数个0和偶数个1构成的所有0和1的串，故状态0既为初始状态又为终结状态，其状态转换图： 由此可以写出其正规文法为： S0 → 1S1 | 0S2 | ε S1 → 1S0 | 0S3 | 1 S2 → 1S3 | 0S0 | 0 S3 → 1S2 | 0S1 在不考虑S0 →ε产生式的情况下，可以将文法变形为： S0 = 1S1 + 0S2 S1 = 1S0 + 0S3 + 1 S2 = 1S3 + 0S0 + 0 S3 = 1S2 + 0S1 所以： S0 = (00|11) S0 + (01|10) S3 + 11 + 00 (1) S3 = (00|11) S3 + (01|10) S0 + 01 + 10 (2) 解(2)式得： S3 = (00|11)* ((01|10) S0 + (01|10)) 代入(1)式得： S0 = (00|11) S0 + (01|10) (00|11)*((01|10) S0 + (01|10)) + (00|11) => S0 = ((00|11) + (01|10) (00|11)*(01|10))S0 + (01|10) (00|11)*(01|10) + (00|11) => S0 = ((00|11)|(01|10) (00|11)*(01|10))*((00|11) + (01|10) (00|11)* (01|10)) => S0 = ((00|1 1)|(01|10) (00|11)* (01|10))+ 因为S0→ε所以由偶数个0和偶数个1构成的所有0和1的串的正规定义为： S0 → ((00|11)|(01|10) (00|11)* (01|10))* (g) 由偶数个0和奇数个1构成的所有0和1的串。 ［解答］此题目我们可以借鉴上题的结论来进行处理。 对于由偶数个0和奇数个1构成的所有0和1的串，我们分情况讨论： 第二章 P36-6 (１） L G ()1是0~９组成的数字串 (２) 最左推导： 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 P3６-7 G(Ｓ) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P3６-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 ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/*****＊＊*＊***********＊*＊＊******** 三 12 将图a 确定化 最小化 图a 解：引入新的初态结点X 和终态结点Y(X,Y 不属于源非确定集)得图如下： 列出状态转换矩阵如下所示： a b A {X,0,Y} {0,1,Y} {1} B {0,1,Y} {0,1,Y} {1} C {1} {0,Y} ? D {0,Y} {0,1,Y} {1} 最少化：终态{A,B,D}a ={A,B }∈{A,B,D} {A,B,D}b ={B,}∈{A,B,D} ∴ 最少化为： a (b)将图b 最少化 图b 解：终态{0,1} a ∈{0,1} {0,1} b ={2,4}∈{2,3,4,5} ∴{0,1}不能再分 非终态{2,3,4,5} a ={0,1,3,5} {2,4} a ={0,1} {2,4} b ={3,5} {3,5} a ={3,5} {3,5} b ={2,4} 0代表{0,1},2代表 {2,4},3代表{3,5}得最少化为： 14.构造一个DFA ，它接收∑={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。 解：构造正规式为：（0|10）* 则可构造如下NFA ： ε 列出状态转换矩阵如下： 0 1 A { q 0,F,A,C, q f } {B,G ,F,A,C, q f } {D} B {B,G ,F,A,C, q f } {B,G ,F,A,C, q f } {D} C {D} {E,G ,F,A,B,C, q f } ? D {E,G ,F ,A,B,C, q f } {B,G ,F,A,C, q f } {D} 则得DFA 如下： 最少化得 {A,B,D}0={B} {A,B,D}1={C} 15.给定右线性文法G ： S->0S|1S|1A|0B A->1C|1 B->0C|0 C->0C|1C|0|1 求出一个与G 等价的左线性文法。 编译原理试题A (2003.12.4) 一、回答下列问题：(30分) 1.(6分)对于下面程序段 program test (input, output) var i, j: integer; procedure CAL(x, y: integer); begin y:=y*y; x:=x-y; y:=y-x end; begin i:=2; j:=3; CAL(i, j) writeln(j) end. 若参数传递的方法分别为(1)传值、(2)传地址，(3)传名，请写出程序执行的输出结果。 2.(6分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，并判断该文 法是否是LL(1)的，请说明理由。 G(M)： M → TB T → Ba | ε B → Db | eT | ε D → d | ε 3.(4 产生式语义规则 S→ABC A→a B→b C→c B.u := S.u A.u := B.v + C.v S.v := A.v A.v :=3*A.u B.v := B.u C.v := 1 (1)画出字符串abc的语法树; (2)对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v的值为多少? 4.(4分)运行时的DISPLAY表的内容是什么？它的作用是什么？ 5. (5分)对下列四元式序列生成目标代码： A:=B*C D:=E+A G:=B+C H:=G*D 其中，H 在基本块出口之后是活跃变量， R0和R1是可用寄存器。 6. (5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。 二、(8分)构造一个DFA ，它接受∑={a ，b}上所有包含ab 的字符串。 三、 (6分)写一个文法使其语言为L(G)={a n b n c m | m,n≥1，n 为奇数，m 为偶数}。 四、(8分)对于文法G(S): ） Ma L a |(L M bMb S →→→ 1. 写出句型b(Ma)b 的最右推导并画出语法树。 2. 写出上述句型的短语，直接短语和句柄。 五、(12分)对文法G(S)： S → a | ^ | (T) T → T ，S | S (1) 构造各非终结符的FIRSTVT 和LASTVT 集合; (2) 构造算符优先表; (3) 是算符优先文法吗? (4) 构造优先函数。 六、(8分)设某语言的do-while 语句的语法形式为 S → do S (1) While E 其语义解释为： 真 假 S (1)的代码 E 的代码 编译原理试题国教A (2005.2.4) 一、回答下列问题：(30分) 1.(6分)对于下面程序段 program test (input, output) var i, j: integer; procedure CAL(x, y: integer); begin y:=y*y; x:=x-y; y:=y-x end; begin i:=2; j:=3; CAL(i, j) writeln(j) end. 若参数传递的方法分别为(1)传值、(2)传地址，(3)传名，请写出程序执行的输出结果。 答： (1) 3 (2) 16 (3) 16 (每个值2分) 2.(6分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，并判断该文 法是否是LL(1)的，请说明理由。 G(M)： M → TB T → Ba | ε B → Db | eT | ε D → d | ε 解答： 计算文法的FIRST和FOLLOW集合：(4分) FIRST(M) = { a，b，e，d，ε } FIRST(T) = { a，b，e，d，ε } FIRST(B) = {b，e，d，ε } FIRST(D) = {d，ε} FOLLOW (M) = {#} FOLLOW (T) = { a，b，e，d，#} FOLLOW (B) = {a，# } FOLLOW (D) = { b} 检查文法的所有产生式，我们可以得到： 1. 该文法不含左递归， 2. 该文法中每一个非终结符M ，T ，B ，D 的各个产生式的候选首符集两两不相交。 3. 该文法的非终结符T 、B 和D ，它们都有ε候选式，而且 FIRST(T)∩FOLLOW(T)={ a ，b ，e ，d }≠φ 所以该文法不是LL(1)文法。(2分) 3. (4 (1) 画出字符串abc 的语法树; (2) 对于该语法树，假设S.u 的初始值为5，属性计算完成后，S.v 的值为 多少。 答：(1) (2分) (2) S.v 的值为18 (2分) 4. (4分)运行时的DISPLAY 表的内容是什么？它的作用是什么？ 答：DISPLAY 表是嵌套层次显示表。每当进入一个过程后， 在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i ，则它的diaplay 表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY 表可以访问其外层过程的变量。 第二章 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 ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/******************************** 第二章 P36-6 ⑴ L(G)是o~9组成的数字串 ⑵ 最左推导： N= ND= NDD= NDDD= DDDD= ODDD= 01DD= 012D= 0127 N= ND= DD= 3D= 34 N= ND= NDD= DDD= 5DD = 56D= 568 最右推导: N= ND= N7= ND7= N27= ND 27= N127= D127= 0127 N= ND= N 4= D4= 34 N= ND= N8= ND8= N 68= D68= 568 P36-7 G(S) O > 1|3|5|7|9 N > 2∣4∣6∣8∣O D > 0|N S > OlAo A—；AD |N P36-8 文法： E τ T E +T|E —T 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 τ)= 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) ^语法树. /********************************编译原理_第三版_课后答案
编译原理课后答案
编译原理课后习题答案(陈火旺+第三版)
编译原理课后答案_第三版
编译原理考试 陈火旺(含答案)
编译原理 试题 陈火旺(含答案)
程序设计语言编译原理第3版课后答案
陈火旺编译原理(第三版)课后习题答案
相关主题
文本预览