编译原理第三章

编译原理电子教案第三章词法分析（lexicalanalysis）谢强计算机科学与技术学ieqiang@.con2本章的主要内容词法分析器的设计要求状态转换图正规表达式有限自动机正规式、正规文法、有限自动机的等价性确定有限自动机的化简词法分析器的自动产生（了解）3本章要求知识点：词法分析程序的功能及构造方法，正规表达式与正规集，正规表达式与正规文法，状态转换图与基本符号的识别，有限自动机。深刻理解：正规表达式，有限自动机，正规文法以及三者之间的等价性；确定的有限自动机和非确定的有限自动机之间的等价性。熟练掌握：（1）对于某一正规集，写出其正规表达式，构造其非确定的有限自动机、确定的有限自动机，并将其最小化；（2）对于某一正规集，写出正规表达式，构造自动机，然后构造正规文法。4本章教学线索1词法分析程序的设计1.1词法分析程序的功能1.2词法分析程序作为一个独立子程序2词法分析器的设计3状态转换图4正规表达式与有限自动机5确定有限自动机的化简6词法分析程序的自动构造工具LEX简介51.1词法分析程序的功能

词法分析的任务：从左到右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。词法分析器源程序单词符号6单词符号关键字、标识符、常数、（运）算符、界符；词法分析器输出单词符号的表示

（单词种别，单词符号的属性值）单词种别通常用整数编码。词类编码提供给语法分析程序使用；单词自身的属性值提供给语义分析程序使用。具体的分类设计以方便语法分析程序使用为原则。单词分种策略标识符一般统规为一种；常数则宜按类型（整、实、布尔等）分种；关键字可以将全体视为一种，也可以一字一种；运算符可采用一字一种，一个将具有共性的运算符视为一种。界符一般采用一字一种。71.2词法分析程序作为一个独立子程序（1）语法分析程序的子程序；（2）组织成一遍扫描。（为什么？）复杂问题分解，模块化设计，使得整个编译程序的结构更简洁、清晰。由于词法分析程序相对于语法分析程序来说要简单得多，如果把词法分析和语法分析合在一起将会导致语法分析程序变得非常复杂，并且使编译程序的执行效率变得很低。8词法分析语法分析语义分析和中间代码生成源程序中间代码符号表管理错误的诊查处理9whilei＜＞jdoifi＞jthen

i:＝i-jelsej:=j-i‘while’，‘i’，‘＜＞’，‘j’，‘do’，‘if’，‘i’，‘＞’，‘j’,‘then’,'i',':=’,'i',’-’,'j','else','j',':=','j','-',‘i'词法分析器〈while，——〉〈id，指向i的符号表入口的指针〉〈relational－op，NE〉〈id，指向j的符号表入口的指针〉〈do，——〉〈if，——〉〈id，指向i的符号表入口的指针〉〈id，指向j的符号表入口的指针〉例子：10本章教学线索1词法分析程序的设计2词法分析器的设计2.1输入、输出预处理2.2单词符号的识别（P40—41）3状态转换图4正规表达式与有限自动机5确定有限自动机的化简6词法分析程序的自动构造工具LEX简介112.1输入、输出预处理（1）去除掉空白符、跳格符、回车符和换行符等编辑性字符；（2）去除程序中的注释符；（3）扫描缓冲区122.2单词符号的识别（P40—41）超前搜索问题关键字的识别标识符的识别常数的识别算符和界符的识别13本章教学线索1词法分析程序的设计2词法分析器的设计3状态转换图3.1状态转换图的概念3.2构造识别一种简单语言的单词符号的转换图4正规表达式与有限自动机5确定有限自动机的化简6词法分析程序的自动构造工具LEX简介143.1状态转换图的概念状态转换图是一张有限方向图，在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符、正规式）代表在射出结点（即箭符始结点）状态下可能出现的输入字符或字符类。一张状态转换图只包含有限个状态（即有限个结点），其中含有一个初态（用双线箭头指示）和若干个终态（用双圈表示），而且实际上至少要有一个终态，初态表示分析的开始，终态表示分析的结束。一个状态转换图可用于识别（或接受）一定的字符串。15012*字母其它字母或数字图A—识别标识符的转换图012*数字其它图B—识别整数的转换图数字017*其它图C—识别Fortran实型常数的转换图23456数字数字数字其它+或-E或D数字E或D··数字数字数字163.2构造识别一种简单语言的单词符号的转换图限制条件：（1）所有关键字都是“保留字”，用户不得使用它们作为自己定义的标识符。（2）关键字作为一类特殊的标识符来处理，不再专门设置对应的转换图，把它们预先安排在一张表格中，当转换图识别出一个标识符，就去查询这张表，确定是否为一个关键字。（3）如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔2**38*121311非*空白字母非字母与数字字母或数字数字数字非数字=+*...，（）其它1819本章教学线索1词法分析程序的设计2词法分析器的设计3状态转换图4正规表达式与有限自动机4.1正规式与正规集4.2确定有限自动机（DFA）4.3非确定有限自动机NFA4.4DFAM和NFAM的等价性4.5正规文法与有限自动机的等价性4.6正规式与有限自动机的等价性5确定有限自动机的化简6词法分析程序的自动构造工具LEX简介204.1正规式与正规集4.1.1正规式与正规集的定义（概念）（1）ε、Φ都是∑上的正规式，它们所表示的正规集分别为{ε}和Φ；（2）任何a∈∑，a是∑上的一个正规式，它所表示的正规集为{a}；（3）如果U、V都是∑上的正规式，它们所表示的正规集分别记为L（U）和L（V），那么，（U|V）、（U*V）和（U）*也是正规式，它们所表示的正规集分别为L（U）∪L（V）、L（U）L（V）和（L（U））*；仅由有限次使用上述步骤而得到的表达式才是∑上的正规式；仅由这些正规式所表示的字集才是∑上的正规集。21例子：令∑={a，b}，下面是∑上的正规式和相应的正规集正规式正规集ba*∑上所有以b为首后跟任意多个a的字a(a|b)*∑上所有以a为首的字（a|b）*

