第2讲-词法分析

第二讲词法分析词法分析器的构造正规表达式与有穷自动机词法分析器的自动产生1CompilerPrinciples§1.词法分析器的构造

编译程序首先在单词级别上来分析和翻译源程序。词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，即把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器(通常又称为扫描器,scanner）。2CompilerPrinciples一、一般考虑：

1.词法分析程序的主要任务：读入字符串形式的源程序—输入剔除非单词符号—空格、换行，注释宏展开，……拼单词符号—**、:=、FOR、BEGIN等源程序的列表输出行号3CompilerPrinciples

2.词法分析器的输入和输出形式输入—字符串形式的源程序输出—单词符号串。程序语言的单词符号一般分为五种：

关键字、运算符、界符、标识符、常数词法分析器输出的单词符号常常表示为二元式：

（单词种类编号，单词符号的属性值）4CompilerPrinciples

单词种类编号一个语言的单词符号分成几种，怎样编码是一个技术性问题，它取决于处理上的方便。标识符一般归为一种。常数则宜按类型（整、实、布尔、字符等）分种。关键字可视其全体为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般用一符一种的分法。

5CompilerPrinciples单词符号的属性值

如果一个种别只含有一个单词符号，那么对于这个单词符号，种别编码就完全代表它自身了，因此属性值就没有意义了。若同一个种别含有多个单词符号，那麽对于它的每个单词符号，除了给出种别编码之外，还应给出各有关单词符号的属性信息。

属性值是反映特性或特征的值。例如，对于某个标识符，常将存放它有关信息的符号表项的指针作为其属性值；对于某个字符串常量，则将该串的首地址指针作为其属性值。6CompilerPrinciples作为例子考虑下述C++语句：

while(i>=j)i-

-;

若while种别为01,(种别为11,标识符种别为20,>=种别为12,)种别为13,－－种别为14,;种别为30,则经词法分析器处理后，它将被转换为如下的单词符号序列：

(01,—)(11,—)(20,指向i的符号表项的指针)(12,—)(20,指向j的符号表项的指针)(13,—)(20,指向i的符号表项的指针)(14,—)(30,—)7CompilerPrinciples3.词法分析器与语法分析器的衔接

通常把词法分析器安排成一个独立子程序，而不是单独的一遍。这样一来，就无须在存储器中保留整个单词符号串，而是每当语法分析器需要单词符号时就调用这个子程序。每一次调用，词法分析器就从源程序字符串中识别出一个（一批）单词符号，把它交给语法分析器。这样做的好处是：压缩编译时扫描字符的时间词法规则描述简单，也便于独立处理；使得语法分析获得更多信息（上下文环境）；便于处理同一语言的几种不同表示形式（扩展）；

8CompilerPrinciples由以上考虑，可以初步设计为：源程序扫描器语法分析器取符号送符号9CompilerPrinciples二、进一步考虑：

1.输入、预处理

输入串一般放在一个缓冲区中，这个缓冲区称源程序输入缓冲区。词法分析器的工作可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注释等。于是可以设想构造一个预处理子程序，它完成上面的工作。每当词法分析器调用它时就处理出一串确定长度的输入字符，并将其装入词法分析器所指定的缓冲区中（称为扫描缓冲区）。这样分析器就可以在此缓冲区中直接而方便地进行单词符号的识别工作。10CompilerPrinciples2.对半互补缓冲区

分析器对扫描缓冲区进行扫描时一般使用两个指示器，一个指向当前正在识别单词的开始位置（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。但是不论扫描缓冲区设得多大都不能保证单词符号不会被缓冲区的边界所打断。因此，扫描缓冲区最好使用一分为二的区域，并使两区首尾相接，形成一个对半互补缓冲区。

11CompilerPrinciples例如：

。。。。。。While。。。。。。

起点指针搜索指针12CompilerPrinciples符号表单词符号扫描器预处理子程序输入缓冲区源程序扫描

缓冲区语法分析器取单词

综上所述，预处理子程序、扫描器和语法分析器相互之间的关系及工作情况可图示如下：

13CompilerPrinciples3.单词符号识别－超前搜索技术

问题发生在对基本字不加任何保护的语言中，基本字及用户自定义的标识符或标号之间无特殊分界符，这使得关键字的识别甚为麻烦。

请看下面的例子：

1DO99K=1,102IF(5.EQ.M)I=103DO99K=1.104IF(5)=55

这四个语句都是正确的FORTRAN语句。语句1和2分别是DO和IF语句，它们都是以某基本字开头的。语句3和4是赋值语句，它们都是以用户自定义的标识符开头的。14CompilerPrinciples

为了从1、2中识别出关键字DO和IF，我们必须要能够区别1、3和区别2、4。语句1、3的区别在于等号之后的第一个界符：一个为逗号，另一个为小数点，语句2、4的主要区别在于右括号后的第一个字符：一个为字母，另一个为等号。这就是说，为了识别1、2句中的关键字，我们必须超前扫描许多个字符，超前到能够肯定词性的地方为止。这种向前扫描若干字符直到找到能区分单词的字符为止的技术就叫超前搜索。15CompilerPrinciples单一符号运算符和复合运算符：思考：如何从程序中删除注释：/**/16CompilerPrinciples17CompilerPrinciples4.词法错误如果没有其他组件的帮助，词法分析器很难发现源代码中的错误。18CompilerPrinciples[例]在TurboC下运行下面的C程序

1intmain(){2intx=3;3 if(x%2==0)/*evennumber*/4 return0;5else/*oddnumber*/6 return1;7}19CompilerPrinciples如果把if写成iif，则编译得到以下2条错误信息：

Error…4:Statementmissing;infunctionmain.

Error…5:Misplacedelseinfunctionmain.如果把else写成els，则编译得到以下3条错误信息：

Error…6:Undefinedsymbol‘els’infunctionmain.Warning…6:Codehasnoeffectinfunctionmain.Error…6:Statementmissing;infunctionmain.

20CompilerPrinciples现在有关扫描器的输入、处理、输出等问题都清楚了，可以进行扫描器的设计了。为此，引入一种新的图形工具--状态转换图。

1.

状态转换图是一张有限个结点的有向图，结点代表状态，用圆圈表示，状态之间用带标识的箭弧连结，箭弧上的标识代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。三、状态转换图21CompilerPrinciples

如右图所示：在状态1下，若输入字符为a，则读进a，并转换到状态2。若输入字符为b，则读进b，并转换到状态3。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示），图中3为终态。状态转换图①②③ab22CompilerPrinciples2.状态转换图可用来识别一定的字符串例如：

<标识符>→字母|<标识符>字母|<标识符>数字

<整数>→数字|<整数>数字

终态上打个*号，表示多读进了一个不属于该标识符或数字部分的字符，应把它退还给输入串。012字母字母或数字其他**012数字数字其他23CompilerPrinciples*01234576数字数字··数字E或DE或D+或-数字数字数字数字其它其它上图是识别Fortran实常数的转换图思考：结合前面的思考题，作出能够识别注释的状态转换图：/**/和//...24CompilerPrinciples3.状态转换图可以用来识别程序语言的单词符号

例：假设某程序语言只有前述的五类单词符号，运算符只有+、*、=，界符只有#、(、)，那么就可以用左边的状态转换图来识别其所有单词符号。0→1→2识别的串是基本字还是标识符，要查保留字表区分。

当然，还要加上两个限制：(1)所有基本字都是保留的；(2)所有单词间若无明显分界，则用空格分开；空白字母或数字01245678931011字母非字母与数字数字非数字数字=+*#（）其它**25CompilerPrinciples4.状态转换图的程序实现为每个状态编写一小段程序即可例：使用如下一组全局变量和过程，作为实现状态转换图的基本部分：⑴CHAR：字符变量，存放最新读进的源程序字符；⑵Token：字符数组，存放构成单词符号的符号串；⑶GetChar：取字符过程，将下一个输入字符读到CHAR中，并把搜索指示器的指针前移一个字符位置；⑷GetBC：检查CHAR中的字符是否为空白，若是则调用GetChar直至CHAR中进入一个非空白字符；⑸ConCat：拼单词过程，每调用一次就将CHAR中的字符连接到Token之后；26CompilerPrinciples⑹IsLetter和IsDigit：两个布尔函数，分别判断CHAR中的字符为字母或是数字而返回真假值；⑺Reserve：整型函数，对Token中的字符串查保留字表，查到则返回该保留字的整型编码，否则返回0值；⑻Retract：回退子程序，专门用来把搜索指示器回调一个字符位置，并置CHAR为空；⑼Error：出错处理子程序；⑽DTB：类型转换函数，将Token中的十进制数转换为二进制数；于是，可编出如下程序：⊙Start:Token:=‘’;GetChar;GetBC;

27CompilerPrinciplesCASECHAROF‘A…z’:BEGINWHILEIsLetterORIsDigitDOBEGINConCat;GetCharEND;

Retract;C:=Reserve;IFC=0THENReturn($ID,Token)ELSEReturn(C,─)

END;‘0…9’:BEGINWHILEIsDigitDOBEGINConCat;GetCharEND;Retract;Return($INT,DTB)

END;

‘=‘:Return($ASSIGN,─);

‘+‘:Return($PLUS,─);

‘*‘:Return($START,─);

‘(‘:Return($LPAR,─);

‘)‘:Return($RPAR,─);‘#‘:Return($,─);

ENDOFCASE;DealError;GotoStart;

28CompilerPrinciples§2.正规表达式与有穷自动机

RegularExpressionandFiniteAutomata

上一节我们讨论了扫描器的手工编制，是在讨论了Scanner的主要工作拼单词符号并进行相应的词法检查的基础上，通过构造状态转换图再转换为程序代码来实现的。本节要进一步讨论两个抽象的工具，以便研究词法分析程序的自动生成问题。由于我们集中注意力于扫描器的自动生成，故对有关结论一般不加形式证明，大家若对这方面感兴趣，可以查阅相关书籍，如《形式语言与自动机》（FormalLanguage&Automata）。

29CompilerPrinciples我们知道，任何高级程序设计语言都有自己的字母表，但并非字母表上的任何字符串都能称为一个程序，我们感兴趣的是能称为程序的那些串，它们的集合称为正规集。正规式是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具，可用以描述单词符号。这同样是一个无穷语言的有穷描述的问题。1.正规式(RE)的定义：这是一种与我们以前常见的算术、逻辑等表达式不同的表达式。设Σ为字母表，⑴ε是

Σ上的正规式，它所表示的正规集分别为{ε}；⑵对于任何aΣ,a都是Σ上的一个正规式，它所表示的正规集为{a}；一、正规表达式和正规集30CompilerPrinciples⑶假定U和V都是Σ上的正规式，它们所表示的正规集分别记为L(U)和L(V),那么，(U|V),(UV)和(U)*也都是正规式，它们所表示的正规集分别为L(U)∪L(V),L(U)L(V)(连接积）和(L(U))*（闭包）。

仅由有限次使用上述三步骤而得到的表达式才是Σ上的正规式。仅由这些正规式所表示的字集才是Σ上的正规集。*这个定义本身是构造型的，今后我们应该习惯这种构造型定义及证明方式。31CompilerPrinciples2.正规表达式的运算顺序：

括号→*（闭包）→·（连接）→∣（或）例1：Σ={a,b}。∵a,b都是正规式∴a*是正规式。

ba*也是正规式，它所表示的正规集为：{b,ba,baa,……}，也就是Σ上所有以b为首后跟着任意多个a的字。同样，a(a|b)*

亦为Σ上的正规式，其所表示的正规集为Σ上所有以a为首的字；(a|b)*(aa|bb)(a|b)*

对应的正规集是所有含有两个相继的a或相继的b的字。

32CompilerPrinciples3.正规表达式的等价：若两个正规式所表示的正规集相同，则认为二者等价，记为‘=’。例：Σ={a,b}

∵L(b(ab)*)={b,bab,babab,…}L((ba)*b)={b,bab,babab,…}

∴b(ab)*=(ba)*b33CompilerPrinciples4.正规表达式的运算律：

U∣V=V∣U（交换律）U∣(V∣W)=(U∣V)∣W（结合律）U(VW)=(UV)W（结合律）U(V∣W)=UV∣UW（分配律）(U∣V)W=UW∣VW（分配律）

εU=Uε=U（幺元）(R*)*=R*（幂等律）☺思考：证明？34CompilerPrinciples5.标识符的正规式 letter ->A|B|...|Z|a|b|...|z|_ digit ->0|1|...|9 id ->letter(letter|digit)*

扩展写法： letter ->[A-Za-z_] digit ->[0-9] id ->letter(letter|digit)*

35CompilerPrinciples练习：P72~78.3.2.2(1)~(4),3.2.5(3)3.2.11,3.2.1236CompilerPrinciples二、确定的有穷自动机（DFA)1.问题的提出：上节我们介绍了状态转换图：

我们也可以写：S0→aS1:δ(S0,a)=S1

S1→bS2:δ(S1,b)=S2

……于是我们可以认为所有状态构成一个集合S，所有弧的标识构成一个集合Σ，函数δ，起始状态S0和所有终态构成的集合F。这样我们可以把状态转换图形式化为如下的数学系统—DFA。S0SnS1S2ab37CompilerPrinciples38CompilerPrinciples3.DFA的表示形式：由前所述，DFA是状态转换图的抽象模型。显然DFA也可以表示成一张（确定的）状态转换图，它们是一一对应的。假定DFAM含有m个状态、n个输入字符，那末，这张图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用上的一个字符作标记，整张图含有唯一的初态和若干个（可以是0个）终态结点。

39CompilerPrinciplesDFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示δ(s,a）的值，该矩阵称为状态转换矩阵。3012abababa,b状态转换图状态转换矩阵40CompilerPrinciples

对于*中的任何一个字符串，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字等于，则称为DFAM所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字可以为M所识别。DFAM所能识别的字的全体记为L(M).DFA的确定性表现在δ是一个从Sx→S的单值部分映射。也就是说，对任何状态sS和输入符号aΣ，δ(s,a)唯一地确定了下一个状态。从状态转换图的角度来看，任何状态发出的弧具有不同的标识。

41CompilerPrinciples例：DFAM=({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)=3问：有几个状态,几个输入字符？并画出其转换图。L(M)=?解：有0，1，2，3共四个状态。输入字符为a,b两个。其状态转换图如右L(M)为在上含相继两个a或相继两个b的字的集合。012abababa,b342CompilerPrinciples43CompilerPrinciples

显然，NFA也可以表示成一张状态转换图。假定NFA含有m个状态、n个输入字符，那么，这张图含有m个状态结点，每个结点可以射出若干条箭弧和别的结点相连接，每条箭弧用*上的一个字（不一定要不同的字而且可以是空字）作标记（称为输入字），整张图至少含有一个初态和若干个（可以是0个）终态结点。某些结点既可以是初态也可以是终态结点。对于*中的任何一个字符串，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字（忽略那些标记为的弧）等于，则称为NFAM所识别。也就是：δ(S0,)∩F≠φ。若M的初态结点同时又是终态结点，或者存在一条某初态结点到某各终态结点的通路，则空字可以为M所识别。44CompilerPrinciples例：M=({0,1,2,3,4},{a,b},δ,{0},{2,4})，其中δ：

δ(0,a)={0,3},δ(1,a)=φ,δ(2,a)={2},

δ(3,a)={4},δ(4,a)={4},δ(0,b)={0,1},

δ(1,b)={2},δ(2,b)={2},δ(3,b)=φ,

δ(4,b)={4}03142a,ba,ba,baabb它能接受：所有含有两个连续的a或两个连续的b的串45CompilerPrinciples2.有穷自动机的等价：对于任何两个有穷自动机M和M´，如果L(M)=L(M´)，则称M和M´是等价的。对此我们有一个重要结论：判定任何两个有穷自动机等价的算法是存在的。46CompilerPrinciples四、正规式与有穷自动机的等价性：

我们先来证明两个重要的事实：1.定理1：Σ上的有穷自动机所接受的字的全体L(M)是Σ上的一个正规集。(1)一般考虑：要证明L(M)是Σ上的一个正规集，很容易想到正规式。因为正规集是正规式的值。同时我们又知道任何一个

FAM都可以表示成一个状态转换图，而该图中从某个初态结点到某个终态结点的路上所有弧的标记连接而成的串，恰恰就是L(M)的一个字，L(M)就是这样一些字的全体，于是我们想，是否能构造一个正规表达式V，使得L(V)=L(M)呢？如果能构造出这样的一个V，问题也就解决了。为此，我们把转换图的概念加以拓广，使每条弧可以用一个正规式来标记，如，这样我们就可以借助M来构造V了。01a∣b47CompilerPrinciples(2)证明（简略）：a.在NFAM的状态转换图上加入唯一的初态X和终态Y，从X到M原来的每个初态用标有ε的弧相连接，而每个原终态则用标有ε的弧与Y相连接。显然这样的NFAM与NFAM´是等价的—L(M´)=L(M)。b.反复使用以下规则对M´中的所有状态进行逐步消去：

123V1V213V1V212V1V212V1∣V2123V1V2V313V1V2*V3由于M´的状态集是有限的，因此经过有限次使用上述规则，必然得到

，显然L(V)=L（M´）=L（M）。

对于NFA的情况具有一般性，若用DFAM则更简单。XYV48CompilerPrinciples①②③④abababa,b例：③bbab②①XYaaεεa,b拓广①②③XεεYaabb④④(ba)*(ab)*Xε①④εYa(ba)*(a∣bb)b(ab)*(b∣aa)XY(a(ba)*(a∣bb)∣b(ab)*(b∣aa))(a∣b)*a,ba,b这样就得到了与所给DFA等价的正规式。49CompilerPrinciples2.定理2：对于Σ上的每个正规表达式V，存在一个Σ上的DFAM，使得L(M)=L(V)。(1)一般考虑：由定理1的证明，我们很容易想到，对Σ上的每个正规式V，可以画出拓广转换图：然后我们与逐次减少结点过程相反，可以对V逐次分裂并加入新结点和弧，直到每条弧的标记或者为Σ中的一个符号，或者为ε，这样就构造了一个转换图，也就是一个NFAM´,然后再把M´确定化为DFA就可以了。XYV50CompilerPrinciples(2)证明：

a.把正规式V表示成拓广转换图

b.根据以下规则分裂V并加入新状态结点和标识弧

整个分裂过程保持和为唯一初态和终态，由正规式定义，显然经过有限次分裂就可以构造出一个NFAM´使得L(M´)=L(V)。XYVXYijABijA∣BijA*ikjABijABikjεεA51CompilerPrinciples

c.对NFAM´确定化—构造一个DFAM使得L(M)=L(M´)

＊一般考虑：变多值映射为单值映射，可采用子集法。NFA不确定的原因主要在于含有ε弧和从某结点经由相同标识的弧而到达不同的结点——结点集。这两个问题解决了，NFA也就确定了。①预备定义1：状态集I的ε闭包，记为

ε_CLOSURE(I),如下定义：ⅰ.若s∈I,则s∈ε_CLOSURE(I)；ⅱ.若s∈I，则由s出发经任意条ε弧而能够到

达的任何状态s´∈ε_CLOSURE(I)；②预备定义2：对状态集I和a∈Σ，定义Ia=ε_CLOSURE(J)；其中J是那些可从I中某一结点出发经过一条a弧而到达的状态结点的全体。52CompilerPrinciples设I={1}，则由I经一条a弧而到达的状态结点的全体J={5,3,4}，从而Ia=ε_CLOSURE(J)={5,6,2,3,8,4,7}例：状态转换图如下：①⑤②④⑥③⑧⑦aaaεεεεε53CompilerPrinciples

③M′的确定化：从以上所谈不难看出确定化的复杂程度与符号个数密切相关，为此我们设Σ={a,b}，并依如下过程构造一个转换矩阵。该矩阵有三列，分别记为I,Ia,Ib，第一行第一列置为ε_CLOSURE({X})，其中X为M′的初态集。由此我们就可以根据预备定义构造Ia和Ib，然后检查Ia、Ib中是否有不同于已构造出的I的，若有则将其作为新的I，又可以构造新的Ia和Ib。依次下去，直到不再有新的状态子集出现为止。因为M′的状态数是有限的，故上述过程必在有限步内停止。把上述表中第一列的状态子集进行编号，最终可得到一个状态矩阵，该矩阵唯一地画出了一个确定的有穷自动机M，其唯一初态为ε_CLOSURE({X})，终态是那些含有M′的终态Y的子集。由上述构造过程不难看出：L(M)=L(M′),于是达到了确定化的目的。54CompilerPrinciples例:设V=(a|b)*(aa|bb)(a|b)*(1)构造NFAM′XY(a|b)*(aa|bb)(a|b)*①③④εεaabb②a,bXY⑤a,bε⑥ε(2)构造状态转换矩阵012345655CompilerPrinciples(3)重新编号的状态矩阵:(4)DFAM的状态转换图为:b(5)DFAM=({0,1,2,3,4,5,6},{a,b},δ,0,{3,4,5,6}),其中δ如左上表所示。a0123456aaaaaabbbbbb56CompilerPrinciples3.推论1：一个字集V是正规的当且仅当有一自动机M,使得L(M)=L(V)。推论2：NFA与DFA接收相同的集合。

[定理]：推论2也可作为一个定理来证明：若L(M)被NFAM接受，则必定存在一个DFAM′接受L(M)。

证明过程不再介绍，感兴趣者可以尝试用构造法加归纳法来证明。

57CompilerPrinciples五、DFA的化简所谓对一个DFAM的化简，就是找一个DFAM´，使得L(M)=L(M´)但是M´的状态数比M少。1.等价状态和可区别状态：若分别从状态s和t出发而停于终态能读出同一个字α，则称s,t为等价状态；不等价的两个状态称为可区别状态。a0st12zaabaabb58CompilerPrinciples2.状态的最小化过程所谓DFAM的状态最小化过程就是找一个最少状态的DFAM´使得L(M)=L(M´)。具体做法：把DFAM的状态集分割成一些不相交的子集，使得不同的两个子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的，最后让每个子集选出一个代表，把所有与该子集相关的弧都与该代表相连接，并消去其他等价状态，即可求得最少状态的DFAM´。59CompilerPrinciples3.例：DFAM=({0,1,2,3,45,6},{a,b},δ,0,{3,4,5,6})其中δ：δ(0,a)=1,δ(0,b)=2,δ(1,a)=3,δ(1,b)=2,

δ(2,a)=1,δ(2,b)=4,δ(3,a)=3,δ(3,b)=5,

δ(4,a)=6,δ(4,b)=4,δ(5,a)=6,δ(5,b)=4,

δ(6,a)=3,δ(6,b)=5.状态图：0123456aaaaaabbbbbba（1）形成基本分划π─分成两个子集:非终态子集I(1)和终态子集I(2)即：I(1)＝{0,1,2}I(2)={3,4,5,6}b60CompilerPrinciples(2)对每个子集I(i)和每个a∈Σ,来考察Ia(i)是否包含在某个I(j)中(j=1,2,…n)，若不是完全包含在某个I(j)中则至少可一分为二，形成新的分划。例：Ia(1)＝{0,1,2}a={1,3}而{1,3}不在π的任一子集中，故应分割。又因{0,2}a={1}，故分成{0,2}和{1}，显然{1}是不能再分割的了。至此得到：

π´={{0,2},{1},{3,4,5,6}}(3)重复(2)的工作直到所有子集不能再分割为止。

{0,2}b={2,4}不在任一子集中，故一分为二得:π´={{0},{1},{2},{3,4,5,6}}，而{3,4,5,6}a={3,6}{3,4,5,6},{3,4,5,6}b={5,4}{3,4,5,6},不能再分割了。所以最后的分划:

π={{0},{1},{2},{3,4,5,6}}。61CompilerPrinciples(4)选等价状态子集的代表，并重构状态图。

如{3,4,5,6}的代表为{3}，可得状态图：02b13abba,baa(5)最后可得最少状态自动机为：DFAM´=({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)=3.62CompilerPrinciplesRGDFANFAε-NFARE总结：

正规语言的描述模型63CompilerPrinciples§3.词法分析器的自动产生

前面我们已经谈了状态转换图可以用来识别单词符号，DFA可以用一张确定的状态转换图来表示，而DFA又与正规式等价，所以我们可以用正规式来描述程序语言的词法规则。而从正规式到自动机（状态图）再到程序的转换工作，可以交予一个程序来自动生成。这类程序就是词法分析器的自动生成器。参考书3.4节介绍的Lex(Flex)就是其中典型的代表。此处不再赘述。

64CompilerPrinciples小结本讲内容：

★词法分析器的构造

★状态转换图★正规表达式与正规集★DFA与NFA★RE,RG,DFA,NFA的等价关系★DFA的最小化65CompilerPrinciples

功能：分割字符串形式的源程序，得到单词符号串输入：字符串形式的源程序输出：单词符号串（二元式）分析技术超前搜索对半互补缓冲区预处理子程序设计独立子程序状态转换图─最小化DFA的状态转换图

实现：最小化的DFA的每个状态对应一小段程序词法分析器RERGA→Ba∣aA→aB∣aNFADFA最小化DFA转换规则增加开始状态增加终止状态确定化划分等价类66CompilerPrinciples例题与解答[例1]写出产生语言：{能被5整除的十进制整数}的文法及正则表达式。解：能被5整除的正则表达式：

(+|-)A*(0|5)

A∈{0,1,2,3,4,5,6,7,8,9}如果要求除零以外不以0开头，则文法为：G[Z]:Z→XAD

|D|-5A→AB|CB→0|C|BBC→1|2|3|4|5|6|7|8|9D→0|5X→+|-67CompilerPrinciples[例2]写一个文法，使其语言是奇数集，且每个奇数不以0开头。解：文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D

68CompilerPrinciples[例3]写出能被3整除十进制整数的文法和正则表达式：解：能被3整除的文法：G=({0,1,2,3,4,5,6,7,8,9},{S,A,B},S,P),其中P为：S→(0|3|6|9)S|εS→(1|4|7)A|(2|5|8)BA→(0|3|6|9)A|(1|4|7)B|(2|5|8)SB→(0|3|6|9)B|(2|5|8)A|(1|4|7)S正则表达式：

Z=a*|(bc)*|(cb)*|(a|cibi)*|(ci