第三章词法分析教案.doc

《第三章词法分析教案.doc》由会员分享，可在线阅读，更多相关《第三章词法分析教案.doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 词法分析本章概述执行词法分析的程序称为词法分析器。本章中，我们将将讨论词法分析程序的构造。前一部分讨论手工构造方法，后一部分讨论自动构造方法。主要学习内容：词法分析器的功能和输出形式，词法分析器的设计方法状态转换图的实现，正规表达式与有限自动机，LEX的一般描述和实现。学习目标：了解词法分析器的功能和输出形式，熟练掌握词法分析器设计的原理和方法，能够以转换图为工具使用某种语言的编写并调试一个扫描器。在正确理解正规表达式与有限自动机的有关概念、理论的基础上，了解词法分析的自动产生原理。学习重点和难点：词法分析器的功能和设计方法，正规表达式与有限自动机的等价性，有限自动机的确定化和最小化。

2、本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。首先需要描述和刻画程序设计语言中的原子单位-单词，其次需要识别单词和执行某些相关的动作。描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。回顾什么是词法分析程序?实现词法分析（lexical analysis）的程序称为词法分析程序（或扫描器）。词法分析程序的主要任务：对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符并按照构词规则切分成一个一个具有独立意义的单词。并确定其属性（如保留字、标识符、运算符、界限符和常量等）。再把它们转换成长度统一的标准形式属性字（TOKEN）。词法

3、分析是编译过程中的第一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。词法分析程序和语法分析程序的关系见图3.1。词法分析工作从语法分析工作独立出来的原因：l 简化设计l 改进编译效率l 增加编译系统的可移植性3.1 对于词法分析器的要求3.1.1 词法分析器的功能和输出形式功能：输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。单词的分类（五类）：1关键字：由程序语言定义的具有固定意义的标识符。也称为保留字或基本字。2. 标识符：用来表示程序中各种名字的字符串。3. 常 数：常数的类型一般有整型、实型、

4、布尔型、文字型。4. 运算符：如+、 、*、/ 等。5. 界限符：如逗号、分号、括号等。一个程序语言的关键字、运算符、界限符都是固定的，即数量有限及意义明确；而对于标识符和常数通常是不确定的。词法分析器所输出的单词符号常常表示成如下的二元式：（单词种别，单词符号的属性值）单词种别通常用整数编码。一个语言的单词符号如何分种，分成几种，怎样编码，是一个技术性的问题。它主要取决于处理上的方便。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可将其全体视为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。

5、至于界符一般用一符一种的分法。单词符号的属性是指单词符号的特性或特征。属性值则是反应特性或特征的值。例如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。在教程中，我们假定关键字、运算符和界限符都是一符一种。对于它们，词法分析器只给出其种别编码，不给出它自身的值。标识符单列一种。常数按类型分种。考虑下述C十代码段： while（ij）i； 经词法分析器处理后，它将被转换为如下的单词符号序列：while，（，id，指向i的符号表项的指针，id，指向j的符号表项的指针，id，指向i的符号表项的指针，； ，3.1.2词法分析器的

6、设计词法分析器的设计通常要经历如下几步:首先确定词法分析器的接口，即确定是把它作为独立的一遍扫描处理还是作为语法分析的子程序，这里我们将按照词法分析的任务和作为一个独立扫描处理程序的要求来考虑词法分析器的设计。确定单词分类和属性字的结构。根据上步确定的单词分类，对每类单词构造状态转换图。根据状态转换图设计分析算法。在词法分析器的具体实现时要注意下面几点:一、 输入、预处理词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分析的工作（单词符号的识别）可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。

7、预处理的主要工作：某些跳格符、回车符和换行符等编辑性字符，在别处的任何出现都没有意义，预处理时可以将其剔掉。注解部分仅在于改善程序的易读性和易理解性。对于它们，预处理时可以将其剔掉。空白符（一个或相继数个）用作单词符号之间的间隔，即用作界符。在这种情况下，预处理时可把相继的若干个空白结合成一个。我们可以构造一个预处理子程序，它能够完成上面所述的任务。二、 单词符号的识别：超前搜索词法分析器的结构如图3.2所示。当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后，分析器就从此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后，它又调用预处理程序装入新串。为什么要采用超前搜索在

8、程序中有一些单词的识别经常需要多读入一些字符才能知道哪些字符组成一个单词。如：1 DO99Kl,102 IF（5.EQ.M） I103 DO99K1.104 IF（5）55这四个语句都是正确的FORTRAN语句。语句1和2分别是DO和IF语句，它们都是以基本字开头的，语句3和4是赋值句，它们都是以用户自定义标识符开头的。又如C中：a=a+;a=a+1;如此之类，等等。三、 状态转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。例如，图3.3（a）表示：在状态1下，若输入字符为