(aa|bb)(a|b)*∑上所有含有两个相继的a或两个相继的b的字224.1.2正规式的数学运算交换律：U|V=V|U；结合律：U|（V|W）=（U|V）|W、U（VM）=（UV）W；分配律：U（V|W）=UV|UW（V|W）|U=VU|WUε连接：εU=Uε=U23另外一种定义方法：定义正规表达式（regularexpression）是以下的一种：基本（basic）正规表达式由一个单字符a（其中a在字母表∑中），以及元字符ε或元字符Φ组成。在第1种情况下，L(a)={a}；在第2种情况下，L(ε)={ε}；在第3种情况下，L(Φ)={}。r|s格式的表达式：其中r和s均是正规式。在这种情况下，L（r|s）=L（r）∪L（s）。rs格式的表达式：其中r和s是正规式。在这种情况下，

L（rs）=L(r)L（s）。r*格式的表达式：其中r是正规表达式。在这种情况下，L（r*）=L（r）*。（r）格式的表达式：其中r是正规式。在这种情况下，L（（r））=L（r），因此，括号并不改变语言，它们只调整运算的优先权。24需要注意：｜的优先权最低，连结次之，*则最高。另外还注意到在这个定义中，5个符号|、*、*、（和）都有了元字符的含义。正规式的连接一般不满足交换律254.2确定有限自动机（DFA）4.2.1确定有限自动机的定义

