下载文档原格式
正规⽂法与正规式 3型⽂法也叫作正规⽂法，它对应于有限状态⾃动机，它是在2型⽂法的基础上满⾜：A->a|aB（右线性）或A->a|Ba（左线性）。
如果有A->a,A->aB,B->a,B->cB则符合3型⽂法的要求。
但是A->ab,A->aB,B->a,B->cB或A->a,A->Ba,B->a,B->cB则不符合3型⽂法的要求。
也就是说，不能够推导出两个终结符，⽽且左线性和右线性只能使⽤⼀种，不能够同时出现。
1.分别写出描述以下语⾔的正规⽂法和正规式：（1）L1={ab n a|n≥0}。
（2）L2={a m b n|n≥1,m ≥1}（3）L3={（ab）n|n≥1}答：（1） S → aA A → bA | a L1 = ab*a （2）S → aAA → aA | bB | b B → bB | b L2 = a*b* （3）S → aA A → bB B → aA | ε L3 = (ab)*2.将以下正规⽂法转换到正规式·Z→0A· A→0A|0B· B→1A|ε答：Z = 0A A = 0A + 0B B = 1A + ε A = 0A + 0(1A + ε) = 0A + 01A + 0 A = aA | b Z = 0(0 | 01)*0Z→U0|V1 U→Z1|1 V→Z0|0答：Z = U0 + V1 U = Z1 + 1 V = Z0 + 0 Z = (Z1+1)0 + V1 Z = (Z1+1)0 +(Z0+0)1 Z = Z10 + 10 +Z01 + 01 Z = Z(10+01)+10+01 Z = (10+01)*1001 Z = (10 | 01)*1001S→aA A→bA|aB|b B→aA答：S = aAA = bA + aB + b B = aA A = bA + a(aA) +b = (b + aa)A +b S = (b | aa)*bI→l|Il|Id答： I = l + Il + Id I = l + I(l +d) I = l(l | d)*。
第三章习题参考解答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．一个正规语言只能对应(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．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)上。
第二章 高级语言及其语法描述6．（1）L （G 6）={0,1,2,......,9}+（2）最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568 最右推导：N=>ND =>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>5687．【答案】Ｇ：S →ABC | AC | CA →1|2|3|4|5|6|7|8|9B →BB|0|1|2|3|4|5|6|7|8|9C →1|3|5|7|98．（1）最左推导：E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*iE=>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*iE=>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) (2)9．证明：该文法存在一个句子iiiei 有两棵不同语法分析树，如下所示，因此该文法是二义的。
*编译原理复习题一．简答题：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
课上练习
1. ＝{a, b, c}, 构造NFA，可以识别a,b,c组成的串,
串中所含 a的个数不超过1. (即可以含一个a或不含a)
2. ＝{a, b, c}, 构造NFA，可以识别a,b,c组成的串,
串中只含一个a
3. ＝{a, b, c}, 构造NFA，可以识别a,b,c组成的串,
串中 至少含一个a
4. 构造识别标识符的自动机 l(l|d)*
5. ＝{a, b} , 构造NFA, 可以识别不以a开头, 但以aa结尾的字符串
并写出等价的正规式
b(a|b)*aa
6. ＝{a, b}, 构造NFA, 可以识别a,b组成的串,
每个a后面至少紧随两个b,
并写出等价的正规式
(b|abb)*
a
b, c
AS
b, c
a
a
阿
A S
b, c
b, c
a
2
A S
b, c
a, b, c
2
ab a
Y1X
a
b
X l l, d Y
B
b
a
a
A S
b
b
文法、正规式、自动机、正规语言
2
课下练习1
1. 给语言 L={an|n≥0} , 写3型文法，并构造自动机
可以构造出L的自动机如下: 再将自动机转换成3型文法,
G: SaS |ε
2. 给语言L={ anbm |n,m≥1}，写3型文法，并构造自动机
可以构造出L的自动机如下: 再将自动机转换成3型文法,
G: S→aA
A→aA|bB
B→bB|
3. 构造自动机
L={ a2n+1b2ma2p+1 | n≥0,m≥1, p≥0 }
4. 给语言 L(G)={ anbmck |n,m,k≥0} ，写3型文法，并构造自动机
a*b*c*
G: S→aS|B
B→bB|C
C→cC|ε
将DFA 1和DFA 2确定化最小化, 得到结果相同：
S
a
A a bbCSaabbB
aa
a
b
A
a
b
b
BS
b
A
a
S
a
B C
b Sc
a
ε
ε
S
a
B C
b c
a,b b,c
a,b,c
S
a
B C
bc
b
c
b
c
b
文法、正规式、自动机、正规语言
3
课下练习2
5. 构造自动机，识别能被3整除的二进制数
状态0: 被3整除
状态1: 被3除余1
状态2: 被3除余2
6. 构造自动机，识别含奇数个0 且 奇数个1 的二进制数串
S: 偶数个0, 偶数个1
A: 奇数个0, 偶数个1
B: 奇数个0, 奇数个1
C: 偶数个0, 奇数个1
7. 构造文法, 产生含有偶数个1的二进制数串， ＝{0,1}
解法一：
G : S 0S | 1A |
A 0A | 1S
解法二：
S: 偶数个0, 偶数个1
A: 奇数个0, 偶数个1
B: 奇数个0, 奇数个1
C: 偶数个0, 奇数个1
确定化，最小化，则得到解法一中的DFA
0
0
1 2
1
10
01
S
A
0
0
C1 11 0 011 B
0 00
0
A
1
1
S
0
0
C11 001B
S A
1
文法、正规式、自动机、正规语言
4
单元测试2
8. 构造自动机，识别满足以下条件的符号串：
至少含有两个1, 又在任何两个1之间有偶数个
0
9. 写出下图所示自动机所描述的语言
100*|100*11*0|111*0
化简得: 10*1*0
L={10m1n0 | m≥0, n≥0}
10. 证明题：正规集的子集不一定是正规集
证明如下:
a*b* 是正规集, L1={ anbn |n≥0}是它的子集, 但是L1不是正规集,
因为找不到一个3型文法描述L1, 即只能用2型文法描述L1
G: SaSb|
A
1
b
1
C S 0 B
0
D
0 1 1
A
1
b
1
B S
1
A
0
C0 0 0 0 D