9、X，则读进X，并转换到状态2。若输入字符为Y，则读进Y，并转换到状态3。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。一个状态转换图可用于识别（或接受）一定的字符串。例如，识别标识符的转换图如图3.3（b）所示。其中0为初态，2为终态。这个转换图识别（接受标识符的过程是：从初态0开始，若在状态0之下输入字符是一个字母，则读进它，并转入状态1。在状态1之下，若下一个输入字符为字母或数字，则读进它，并重新进入状态1。一直重复这个过程，直到状态1发现输入字符不再是字母或数字时（这个字符也已被读进）就进入状态2。状态2是终态，它意味着到此

10、已识别出一个标识符，识别过程宣告终止。终态结上打个星号。意味着多读进了一个不属于标识符部分的字符，应把它退还给输入串。如果在状态0时输入字符不为“字母”，则意味着识别不出标识符，或者说，这个转换图工作不成功。3.2 正规表达式与正规集（正规语言）程序设计语言中的单词是基本语法成分。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造。 正规表达式是典型的词法规则描述工具。 正规式也称正则表达式。正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。下面是正

11、规式和它所表示的正规集的递归定义。定义（正规式和它所表示的正规集）：设字母表为S,辅助字母表S= ， ， |，*，(，)1.和都是S上的正规式，它们所表示的正规集分别为和 ；2.对任何a，a是上的一个正规式，它所表示的正规集为a；3.假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1)，e1|e2，e1e2，e1*也都是正规式，它们所表示的正规集分别为L(e1)，L(e1)L(e2)，L(e1)L(e2)和(L(e1)*。4.仅由有限次使用上述三步骤而定义的表达式才是S上的正规式，仅由这些正规式所表示的集合才是S上的正规集。注意其中“ ”、“|”、“*”

12、均为正规式子运算符：（1） “”读为“连接”；（2） “|”读为“或”；（3） “*”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“|”、“*”。连接符“”一般可省略不写。“”、“|”和“*”都是左结合的。例子:令=a，b，上的正规式和相应的正规集的例子有：正规式 正规集a aa|b a,bab ab(a|b)(a|b) aa,ab,ba,bba * e ,a,a, 任意个a的串(a|b)* e ,a,b,aa,ab 所有由a和b组成的串(a|b)*(aa|bb)(a|b)* S*上所有含有两个相继的a或两个相继的b组成的串讨论下面两个例子

13、：例3.1：令S=l，d，则S上的正规式 r=l(l|d)* 定义的正规集为:l,ll,l d,ldd, 其中l代表字母,d代表数字。正规式即是 字母(字母|数字) * 。它表示的正规集中的每个元素的模式是“以字母打头的字母数字串”。就是Pascal和多数程序设计语言允许的的标识符的词法规则。例3.2：有S=d，e，+，-，则S上的正规式 d*(dd*|e )(e(+|-e|)dd* |e)表示的是无符号数的集合。其中d为09的数字。结论：程序设计语言的单词都能用正规式来定义。正规式的等价性：若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：e1=(a|b)

14、， e2=b|a， e1=e2又如：e1=b(ab)* , e2=(ba)*b， e1=e2 e1= (a|b)* , e2=(a*|b*)*， e1=e2正规式的代数运算规律:设U,V,W为正规式，正规式服从的代数运算规律有：（1） U|V=V|U “或”服从交换律（2） U|(V|W)=(U|V)|W “或”的可结合律（3） (UV)W=U(VW) “连接”的可结合律（4） U(V|W)=UV|UW (V|W)U=VU|WU 分配律（5） U=U，U =U “连接”的恒等元素零一律有穷自动机有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规

15、式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata) 。关于有穷自动机我们将讨论如下题目：确定的有穷自动机DFA 不确定的有穷自动机NFA NFA的确定化 DFA的最小化3.3.1 确定的有穷自动机DFA一、DFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，s0 ，Z）,其中:1. K是一个有穷集，它的每个元素称为一个状态；2. 是一个有穷字母表，它的

16、每个元素称为一个输入符号，所以也称为输入符号表；3. f是转换函数，是在KK上的单值部分映射。即，如果 f（ki，a）=kj，（kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4. s0 K是唯一的一个初态；5. Z K是一个终态集（可空），终态也称可接受状态或结束状态。二、一个DFA 的例子：DFA M=（S，U，V，Q，a，b，f，S，Q其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q显然，一个DFA可用一个矩阵表示，该矩阵