一个确定有限自动机（DFA）M是一个五元式：M=（S，∑，δ，s0，F），其中：S是一个有限集，它的每个元素称为一个状态；∑是一个有穷字母表，它的每个元素称为一个输入字符；δ是一个从Sx∑至S的单值部分映射。δ（s，a）=s′，意味着：当现行状态为s、输入为字符a时，将状态转换到下一个状态s′。我们称s′为s的一个后继状态。s0∈S，是唯一的初态。FS，是一个终态集（可空）。264.2.2DFA的矩阵表示及状态转换图表示行表示状态列表示输入字符矩阵元素表示δ（s，a）的值。这个矩阵称为状态转换矩阵。例子：M=（{0，1，2，3}，{a，b}，δ，0，{3}）其中δ为：δ(0，a)=1δ(0，b)=2δ(1，a)=3δ(1，b)=2δ(2，a)=1δ(2，b)=3δ(3，a)=3δ(3，b)=327对应的状态转换矩阵：状态ab012132213333一个DFA也可以表示成一张（确定的）状态转换图：δ(0，a)=1δ(0，b)=2δ(1，a)=3δ(1，b)=2δ(2，a)=1δ(2，b)=3δ(3，a)=3δ(3，b)=31023ababa，bab28确定有限自动机（DFA）的三种表示形式1）状态转换函数2）状态转换矩阵3）状态转换图开始状态一般状态终态状态转换图节点的三种形式294.2.3有限自动机DFAM接受的语言从状态转换函数来看：如果对所有α∈Σ*，以下述方式递归扩张δ的定义：δ（s，ε）＝s，δ(s，αa）＝δ（δ（s，α），a）（ａ∈Σ，s∈S），则有Ｌ（Ｍ）＝｛α｜α∈Σ*，若存在s∈Ｆ，使δ（s0，α）＝s｝对上例的DFAM和w=baa，δ（0，baa）=δ（2，aa）=δ(1，a）=3（注意：其中0代表0态，1表示1态，2表示2态，3表示3态）30从状态转换图来看：对于Σ*上的任何字α，如果存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于α，则称α可为DFAM所识别（读出或接受），如果M的初态结点同时又是终态结点，则空字ε可为DFAM所识别。DFAM所能识别的字的全体记为L(M)。课后例子：给出接受下列在字母表{0，1}上的语言的DFA：所有以00结束的串的集合；（1|0）*00所有具有三个0的串的集合。1*01*01*01*314.2.4DFA的程序模拟DFAM=（K，Σ，f，S，Z）的行为的模拟程序K=S；c=getchar;whilec<>eofdo{K=f(K,c);c=getchar;};ifKisinZthenreturn(‘yes’)Elsereturn(‘no’)324.3非确定有限自动机NFA一个非确定有限自动机NFAM是一个五元式：M=(S，Σ，δ，S0，F)其中：S是一个有限集，它的每个元素称为一个状态；∑是一个有穷字母表，它的每个元素称为一个输入字符；δ是一个从Sx∑*至S的子集的映射，即δ：Sx∑*→2s（S集合的幂集/S的所有子集的集合）S0S，是一个非空初态集。FS,是一个终态集（可空）。33对于∑*中的任何一个字α，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略那些标记为ε的弧）等于α，则称α可为NFAM所识别（读出或接受）。若M的某些结点既是初态结点又是终态结点，或者存在一条从初态结点到某一终态结点的ε通路，那么，空字ε可为M所接受。例子：识别所有含有相继两个a或相继两个b的字NFA。5X12346Yaaaabbbbεεεε344.4DFAM和NFAM的等价性定理：对于每个NFAM存在一个DFAM′，使得L(M)=L(M′)证明思想：用M′的一个状态对应M的一个状态集合，用这种方法，能从一个NFAM构造一个DFAM′使得L（M′）=L（M），这种方法称作子集构造法。354.4.1状态集的ε闭包定义设I是有限自动机的状态集的子集，I的ε闭包ε_CLOSURE(I)为：(1)如果状态q∈I，则q∈ε_CLOSURE（I）（既I中的状态全部属于ε_CLOSURE(I)）(2)如果状态q∈I，那么从状态q出发经过任意ε弧而能到达的任何状态q′都属于ε_CLOSURE(I)。（注意：可以连续经过多条ε弧）364.4.2有限自动机的转移函数假定I是非确定有限自动机的状态集的子集，则定义：

Ia=ε_CLOSURE(J)

其中：a∈Σ，J是从I中的某一状态结点出发经过一条a弧而达到的状态结点的全体。

374.4.3从NFAM构造DFAM的步骤（方法）（1）设NFAM=<S，Σ，δ，S0，F>，对M的状态图进行改造：引进新的初态结点X和终态结点Y，且X，Y∉S，从X到S0中任意状态结点连一条ε箭弧，从F中任意状态结点连一条ε箭弧到Y；对M中的状态图进行下图所示的替换，其中k是新引进的状态。重复这种分裂过程直到状态图中的每条箭弧上的标记或为ε，或为Σ中的单个字母。将最终得到的NFA记为M′，显然L（M′）=L（M）ijikjABABijA|BijA*ijAB

ikjεεA38（2）将非确定有限自动机M′转换成确定有限自动机M"

方法：假设Σ={a1，a2，a3，…，ak}，构造状态转化表，表的构成：a)每一行包含k+1列，首行首列为ε_CLOSURE(X)；b)如果每行的第一列假定为I，则该行的i+1列为Iai(i=1，2，…，k)。然后检查该行的所有状态子集，将未曾在第一列出现的填入到后面空行的第一列。c)重复上述b)，直到出现在表的第i+1列上的所有状态子集均在第一列中出现。d)将构造出来的表视为状态转换表，将其中的每个状态子集视为新的状态，显然该表唯一的刻画了一个DFAM"，该有限自动机的初态为该表的首行首列，终态为那些包含原终态的状态子集。显然L(M")=L(M')=L(M)39例子：p50正规式（a|b）*（aa|bb）（a|b）*对应的NFA如例3.3中图。其中X为初态，Y为终态。状态转换矩阵如下表：

IJIaJIb{X,5,1}{5,3}{5,3,1}{5,4}{5,4,1}{5,3,1}{5,3,2}{5,3,1,2,6,Y}{5,4}{5,4,1}{5,4,1}{5,3,1}{5,4,1,2,6,Y}{5,3,1,2,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}{5,4,1,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}X5126Y34εεεεababaabb40转换成状态转换矩阵：（将第一列从上向下编号）

sab0121322153344655656340123564abababababbaba41312ababaBSAbabCaa，baaIaIb{S}{A,C}Φ{A,C}{A,C}{A,B}{A,B}{A,C}{A,B}42a，bSAaa，bbb132babIaIb{S}{S,A}{A}{S,A}{S,A}{S,A}{A}Φ{S,A}43124εbaεεb3cASBccabbIaIbIc{1，2，3，4}{1，2，3，4}{2，4}{3，4}{2，4}Φ{2，4}Φ{3，4}ΦΦ{3，4}444.5正规文法与有限自动机的等价性正规文法与有限自动机的等价性结论：对每个右线性正规文法GR或左线性正规文法GL，都存在一个有限自动机（FA）M，使得：L（M）=L（G）对每一个FAM，都存在一个右线性正规文法GR和左线性正规文法GL，使得：L（M）=L（GR）=L（GL）右线性正规文法：A→αB或A→α,α∈VT*，A，B∈VN左线性正规文法：A→Bα或A→α,α∈VT*，A，B∈VN45证明1：右线性正规文法GR同有限自动机的等价性（1）设右线性正规文法GR=<VT，VN，S，P>。将VN中的每一非终结符号视为状态符号，并增加一个新的终结状态符号f，f∉VN。构造有限自动机M=<VN∪{f}，VT

，δ，S，{f}>，其中状态转换函数δ定义如下：如果对某个A∈VN且a∈VT∪{ε}，P中有产生式A→a，则令δ（A，a）=f。对任意A∈VN且a∈VT∪{ε}，设P中左端为A，右端第一符号为a的所有产生式为：A→aA1|aA2|…|aAk（不包含：A→a）则令：δ（A，a）={A1，A2，…，AK}显然，上述的自动机M为一非确定有限自动机（NFA）（为什么是非确定）。46（2）设左线性正规文法GL=<VT，VN，S，P>，将VN中的每一符号视为状态符号，并且增加一个初态符号q0，q0VN。 令M=<VN∪{q0}，VT，δ，q0，{S}>，其中状态转换函数可以由以下规则定义：若对某个A∈VN及a∈VT∪{ε}，P中有产生式A→a，则令δ（q0，a）=A对任意的A∈VN及a∈VT∪{ε}，若P中所有右端第一符号为A，第二符号为a的产生式为：A1→Aa，A2→Aa，A3→Aa，…，Ak→Aa。则令δ（A，a）={A1，A2,…,Ak}q0AaAA1A2Ak…aaa47证明2：有限自动机同正规文法的等价性设DFAM=<S，Σ，δ，s0，F>，构造右线性正规文法：（1）若s0∉F，令GR=<Σ，S，s0，P>，其中P的产生式集合如下定义：对任何a∈Σ及A，B∈S，若有δ（A，a）=B则：当B∉F时，令A→aB；当B∈F时，令A→a|aB；对于w∈Σ*，不妨设w=a1a2…ak，其中ai∈Σ(i=1,…,k)。若s0w，则存在一个最左推导:s0⇒a1A1⇒

a1a2A2⇒…⇒a1…aiAi⇒…⇒a1a2…ak，因而，在M中有一条从s0出发依次经过A1，…，Ak-1，达到终态的通路，该通路上所有箭弧依次标记为a1，a2，…，ak。反之亦然。所以：w∈L(GR)当且仅当w∈L(M)。48（2）当s0∈F，因为δ(s0，ε)=s0，所以ε∈L(M)。但ε不属于上面构造的GR产生的文法L(GR)。但是：L(GR)=L(M)-{ε}。所以在上面的GR中添加新的非终结符号s0´(s0´∉S)和产生式s0´→s0|ε,并用s0´代替s0作开始符号。这样修正后的文法GR´仍然是右线性正规文法，并且L(GR´)=L(M)。注意：构造左线性正规文法，将终态视为开始符号，P的定义如下：对任何a

及A1，A2VN,有(A1，a)=A2,则

(a)A1是初态，A2a|A1a(b)A1不是初态,A2A1a

如果有多个终态，需要引入新终态，将原来的终态连接到新终态，箭符上的标记符为ε，将新的终态作为左线性正规文法的开始符号，其产生式为f′→f1|f2|…

49综合例子：P52~53

DFAM=<{A,B,C,D},{0,1},δ,A,B>ADBC0,1000111504.6正规式与有限自动机的等价性包含两方面的含义：（1）对于任何有限自动机M，都存在一个正规式r，使得L(r)=L(M)；（2）对于任何正规式r，都存在一个有限自动机M，使得L(M)=L(r)

正规文法、正规式、确定有限自动机和非确定有限自动机在接受语言的能力上是一致的。51证明1：对于Σ上的NFAM，构造Σ上的正规式r，使得L(r)=L(M)；对M的状态转换图进行改造：在M中加入两个结点X、Y。从X用ε弧连接到M的所有初态结点；从M的所有终态结点用ε连接到Y，从而形成一个新的NFA，记为M´，它只有一个初态X和一个终态Y。显然，L(M)=L(M´)。按下列方式消除M´中的所有结点，直至只剩X和Y。

123V1V2ij12V1V2ijV1|V2V1V2123V1V3V2ijV1V2*V352证明2：有Σ上的正规式r，构造一个NFAM（M只有一个终态，并且没有从终态出发的箭弧）方法：对r中运算符数目进行归纳证明：(运算符：|，*,*)(1)若r具有0个运算符，则r=ε，r=Φ，r=a，a∈Σ，下图的三个有限自动机显然符合要求。q0q0qfq0qfa对应ε的状态转换图(q0既是初态又是终态)对应Φ的状态转换图（初态到终态没有通路）对应a的状态转换图Thopmson

方法53（2）设结论对少于i(i≥1)个运算的正规表达式r成立。当r有i个运算时，有三种情况：a)r=r1|r2，r2中的运算符个数少于k。由归纳假设，对ri存在Mi=<Si，Σi，δi，qi，fi>，使得L(Mi)=L(ri)，并且Mi没有从终态出发的箭弧（i=1,2）。设S1∩S2=Φ，在S1∪S2中加入新状态q0，f0。设M=<S1∪S2∪{q0，f0}，Σ1∪Σ2，δ，q0，f0>，其中δ定义为：(a)δ（q0，ε）={q1，q2}；(b)δ（q，a）=δ1（q，a），当q∈S1–{f1}，a∈Σ1∪{ε}；

