下载文档原格式
第三章1、L(G[S])={ abc }2、L(G[N])={ n位整数或空字符串| n>0 }3、G[E]：E—>E+D | E-D | DD—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 94、L(G[Z])={ a n b n | n>0 }5、(1) 考虑不包括“0”的情况G[S]：S—>0S | ABC | 2 | 4| 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8考虑包括“0”的情况：G[S]：S—>AB | CB—>AB | CA—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>0 | 2 | 4 | 6 | 8(2)方法1：G[S]：S—> ABC | 2 | 4 | 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8方法2：G[S]：S—>AB | CB—> AB | 0B | C | 0A—> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>2 | 4 | 6 | 86、设<表达式>为E，<项>为T，<因子>为F，注：推导过程不能省略，以下均为最左推导(1) E => T => F => i(4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i(6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I7、<表达式><表达式>*<表达式><表达式>+<表达式>i i i<表达式><表达式>+<表达式>i <表达式>*<表达式>i i8、是有二义性的，因为句子abc 有两棵语法树（或称有两个最左推导或有两个最右推导）最左推导1：S => Ac => abc最左推导2：S => aB => abc9、(1)(2) 该文法描述了变量a 和运算符+、*组成的逆波兰表达式10、(1) 该文法描述了各种成对圆括号的语法结构(2) 是有二义性的，因为该文法的句子()()存在两种不同的最左推导：最左推导1：S => S(S)S => (S)S => ()S => ()S(S)S => ()(S)S => ()()S => ()()最左推导2：S => S(S)S => S(S)S(S)S => (S)S(S)S => ()S(S)S => ()(S)S => ()()S => ()()11、(1) 因为从文法的开始符E 出发可推导出E+T*F ，推导过程如下：E => E+T => E+T*F ，所以E+T*F 是句型。
编译原理第三章练习题答案编译原理第三章练习题答案编译原理是计算机科学中的重要课程之一，它研究的是将高级语言程序转化为机器语言的过程。
在编译原理的学习过程中，练习题是提高理解和应用能力的重要途径。
本文将为大家提供编译原理第三章的练习题答案，希望能够对大家的学习有所帮助。
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来识别词素。
3.3.2, 3.3.6, 3.3.7, 3.3.8, 3.3.9,3.6.3, 3.6.4, 3.6.53.7.1, 3.7.2, 3.7.33.8.1, 3.8.23.9.3《编译原理》（龙书）第三章答案3.3.2 描述下列正则表达式代表的语言。
a) a(a|b)*ab) ((ε|a)b*)*c) (a|b)*a(a|b)(a|b)d) a*ba*ba*ba*e) (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*答案(a)由a开头并结尾的由a和b构成的字符串(b)由a和b构成的字符串(c)倒数第三位为a的由a和b构成的字符串(d)仅含3个b的由a和b构成的字符串(e)含有偶数个a和偶数个b的由a和b构成的字符串注意：请准确描述语言的性质而不是列举满足正则表达式的串3.3.6 写出满足下列定义的字符a) The first ten letters in either upper or lower caseb) The lowercase consonantsc) The “digits” in a hexadecimal numberd) The characters that can appear at the end of a legitimate English sentence答案(a)a-jA-J(b)a-j(c)0-9a-f(d).?!3.3.7 写出匹配字符串“\ 的正则表达式答案：\”\\3.6.3 对于图3.29表示的NFA,列出aabb的所有路径。
这个NFA能否接受aabb? 答案：aabb的所有路径01223 00111 012000 00000 01222 00011 00123存在路径1223和0123所以能接受aabb3.6.4 对于图3.30表示的NFA,列出aabb的所有路径。
这个NFA能否接受aabb? 答案：01012301012120301230301212030303232030303212303030321212由于存在03210这样的环,所以这里有无数种路径存在路径终止于3,所以能接受aabb3.6.5 给出以下NFA的Transition Table(a) 图3.29(b) 图3.30(c) 图3.26答案:3.7.1 把下列NFA转化为DFA(a)图3.26(b)图3.29(c)图3.30答案:(a)(b)注意:以上答案并不唯一,等价即可3.7.2 用算法3.22模拟NFA(输入为aabb)(a)图3.29(b)图3.30答案:F={3} 所以返回yesF={3},所以返回yes3.7.3 用算法3.23和3.20把下列正则表达式转换为DFAa) (alb)*b) (a*lb* )*c) ((ela)b*)*d) (alb)*abb(alb)*答案：a) NFAb) NFAc) NFAd) NFA注意：这道题要求大家按照算法构造NFA和DFA，有些同学的NFA没有完全按照算法构造。
第三章语法分析3.1 完成下列选择题：(1) 文法G：S→xSx|y所识别的语言是。
a. xyxb. (xyx)*c. xnyxn(n≥0)d. x*yx*(2) 如果文法G是无二义的，则它的任何句子α。
a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同(3) 采用自上而下分析，必须。
a. 消除左递 a. 必有ac归b. 消除右递归c. 消除回溯d. 提取公共左因子(4) 设a、b、c是文法的终结符，且满足优先关系ab和bc，则。
b. 必有cac. 必有bad. a～c都不一定成立(5) 在规范归约中，用来刻画可归约串。
a. 直接短语b. 句柄c. 最左素短语d. 素短语(6) 若a为终结符，则A→α·aβ为项目。
a. 归约b. 移进c. 接受d. 待约(7) 若项目集Ik含有A→α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α·”动作的一定是。
a. LALR文法b. LR(0)文法c. LR(1)文法d. SLR(1)文法(8) 同心集合并有可能产生新的冲突。
a. 归约b. “移进”/“移进”c.“移进”/“归约”d. “归约”/“归约”【解答】(1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d3.2 令文法G[N]为G[N]: N→D|NDD→0|1|2|3|4|5|6|7|8|9(1) G[N]的语言L(G[N])是什么?(2) 给出句子0127、34和568的最左推导和最右推导。
【解答】(1) G[N]的语言L(G[N])是非负整数。
(2) 最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568最右推导：NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D685683.3 已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。
第三章习题参考解答3.1 构造自动机A，使得①②③当从左至右读入二进制数时，它能识别出读入的奇数；④它识别字母表{a, b}上的符号串，但符号串不能含两个相邻的a，也不含两个相邻的b；⑤它能接受字母表{0, 1}上的符号串，这些符号串由任意的1、0和随后的任意的11、00对组成。
⑥它能识别形式如±dd*⋅ d*E ±dd的实数，其中，d∈{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。
3.2 构造下列正规表达式的DFSA：① xy*∣yx*y∣xyx；② 00∣(01)*∣11；③ 01((10∣01)*(11∣00))*01；④ a(ab*∣ba*)*b。
3.3 消除图3.24所示自动机的空移。
bεq1q2q3aba,bqaq6q4q5abεεε图3.24 含空移的自动机3.4 将图3.25所示NDFSA确定化和最小化。
xyqq1q2q4q3xyxyx,yx图3.25 待确定化的NDFSA3.5 设e、e1、e2是字母表∑上的正规表达式，试证明① e∣e=e；② {{e}}={e}；③ {e}=ε∣e{e}；④ {e1 e2} e1= e1{e2 e1};⑤ {e1∣e2}={{e1}{e2}}={{e1}∣{e2}}。
3.6 构造下面文法G[Z]的自动机，指明该自动机是不是确定的，并写出它相应的语言： G[Z]:Z→A0A→A0∣Z1∣03.7 设NDFSA M=({x, y},{a, b},f, x, {y}), 其中，f(x, a)={x, y}, f(x, b)={y}, f(y, a)=∅, f(y, b)={x, y}。
试对此NDFSA确定化。
3.8 设文法G[〈单词〉]：〈单词〉→〈标识符〉∣〈无符号整数〉〈标识符〉→〈字母〉∣〈标识符〉〈字母〉∣〈标识符〉〈数字〉〈无符号整数〉→〈数字〉∣〈无符号整数〉〈数字〉〈字母〉→a∣b〈数字〉→1∣2试写出相应的有限自动机和状态图。
编译原理第三章练习题答案编译原理第三章练习题答案编译原理是计算机科学中的重要学科，它研究的是如何将高级语言代码转化为机器语言的过程。
在编译原理的学习过程中，练习题是不可或缺的一部分，通过完成练习题可以更好地理解和掌握编译原理的知识。
本文将为大家提供编译原理第三章练习题的答案，希望对大家的学习有所帮助。
1. 什么是语法分析？语法分析是编译器中的一个重要模块，它的主要任务是根据给定的语法规则，对输入的源代码进行分析和解释。
语法分析器会根据语法规则构建一个语法树，用于表示源代码的结构和含义。
常用的语法分析方法有递归下降法、LL(1)分析法和LR分析法等。
2. 什么是LL(1)文法？LL(1)文法是一种特殊的上下文无关文法，它具有以下两个特点：(1) 对于任何一个句子，最左推导和最右推导是唯一的。
(2) 在预测分析过程中，只需要向前看一个输入符号就可以确定所采用的产生式。
LL(1)文法是一种常用的文法形式，它适用于递归下降法和LL(1)分析法。
3. 什么是FIRST集合和FOLLOW集合？FIRST集合是指对于一个文法符号，它能够推导出的终结符号的集合。
FOLLOW 集合是指在一个句型中，某个非终结符号的后继终结符号的集合。
计算FIRST集合和FOLLOW集合可以帮助我们进行语法分析，特别是LL(1)分析。
4. 什么是递归下降语法分析法？递归下降语法分析法是一种基于产生式的自顶向下的语法分析方法。
它的基本思想是从文法的开始符号开始，递归地根据产生式进行分析，直到推导出输入符号串或发现错误。
递归下降语法分析法的实现比较简单，但对于某些文法可能会出现回溯现象，影响分析效率。
5. 什么是LR分析法？LR分析法是一种自底向上的语法分析方法，它的基本思想是从输入符号串开始，逐步构建语法树，直到推导出文法的开始符号。
LR分析法具有较好的分析效率和广泛的适用性，常用的LR分析方法有LR(0)、SLR(1)、LR(1)和LALR(1)等。
第 3 章习题3-1 试构造一右线性文法，使得它与如下的文法等价4AB A f UT U faU|a D fbT|b B fcB|c并根据所得的右线性文法，构造出相应的状态转换图。
3-2 对于如题图3-2 所示的状态转换图(1) 写出相应的右线性文法；(2) 指出它接受的最短输入串；(3) 任意列出它接受的另外 4 个输入串；(4) 任意列出它拒绝接受的 4 个输入串。
3-3 对于如下的状态转换矩阵：(1) 分别画出相应的状态转换图；(2) 写出相应的 3 型文法；(3) 用自然语言描述它们所识别的输入串的特征。
3-4 将如下的NFA确定化和最小化:3-5 将如题图3-5所示的具有£动作的NFA确定化。
题图3-5 具有£动作的NFA试用正规式描述它所产生的语言。
3-7 分别构造与如下正规式相应的 NFA(1) ((0 |1)(1 0)) ⑵ b|a(aa *b)*b3-8 构造与正规式(a|b) *(aa|bb)(a|b)*相应的 第3章习题答案3-1 解：根据文法知其产生的语言是L[G]={am 3n c i| m,n,i 仝 1}可以构造与原文法等价的右线性文法其状态转换图如下：3-2 解:4 aA L aA|bB 4 bB|cC|c C^ cC|cDFAA ^ aA|bB4 bB|cC|cC^ cC|cc4 0A|1C0110,0011,000011,00110Df0B|1CEf0B|1CFf 1A|0E|0(2) 最短输入串为 O11(3) 任意接受的四个输入串为：(1) 其对应的右线性文法是 G[A]:0A|1F|1 (4) 任意拒绝接受的输入串为： 0111，1011，1100，10013-3 解:(1) 相应的状态转换图为：(2) 相应的 3 型文法为： (i ) S f aA|bS AfaA|bB| b Bf aB|bB|a|b(ii) S f aA|bB| AfbA|aC| a|b BfaB|bC| b Cf aC|bC|a|b(iii) S f aA|bB| AfaB|bA| a BfaB|bB|a|b (iv) S f bS|aAAfaC|bB| aBfaB|bC| bCf aC|bC|a|b（3） 用自然语言描述的输入串的特征为：（i ）以任意个（包括0个）b 开头，中间有任意个（大于1） a ,跟一个b ,还可以有一个由 a,b 组成的任意字符串。
第3章文法和语言
第1题
文法G＝({A,B,S},{a,b,c},P,S)其中P为：
S→Ac|aB
A→ab
B→bc
写出L(G[S])的全部元素。
答案：
L(G[S])={abc}
第2题
文法G[N]为：
N→D|ND
D→0|1|2|3|4|5|6|7|8|9
G[N]的语言是什么？
答案:
G[N]的语言是V+。
V={0,1,2,3,4,5,6,7,8,9}
N=>ND=>NDD.... =>NDDDD...D=>D......D
或者：允许0开头的非负整数？
第３题
为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。
答案：
G[S]: S->S+D|S-D|D D->0|1|2|3|4|5|6|7|8|9
第4题
已知文法G[Z]：
Z→aZb|ab
写出L(G[Z])的全部元素。
答案：
Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb
L(G[Z])={a n b n|n>=1}
第5题
写一文法，使其语言是偶正整数的集合。
要求：
(1) 允许0打头；
(2)不允许0打头。
答案：
(1)允许0开头的偶正整数集合的文法E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8
(2)不允许0开头的偶正整数集合的文法E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0
第6题
已知文法G：
<表达式>::=<项>｜<表达式>＋<项>
<项>::=<因子>｜<项>*<因子>
<因子>::=（<表达式>）｜i
试给出下述表达式的推导及语法树。
（５）i+(i+i)
（６）i+i*i
第8题
文法G[S]为：
S→Ac|aB
A→ab
B→bc
该文法是否为二义的？为什么？
答案：
对于串abc
(1)S=>Ac=>abc (2)S=>aB=>abc
即存在两不同的最右推导。
所以，该文法是二义的。
或者：
第10题
文法S→S(S)S|ε
(1) 生成的语言是什么？
(2) 该文法是二义的吗？说明理由。
答案：
（１）嵌套的括号
（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。
第11题
令文法G[E]为：
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
第14题
给出生成下述语言的上下文无关文法：（1）{ a n b n a m b m| n，m>=0} （2）{ 1n0m 1m0n| n，
m>=0}
（3）{WaWr|W属于{0|a}*，Wr表示W的逆}
答案：
（１）S→AA A→aAb|ε （２）S→1S0|A A→0A1|ε （３）
S→0S0|1S1|ε
第16题给出生成下述语言的三型文法：
(1){an|n >=0 }
(2) { a n b m|n,m>=1 }
(3){a n b m c k|n,m,k>=0 }
答案：
(1) S→aS|ε
(2) S→aA A→aA|B B→bB|b
(3) A→aA|B B→bB|C C→cC|ε
第18题
解释下列术语和概念：
（１）字母表
（２）串、字和句子
（３）语言、语法和语义
答案：
（１）字母表：是一个非空有穷集合。
（３）语言：它是由句子组成的集合，是由一组记号所构成的集合。
程序设计的语言就是所有该语言的程序的全体。
语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。
语法：表示构成语言句子的各个记号之间的组合规律。
程序的结构或形式。
语义：表示按照各种表示方法所表示的各个记号的特定含义。
语言所代表的含义。
附加题
问题1：
给出下述文法所对应的正规式：S→0A|1B A→1S|1 B→0S|0
答案：
R = (01 | 10) ( 01 | 10 )*
问题2：
已知文法G[A]，写出它定义的语言描述G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC
答案:
G[A]定义的语言由0、1符号串组成，串中0和1的个数相同.
问题3：
给出语言描述，构造文法. 构造一文法,其定义的语言是由算符+, *, (,)和运算对象a构成的算术表达式的集合.
答案一：
G[E] E→E+T|T T→T* F|F F→(E)|a
答案二：
G[E] E→E+E|E* E|(E)|a
问题4：
已知文法G[S]:
S→dAB
A→aA|a
B→ε|bB
相应的正规式是什么？G[S]能否改写成为等价的正规文法？
答案：
正规式是daa*b*；
相应的正规文法为(由自动机化简来)：
G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b
也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε
问题5：
已知文法G：
E→E+T|E-T|T
T→T*F|T/F|F
F→(E)|i
试给出下述表达式的推导及语法树
(1) i;
(2) i*i+i
(3) i+i*i
(4) i+(i+i)
答案：
(1)E=>T=>F=>i
(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i
(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i
(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i)。