17、的行表示状态，列表示输入字符，即k行a列的 矩阵元素表示f（k，a）的值。这个矩阵称为状态转换矩阵。对于上例，有如下状态转换矩阵状态abSUVUQVVUQ+QQQ注意：在状态矩阵中初态结点的旁边标以；终态结点旁边标以。一个DFA也可表示成一张（确定的）状态转换图。假定DFA M含有 m个状态和 n个输入字符，那么，这个图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用中的一个不同输入字符作标记，整张图含有唯一的一个初态结点和若干个（可以是0个）终态结点。注意：初态结点的旁边标以； 终态结点则用双圈表示。对于*中的任何字，若存在一条从初态结点到某一终态结点的通路，且这条通

18、路上所有弧的标记符连接成的字符串等于，则称可为DFA M所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字可为M所识别（或接受）DFA M所能识别的字的全体记为L(M) 。 如有 =abb，显然可为上例的DFA M所识别。换言之：若t* ，f (S，t) =P，其中S为DFA M的初态，PZ，Z为终态集。则称t 可为DFA M所接受（识别）。如果一个DFA M的输入字母表为，则我们也称M是的一个DFA。结论：上的一个字集V，*是正规的，当且仅当存在上的DFA M，使得VL（ M）。*上的符号串t 在DFA M上运行:一个输入符号串t，（将它表示成Tt1的形式，其中T， t1*）在DF

19、A M=（K，f，S，Z）上运行的定义为：f（Q，Tt1）=f（f（Q，T），t1）,其中QK;扩充转换函数f 为 K*K上的映射，且： f（ki， e ）= ki 例：证明t=baab被图3.4的DFA所接受。 f（S，baab）=f（f（S，b )，aab） = f（V，aab）= f（ f（V，a），ab） = f（U，ab）=f （ f（U，a），b） = f（Q，b）=QQ属于终态。得证。三、DFA的确定性表现两个方面：1. 映射f：KK是一个单值函数。也就是说，对任何状态sK和输入符号a，f（s，a）唯一地确定了下一状态。从转换图的角度来看，假定字母表含有n个输入字符，那么，任何一

20、个状态结最多只有n条弧射出，而且每条弧以一个不同的输入字符标记。2. DFA有且仅有唯一的一个初态s0K 。3.3.2 非确定的有穷自动机NFA一、NFA定义：一个非确定的有穷自动机（NFA）M是一个五元组：M=（K，f，S ，Z）。其中：1. K是一个有穷集，它的每个元素称为一个状态；2. 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；3. f是状态转换函数，是在K*K的子集的映射，即，f： K*2K ；表明在某状态下对于某输入符号可能有多个后继状态；4. SK是一个非空初态集； 5. ZK是一个终态集（可空）。显然，一个NFA可用一个矩阵表示，该矩阵的行表示状态，列

21、表示输入字符，即k行a列的 矩阵元素表示f（k，a）的值。这个矩阵称为状态转换矩阵。同前，一个含有m个状态和n个输入字符的NFA可表示成如下的状态转换图：该图含有m个状态结点，每个结点可射出若干条箭弧与别的结点相连接，每条弧用*中的一个字（不一定要不同的字而且可以是空字。）作标记（称为输入字），整张图至少含有一个初态结点以及若干个（可以是0个）终态结点。某些结点既可以是初态结点也可以是终态结点。 二、一个NFA 的例子：NFA M=（S，P，Z，0，1，f，S，P，Z）其中：f（S，0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1）=Pf（S，1）=S，Z矩阵表示如下：01SPSP Z+ZP

22、P简化为01SPS PZ+ZPP状态图表示为图3.5。具有转移的不确定的有穷自动机为图3.6。定理：对任何一个具有转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA ，使得L(M)=L(N)。 与上例等价的一个NFA为图3.7。类似DFA, 对NFA M=K，f，S，Z也有如下定义：*上的符号串t在NFA M上运行：一个输入符号串t，（我们将它表示成T t1的形式，其中T，t1*）在NFA M上运行的定义为：f（Q，Tt1）=f（f（Q，T），t1） 其中QK。*上的符号串t被NFA M接受：若t*，f(S0，t)=P，其中S0 S，P Z，则称t为NFA M

23、所接受（识别）。*上的符号串t被NFA M接受也可以这样理解：对于*中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为，那么空字可为M所接受。NFA M所能接受的符号串的全体记为 L(M)。结论：上一个符号串集V *是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。3.3.3 NFA与DFA的等价性显然， DFA是NFA的特例。对于每个NFA M，存在一个