(c)δ（q，a）=δ2（q，a），当q∈S2–{f2}，a∈Σ2∪{ε}；

(d)δ（f1，ε）=δ（f2，ε）={f0}M的状态转换图中不难看出，M中有一条从q0到f0的通路w，当且仅当在M1中有一条从q1到f1的通路w或者在M2中有一条从q2到f2的通路w，即：L(M)=L(M1)∪L(M2)=L(r1)∪L(r2)=L(r)q0M1q1f1M2q2f2f0εεεε54b)r=r1r2。Mi同a)设M=<S1∪S2，∑1∪∑2，δ，q1，{f2}>δ:(a)δ（q，a）=δ1（q，a），当q∈S1–{f1}，a∈Σ1∪{ε}；(b)δ（q，a）=δ2（q，a），当q∈S2–{f2}，a∈Σ2∪{ε}；(c)δ（f1，ε）={q2}c)r=r1*。设M1同a)设M=<S1∪{q0，f0}，∑1，δ，q0，{f0}>，其中q0,f0∉S1，δ:(a)δ（q0，ε）=δ（f1，ε）={q1，f0}；(b)δ（q，a）=δ1（q，a），当q∈S1–{f1}，a∈Σ1∪{ε}

M1q1f1q0f0εεεε

M2

M1q1f1q2f2ε55Thompson方法所构造的NFA的状态数和转换较多。可以采用下面方法减少之：

R=R1|R2R1R2

R=R1R2R1R2

R=R1*R1

RRR156本章教学线索1词法分析程序的设计2词法分析器的设计3状态转换图4正规表达式与有限自动机5确定有限自动机的化简6词法分析程序的自动构造工具LEX简介575确定有限自动机的化简1)确定的有限自动机的化简一个DFAM=(，S，，s0，F)的化简是指寻找一个状态数比较少的DFAM′，使L(M)=L(M′)。而且可以证明，存在一个最少状态的DFAM′，使L(M)=L(M′)。2)等价状态的定义设s，tS，若对任何w

*，(s，w)F当且仅当(t，w)F，则称s和t是等价状态。否则，称s和t是可区别的。（即假定s和t是M的两个不同状态，如果从状态s出发能够读出某个字而停于终态，同样从t出发也能读出某个字而停于终态，称s和t是等价的，如果