编译原理（3）——词法分析

词法分析

码文不易，希望支持，谢谢->支持原创

 词法分析（扫描）器的功能

  输入源程序，输出(单词)符号(token)。

即：把构成源程序的字符串转换成(单词)符号序列

 1. 单词符号的表示

(单词符号种别，属性值)

• 常用单词符号种别——分类

1.各关键字（保留字、基本字），各种运算符，各种分界符——各用一个种别码标识
2.其它标识符——用一个种别码标识
3.常数——用一个种别码标识

• 单词符号的值——属性

常数的值，标识符的名字等
保留字、运算符、分界符的属性值可以省略

代码块举例

 {            (LP,    _ )
 S        (IDN,符号表项指针)
 =        (EQ,  _)
 S        (IDN,符号表项指针)
 ++       (INC,    _ )
 ;                (SEMI,   _ )
 pointer          (IDN,  符号表项指针)
 ++           (INC,    _ )
 ;                (SEMI,   _ )
 }            (RP,     _ )    

码文不易，希望支持，谢谢->支持原创

 符号的正规(表达)式描述

  正规文法是左线性文法和右线性文法的统称。它们都是Chomsky分类下的3型文法。由正规文法产生的语言称为正规集。下面我们将会看到，这里之所以用“正规”二字为一种语言命名，是因为这种语言的结构可以用所谓正规式来描述。正规表达式——百度百科

  下面两种文法中l代表字母（终极符），d代表数字（非终极符）。

  左线性文法

  S→l | Sd | Sl

  右线性文法

  S→ l| lT
  T→ l| d| lT| dT

 1. 正规式

正规语言的另一种描述方法

例：l (l|d)*
 | 表示"或"
 * 表示Kleene闭包
 符号的并列表示符号连接关系

正规式 r 表示正规集,相应的正规集记为 L(r),意思明确时也可以直接记为r。

  正规(表达)式(Regular Expression——RE)

设 ∑ $\sum$是一个字母表，
⑴ ϕ $\varphi$是 ∑ $\sum$上的RE， L(ϕ)=ϕ $L(\varphi )=\varphi$；
⑵ ε $\epsilon$是 ∑ $\sum$上的RE， L(ε)={ε} $L(\epsilon )=\{\epsilon \}$；
⑶ 对于 ∃a∈∑ $\mathrm{\exists }a\in \sum$， a $a$是RE， L(a)=a $L(a)=a$；
⑷ 如果 r $r$和 s $s$是RE， L(r)=R $L(r)=R$, L(s)=S $L(s)=S$，则：
  r与s的“和” (r|s)是RE，L((r|s))=R∪S，
  r与s的“乘积/连接” (rs)是RE，L((rs))=RS，
  r的克林闭包(r*)是RE，L((r*))=R*。

  运算的优先级

• * 高于“连接” 和| ， “连接” 高于 |
• | 具有交换律、结合律
• “连接” 具有结合律、和对|的分配律
• ( ) 指定优先关系，意义清楚时，括号可以省略

 2. 正规文法与正规式

正规文法与正规式等价
对任何正规文法，存在定义同一语言的正规式
对任何正规式，存在生成同一语言的正规文法

  正规式到正规文法的转换

按如下方法构造正规定义式，并逐步将其转换成正规文法
1. 引入开始符号S，从如下正规定义式开始
S→r
2. 对r中的形如r1|r2|…|rn的子串
用产生式组 A→ r1|r2|…|rn 表示
3. 对r中的形如r1*的子式子
用产生式组 A→ε|r1A 表示
4. 对r中的形如 r1+ $r{1}^{+}$的子式子，
用产生式组 A→ r1|r1A 表示
5. 执行连接对|的分配律
对连接运算，要作特殊处理：按出现顺序定义
正规式到正规文法的转换用到了正规定义式的概念

下面是正规式

a(a|b)*(ε|((.|_)(a|b)(a|b)*))
    = a(a|b)*
    | a(a|b)*.(a(a|b)*|b(a|b)*)
    | a(a|b)*_(a(a|b)*|b(a|b)*)
    =aA | aC
A→aA | bA | ε
C→aC | bC | .B | _B
B→aA | bA | a | b

下面是转换后的正规表达式

S→aA | aC
A→aA | bA | ε
C→aC | bC | .B | _B
B→aA | bA | a | b

  一个简单词法的正规定义式

词法规则	单词种别	属性
<标识符>→<字母>(<字母>|<数字>)*	IDN	符号表项入口
<无符号整数>→ <数字> (<数字>)*	NUM	数值
<赋值符>→ :=	ASG	无
<加号>→+	+	无
<减号>→-	MINUS	无
<星号>→*	STAR	无

  变换为正规文法

<标识符> →letter<标识符尾>
<标识符尾>→ε | letter<标识符尾> | digit<标识符尾>
<整数> →digit <整数尾>
<整数尾> →ε | digit<整数尾>
<赋值号> →:=
<加号> →+
<等号> →=
…

  正规文法到正规定义式的转换

1. 代入：对于 A→xB, B→y，构造 A→xy
2. 递归：对于 A→xA|y，构造 A→x*y
3. 多候选式：对于 A→x，A→y，构造A→x|y

码文不易，希望支持，谢谢->支持原创

 符号的识别

  1. 状态转换图

用来描述词法分析器识别记号的分析过程

• 结点：状态用○表示；终态用◎表示
• 有向弧 ── 箭头

• 弧标记 ── 输入字符

    标识符的状态图

    <标识符>→letter(letter|digit)*

  从正规式到状态转换图

 2.从正规文法出发，构造状态图

(1) 以每个非终结符为状态结点，开始符号对应初态 S
(2) 增设一个终态 T
(3) 对于规则 A→aB，画从状态 A 到 B 的弧，标为 a
(4) 对于规则 A→a，画从状态 A 到终态 T 的弧，标为 a
(5) 对于规则 A→rB, B→sB，画从状态 A 到状态 B标为 r的弧，从状态B到B的标记为s的弧

 利用状态转换图识别单词符号

(1) 从初始状态出发
(2) 读入一字符
(3) 按当前字符转入下一状态
(4) 重复 2,3 直到完成一个单词的识别或者发现错误

在遇到读入的字符是Token的分割符时，若进入的状态是终止态，说明读入的字符组成一单词；否则，说明输入不符合词法规则

 词法分析程序的设计与实现

 1. 数据结构与子例程

  数据结构

数据结构	解释
ch	当前输入字符
token	输入缓冲区(字符数组)
symbol	单词种别（子程序的返回值）
attr	属性（全局变量）

  子程序

Lookup(token):将 token 存入符号表，返回入口指针
isKeyword(token):判别 token是关键字？返回关键字种别或 -1
getchar():从输入缓冲区中读入一个字符放入ch
isdigit()
isalpha()
···

 2. 需要说明的问题

1. 冲区预处理，超前搜索
2. 关键字的处理，符号表的实现
3. Lookup：查找效率，算法的优化实现
4. 词法错误处理

 3. 扫描器的自动生成

 词法分析器实现总结

支持原创

码文不易，希望支持，谢谢->支持原创

再次感谢，大家对本人的支持。