第三章 词法分析及词法分析程序 课后答案【khdaw_lxywyl】
- 格式：pdf
- 大小：339.03 KB
- 文档页数：14
下载文档原格式
合集下载
编译原理第三章练习题答案
编译原理第三章练习题答案编译原理第三章练习题答案编译原理是计算机科学中的重要课程之一，它研究的是将高级语言程序转化为机器语言的过程。
在编译原理的学习过程中，练习题是提高理解和应用能力的重要途径。
本文将为大家提供编译原理第三章的练习题答案，希望能够对大家的学习有所帮助。
1. 什么是词法分析？请简要描述词法分析的过程。
词法分析是编译过程中的第一个阶段，它的主要任务是将源程序中的字符序列划分为有意义的词素（token）序列。
词法分析的过程包括以下几个步骤：1）扫描：从源程序中读取字符序列，并将其转化为内部表示形式。
2）识别：根据预先定义的词法规则，将字符序列划分为不同的词素。
3）分类：将识别出的词素进行分类，如关键字、标识符、常量等。
4）输出：将分类后的词素输出给语法分析器进行进一步处理。
2. 什么是正则表达式？请给出一个简单的正则表达式示例。
正则表达式是一种用于描述字符串模式的工具，它由一系列字符和操作符组成。
正则表达式可以用于词法分析中的词法规则定义。
以下是一个简单的正则表达式示例：[a-z]+该正则表达式表示匹配一个或多个小写字母。
3. 请简要描述DFA和NFA的区别。
DFA（Deterministic Finite Automaton）和NFA（Nondeterministic Finite Automaton）是有限状态自动机的两种形式。
它们在词法分析中常用于构建词法分析器。
DFA是一种确定性有限状态自动机，它的状态转换是确定的，每个输入符号只能对应一个状态转换。
相比之下，NFA是一种非确定性有限状态自动机，它的状态转换是非确定的，每个输入符号可以对应多个状态转换。
4. 请简要描述词法分析器的实现过程。
词法分析器的实现过程包括以下几个步骤：1）定义词法规则：根据编程语言的语法规范，定义词法规则，如关键字、标识符、常量等。
2）构建正则表达式：根据词法规则，使用正则表达式描述不同类型的词素。
3）构建有限状态自动机：根据正则表达式，构建DFA或NFA来识别词素。
编译原理第三版课后习题答案
编译原理第三版课后习题答案编译原理是计算机科学中的一门重要课程，它研究的是如何将高级程序语言转换为机器语言的过程。
而《编译原理》第三版是目前被广泛采用的教材之一。
在学习过程中，课后习题是巩固知识、提高能力的重要环节。
本文将为读者提供《编译原理》第三版课后习题的答案，希望能够帮助读者更好地理解和掌握这门课程。
第一章：引论习题1.1：编译器和解释器有什么区别？答案：编译器将整个源程序转换为目标代码，然后一次性执行目标代码；而解释器则逐行解释源程序，并即时执行。
习题1.2：编译器的主要任务是什么？答案：编译器的主要任务是将高级程序语言转换为目标代码，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等过程。
第二章：词法分析习题2.1：什么是词法分析？答案：词法分析是将源程序中的字符序列划分为有意义的词素（token）序列的过程。
习题2.2：请给出识别下列词素的正则表达式：（1）整数：[0-9]+（2）浮点数：[0-9]+\.[0-9]+（3）标识符：[a-zA-Z_][a-zA-Z_0-9]*第三章：语法分析习题3.1：什么是语法分析？答案：语法分析是将词法分析得到的词素序列转换为语法树的过程。
习题3.2：请给出下列文法的FIRST集和FOLLOW集：S -> aAbA -> cA | ε答案：FIRST(S) = {a}FIRST(A) = {c, ε}FOLLOW(S) = {$}FOLLOW(A) = {b}第四章：语义分析习题4.1：什么是语义分析？答案：语义分析是对源程序进行静态和动态语义检查的过程。
习题4.2：请给出下列文法的语义动作：S -> if E then S1 else S2答案：1. 计算E的值2. 如果E的值为真，则执行S1；否则执行S2。
第五章：中间代码生成习题5.1：什么是中间代码？答案：中间代码是一种介于源代码和目标代码之间的表示形式，它将源代码转换为一种更容易进行优化和转换的形式。
![《数字信号处理》王世一版北京理工大学出版社部分习题答案【khdaw_lxywyl】[1]](https://uimg.taocdn.com/3617903610661ed9ad51f33f.webp)
《数字信号处理》王世一版北京理工大学出版社部分习题答案【khdaw_lxywyl】[1]
w.
ww
我们希望找到如下一个取样 于单位圆上 10 个等间隔点的 X ( z ) 的取样。
的周期性序列 . 试用
后
N −1
答
∑
n =0
% (n)W kn = % (n)W kn / 2 + x ∑x 2N N
n =0
N −1
2 N −1 n= N
% (n)W kn / 2 ∑x N
N −1
N −1
= (1 + e
− jkπ
% (n)W kn / 2 )∑ x N
n =0
N −1
⎛k⎞ = (1 + e − jkπ ) X 1 ⎜ ⎟ ⎝2⎠
后
（b） 求这个系统的单位取样响应。 （c） 读者会发现它是一个不稳定系统，求满足上述差分方程的一个稳定（但非因果）系统的单位取样响应。 解:
由于 H ( z ) 的收敛域不包括单位圆，所以这是个不稳定系统 c)若要使系统稳定，则其收敛域应包括单位圆，则选 H ( z ) 的收敛域为 0.62 <
kh da w. co m
n =0
1 ⎛ ⎞ H D (e jω ) = c ⎜ − aT −2 aT ⎟ ⎝ 1 − 2e cos ω + e ⎠
答
1− e
（a） 试求模拟滤波器的频率响应，并会出其振幅特性略图
kh da w. co m
1 a + jΩ
e j 3ω − e − j 4ω 1− e jω
案 网
c
− aT − jω
w.
课
QZ = a −2 − 2a −1 cos ω + 1 = 1/ a a 2 − 2a cos ω + 1
电路分析基础 俎云霄 课后答案【khdaw_lxywyl】
解： i1 5 4 2 i1 7A ， i1 i2 4 6 8 i2 5A
w.
u3
1-8 求题图 1-6 所示电路中的电压 u1 、 u2 和 u3 。
ww
解：10 6 u1 0 u1 4V ，10 10 u3 0 u3 0 ， u1 u2 u3 0 u2 4V
解： G11 1
1 3 1 1 3 5 1 ， G22 ， G33 ， G12 G21 ， G13 G31 0 ， 2 2 2 4 4 4 2 1 G23 G32 ， is11 2u 1 ， is 22 3i1 ， is 33 1 ，所以有 4
30
对回路 3，有回路方程： 35im1 50im 2 65im 3 10 则： 35 75i 65(1 i ) 10 ， i 2 A 此题最好选边{ac,bd,dc}为树，即将所求电流所在的支路选为连支。
da
im 3
1.5i
c
后 答
im 2
20
题图 2-21
第一章 作业解答 1-1 已知在如题图 1-1 所示电路的电压、电流参考方向下， u 5V ， i 2A ，请标出电 压、电流的实际方向。
a
i + u
－
b
题图 1-1
i
A +
u
i
B u
-
+
解：对于元件 A， PA ui 3 5 15W
3
2A 5A
4A
8A
题图 1-3
m
答：电压值为正数，实际方向与参考方向一致，为由 a 到 b，电流值为负数，实际方向与参 考方向相反，为由 b 到 a。
编译原理课后答案 (3)
编译原理课后答案问题一计算机程序的执行是一个多阶段的过程，其中编译是其中的一环。
请问编译的三个主要阶段分别是什么？答：编译过程一般可以分为三个主要阶段，分别是词法分析、语法分析和代码生成。
下面分别对这三个阶段进行介绍。
1. 词法分析词法分析是编译过程的第一步，也是最基础的一步。
它的任务是将源代码中的字符序列分解成一个个具有独立含义的单词，这些单词被称为“记号”或“词法单元”。
词法分析器根据程序中每一个字符的组合规则，将其转化为一个个词法单元，并记录下词法单元的类型标记。
词法分析器的工作一般通过有限状态自动机来实现，它根据一定的词法规则进行扫描和分析。
2. 语法分析语法分析是编译过程的第二步，它接收词法分析器生成的词法单元流，根据语法规则进行分析，并生成一棵语法树。
语法分析的主要任务是确定输入程序的结构，检查程序的语法正确性，并生成用于后续处理的输入形式。
语法分析器一般采用的是自顶向下或自底向上的分析方法，常用的方法有递归下降法和LR(1)分析法。
3. 代码生成代码生成是编译过程的最后一步，它将语法分析生成的语法树转化为目标机器的可执行代码。
代码生成器通过遍历语法树，将每个语法树节点转化为相应的目标机器代码。
代码生成过程中需要考虑到目标机器的特性和限制，以及优化代码的效率和性能。
问题二请解释一下编译原理中的词法规则是什么？答：编译原理中的词法规则指的是一组规定词法单元模式的规则。
它描述了如何将输入字符序列转换为词法单元，并为每个词法单元定义了一个标记。
词法规则一般使用正则表达式来描述词法单元的模式。
编译器根据词法规则构建词法分析器，用于将源代码分割成一系列的词法单元。
词法规则的灵活性和准确性对编译过程的性能和结果都有较大的影响。
一个完整的词法规则一般包含以下几个部分：1.正则表达式：描述了词法单元的模式，使用特定的正则表达式语法来表示。
2.动作：描述了当词法单元匹配到模式时，需要执行的动作或处理过程。
编译原理第三版 第三章 词法分析
超前搜索
例：FORTRAN语言中关键字的识别: DO99K=1,10 识别DO为关键字要搜 DO99K=1.10 索到“，” FORTRAN语言中常数的识别：
5.EQ.M, 5.E08
识别5为常数要搜索到Q
2、状态转换图
大多数程序设计语言中单词符号的词法规则可 以用正规文法描述。如： <标识符>→ 字母|<标识符>字母|<标识符>数字 <整数>→数字|<整数>数字 <运算符>→+|－|×|÷„ <界符>→; |, |( | )|„
#
3.3 正规表达式与有限自动机
目的： 形式化地描述词法规则和词法分析程序 词法分析程序的自动生成 主要内容 正规式与正规集 确定有限自动机 (DFA) 非确定有限自动机(NFA) 正规式与有限自动机的等价性 确定有限自动机的化简
正规文法
多数程序设计语言单词的语法都能用正规文法 (3型文法)描述 正规文法回顾 文法的任一产生式α→β的形式都为
单词符号的种类
(3) 常数 常数的类型一般有整型、实型、布 尔型、字符型等。
(4) 运算符 如 +，-，*，/等，对具体语言个 数是确定的。 (5) 界符 如 , ；（）等，对具体语言个数是 确定的。
单词符号的表示形式
词法分析器所输出的单词符号常常表示成如下的 二元式：<单词种别，单词符号的属性值> 单词种别:由语法分析阶段使用的抽象符号。如： 用整数编码。 最简单的编码方案为一类一码，种别编码可设为： 1,2,3,4,5。 另一种编码方案（如本教材中）： 标识符:列为一种，用一个整数编码表示； 常数:按类型分种编码； 关键字、运算符、界符:采用一字一种编码。
编译原理-第3章 词法分析--习题答案
第3章词法分析习题答案1．判断下面的陈述是否正确。
（1）有穷自动机接受的语言是正规语言。
(√)（2）若r1和r2是Σ上的正规式，则r1|r2也是Σ上的正规式。
(√)（3）设M是一个NFA，并且L(M)={x,y,z}，则M的状态数至少为4个。
(× )（4）设Σ={a,b}，则Σ上所有以b为首的符号串构成的正规集的正规式为b*(a|b)*。
(× )（5）对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。
(√)（6）对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。
(√) （7）一个DFA，可以通过多条路识别一个符号串。
(× )（8）一个NFA，可以通过多条路识别一个符号串。
(√)（9）如果一个有穷自动机可以接受空符号串，则它的状态图一定含有 边。
(× )（10）DFA具有翻译单词的能力。
(× )2.指与出正规式匹配的串.（1)(ab|b)*c 与后面的那些串匹配？ababbc abab c babc aaabc（2）ab*c*(a|b)c 与后面的那些串匹配？ acac acbbc abbcac abc acc（3）(a|b)a*(ba)* 与后面的那些串匹配? ba bba aa baa ababa答案（1) ababbc c babc（2) acac abbcac abc（3) ba bba aa baa ababa3. 为下边所描述的串写正规式，字母表是{0, 1}.（1)以01 结尾的所有串（2)只包含一个0的所有串（3) 包含偶数个1但不含0的所有串（4)包含偶数个1且含任意数目0的所有串（5)包含01子串的所有串（6)不包含01子串的所有串答案注意 正规式不唯一（1)(0|1)*01（2)1*01*（3)(11)*（4)(0*10*10*)*（5)(0|1)*01(0|1)*（6)1*0*4.请描述下面正规式定义的串. 字母表{x, y}.（1) x(x|y)*x（2)x*(yx)*x*（3) (x|y)*(xx|yy) (x|y)*答案（1)必须以 x 开头和x结尾的串（2)每个 y 至少有一个 x 跟在后边的串 （3)所有含两个相继的x或两个相继的y的串5．处于/* 和 */之间的串构成注解，注解中间没有*/。
编译原理教程第五版课后答案
编译原理教程第五版课后答案第一章：引言问题1答：编译器是一种将高级编程语言源代码转换为目标机器代码的软件工具。
它由多个阶段组成，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成等。
问题2答：编译器的主要任务包括以下几个方面： - 词法分析：将源代码划分为词法单元，如标识符、关键字、操作符等。
- 语法分析：根据语法规则，将词法单元组成语法树。
- 语义分析：对语法树进行语义检查，如类型匹配、变量声明等。
- 中间代码生成：将语法树转换为中间代码表示形式。
- 代码优化：对中间代码进行优化，以提高程序的效率。
- 代码生成：将优化后的中间代码转换为目标机器代码。
第二章：词法分析问题1答：词法单元是编译器在词法分析阶段识别的最小的语法单位，它由一个或多个字符组成。
常见的词法单元包括关键字、标识符、常量和运算符等。
问题2答：识别词法单元的方法包括以下几种： - 正则表达式：通过正则表达式匹配字符串，识别出各类词法单元。
- 有限自动机：构建有限状态自动机，根据输入字符的不同状态转移，最终确定词法单元。
- 递归下降法：使用递归下降的方式，根据语法规则划分出词法单元。
第三章：语法分析问题1答：语法分析是编译器的一个重要阶段，它的主要任务是根据给定的语法规则，将词法单元序列转换为语法树。
语法分析有两个主要的方法：自顶向下的分析和自底向上的分析。
问题2答：自顶向下的分析是从文法的起始符号开始，根据语法规则逐步向下展开，直到生成最终的语法树。
常见的自顶向下的分析方法包括LL(1)分析和递归下降分析。
问题3答：自底向上的分析是从输入串开始，逐步合并词法单元，最终生成语法树。
常见的自底向上的分析方法包括LR分析和LALR分析。
第四章：语义分析问题1答：语义分析的主要任务是对语法树进行语义检查和类型推断。
语义分析阶段会检查变量的声明和使用是否合法，以及类型是否匹配等。
问题2答：常见的语义错误包括变量未声明、类型不匹配、函数调用参数不匹配等。
第三章 词法分析及词法分析程序
a 开始 0 b a 1 b 2
3、由文法构造状态图
正规文法描述语言单词 状态转换图可识别单词 正规文法描述语言单词，状态转换图可识别单词，它们 描述语言单词， 单词， 之间存在等价关系。 等价关系 之间存在等价关系。
1) 右线性文法向状态图转换方法
构造状态集： G=（ 是一右线性文法， 构造状态集：设G=（VN，VT，P，S）是一右线性文法， |=k,共有k+1个节点（状态）。其中， k,共有k+1个节点 ）。其中 |VN|=k,共有k+1个节点（状态）。其中，k个状态是非终 结符号，另一个状态引入一个F∈V作为终态，初态为S F∈V作为终态 结符号，另一个状态引入一个F∈V作为终态，初态为S。 构造状态间弧： 中每个产生式， 构造状态间弧：P中每个产生式，对于 形如A→aB的产生式,从节点A引一条矢线到节点B, 形如A→aB的产生式,从节点A引一条矢线到节点B,矢 A→aB的产生式 B,矢 线标记为a 线标记为a； 形如A→a的产生式， 形如A→a的产生式，从A引一条矢线到终态F，并用 A→a的产生式 引一条矢线到终态F 符号a标记此矢线。 符号a标记此矢线。
Q
b
4）符号串的识别
对于符号串W=a 对于符号串W=a1a2a3……an，ai∈VT 可对W识别。 可对W识别。 从初态F出发，自左至右逐个扫视W中的各个字符， 从初态F出发，自左至右逐个扫视W中的各个字符，在 F下扫视的符号为a1； 下扫视的符号为a 在节点F所射出诸矢线中寻找标记为a 的矢线（ 在节点F所射出诸矢线中寻找标记为a1的矢线（若不存 则说明W有错）； 在，则说明W有错）； 读入a 沿矢线所指方向到下一状态， 读入a1沿矢线所指方向到下一状态，在从此状态扫描 a2，……， ……， 直到W中全部字符读完且进入终态S 直到W中全部字符读完且进入终态S，则W已被接受。 已被接受。
编译原理第3章课后习题答案
Dtran[I,b] =ε-closure(move(I,b))= ε-closure（{5, 16}）=G DFA D 的转换表 Dtran NFA 状态 {0,1,2,4,7} {1,2,3,4,6,7,8} {1,2,4,5,6,7} {1,2,4,5,6,7,9} {1,2,4,5,6,7,10,11,12,13,15} {1,2,3,4,6,7,8,12,13,14,15,17,18} {1,2,4,5,6,7, 12,13,15,16,17,18} {1,2,4,5,6,7, 9,12,13,15,16,17,18} {1,2,4,5,6,7, 10,11,12,13,15,16,17,18} 可得 DFA 的如下状态转换图： DFA 状态 A B C D E F G H I a B B B B F F F F F b C D C E G H G I G
3.3.1 给出 3.2.2 中正则表达式所描述的语言的状态转换图。
(1)a( a|b )*a 的状态转换图如下：
（2）
ε
ε a
b
（3）
a
start 0
a a a
1 2
4
b a b
5
b b
3
6
7
（4）a*ba*ba*ba*
a b
a b
a b
a
3．6.3 使用算法 3.25 和 3.20 将下列正则表达式转换成 DFA： (1)
注：consonant 为除五元音外的小写字母，记号 ctnvowels 对应的定义即为题目要求的正则
定义。
(2) 所有由按字典顺序递增序排列的小写字组成的串。 a*b*……z* （3)注释，即/*和*/之间的串，且串中没有不在双引号（ “）中的*/。 head——>/* tail ——>*/ * * incomment->(~(*/)|“. ”) comment->head incomment tail （9）所有由 a 和 b 组成且不含有子串 abb 的串。 * * A->b (a︱ab)
编译原理第三章词法分析
L→ a | b | … | z | A | B | … | Z D → 0 | 1 | … | 9 <标识符> → L(L|D|_)* <无符号正整数> → DD*
z19
step1 : 对语言的各类单词分别构造状态图；
step1
L
1
2
other
*
3 其中： other表示非L| D | _字符
z8
3.2.1 单词与属性字
注意：
(1) 同一个字符开头+后续字符->跨多个单词类；
(2) 非单词成分和预处理成分；
•例:源程序注释；/* …….*/
预处理指令：
•# define… # include…
z9
3.2.1 单词与属性字
2. 属性字 对所识别的单词的数据结构表示。
控制线
数据线
X : 固定长度的存储空间 ; z16
预处理程序（作用）
(1) 减少内存空间占用；
(2) 减轻扫描器实质性处理的负担；
预处理程序主要任务：
(1) 滤掉源程序中的非单词成分(如无用空格；换行
符等)；
•滤掉注释；
(2) 实际的预处理工作
•宏替换； •文件包含的嵌入；
L1= （ T，C）
属性字 Token
Code
刻画单词类别（单词性质）
如:标识符；运算符；…
单词的内码值（可空）
z10
说明
单词类别通常用整数编码 单词类别提供给语法分析程序使用 单词符号属性信息记录单词符号的特征或特性 单词的属性值提供给语义分析程序使用
编码形式：
一类一种：关键字、标识符、常数、运算符、界符 一字一种：关键字、运算符、分界符各一码
z19
step1 : 对语言的各类单词分别构造状态图；
step1
L
1
2
other
*
3 其中： other表示非L| D | _字符
z8
3.2.1 单词与属性字
注意：
(1) 同一个字符开头+后续字符->跨多个单词类；
(2) 非单词成分和预处理成分；
•例:源程序注释；/* …….*/
预处理指令：
•# define… # include…
z9
3.2.1 单词与属性字
2. 属性字 对所识别的单词的数据结构表示。
控制线
数据线
X : 固定长度的存储空间 ; z16
预处理程序（作用）
(1) 减少内存空间占用；
(2) 减轻扫描器实质性处理的负担；
预处理程序主要任务：
(1) 滤掉源程序中的非单词成分(如无用空格；换行
符等)；
•滤掉注释；
(2) 实际的预处理工作
•宏替换； •文件包含的嵌入；
L1= （ T，C）
属性字 Token
Code
刻画单词类别（单词性质）
如:标识符；运算符；…
单词的内码值（可空）
z10
说明
单词类别通常用整数编码 单词类别提供给语法分析程序使用 单词符号属性信息记录单词符号的特征或特性 单词的属性值提供给语义分析程序使用
编码形式：
一类一种：关键字、标识符、常数、运算符、界符 一字一种：关键字、运算符、分界符各一码
《编译原理》蒋立源课后答案【khdaw_lxywyl】
www.khd课后a答w案.网com
课后答案网
最右推导： <程序>T<分程序>T<标号>：<分程序> T<标号>：<标号>：<分程序> T<标号>：<标号>：<无标号分程序> T<标号>：<标号>：<分程序首部>；<复合尾部> T<标号>：<标号>：<分程序首部>；<语句>；<复合尾部> T<标号>：<标号>：<分程序首部>；<语句>；<语句>；end T<标号>：<标号>：<分程序首部>；<语句>；s；end T<标号>：<标号>：<分程序首部>；s；s；end T<标号>：<标号>：<分程序首部>；说明；s；s；end T<标号>：<标号>：<分程序首部>；d；s；s；end T<标号>：<标号>：begin 说明；d；s；s；end T<标号>：<标号>：begin d；d；s；s；end T<标号>： L：begin d；d；s；s；end TL：L：begin d；d；s；s；end （2）句子 L：L：begin d；d；s；s end 的相应语法树是：
第二章 习题解答
1.（1）答：26*26=676
（2）答：26*10=260
（3）答：{a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz}, 共 26+26*36+26*36*36=34658 个
编译原理第三章习题讲解
词法分析器的实现
实现词法分析器可以采用工具如Lex或Flex，这些工具可以根据词法规则自动生成相 应的词法分析器代码。
也可以手动编写词法分析器的代码，但需要熟练掌握正则表达式和有限自动机等相 关知识。
在实现过程中，需要注意处理输入缓冲区的管理、记号的输出和错误处理等问题。
02
习题二：语法分析
语法分析概述
03
中间代码生成的方法
包括解析、语义分析和控制流分析等步骤，最终将源代码转换为中间代
码。
代码优化技术
代码优化概述
通过各种技术手段对中间代码进行优化，以提高目标 代码的执行效率。
常见的代码优化技术
包括常量折叠、死代码消除、循环展开、内联函数等。
代码优化策略
根据程序特性和系统环境选择合适的优化策略，以达 到最佳的优化效果。
3
词法分析器通常采用正则表达式或有限自动机来 实现。
词法分析算法
01
词法分析算法通常采用“自顶向下”的分词方法，即从源代码 的开头开始，逐步识别出各个记号。
02
常用的分词算法有正向最大匹配法、逆向最大匹配法和双向最
大匹配法等。
在词法分析过程中，需要特别注意处理源代码中的注释、字符
03
串文字和符号文字等特殊情况。
03
实现过程中还需要注意处理各 种语法错误和异常情况，以确 保语法分析的正确性和可靠性 。
03
习题三：语义分析
语义分析概述
语义分析是编译过程的核心环 节之一，主要负责对源程序的 语法结构进行分析，并检查其
语义是否合法。
语义分析的目的是在语法分 析的基础上，进一步确定源 程序中各个语句的含义，以
及它们之间的关系。
编译器设计实践概述
编译原理部分课后答案,仅供参考
第一章编译程序概述1.1 什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序。
对有些高级语言甚至配置了几个不同性能的编译程序。
1.2编译过程概述和编译程序的结构编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。
从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。
一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。
事实上，某些阶段可能组合在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了。
我们将分别介绍各阶段的任务。
另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。
编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。
图1.3表示了编译的各个阶段。
图1.3 编译的各个阶段1.3 高级语言解释系统为了实现在一个计算机上运行高级语言的程序,主要有两个途径：第一个途径是把该程序翻译为这个计算机的指令代码序列，这就是我们已经描述的编译过程。
第二个途径是编写一个程序，它解释所遇到的高级语言程序中的语句并且完成这些语句的动作，这样的程序就叫解释程序。
从功能上说，一个解释程序能让计算机执行高级语言。
它与编译程序的主要不同是它不生成目标代码，它每遇到一个语句，就要对这个语句进行分析以决定语句的含义，执行相应的动作。
右面的图示意了它的工作机理第二章：PL/0编译程序问答第1题PL/0语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管理。
编译原理chapter3 (2016)
编译原理chapter3词法分析33正规表达式与有限自动机一正规式和正规集为了识别正则语言我们引入了状态转换图和有限自动机正规表达式与有限自动机一正规式和正规集为了识别正则语言我们引入了状态转换图和有限自动机有限自动机所接受的语言正是正则文法产生的语言正则文法产生的语言正则语言程序设计语言中的单词也大多是由正
5
1 4 1
―）”
指向x的符号表入口 ―=‖ 指向y的符号表入口
5
―;‖
编译原理
chapter3
词法分析
词法分析的分离：
实际上，词法也是语法的一部分，词法描述完全可 以归并到语法描述中去，只不过词法规则更简单些。 进一步说，在编译程序中可以将词法分析包含在语法 分析之中，那么为什么把编译过程的分析工作划分成 词法分析和语法分析两个阶段？主要考虑的因素为： (1)使整个编译程序的结构更简洁、清晰和条理化； (2)编译程序的效率会改进； (3)增强编译程序的可移植性。
编译原理
chapter3
词法分析
具体地：
(1)ε和ф是Σ上的正规式，它们所表示的正规集分别为{ε}和ф; (2) 若a∈Σ，则a是Σ上的正规式，它所表示的正规集为{a}; (3)若e1和e2都是Σ上的正规式，且它们所表示的正规集分别为 L(e1)和L(e2)，那么： (e1) 是正规式，表示的正规集为L(e1)； e1|e2 是正规式，表示的正规集为L(e1)∪L(e2) ； e1.e2 是正规式，表示的正规集为L(e1)L(e2) ； e1* 是正规式，表示的正规集为(L(e1))*。 (4)仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式， 仅由这些正规式所表示的字集(符号串集合)才是Σ上的正规集。
编译原理
chapter3
5
1 4 1
―）”
指向x的符号表入口 ―=‖ 指向y的符号表入口
5
―;‖
编译原理
chapter3
词法分析
词法分析的分离：
实际上，词法也是语法的一部分，词法描述完全可 以归并到语法描述中去，只不过词法规则更简单些。 进一步说，在编译程序中可以将词法分析包含在语法 分析之中，那么为什么把编译过程的分析工作划分成 词法分析和语法分析两个阶段？主要考虑的因素为： (1)使整个编译程序的结构更简洁、清晰和条理化； (2)编译程序的效率会改进； (3)增强编译程序的可移植性。
编译原理
chapter3
词法分析
具体地：
(1)ε和ф是Σ上的正规式，它们所表示的正规集分别为{ε}和ф; (2) 若a∈Σ，则a是Σ上的正规式，它所表示的正规集为{a}; (3)若e1和e2都是Σ上的正规式，且它们所表示的正规集分别为 L(e1)和L(e2)，那么： (e1) 是正规式，表示的正规集为L(e1)； e1|e2 是正规式，表示的正规集为L(e1)∪L(e2) ； e1.e2 是正规式，表示的正规集为L(e1)L(e2) ； e1* 是正规式，表示的正规集为(L(e1))*。 (4)仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式， 仅由这些正规式所表示的字集(符号串集合)才是Σ上的正规集。
编译原理
chapter3
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
课 后 答 案 网
第三章 词法分析及词法分析程序 1 试用某种高级语言编写一个 FORTRAN 源程序的预处理子程序，其功能是： 每调用它一次， 即把源程序中的一个完整语句送入扫描缓冲区。要求删去语句中的注释行；删去续行标记字 符，把语句中的各行连接起来，并在语句的末端加上语句结束符。此外，还要求此程序具有 组织源程序列表输出的功能。 2 画出用来识别如下三个关键字的状态转移图。 STEP STRING SWITCH 3 假定有一个猎人带着一只狼、一头山羊和一棵白菜来到一条河的左岸，拟摆渡过河，而岸 边只有一条小船，其 大小仅能装载人和其余三件东西中的一件，也就是说，每一次猎人只 能将随行者中的一件带到彼岸。若猎人将狼和山羊留在同一岸上而无人照管，那么，狼就会 将羊吃掉；如果猎人把山羊和白菜留在同一岸，山羊也会把白菜吃掉。现在，请你用状态转
试找出一个长度最小的输入串，使得：
h (1) 在识别此输入串的过程中，每一状态至少经历一次；
(2) 每一状态转换至少经历一次。 9 对于下列的状态转换矩阵：[]a[]bS[]A[]SA[]A[]BB[]B[]B(i) 初态：S
k 终态：B[][][]a[]bS[]A[]BA[]B[]AB[]B[]B(ii) 初态：S
26 指出下列 LEX 正规式所匹配的字符串：
. (1) "{" ［^{］*"}"
(2) ^［^a-z］［A-Z］［0-9］$ (3) ［^0-9］|［＼r＼n］
w (4) ＼′(［^′＼n］|＼′＼′)+＼′
(5) ＼"(［^"＼n］|＼＼［"＼n］)*＼"
a 27 写出一个 LEX 正规式，它能匹配 C 语言的所有无符号整数 (例如：OX89ab，0123，45，
A→BbB→BbB→a
课 后 答 案 网
C→DC→BabD→d (1) 试分别对 G1 和 G2 构造相应的状态转换图 (提示：对于右线性文法，可将形如 C→D 的 产生式视为 C→εD；而对左线性文法，则可将它视为 C→Dε)。 (2) 对于 G1，构造一等价的左线性文法 G1′；对于 G2 构造一等价的右线性文法 G2′。 (3) 对于 G1 和 G1′，分别给出如下符号串的推导序列： abbaababbbcdcbb
〈WHILE 语句〉→WHILE〈关系表达式〉DO〈语句〉 〈复合语句〉→BEGIN〈语句表〉END 〈过程定义〉→PROCEDURE〈标识符〉〈参数表〉； BEGIN〈语句表〉END
课 后 答 案 网
〈参数表〉→(〈标识符表〉)|〈空〉 〈标识符表〉→〈标识符表〉，〈标识符〉|〈标识符〉 〈算术表达式〉→〈算术表达式〉+〈项〉|〈项〉 〈项〉→〈项〉*〈初等量〉|〈初等量〉 〈初等量〉→(〈算术表达式〉)|〈变量〉|〈无符号数〉 〈关系表达式〉→〈算术表达式〉〈关系符〉〈算术表达式〉 〈变量〉→〈标识符〉 〈标识符〉→〈标识符〉〈字母〉|〈标识符〉〈数学〉|〈字母〉 〈无符号数〉→〈无符号数〉〈数字〉|〈数字〉 〈关系符〉→=|＜|＜=|＞|＞=|＜＞
课后答案网，用心为你服务！
大学答案 --- 中学答案 --- 考研答案 --- 考试答案 最全最多的课后习题参考答案，尽在课后答案网（）！ Khdaw团队一直秉承用心为大家服务的宗旨，以关注学生的学习生活为出发点，
旨在为广大学生朋友的自主学习提供一个分享和交流的平台。 爱校园（） 课后答案网（） 淘答案（）
终态：A[]a[]bS[]A[]BA[]C[]AB[]B[]CC[]C[]C(iii) 初态：S
. 终态：A,C[][][]a[]bS[]A[]SA[]C[]BB[]B[]CC[]C[]C(iv) 初态：S
终态：C (1) 分别画出相应的状态转换图； (2) 写出相应的 3 型文法；
w(3) 用自然语言分别描述它们所识别的输入串的特征。
m 14 将如题图 314 所示的有限自动机最小化。
15 试用一种高级语言分别写出将 NFA 确定化以及将 DFA 最小化的算法。
o 16 构造一产生 FORTRAN 语言 COMMON 语句的 3 型文法 (假定分别用λ和μ代表标识符和整常
数，它们都是终结符号，且假定数组的维数不加限定)，构造相应的 DFA，并写出描述 COMMON 语句的正规式。
a 8 对于有限自动机 M=(K,Σ,f,S0,Z)
其中，K={S0,S1,S2,S3,S4,S5},Σ={a,b},Z={S1,S4,S5}。 f 由如下的状态转移矩阵给出：
d []a[]bS0[]S2[]S1S1[]S3[]S1S2[]S0[]S4S3[]S0[]S0S4[]S5[]S4S5[]S4[]S0
′Z′,′＼t′,′＼xab′,′＼012′,等等)。 28 写出一个 LEX 正规式，它能匹配 C 语言的标识符。
d 29 编写一个 LEX 源程序，它将一个正文文件中的全部小写字母均换为大写字母，并将其中
的制表字符、空白字符序列均用单个空格字符进行替换 (提示： 在语义动作中使用全程变
h 量 yytext)。
程中建立。 (3) 单词串的输出形式。
w 所输出的每一单词，均按形如
(CLASS，VALUE)
a 的二元式编码。对于变量标识符和常数，CLASS 字段为相应的类别码，VALUE 字段则是该标
识符、常数在其符号表中登记项的序号 (要求在变量名表登记项中存放该标识符的字符串， 其最大长度为四个字符；常数表登记项中则存放该整数的二进制形式)。对于保留字和分隔
c 17 设 r,s 等为任意的正规式，试证明下列的关系式成立：
(1) r*=(ε|r)*=ε|rr*=(r*)*
. (2) (rs)*r=r(sr)*
(3) (r|s)*=(r*s*)*=(r*|s*)* 18 对于解习题 36 所得的文法，试用正规式描述它所产生的语言。
w []a[]bS0[]S1[]S5S1[]S2[]S7S2[]S3[]S5S3[]S5[]S7S4[]S5[]S5S5[]S3[]S1S6[]S3[]S0S7[]
m 换图作为工具，描述猎人可能采取的种种摆渡方案，并从中找出可将上述三件东西安全地带
到右岸的方案来。
o 4 设已给文法 G=(VN,VT,P,S)，其中，P 仅含形如
A→αBA→αα∈V*T，B∈VN 的产生式，试证明： 由此种文法所产生的语言是一正规语言。 5 试证明： 任何有限个符号串所组成的集合 L={x1,x3,…,xn}xi∈Σ+ 都是 3 型语言。
〈变量说明〉→VAR〈变量表〉：〈类型〉；|〈空〉 〈变量表〉→〈变量表〉，〈变量〉|〈变量〉
w〈类型〉→INTEGER
〈语句表〉→〈语句表〉；〈语句〉|〈语句〉 〈语句〉→〈赋值语句〉|〈条件语句〉|〈WHILE 语句〉|〈复合语句〉|〈过程定义〉
w〈赋值语句〉→〈变量〉∶〈语句〉ELSE〈语句〉
10 对于下面所给的文法： G1=({S,A,B,C,D}, {a,b,c,d},P1,S)
wP1 由如下产生式组成： S→aAS→BA→abS w A→bBB→bB→cC
C→DD→dD→bB 以及 G2=({S,A,B,C,D},{a,b,c,d},P2,S) P2 由如下产生式组成： S→AaS→BA→Cc
30 编写一个 LEX 源程序，它能统计一个 PASCAL 程序中所含用户定义之标识符个数，并能找 出最长标识符中的字符个数 (提示： 使用全程变量 yytext 及 yyleng)。
k 上 机 实 习 题
对于如下文法所定义的 PASCAL 语言子集，试编写并上机调试一个词法分析程序：
. 〈程序〉→〈变量说明〉BEGIN〈语句表〉END.
19 对于习题 310 所给的文法 G1 和 G2，试分别用正规式描述它们所产生的语言。
h 20 设有如下的文法 G［〈标号说明〉］：
〈标号说明〉→′LABEL′〈标号表〉 〈标号表〉→d〈标号段〉
k 〈标号段〉→d〈标号段〉|,〈标号〉|；
〈标号〉→d〈标号段〉
. 其中′LABEL′,′d′,′,′,′;′等为终结符号。
m 〈字母〉→A|B|C|…|X|Y|Z
〈数字〉→0|1|2|…|8|9
o 〈空〉→
要求和提示： (1) 单词的分类。
c 可将所有标识符归为一类；将常数归为另一类；保留字和分隔符则可采取一词一类。
(2) 符号表的建立。
. 可事先建立一保留字表，以备在识别保留字时进行查询。变量名表及常数表则在词法分析过
(4) (b|aa|ac|aaa|aac)* (5) a(a|b)*b(a|b)*a(a|b)*b(a|b)* 23 试设计一个识别器，它识别由下列英语单词： ONE, TWO, THREE, …， NINE， TEN，
课 后 答 案 网
ELEVEN， TWELVE， THIRTEEN， …， NINETEEN， TWENTY， THIRTY， FORTY， …， NINETY， HUNDRED 所表示的从 1 到 999 间的任何整数 (各单词间用空格分隔，如 THREE HUNDRED FIFTY SIX)， 并将它们翻译为相应的阿拉伯数字 (如 356)作为输出。 24 设有辅助定义式 D0=a|b D1=D0D0 D2=D1D1 … Dn=Dn-1Dn-1
k (5) 写出它的 LEX 源程序，并上机进行处理。 第三章 习题解答
. 1．从略 www2．
课 后 答 案 网
3 假设 W:表示载狐狸过河，G:表示载山羊过河，C:表示载白菜过河 用到的状态 1：狐狸和山羊在左岸 2：狐狸和白菜载左岸 3:羊和白菜在左岸 4:狐狸和山羊 在右岸 5:狐狸和白菜在右岸 6:山羊和白菜在右岸 F:全在右岸
c 6 试构造一右线性文法，使得它与如下的文法等价
S→ABA→UTU→a|aU
. T→b|bTB→c|cB