#编译原理# 词法分析（三）第二部分

2019 年 10 月 6 日
筆記

词法分析

编译原理笔记第三部分，由于内容过长所以分为了两部分，跳转链接在总阅读目录处，内容参考：北航软院教师邵兵课堂课件及内容、张莉著《编译原理及编译程序构造》、国防工业出版社的《编译原理——学习指导与典型题解析》、AlvinZH的学习笔记以及个人理解

目前是包含了全部内容的版本，后续会推出精简版和复习知识点版

如有建议或错误错误欢迎在评论中指出或联系我：QQ：847590417

总阅读目录

本章总内容

第一部分：

3.1 词法分析程序的功能及实现方案

3.2 单词的种类及词法分析程序的输出形式

3.3 正则文法及状态图

3.4 正则表达式与有穷自动机FA

第二部分：

3.5 有穷自动机、正则文法、正则表达式的转化

本章总内容

重点：词法分析介绍、词法分析单词种类划分、正则文法、状态图、正则表达式、自动机、自动机的转化、表达式文法和自动机的转化、词法分析程序的设计实现，词法分析程序自动生成器LEX。

之前的内容

词法分析介绍、词法分析单词种类划分、正则文法、状态图、正则表达式、自动机、自动机的转化会在第三章的第一部分进行介绍。

3.5 有穷自动机、正则文法、正则表达式的转化

转化流程图：

以下转换的顺序是按图上箭头的顺序进行排序的（NFA包含DFA，所以和NFA的转化可能称之为DFA的转化）。

0.正则文法G转状态图

绘制左线性文法的状态图（状态图只能用于左线性文法，这是和后面的DFA的明显区别）状态图的绘制没有严格规定（右线性的暂时不做考虑）

1.文法的非终结符号是一个个的结点

2.设一开始状态S（句子）

3.对规则Q::=t（t为终结符），需要一条从S到Q的一条弧，弧上标记为t

4.对Q::=Rt，画一条从R到Q的弧，弧上标记为t

（倒，谁规约于谁，谁指向谁）

5.根据自动机方法，可加上开始状态和终止状态标志，识别符号作终止状态，用双圆圈标识

1.DFA M转正则文法 G

规则：

1.对(A,t) = B，写成：A→tB（只推右线性，左线性在推导时可能递归）

2.对每个可接受状态Z（终止状态），增加产生式Z→ε

3.有穷自动机的初态对应文法开始符号，有穷自动机的字母表为文法的终结符号集

例：

2.正则文法 G转DFA M

规则：（和状态图的转化类似）

1.字母表（弧上的所有符号组成的表）和G的终结符号相同

2.为G中的每个非终结符生成M的一个状态，G大的开始符号S是开始状态S

3.增加一个新状态Z，作为NFA的终态

4.对G中的形如A→tB，其中t为终结符或空字符，A和B为非终结符号的产生式，构造M的一个转换函数(A,t)=B

4.对G中形如A→t的产生式，构造M的一个转换函数(A,t)=Z

例：

3.正则表达式转DFA M

他们是等价的

定理：在Σ上的一个字集V，V是Σ*的子集，是正则集合，当且仅当存在一个DFA M使V=L(M).

规则：

一个正则表达式，构建时从左到右拆解分析即可

a. 对空集φ不作处理

b. 对正则式ε，由x射出符号为空符号的弧到y

c. 对字母表中存在的字母符号如正则式a，由x射出符号为该字符的弧到y

（x,y为状态，只是构建的临时初态终态，符号即是正则表达式中读取到的字符（从左到右分解））

多个正则式，例如s,t，他们的NFA为Ns和Nt

a. R=s|t

b. R=st

c. R=s*

d. R=(s)，和R=S的NFA一样

例：

1.从里开始构建NFA

2.从外开始构建

4.DFA M转正则表达式

规则：

（1）在M上加两个结点x,y。从x用空符号弧连接到M的所有初态节点，从M的所有终态节点用空符号弧连接到y，形成和M等价的的M’，此时只有一个初态一个终态。

（2）消除M’中的其他节点（除了x，y）

1.邻合并

2.并变或

3.递归加边加星号

即正则表达式转NFA倒过来

例：

5.正则文法 G转正则表达式

三个规则，可将正则文法转换为一个只剩一个开始符号的产生式，并且右侧不含非终结符，仅含对应的表达式。转换后的产生式应用扩充的BNF表示，而在标识符好的0~n次重复时应该用*代替

（1）代入规则：对A→xB，B→y转化为A→xy

（2）消除递归规则：对A→xA|y转化为A→x*y

（3）BNF规则：对A→x，A→y转化为A→x|y

注:左线性的话，对A→Ax|y转化为A→yx*

例如：

例：

6.正则表达式转正则文法 G

规则如下：

（1）对任何正则表达式r，选择一个非终结符S作为识别符号，并产生产生式S→r

（2）若x，y是正则表达式：

1.对A→xy，转化为A→xB，B→y，B为新的非终结符

2.对A→x*y，转化为A→xA，A→y（注：对A→x*y，则需要转化为A→xA，A→ε）

3.对A→x|y的产生式

例如：

例：

左线性的话：（会死循环）

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

3.6.1 词法分析原理

说明：

1.对于注释符号是不输出的

2.各单词之间用空白符号（空格、制表、回车）分开

在得知文法后

需要根据文法将所有终结符号的转化过程给绘制出来（初始符号就是每个终结符号）

这里出现的其他字符，实际是任意字符，例如读到+后再读入+，后一个+相对于前一个也是其他字符。

然后将这些转化过程都结合起来，初始状态当做传入的符号串。合并后还需要注意：对重复符号进行特殊处理（单双字符分界符处理合并），还需要一个出错的状态（符号串不属于任一流程）。

3.6.2 词法分析程序的构造

不同状态的做法

开始状态：利用程序依次读入字符，读到空字符就跳过，然后对每一个非空字符串转到程序中进行处理。

标识符状态：在组合成标识符后，判断是保留字还是用户自定义的

整数状态：组成数字后还要做数字字符到二进制数值的转换

单字符分界符状态：判断对应的类别编码即可

冒号状态：需要和下一个字符结合进行判断，是单字符还是双字符

斜竖状态：同样需要判断后面的字符，作为字符还是跳过注释

错误状态：打印错误信息并跳过

注：在词法分析时为了判别是否已经读到了单词的右端符号，有时候需要向前多读一个字符，例如在标识符和无符号整数等状态。这是为了防止跳过某个不该跳过的字符。所以在返回调用程序前应该将读字符指针后退一个字符。（字符指针后退实际就是退到前一个字符，因为在读取字符时可能多读一个字符，导致后面读取时这个字符就被忽略了，所以需要后退（字符指针是一直前进的，后退就是向上一个读的字符吐出来一个））