词法分析
重点与难点
重点与难点
重点：词法分析器的输入、输出，用于识别符号的状态转移图的构造，根据状态转移图实
现词法分析器。
难点：词法的正规文法表示、正规表达式表示、状态转移图表示，它们之间的转换。
基本要求
基本要求
明确词法分析的任务，熟练掌握词法的正规文法表示、正规表达式表示、状态转移图
表示及它们之间的转换，掌握词法分析器的设计与实现，重点掌握根据状态转移图实现词
法分析器。
例题解析
例题解析
例 1 用正规表达式标识符的文法。
【解】设标识符是由字母和数字组成的有限长的符号串，且第一个符号只能是字母。
用 l 表示字母: a,b,… ,z,A,B,…,Z; d 表示数字:0,1,… |9。
标识符的正规表达式表示为： l ( l | d)
*
例２用正规文法描述标识符的文法。
【解】用 l 表示字母: a,b,… ,z,A,B,…,Z; d 表示数字:0,1,… |9。
定义文法 G,G =({d,l}, {S,T}, P, S)
P:S→l|lT T→l|lT T→d | dS
得到标识符文法的右线性文法表示。
或者 定义文法 G,G =({d,l}, {S,T}, P, S)
P:S→l S→Sd S→Sl
得到标识符文法的左线性文法表示
或者通过正规表达式转换为正规文法的方法得到标识符文法的正规文法。
引入开始符号 S，构造 S
→
→l ( l | d)
*
引入非终结符 T，
分解“连接”的正规式 构造
分解“连接”的正规式 构造 S
→
→l T , T
→
→ ( l | d)
*
，因为
，因为
( l | d)
*
=
ε
ε
|
| ( l | d)
+
=
ε
ε
|
| ( l | d) ( l | d)
*
=
ε
ε
|
|
lT | dT
lT | dT
得到产生式的集合
得到产生式的集合
P :
P :
S
S
→ lT
→ lT
T
T
→ ε| lT | dT
→ ε| lT | dT
构成右线性文法
构成右线性文法
:
:
Ｇ ＝（
Ｇ ＝（
{l,d}
{l,d}
，
，
{S,T}
{S,T}
，
，
P
P
，
，
S
S
）
）
例 3 用状态图描述标识符（变量名等）的文法。
【解】用正规文法转换为状态图的方法。
标识符的正规文法
S
S
→ lT
→ lT
T
T
→ ε| lT | dT
→ ε| lT | dT，是一个右线性文法,
按照由右线性正规文法构造状态转换图的方法,构造标识符的状态转换图如下:
1