24、DFA M，使得L( M ) =L( M)。对每个NFA M存在着与之等价的DFA M。即：对于任何两个有穷自动机M和M，如果L( M )=L( M)，则称M与M是等价的。有一种算法，将NFA转换成接受同样语言的DFA。这种算法称为子集法。与某一NFA等价的DFA不唯一。从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态。DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。NFA确定化算法（NFADFA的转换）: 假设NFA N=(K，f，K0，Kt)按如

25、下办法构造一个DFA M=(S，d，S0，St)，使得L(M)=L(N)：1. M的状态集S由K的一些子集组成。用S1 S2Sj表示S的元素，其中S1，S2，Sj是K的状态。并且约定，状态S1， S2， Sj是按某种规则排列的，即对于子集S1， S2= S2，S1来说，S的状态就是S1 S2；2 M和N的输入字母表是相同的，即是；3转换函数是这样定义的： d(S1，S2，Sj，a)= R1R2Rt 其中 R1，R2，Rt =-closure(move(S1， S2，Sj，a)4 S0=-closure(K0)为M的开始状态；5 St=SiSkSe，其中 SiSkSeS且Si，Sk，SeKt二、

26、定义对状态集合I的几个有关运算：状态集合I的-闭包：状态集合I的-闭包表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。状态集合I的a弧转换：定义状态集合J表示为 J=move(I，a) ，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。Ia=-closure(J ) =-closure(move(I，a) )状态集合I的有关运算的例子见图3.8。I=1，-closure(I)=1，2；I=5，-closure(I)=5，6，2；move(1，2，a)=5，3，4-clos

27、ure(5，3，4)=2，3，4，5，6，7，8；三、构造NFA N的状态K的子集的算法：假定所构造的子集族为C，即C= (T1， T2，TI)，其中T1， T2，TI为状态K的子集。 1.开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。2.while （C中存在尚未被标记的子集T）do 标记T；for 每个输入字母a do U:= e-closure(move(T，a)；if U不在C中 then 将 U作为未标记的子集Ti加在C中NFA转换成DFA的例子见图3.9。IIaIbI，1，21，2，31，2，41，2，31，2，3，5，6，f1，2，41，2，41，2，31，

28、2，4，5，6，f1，2，3，5，6，f1，2，3，5，6，f1，2，4，6，f1，2，4，5，6，f1，2，3，6，f1，2，4，5，6，f1，2，4，6，f1，2，3，6，f1，2，4，5，6，f1，2，3，6，f1，2，3，5，6，f1，2，4，6，f得到等价的DFA见图3.10。3.3.4 确定有穷自动机的化简说一个有穷自动机是化简了的，就是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。即用一个状态代替所有与其等价的状态。所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何

29、输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。DFA的最小化就是寻求最小状态DFA。一、最小状态DFA的含义：1.没有多余状态(死状态)；2.没有两个状态是互相等价（不可区别）。两个状态s和t可区别：不满足兼容性同是终态或同是非终态；传播性从s出发读入某个a(a)和从t出发读入某个a到达的状态等价。两个状态s和t等价：如果由s出发能导出的所有串的集合与t出发能导出的所有串的集合相等，我们称状态s与状态t是等价的。状态等价例子见图3.11。C和D同是终态，读入a到达C和F，C和F同是终态， C和F读入a都到达C，读入b都到达E。 C和D等价。二、“分割法”（逐步分组试探法）DFA的

30、最小化算法的核心：把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。算法假定每个状态射出的弧都是完全的,否则，引入一个新状态，叫死状态，该状态是非状态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己。三、 DFA的最小化算法设有DFA M =（K,f,k0 ,kz）,最小状态DFA M：1. 因为不难证明，如果si是非终结状态，而sj是终结状态，那么si和sj一定互不等价（根据等价的定义可知，它们导出的符号串集不同）。所以开始可以把K中的终态和非终态分开，分成两个子集，形成一个基本划分： P2I1，I2 （

31、I1I2K，I1I2）2. 若此两个子集还可以进行划分，则作进一步的划分，形成Pm ,假定到某个时候Pm已经含有m个子集，记为：PmI1，I2，Im，设s和s是Ii中的任意两个状态，如果对某个a,存在Ij ，使 f(s,a), f(s,a)Ij ，则称s和s关于a是拟等价的。 如果存在s，sIi，使得对字母表中的某个符号a, s和s不为拟等价，则我们说Ii是可分的。 换句话说，令Ii s1，s2, ，sn ，如果对某个a，使得Iai f(s1,a)，f(s2,a)，f(sn,a)不全落在现行Pm的某一个子集Ij之中；即Iai这个集合中的元素分别属于I1，I2，Im中的几个不同集合，则Ii可分为

32、几个集合（至少可一分为二）。3转2,上述过程务必一再重复，直到P中的每个集合均是不可再分时为止。此时，P所含的集合数不再增加，即P中的每个集合中的状态互相等价，而不同集合间的状态互不等价。4.为P中的每一组选一代表，这些代表构成M的状态。把原来导入非代表状态的弧均导入其代表即可，即若k是一代表且f(k,a)=t,令r是t组的代表，则M中有一转换f(k,a)=r，M的开始状态是含有S0的那组的代表，M的终态是含有F的那组的代表。5.去掉M中的死状态。例：有DFA M见图3.11，求其极小化后的DFA M。在采用分割法后,求得极小化后的DFA M见图3.12。3.4 正规式与有穷自动机的等价性一、

33、定理：1.对于上的NFA M，可以构造一个上的正规式R，使得L（R）=L（M）。2.对于上的任一个正规式R ，可以构造一个上的NFA M ，使得L（M）=L（R）。二、把上的NFA M转换为一个上的正规式R转换方法我们把状态转换图的概念拓广，令每条弧可用一个正规式标记。1. 在M的状态图上加进两个结点x、y。从x结点用弧 连接到M的所有初态结点，从M的所有终态结点弧连接到y结点。形成一个与M等价的M，M只有一个初态和一个终态。2. 逐步消去M中的所有结点，直至只剩下x结点和y结点。在消结过程中，逐步用正规式来标记弧，其消结规则如下：最后x结点和y结点之间的弧上的标记就是所求的正规式R。例：有N

34、FA M如图3.14，求其等价的正规式R。最后,可求得其等价的正规式R=(a| b)* (aa| bb)(a| b)*。三、从正规式R 构造一个上的NFA M，使得L(M)= L( R )首先，对正规式R构造拓广转换图如图3.16。然后通过对R进行分裂和加进新结点的办法，逐步把这个图转变为：每条弧标记为中的一个字母或，其转换规则如图3.17。在整个分裂过程中，所有新结点均采用不同的名字，保留x和y为全图的唯一初态结点和终态结点，至此我们就可以得到一个与R 等价的NFA M。3.5 正规文法与有穷自动机的等价性一、定理：1.对于给定的正规文法GR，可以直接构造一个NFA M，使得L（M）=L（G

35、）。2.对于上的任一个NFA M ，可以直接构造正规文法GR ，使得L（ R ）=L（ M ）。 二、把给定的正规文法GR转换为一个上的NFA M构造规则：设GR=（VN，VT，P，R）， NFA M=（ K，f，S，Z）：1.令 = VT；2.令K = VN，S = R；即对G中的每个非终结符生成M的一个状态（不妨取相同的名字，G的开始符号是M的初态）；3.增加一个新状态Z，作为NFA M 的终态，ZK；4.对G中的形如AtB（其中t为终结符或；A和B为非终结符）的产生式，构造M的一个转换函数f（A，t）=B；5.对G中的形如At（其中t为终结符或；A和B为非终结符）的产生式，构造M的一个转

36、换函数f（A，t）=Z。三、把给定的上的NFA M转换为一个正规文法GR的构造规则：设NFA M=（ K，f，S，Z），GR=（VN，VT，P，R）：1.令VT = ；2.令VN = K即对G中的每个非终结符生成M的一个状态（不妨取相同的名字，G的开始符号是M的初态；3.令S=R（如果M有多个初态，应先拓广自动机，引入新初态x）；4.对M 的终态Z增加一个产生式： Z；5.对M的每一个转换函数f（A，t）=B可写G的一个产生式AtB（其中t为终结符或；A和B为非终结符）。3.6 词法分析程序的自动构造词法分析总控程序见图3.18。若对自动机的每一个状态赋予一定的功能，并把其边上的符号视为转移条件，那么自动机就成为一个程序了。以无符号数为例：给定语法图3.19，构造自动机见图3.20。最后可得到无符号数分析算法流图见图3.21。本章内容总结通过这一章的学习，我们了解了词法分析器的功能和输出形式，掌握了词法分析器设计的原理和方法，了解了正规表达式与有限自动机的有关概念、理论，了解了词法分析的自动产生原理。在下一章中，我们将讨论语法分析程序的构造。