北航计算机学院编译习题讲解.pdf
第三章:词法分析
3.1 词法分析的功能
3.2 词法分析程序的设计与实现
–状态图
3.3 词法分析程序的自动生成
–有穷自动机、LEX
7月2 日 1
补充
正则文法
1 5
2
6
4
NFA 正则表达式
3
DFA
最小化
7月2 日 2
P67:1．画出下述文法的状态图
〈Z〉::=〈B〉e
〈B〉::=〈A〉f
〈A〉::= e |〈A〉e
使用该状态图检查下列句子是否是该文法的合法句子
f，eeff，eefe
解：
e
e f e
S A B Z
f，eeff不是该文法的合法句子，eefe是该文法的合法句子
7月2 日 3
0
P67: 2. 有下列状态图，其中S为初态，Z为终态。 0 A
开始
(1) 写出相应的正则文法： S 1
(2) 写出该文法的V，V和V ； 0 Z
n t
(3) 该文法确定的语言是什么？
出错点：第(3)小题，文法确定的语言, 很多同学回
答出了，但是写的格式很不规范。
解：(1) Z→A1|0 A→A0|0
(2) V={A,Z,0,1} Vn={A,Z} Vt={0,1}
n
(3) L (G[S])= {0或01,n≥1}
*
0|00 1
7月2 日 4
P67: 5 ．令A ，B ，C是任意正则表达式，证明以下关系成立：
A|A=A
(A* )*= A*
A*=ε| AA*
(AB )*A = A (BA )*
(A|B )* = (A*B* )*= (A*|B* )
该题做得不错！但少部分同学最
