编译原理讲义
(第三章,词法分析 )
南京大学计算机系赵建华词法分析与词法分析程序
词法分析的任务是识别源程序中具有独立含义的最小语法单位 ----符号或单词,如标识符，无正负号常数与界限符等。并把源程序转换为等价的内部表示形式。
功能：
– 读入源程序字符串；识别单词（符号）；
– 转换成属性字；
– 一些其他的简单工作：删除注解，预加工处理符号识别和重写规则
规则例子：
– <标志符 >,:= 字母 | <标识符 >字母 | …
– 在上面的例子中，实际可以展开为 <标识符 >,:=
a | b | c | d |…
如果我们规定终结符号的集合为字符，那么我们会发现上面的规则都满足正则文法的规则限制,U::=T | UT。因此，我们可以使用有限自动机来辅助完成词法分析。
实现方式
完全融合：由于正则文法是 CFG的一种特例。所以，可以把词法规则和语法规则统一处理。
相对独立：词法分析作为子程序。当语法分析程序需要读下一个符号的时候，
调用这个子程序。
完全独立：词法分析程序作为单独的一趟来实现。
状态转换图与转换系统
识别标志符程序的程序的流程图见图 3-1；
在流程图中的每个边上的操作一般都是判断输入符号是否满足等于某些值。如果不等于，那么识别失败。
实际上，这样的流程图是一种模式。
我们可以把流程图简化为一个状态转换图。状态转换图的运行由输入驱动。状态转换图包括状态，联接状态的边。有些状态是接收状态，每条边都标记了一个符号。
转换图的运行和接受
转换图在运行的时候，由一个当前的状态。每次输入一个符号的时候，转换图的状态改变如下：沿着从当前状态离开的，并且用输入符号标记的边，到达这个边的目标状态。
一个符号串被状态转换图接受当且仅当从初始状态出发，逐次输入符号串中的所有符号的时候，最终的状态是接受状态。
从文法构造状态转换图
我们可以给每个正则文法构造一个状态转换图。
其基本思想如下：
– 当我们使用自底向上的方式规约一个正则文法的句子的时候，得到的句型都是形如
Utx(tx为终结符号串 )。而下次规约的规则总是满足 V::=Ut。如果我们把非终结符号作为状态，而把 tx看作尚未读入的部分时，就得到一个状态转换图。 P61图 3-4。
从文法构造状态转换图 (算法 )
步骤一：引入一个开支状态 S（假定 S不是非终结符号。
步骤二：每个非终结符号作为一个结点。
步骤三：
– Q::=T：从 S到 Q有一条标记为 T的弧。
– Q::=RT：从 R到 Q有一条标记为 T的弧。
识别符号为接受状态。
从文法构造状态转换图 (例子 )
S
A
B
Z
Z,:= Za | Aa | Bb
A::= Ba | a
B,:= Ab | b
使用状态转换图构造正则文法
从构造步骤来看，正则文法和状态转换图之间具有一种对应关系。
状态转换图具有直观的特点，所以给定一个正则语言，构造状态转化图比较方便。
构造正则文法 (例子 )
例子,{(ab)nb2 | n>=0}
S
转换系统
定义：转换系统是具有下列特征的状态转换图：
– 只有唯一的开始状态 S和唯一的终止状态 Z；
– 没有弧进入 S，也没有离开 Z
– 可能有空弧。
S
S2
I
S1 Z
1
Z2
Z
转换系统
定理 3.2 对于任何一个状态图，都存在一个相应的转换系统，它们接受同样的语言。
转换系统对于从正则表达式转换到状态转换图起到了中间表示的作用。
DFA的定义
有穷状态自动机是对状态转换图的一种形式化定义。
定义：一个 DFA是 (K,?,M,S,F)
– K 有穷非空状态集合
–? 有穷的输入字母表集合
– M 从 K?M到 K的映射。
– S 是 K中的一个状态，称为开始状态。
– F K的子集，称为终止状态集合。
DFA的例子
({S,Z,A,B},{a,b},M,S,{Z})；
其中
– M(S,a) = A M(S,b) = B
– M(A,a) = Z M(A,b) = B
– M(B,a) = A M(B,b) = Z
– M(Z,a) = Z
S
A
B
Z
a
b
a b
a
b
a
运行 DFA
扩充后的映射 M的定义：
– M(R,?) = R 表示一定要有输入符号后，
DFA的状态才可能改变。
– M(R,Tt)=M(M(R,T),t) 表示状态的改变是从左到右进行的。
定义：字符串 t被 DFA接受当且仅当 M(S,t)
在 F中。
DFA接受的符号串集合
定义,(D)FA所能够接受的所有字符串的集合写成 L(D),L(D)是正则集合，。
定理 3.3 设 G为正则文法，如果 x数据 L(G)，
那么它能被 G相应的有穷自动机所接受。
定理 3.4 接受正则语言 L的最小状态自动机不记同构是唯一的。
非确定有穷状态自动机 NFA
在前面的从正则文法构造 FA的例子中，
恰好从一个状态射出的弧的标记是两两不同的。但是，如果有两个规则 V::=UT
和 W::=UT，那么从 U到 V和 W的弧的标记都是 T。
此时，不能用 DFA的映射来表示状态为 U
时，输入 T时的后继状态。也就是说，当状态为 U，输入为 T时，这个转换图的下一步动作出现了不确定性。这个状态转换图不再是 DFA。
不确定状态转换图的例子
Z::= Za | Aa | Bb
A::= Ba | Za | a
B::=Ab | Ba | b S
A
B
Z
a
b
a b
a
b
a
a
a
NFA的定义
定义：一个 DFA是 (K,?,M,S,F)
– K 有穷非空状态集合
–? 有穷的输入字母表集合
– M 从 K?M到 K的超集的映射。
– S 是 K的子集，称为开始状态集合。
– F K的子集，称为终止状态集合。
NFA和 DFA的不同在于,
– M的值域是 K的超集。
– 开始状态有不止一个
NFA的例子
({S,A,B,Z},{a,b},M,{S},{Z})
M：
– M(S,a)={Z} M(S,b)={B}
– M(A,a)={Z} M(A,b)={B}
– M(B,a)={A,B} M(B,b)={Z}
– M(Z,a)={A,Z} M(Z,b)={}
S
A
B
Z
a
b
a b
a
b
a
a
a
运行 NFA
扩充的影响 M
– M({R1,R2,…,R n,},T) =?iM(Ri,T)
– M(Q,?) = Q 表示一定要有输入符号后，
NFA的状态才可能改变。
– M(Q,Tt)=M(M(Q,T),t) 表示状态的改变是从左到右逐个进行的。
M(Q,x)表示当输入符号串为 x的时候，所有可能的最后状态。
NFA接受的语言
对于某个输入符号串 x，如果 M(S,x)?F非空，那么我们就说 x被该 NFA接受。
直观地讲,x被一个 NFA接受表示从某个开始状态，按照某种选择，可以到达某个接受状态。表 3-2。
定理 3.5：对于任何一个正则文法 G，都存在一个 NFA A，使得 L(G)=L(A)。反之亦然。
从 NFA到 DFA
使用 NFA判定某个输入符号串的时候，可能出现不确定的情况：不知道下面选择那个状态。如果选择不好，该输入符号串可能不能到达终止状态。但是，我们不能说该输入符号串不能被该 NFA接受。
如果通过尝试的方法，不断试探来确定输入符号串是否可被接受，那么判定的效率将降低。解决的方法是将 NFA转换为等价的 DFA。
从 NFA到 DFA
定理 3.6 对于给定的 NFA (K,?,M,S,F)，
可以构造一个等价的 DFA (K’,?,M’,S’,F’)
如下：
– K’中的状态一一对应于 K的子集。和子集
{Q1,Q2,…,Q n}对应的状态为 [Q1,Q2,…,Q n]
– M’([Q1,Q2,…,Q n],T) = 对应于?iM(Qi,T)的状态。
– S’为 S
– F’为对应于所有与 F相交的子集的状态。
从 NFA到 DFA
例子 3.7
由于 K的子集的个数为 K的个数的指数个，
所以以上面的方法得到的状态非常多。
实际上不是所有的子集都可以到达的。
可以使用列表法来完成 DFA的构造。从开始状态起，只有可以达到的状态才构造其后继。
自动机的等价
定义 3.8：如果 L(A)=L(A’)，那么我们说
A和 A’等价。
定理 3.8：存在判定两个自动机是否等价的算法。
确定自动机的等价
两个等价的 DFA
的状态个数可能不同。 DFA可以进行化简。化简不仅是去除死状态，不可能到达状态，还包括状态的合并。
a
a
b
b
b
a
b
a b
1 3 4
2
0
b
a
b
a
b
a
b
a
0
1
2
3
自动机状态的区分与等价
定义 3.9 如果从 P开始输入 w使得结束时候的状态的终止状态。从 Q开始输入 w时，结束的状态为非终止状态（或无状态），那么我们说 w把 P和 Q区分开来。
定义 3.10 不可区分的两个状态成为等价的状态。
空串把终止状态和非终止状态区分开来。
显然，如果 P,Q等价，那么 P和 Q对于同一个符号的后继也等价。
DFA化简
步骤 1：将 DFA的状态分为互不相交的子集，
使得每个子集中的状态等价（见分划算法）。
步骤 2：每个子集中选取一个状态作为子集中所有状态的代表，其余删除。这些代表构成了化简后的自动机的状态集合。对于原有的状态 P和 Q,如果有 P到 Q的一个标记为 T的边，
那么有从 P的代表到 Q的代表有一个标记为 T
的弧（有可能是圈）。
步骤 3：删除死状态和无用状态。
DFA化简
得到的状态转换图仍然是 DFA吗？为什么？
开始状态为包含有开始状态的子集的代表。
原来为终止状态的，现在仍然是终止状态。
DFA化简（分划算法）
步骤 1：初始分划：终止状态和非终止状态。
步骤 2：重复对于每一组 G都进行下列细分，
直到不能再细分为止：
– 将 G分成子组，使得 P,Q在一组当且仅当对于任何的输入符号，他们的后继都属于同一个小组。
– 将子组加入到分划中替换 G。
注意：前面发现的不能细分的小组后来可能还可以细分。所以重复步骤 2的时候，需要检验所有的组，包括老的和新加入的。
DFA化简（例子）
图 3-9(b)
{4},{0,1,2,3}
{4},{0,1,2},{3}
{4},{0,2},{1},{3}
0,2 1
3 4
DFA化简（例子）
b
a
b
b
a
a
b
a
a
a
b
b
b
a
b
a b
1 3 4
2
0 a
0,2
1
3
4
正则表达式
引入的原因,
– 词法规则简单，容易理解
– 更加容易构造识别程序
– 可以用于一些信息流的处理正则表达式的定义 (语法 )
字母表?上的正则表达式的定义如下：
–?与?都是?上的正则表达式。
–?中的 a是正则表达式。
– 如果 e1和 e2是?上的正则表达式，则 (e1)，
e1|e2，和 {e1}都是?上的正则表达式。
例如,?1={0,1}，那么 (0|1){0|1}就是?1
上的正则表达式。
正则表达式的定义 (语义 )
定义 3.12 正则表达式 e的值是字母表上的正则集合，用 |e| 表示。
– |? | =? |? | =?
– |a| = {a} |(e)| = |e|
– |e1e2| = {xy | x?|e1|,y?|e2|}
– |e1|e2| = |e1|? |e2|
– |{e}| = |e|*
正则表达式的等价
定义：如果两个表达式的正则集合相同，
称这两个表达式等价。
例子：
– b{ab}={ba}b
– {a|b}={{a}{b}}
正则表达式的性质
零正则表达式?：
– e|? =?|e= e e? =?e =?
单位正则表达式：
–? e = e? = e
交换律,e1|e2= e2|e1
结合律：
– e1|(e2|e3)=(e1|e2)|e3 e1(e2e3)=(e1e2)e3
分配律：
– e1 (e2|e3) = e1e2|e1e3 (e1|e2)e3=e1e3|e2e3
正则表达式与有穷状态自动机
正则表达式和有穷自动机的表达能力是相同的。具体表现在：
– 给定一个正则表达式，可以构造出相应的有穷自动机。该自动机接受的符号串的集合恰巧是正则表达式的值
– 给定一个有穷状态自动机，可以构造出相应的正则表达式。该正则表达式的值恰巧是该自动机接受的符号串的集合从正则表达式到自动机
步骤 1：从正则表达式到转换系统。
步骤 2：从转换系统到状态转换图。
步骤 3：从状态转换图到 NFA。
步骤 4：从 NFA到 DFA。
其中，步骤 3和步骤 4的算法已经讲过。
下面讲步骤 1和步骤 2。
从正则表达式到转换系统
根据正则表达式的语法，使用自顶向下的构造方法。
基本部分：
s z
s z?
a s za
s z
从正则表达式到转换系统
结构部分：
s ze1e2 s e1 ze2
s ze1|e2 s
e1
e2
s z{e} s? z?
e
从正则表达式到自动机
具体步骤：对于任意的一个正则表达式 e，
从开始，按照结构部分的规则分解，最终可以得到一个转换系统。对于引入的每一个新状态，应该赋予一个独有的名字。
s ze
例子
e = (A|B){A|B|0|1}
s ze1
s zA|B2 z{A|B|0|1}
s
A
3 z
A|B|0|1
B
从转换系统到状态转换图
关键是消去系统中的空弧。
基本思想：
– 如果存在一个空弧构成的圈，那么圈中的所有节点等价，可合并。
– 对于任何一个如下的组合,A-?->B-a->C，
取代以 A-a-->C。
消空弧算法
步骤 1：从某个有空弧射出的状态开始，
沿空弧前进，试图找到再没有空弧射出状态。若能找到，执行步骤 2，否则到步骤 3。
步骤 2：设没有空弧射出的节点为 B，而
A有空弧到 B。删除该空弧。对于 B到 C的非空弧，添加同样的 A到 C的弧。
步骤 3：此时必然存在一个空弧圈，将圈中的节点合并得到新的节点。所有进入该圈的边都有相应到该点的边，所有离开该点的边都有相应离开该点的边。
消空弧算法 (例子 )
b,?
a
a
S Z
B
B1
B2
A
B
Z
b
b
a
a
a
A
B
Z
b,?
b
a
a
b,?
a
a,?
S Z
B
例子 3.16
{a}|{(a|b)a}
A B{a}|{(a|b)a} A B
{a}
{(a|b)a}
A B
a
(a|b)a
A B
a
a|b
c
从自动机到正则表达式
首先获得一个转换系统。然后逐次按照以下规则消除节点，直到只剩下开始状态和接受状态。此时，唯一的边上的标记就是所要的表达式。
e1
e2
e1|e2
e1
e2 e4
e3
e5 e1{e5}e3
e2{e5}e4
e1{e5}e4
e2{e5}e3
从自动机到正则表达式
在按照第二步骤进行处理时
– 只能删除非接受状态和非开始状态的节点。
– 对于所删除的节点，每个射入的弧和每个射出的弧要一一配对。每对这样的弧要对应一个新的弧。
最后得到的扩展自动机为：有一个开始状态，一个接受状态。两个状态之间只有一条边。
由正则文法直接构造表达式
使用联立方程的方法。
对于 A=A(x1+x2+…+xm)+(y1+y2+…+yn)
的情况，
A= (y1+y2+…+yn){(x1+x2+…+xm)}
然后，逐次将解得到的值代入。
直接构造表达式（例子）
S::=Sc|Bc B::=Bb|Ab A::=Aa|a
S = Sc+Bc B=Bb+Ab A=Aa+a
A=a{a}
B=Bb+a{a}b => B=a{a}b{b}
S=Sc+ a{a}b{b}c => S= a{a}b{b}c{c}
直接构造表达式（例子 2）
Z::=Z0|T1|1|0 T::=Z0|0
(1)Z=Z0+T1+1+0 (2)T=Z0+0
(2)->(1) Z=Z0+Z01+01+1+0
Z=Z(0+01)+(01+1+0)
Z=(01|1|0){(0|01)}
词法分析程序的实现
属性字的一般结构,
– 符号类,符号值
– 要求不同的符号值有唯一的表示，一般要求有同样的长度。
词法分析程序分成处理源程序说明和不处理源程序说明两个类型。两种情况下的属性字有所不同。
不处理说明部分时
词法分析工作相对简单，不需要让说明信息和标识符相联系，属性字结构简单。
属性字由符号类和符号值组成。
– 特定符号类中，一类符号只有一个值，因此，属性字中符号值部分是不使用的。
– 非特定符号类中，一个类包含多个符号。比如：
标识符，常整数等。这些类型的符号的属性字中的属性值部分需要加入值。
– 由于属性字是等长的，所以，标识符的值不能直接加入到属性字中，一般使用标识符的编号。
符号类的编码
对于特定的语言，我们可以根据情况总结出相应的符号类别。在表 3-4中，有符号类的编号（不需要记住）。
属性字序列例子
PROGRAM exp
VAR x,AB,C,integer;
BEGIN
x:=(AB+C**4)/8
END
24‘PROGRAM’
1,’exp’
20,’;’
25,’VAR’
1,’x’
21,’,’
1,’AB’
… …
其它的编码方式
我们可以在属性字中加入一些附加信息以帮助其后的语法分析程序。
这些信息可以包括比如：
– 是否说明符号
– 是否运算符号
– 运算优先级信息
– 其它可以简单表示的信息。
词法分析中使用的数据
字符表：（字母表）列出源程序中所有可能的字符。
特定符号与机内表示表：一切特定符号与相应编码。
标识符表：登录一切源程序中出现的一切标识符。此表的序号作为属性字的值。
常数表：登录一切源程序中出现的常数。
此表的序号作为属性字的值。
处理说明部分时
处理说明部分的时候，不仅仅要识别出各个符号，而且要将标识符与类型等信息相联系。
对于非特定符号的属性字，其结构大致如下,0 | 种类 | 特征 | 符号值
一般来将，一个标识符可以是：常量，简单变量，数组，记录等等。我们需要将这些信息记录在属性字的种类或特征中。
书中的表示方法不需要硬记，但是可以借鉴（如果你真的写编译程序的话）
标识符的处理
如果词法分析处理程序的说明的话，标识符的处理比较复杂，主要要考虑到如下问题：
– 定义性出现与使用性出现
– 标识符的作用域
– 标识符符号值的确定定义性出现与使用性出现
在第一次扫描到一个标识符的时候，需要为这个标识符构造属性字。此后遇到这个标识符的时候，只需要复制这个标识符就可以了。
定义性出现时：为标识符构造属性字。
使用性出现时：查找标识符的属性字并进行复制。
定义性出现与使用性出现
定义性出现：当源程序中某标识符在说明部分被首次说明而与类型等属性相关联时，成为该标识符的定义性出现。
不是定义性出现的都是标识符的使用性出现。
并不是标识符出现在说明部分的时候都是定义性出现。
例子 3.21
标识符表在 P87表 3-8中。表中的属性字的符号值部分直接写了符号本身。实际上将是关于此标识符的信息，比如,A的属性字将表示其数组的信息（维数，上界 … )
表 3-9中列出了程序对应的符号属性字序列。但是其中没有说明部分。因为说明部分的信息已经包含在属性字中。
标识符的作用域
一般的现在程序设计语言都有标识符作用域的规定。 PASCAL,C中有局部变量，
C++中还有类的成员变量。
当相同拼写的标识符在内层被重新定义的时候，内外层的标识符被认为是不同的。并且，在内层的使用性说明以内层的为准。
标识符的作用域（处理方法）
在开始扫描的时候，设置标识符栈为空，
包含一个间隔标记。初始时刻最外层为当前层。
碰到标识符的定义性出现的时候，构造属性字，下推入栈。
进入新的层次的时候，（ C中为 {)将一个间隔入栈。
碰到层次结束标记的时候，退栈直到将最上层的间隔。
标识符的作用域（处理方法续）
当碰到标识符的使用性出现的时候，从栈顶往下查找标识符。首先查找到的标识符记录中相应的属性字就是该标识符的属性字。如果直到栈底都没有找到，
则表示程序出错。
按照上述的法则扫描程序，直到源程序扫描完毕。
标识符的作用域（例子）
P88页程序。
对于函数或过程的说明中，
注意函数名的标识符,以及参数标识符的层次。
间隔
exp2
x
y
f1
间隔
p1
s
间隔
exp2
x
y
f1
间隔
exp2
x
y
f1
f2
间隔
p2
…
标识符的作用域（例子）
在语法和语义分析阶段都要使用标识符表的信息。
所以，上述的退栈是有问题的。
具体实现的时候可以建立树型结构来记录这些标识符的作用域。
间隔
exp2
x
y
f1
p1
s
f2
s
z
x
p2
f21t
标识符属性字的确定
不处理说明的情况：属性字中的符号值就是标识符表中的序号。标识符的类型等信息在语义分析阶段获得。
处理说明的情况：词法分析输出的属性字序列部分没有程序说明部分。此时：
– 简单变量：在属性字中编码表示。
– 常量：符号值用常量表序号表示。
– 其它类型：以相应信息表序号表示。
词法分析程序的结构
取字符子程序
取符号子程序，一般有如下约定：
– 进入子程序时，已经取到当前符号的一个字符。
– 离开子程序时，已经取到其后继字符。
查造标识符表子程序
查造常量表子程序
查符号机内表示对照表子程序词法分析程序的自动生成（ Lex)
Lex是 Unix(Linux)系统中的一个实用程序。
Lex的输入称为 Lex程序，主要定义了一些词法规则。 Lex程序的输出是一个可以识别这些单词的 C语言子过程。
输入分成说明，规则，和辅助过程三个部分。
– 说明：用正则表达式定义了词法规则。
– 翻译规则：表示了当程序识别到一个词型时所需要完成的动作。
– 辅助过程用 C语言书写了一些过程，被识别过程调用。
(第三章,词法分析 )
南京大学计算机系赵建华词法分析与词法分析程序
词法分析的任务是识别源程序中具有独立含义的最小语法单位 ----符号或单词,如标识符，无正负号常数与界限符等。并把源程序转换为等价的内部表示形式。
功能：
– 读入源程序字符串；识别单词（符号）；
– 转换成属性字；
– 一些其他的简单工作：删除注解，预加工处理符号识别和重写规则
规则例子：
– <标志符 >,:= 字母 | <标识符 >字母 | …
– 在上面的例子中，实际可以展开为 <标识符 >,:=
a | b | c | d |…
如果我们规定终结符号的集合为字符，那么我们会发现上面的规则都满足正则文法的规则限制,U::=T | UT。因此，我们可以使用有限自动机来辅助完成词法分析。
实现方式
完全融合：由于正则文法是 CFG的一种特例。所以，可以把词法规则和语法规则统一处理。
相对独立：词法分析作为子程序。当语法分析程序需要读下一个符号的时候，
调用这个子程序。
完全独立：词法分析程序作为单独的一趟来实现。
状态转换图与转换系统
识别标志符程序的程序的流程图见图 3-1；
在流程图中的每个边上的操作一般都是判断输入符号是否满足等于某些值。如果不等于，那么识别失败。
实际上，这样的流程图是一种模式。
我们可以把流程图简化为一个状态转换图。状态转换图的运行由输入驱动。状态转换图包括状态，联接状态的边。有些状态是接收状态，每条边都标记了一个符号。
转换图的运行和接受
转换图在运行的时候，由一个当前的状态。每次输入一个符号的时候，转换图的状态改变如下：沿着从当前状态离开的，并且用输入符号标记的边，到达这个边的目标状态。
一个符号串被状态转换图接受当且仅当从初始状态出发，逐次输入符号串中的所有符号的时候，最终的状态是接受状态。
从文法构造状态转换图
我们可以给每个正则文法构造一个状态转换图。
其基本思想如下：
– 当我们使用自底向上的方式规约一个正则文法的句子的时候，得到的句型都是形如
Utx(tx为终结符号串 )。而下次规约的规则总是满足 V::=Ut。如果我们把非终结符号作为状态，而把 tx看作尚未读入的部分时，就得到一个状态转换图。 P61图 3-4。
从文法构造状态转换图 (算法 )
步骤一：引入一个开支状态 S（假定 S不是非终结符号。
步骤二：每个非终结符号作为一个结点。
步骤三：
– Q::=T：从 S到 Q有一条标记为 T的弧。
– Q::=RT：从 R到 Q有一条标记为 T的弧。
识别符号为接受状态。
从文法构造状态转换图 (例子 )
S
A
B
Z
Z,:= Za | Aa | Bb
A::= Ba | a
B,:= Ab | b
使用状态转换图构造正则文法
从构造步骤来看，正则文法和状态转换图之间具有一种对应关系。
状态转换图具有直观的特点，所以给定一个正则语言，构造状态转化图比较方便。
构造正则文法 (例子 )
例子,{(ab)nb2 | n>=0}
S
转换系统
定义：转换系统是具有下列特征的状态转换图：
– 只有唯一的开始状态 S和唯一的终止状态 Z；
– 没有弧进入 S，也没有离开 Z
– 可能有空弧。
S
S2
I
S1 Z
1
Z2
Z
转换系统
定理 3.2 对于任何一个状态图，都存在一个相应的转换系统，它们接受同样的语言。
转换系统对于从正则表达式转换到状态转换图起到了中间表示的作用。
DFA的定义
有穷状态自动机是对状态转换图的一种形式化定义。
定义：一个 DFA是 (K,?,M,S,F)
– K 有穷非空状态集合
–? 有穷的输入字母表集合
– M 从 K?M到 K的映射。
– S 是 K中的一个状态，称为开始状态。
– F K的子集，称为终止状态集合。
DFA的例子
({S,Z,A,B},{a,b},M,S,{Z})；
其中
– M(S,a) = A M(S,b) = B
– M(A,a) = Z M(A,b) = B
– M(B,a) = A M(B,b) = Z
– M(Z,a) = Z
S
A
B
Z
a
b
a b
a
b
a
运行 DFA
扩充后的映射 M的定义：
– M(R,?) = R 表示一定要有输入符号后，
DFA的状态才可能改变。
– M(R,Tt)=M(M(R,T),t) 表示状态的改变是从左到右进行的。
定义：字符串 t被 DFA接受当且仅当 M(S,t)
在 F中。
DFA接受的符号串集合
定义,(D)FA所能够接受的所有字符串的集合写成 L(D),L(D)是正则集合，。
定理 3.3 设 G为正则文法，如果 x数据 L(G)，
那么它能被 G相应的有穷自动机所接受。
定理 3.4 接受正则语言 L的最小状态自动机不记同构是唯一的。
非确定有穷状态自动机 NFA
在前面的从正则文法构造 FA的例子中，
恰好从一个状态射出的弧的标记是两两不同的。但是，如果有两个规则 V::=UT
和 W::=UT，那么从 U到 V和 W的弧的标记都是 T。
此时，不能用 DFA的映射来表示状态为 U
时，输入 T时的后继状态。也就是说，当状态为 U，输入为 T时，这个转换图的下一步动作出现了不确定性。这个状态转换图不再是 DFA。
不确定状态转换图的例子
Z::= Za | Aa | Bb
A::= Ba | Za | a
B::=Ab | Ba | b S
A
B
Z
a
b
a b
a
b
a
a
a
NFA的定义
定义：一个 DFA是 (K,?,M,S,F)
– K 有穷非空状态集合
–? 有穷的输入字母表集合
– M 从 K?M到 K的超集的映射。
– S 是 K的子集，称为开始状态集合。
– F K的子集，称为终止状态集合。
NFA和 DFA的不同在于,
– M的值域是 K的超集。
– 开始状态有不止一个
NFA的例子
({S,A,B,Z},{a,b},M,{S},{Z})
M：
– M(S,a)={Z} M(S,b)={B}
– M(A,a)={Z} M(A,b)={B}
– M(B,a)={A,B} M(B,b)={Z}
– M(Z,a)={A,Z} M(Z,b)={}
S
A
B
Z
a
b
a b
a
b
a
a
a
运行 NFA
扩充的影响 M
– M({R1,R2,…,R n,},T) =?iM(Ri,T)
– M(Q,?) = Q 表示一定要有输入符号后，
NFA的状态才可能改变。
– M(Q,Tt)=M(M(Q,T),t) 表示状态的改变是从左到右逐个进行的。
M(Q,x)表示当输入符号串为 x的时候，所有可能的最后状态。
NFA接受的语言
对于某个输入符号串 x，如果 M(S,x)?F非空，那么我们就说 x被该 NFA接受。
直观地讲,x被一个 NFA接受表示从某个开始状态，按照某种选择，可以到达某个接受状态。表 3-2。
定理 3.5：对于任何一个正则文法 G，都存在一个 NFA A，使得 L(G)=L(A)。反之亦然。
从 NFA到 DFA
使用 NFA判定某个输入符号串的时候，可能出现不确定的情况：不知道下面选择那个状态。如果选择不好，该输入符号串可能不能到达终止状态。但是，我们不能说该输入符号串不能被该 NFA接受。
如果通过尝试的方法，不断试探来确定输入符号串是否可被接受，那么判定的效率将降低。解决的方法是将 NFA转换为等价的 DFA。
从 NFA到 DFA
定理 3.6 对于给定的 NFA (K,?,M,S,F)，
可以构造一个等价的 DFA (K’,?,M’,S’,F’)
如下：
– K’中的状态一一对应于 K的子集。和子集
{Q1,Q2,…,Q n}对应的状态为 [Q1,Q2,…,Q n]
– M’([Q1,Q2,…,Q n],T) = 对应于?iM(Qi,T)的状态。
– S’为 S
– F’为对应于所有与 F相交的子集的状态。
从 NFA到 DFA
例子 3.7
由于 K的子集的个数为 K的个数的指数个，
所以以上面的方法得到的状态非常多。
实际上不是所有的子集都可以到达的。
可以使用列表法来完成 DFA的构造。从开始状态起，只有可以达到的状态才构造其后继。
自动机的等价
定义 3.8：如果 L(A)=L(A’)，那么我们说
A和 A’等价。
定理 3.8：存在判定两个自动机是否等价的算法。
确定自动机的等价
两个等价的 DFA
的状态个数可能不同。 DFA可以进行化简。化简不仅是去除死状态，不可能到达状态，还包括状态的合并。
a
a
b
b
b
a
b
a b
1 3 4
2
0
b
a
b
a
b
a
b
a
0
1
2
3
自动机状态的区分与等价
定义 3.9 如果从 P开始输入 w使得结束时候的状态的终止状态。从 Q开始输入 w时，结束的状态为非终止状态（或无状态），那么我们说 w把 P和 Q区分开来。
定义 3.10 不可区分的两个状态成为等价的状态。
空串把终止状态和非终止状态区分开来。
显然，如果 P,Q等价，那么 P和 Q对于同一个符号的后继也等价。
DFA化简
步骤 1：将 DFA的状态分为互不相交的子集，
使得每个子集中的状态等价（见分划算法）。
步骤 2：每个子集中选取一个状态作为子集中所有状态的代表，其余删除。这些代表构成了化简后的自动机的状态集合。对于原有的状态 P和 Q,如果有 P到 Q的一个标记为 T的边，
那么有从 P的代表到 Q的代表有一个标记为 T
的弧（有可能是圈）。
步骤 3：删除死状态和无用状态。
DFA化简
得到的状态转换图仍然是 DFA吗？为什么？
开始状态为包含有开始状态的子集的代表。
原来为终止状态的，现在仍然是终止状态。
DFA化简（分划算法）
步骤 1：初始分划：终止状态和非终止状态。
步骤 2：重复对于每一组 G都进行下列细分，
直到不能再细分为止：
– 将 G分成子组，使得 P,Q在一组当且仅当对于任何的输入符号，他们的后继都属于同一个小组。
– 将子组加入到分划中替换 G。
注意：前面发现的不能细分的小组后来可能还可以细分。所以重复步骤 2的时候，需要检验所有的组，包括老的和新加入的。
DFA化简（例子）
图 3-9(b)
{4},{0,1,2,3}
{4},{0,1,2},{3}
{4},{0,2},{1},{3}
0,2 1
3 4
DFA化简（例子）
b
a
b
b
a
a
b
a
a
a
b
b
b
a
b
a b
1 3 4
2
0 a
0,2
1
3
4
正则表达式
引入的原因,
– 词法规则简单，容易理解
– 更加容易构造识别程序
– 可以用于一些信息流的处理正则表达式的定义 (语法 )
字母表?上的正则表达式的定义如下：
–?与?都是?上的正则表达式。
–?中的 a是正则表达式。
– 如果 e1和 e2是?上的正则表达式，则 (e1)，
e1|e2，和 {e1}都是?上的正则表达式。
例如,?1={0,1}，那么 (0|1){0|1}就是?1
上的正则表达式。
正则表达式的定义 (语义 )
定义 3.12 正则表达式 e的值是字母表上的正则集合，用 |e| 表示。
– |? | =? |? | =?
– |a| = {a} |(e)| = |e|
– |e1e2| = {xy | x?|e1|,y?|e2|}
– |e1|e2| = |e1|? |e2|
– |{e}| = |e|*
正则表达式的等价
定义：如果两个表达式的正则集合相同，
称这两个表达式等价。
例子：
– b{ab}={ba}b
– {a|b}={{a}{b}}
正则表达式的性质
零正则表达式?：
– e|? =?|e= e e? =?e =?
单位正则表达式：
–? e = e? = e
交换律,e1|e2= e2|e1
结合律：
– e1|(e2|e3)=(e1|e2)|e3 e1(e2e3)=(e1e2)e3
分配律：
– e1 (e2|e3) = e1e2|e1e3 (e1|e2)e3=e1e3|e2e3
正则表达式与有穷状态自动机
正则表达式和有穷自动机的表达能力是相同的。具体表现在：
– 给定一个正则表达式，可以构造出相应的有穷自动机。该自动机接受的符号串的集合恰巧是正则表达式的值
– 给定一个有穷状态自动机，可以构造出相应的正则表达式。该正则表达式的值恰巧是该自动机接受的符号串的集合从正则表达式到自动机
步骤 1：从正则表达式到转换系统。
步骤 2：从转换系统到状态转换图。
步骤 3：从状态转换图到 NFA。
步骤 4：从 NFA到 DFA。
其中，步骤 3和步骤 4的算法已经讲过。
下面讲步骤 1和步骤 2。
从正则表达式到转换系统
根据正则表达式的语法，使用自顶向下的构造方法。
基本部分：
s z
s z?
a s za
s z
从正则表达式到转换系统
结构部分：
s ze1e2 s e1 ze2
s ze1|e2 s
e1
e2
s z{e} s? z?
e
从正则表达式到自动机
具体步骤：对于任意的一个正则表达式 e，
从开始，按照结构部分的规则分解，最终可以得到一个转换系统。对于引入的每一个新状态，应该赋予一个独有的名字。
s ze
例子
e = (A|B){A|B|0|1}
s ze1
s zA|B2 z{A|B|0|1}
s
A
3 z
A|B|0|1
B
从转换系统到状态转换图
关键是消去系统中的空弧。
基本思想：
– 如果存在一个空弧构成的圈，那么圈中的所有节点等价，可合并。
– 对于任何一个如下的组合,A-?->B-a->C，
取代以 A-a-->C。
消空弧算法
步骤 1：从某个有空弧射出的状态开始，
沿空弧前进，试图找到再没有空弧射出状态。若能找到，执行步骤 2，否则到步骤 3。
步骤 2：设没有空弧射出的节点为 B，而
A有空弧到 B。删除该空弧。对于 B到 C的非空弧，添加同样的 A到 C的弧。
步骤 3：此时必然存在一个空弧圈，将圈中的节点合并得到新的节点。所有进入该圈的边都有相应到该点的边，所有离开该点的边都有相应离开该点的边。
消空弧算法 (例子 )
b,?
a
a
S Z
B
B1
B2
A
B
Z
b
b
a
a
a
A
B
Z
b,?
b
a
a
b,?
a
a,?
S Z
B
例子 3.16
{a}|{(a|b)a}
A B{a}|{(a|b)a} A B
{a}
{(a|b)a}
A B
a
(a|b)a
A B
a
a|b
c
从自动机到正则表达式
首先获得一个转换系统。然后逐次按照以下规则消除节点，直到只剩下开始状态和接受状态。此时，唯一的边上的标记就是所要的表达式。
e1
e2
e1|e2
e1
e2 e4
e3
e5 e1{e5}e3
e2{e5}e4
e1{e5}e4
e2{e5}e3
从自动机到正则表达式
在按照第二步骤进行处理时
– 只能删除非接受状态和非开始状态的节点。
– 对于所删除的节点，每个射入的弧和每个射出的弧要一一配对。每对这样的弧要对应一个新的弧。
最后得到的扩展自动机为：有一个开始状态，一个接受状态。两个状态之间只有一条边。
由正则文法直接构造表达式
使用联立方程的方法。
对于 A=A(x1+x2+…+xm)+(y1+y2+…+yn)
的情况，
A= (y1+y2+…+yn){(x1+x2+…+xm)}
然后，逐次将解得到的值代入。
直接构造表达式（例子）
S::=Sc|Bc B::=Bb|Ab A::=Aa|a
S = Sc+Bc B=Bb+Ab A=Aa+a
A=a{a}
B=Bb+a{a}b => B=a{a}b{b}
S=Sc+ a{a}b{b}c => S= a{a}b{b}c{c}
直接构造表达式（例子 2）
Z::=Z0|T1|1|0 T::=Z0|0
(1)Z=Z0+T1+1+0 (2)T=Z0+0
(2)->(1) Z=Z0+Z01+01+1+0
Z=Z(0+01)+(01+1+0)
Z=(01|1|0){(0|01)}
词法分析程序的实现
属性字的一般结构,
– 符号类,符号值
– 要求不同的符号值有唯一的表示，一般要求有同样的长度。
词法分析程序分成处理源程序说明和不处理源程序说明两个类型。两种情况下的属性字有所不同。
不处理说明部分时
词法分析工作相对简单，不需要让说明信息和标识符相联系，属性字结构简单。
属性字由符号类和符号值组成。
– 特定符号类中，一类符号只有一个值，因此，属性字中符号值部分是不使用的。
– 非特定符号类中，一个类包含多个符号。比如：
标识符，常整数等。这些类型的符号的属性字中的属性值部分需要加入值。
– 由于属性字是等长的，所以，标识符的值不能直接加入到属性字中，一般使用标识符的编号。
符号类的编码
对于特定的语言，我们可以根据情况总结出相应的符号类别。在表 3-4中，有符号类的编号（不需要记住）。
属性字序列例子
PROGRAM exp
VAR x,AB,C,integer;
BEGIN
x:=(AB+C**4)/8
END
24‘PROGRAM’
1,’exp’
20,’;’
25,’VAR’
1,’x’
21,’,’
1,’AB’
… …
其它的编码方式
我们可以在属性字中加入一些附加信息以帮助其后的语法分析程序。
这些信息可以包括比如：
– 是否说明符号
– 是否运算符号
– 运算优先级信息
– 其它可以简单表示的信息。
词法分析中使用的数据
字符表：（字母表）列出源程序中所有可能的字符。
特定符号与机内表示表：一切特定符号与相应编码。
标识符表：登录一切源程序中出现的一切标识符。此表的序号作为属性字的值。
常数表：登录一切源程序中出现的常数。
此表的序号作为属性字的值。
处理说明部分时
处理说明部分的时候，不仅仅要识别出各个符号，而且要将标识符与类型等信息相联系。
对于非特定符号的属性字，其结构大致如下,0 | 种类 | 特征 | 符号值
一般来将，一个标识符可以是：常量，简单变量，数组，记录等等。我们需要将这些信息记录在属性字的种类或特征中。
书中的表示方法不需要硬记，但是可以借鉴（如果你真的写编译程序的话）
标识符的处理
如果词法分析处理程序的说明的话，标识符的处理比较复杂，主要要考虑到如下问题：
– 定义性出现与使用性出现
– 标识符的作用域
– 标识符符号值的确定定义性出现与使用性出现
在第一次扫描到一个标识符的时候，需要为这个标识符构造属性字。此后遇到这个标识符的时候，只需要复制这个标识符就可以了。
定义性出现时：为标识符构造属性字。
使用性出现时：查找标识符的属性字并进行复制。
定义性出现与使用性出现
定义性出现：当源程序中某标识符在说明部分被首次说明而与类型等属性相关联时，成为该标识符的定义性出现。
不是定义性出现的都是标识符的使用性出现。
并不是标识符出现在说明部分的时候都是定义性出现。
例子 3.21
标识符表在 P87表 3-8中。表中的属性字的符号值部分直接写了符号本身。实际上将是关于此标识符的信息，比如,A的属性字将表示其数组的信息（维数，上界 … )
表 3-9中列出了程序对应的符号属性字序列。但是其中没有说明部分。因为说明部分的信息已经包含在属性字中。
标识符的作用域
一般的现在程序设计语言都有标识符作用域的规定。 PASCAL,C中有局部变量，
C++中还有类的成员变量。
当相同拼写的标识符在内层被重新定义的时候，内外层的标识符被认为是不同的。并且，在内层的使用性说明以内层的为准。
标识符的作用域（处理方法）
在开始扫描的时候，设置标识符栈为空，
包含一个间隔标记。初始时刻最外层为当前层。
碰到标识符的定义性出现的时候，构造属性字，下推入栈。
进入新的层次的时候，（ C中为 {)将一个间隔入栈。
碰到层次结束标记的时候，退栈直到将最上层的间隔。
标识符的作用域（处理方法续）
当碰到标识符的使用性出现的时候，从栈顶往下查找标识符。首先查找到的标识符记录中相应的属性字就是该标识符的属性字。如果直到栈底都没有找到，
则表示程序出错。
按照上述的法则扫描程序，直到源程序扫描完毕。
标识符的作用域（例子）
P88页程序。
对于函数或过程的说明中，
注意函数名的标识符,以及参数标识符的层次。
间隔
exp2
x
y
f1
间隔
p1
s
间隔
exp2
x
y
f1
间隔
exp2
x
y
f1
f2
间隔
p2
…
标识符的作用域（例子）
在语法和语义分析阶段都要使用标识符表的信息。
所以，上述的退栈是有问题的。
具体实现的时候可以建立树型结构来记录这些标识符的作用域。
间隔
exp2
x
y
f1
p1
s
f2
s
z
x
p2
f21t
标识符属性字的确定
不处理说明的情况：属性字中的符号值就是标识符表中的序号。标识符的类型等信息在语义分析阶段获得。
处理说明的情况：词法分析输出的属性字序列部分没有程序说明部分。此时：
– 简单变量：在属性字中编码表示。
– 常量：符号值用常量表序号表示。
– 其它类型：以相应信息表序号表示。
词法分析程序的结构
取字符子程序
取符号子程序，一般有如下约定：
– 进入子程序时，已经取到当前符号的一个字符。
– 离开子程序时，已经取到其后继字符。
查造标识符表子程序
查造常量表子程序
查符号机内表示对照表子程序词法分析程序的自动生成（ Lex)
Lex是 Unix(Linux)系统中的一个实用程序。
Lex的输入称为 Lex程序，主要定义了一些词法规则。 Lex程序的输出是一个可以识别这些单词的 C语言子过程。
输入分成说明，规则，和辅助过程三个部分。
– 说明：用正则表达式定义了词法规则。
– 翻译规则：表示了当程序识别到一个词型时所需要完成的动作。
– 辅助过程用 C语言书写了一些过程，被识别过程调用。
