第04章、词法分析

1、第4章 词法分析表格管理程序错误处理程序2 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。4.1 词法分析程序 4.2 正规表达式与正规集（正规语言）4.3 有限自动机4.4 正规文法和有限自动机的转换 4.5 正规式和有限自动机的等价性3本章重点 单词的描述工具 单词的识别系统 设计和实现词法分析程序首先需要描述和刻画程序设计语言中的原子单位单词，其次需要识别单词和执行某些相关的动作。描述程序设计语言的词法的机制是正规表达式，识别机制是有穷状态自动机。44.1 词法分析程序4实现词法分析（lexical analysis）的程序逐个读入源程序字符并按

2、照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括关键字(保留字)、标识符、常数、运算符、界符等。词法分析是编译过程中的一个阶段，在语法分析前进行 ，也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。5词法分析的任务： 主要任务：读源程序，产生单词符号其他任务：滤掉空格，跳过注释、换行符删除注释进行词法检查，报告所发现的错误建立符号表6单词的分类（1）关键字：或称为保留字，是特定的字母序列，在相应的程序设计语言中表示特殊含义。（2）标识符：由用户定义的串，在程序中常用做常量名、变量名、过程名等。（3）常数：各种类型的常数，包括整型

3、、实型、布尔型、文字型等，如100，10.12，TRUE，“ABC”等。（4）运算符：包括算术运算符和逻辑运算符号，如+、*、 0) b = b+1; (1)关键字if (3,if) (2)左括号( (4,( ) (3)标识符a (1,指向a的符号表入口) (4)运算符 (4,) (5)常数0 (2,0) (12)界符; (5,;)8不同分类方法的例子：下述C+代码段：while (i=j) i-;经词法分析器处理以后，它将被转换为如下的单词符号串。4( while , _ )4( ( , _ )4( id, 指向i的符号表指针 )4( = , _ )4( id, 指向j的符号表指针 )4(

4、) , _ )4( id, 指向i的符号表指针 )4( - , _ )4( ; , _ )9词法分析程序的实现方式4词法分析单独作为一遍优点：结构简单、各遍功能单一缺点：效率低10源程序词法分析程序语法分析程序Tokenget token.4词法分析程序作为单独的子程序优点：无须在外存中保留整个源程序的内码形式。11 将词法分析工作分离的原因简化设计改进编译效率增加编译系统的可移植性 124.2 正规表达式与正规集（正规语言） 程序设计语言中的单词是基本语法成分,单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造。13正 规 式正规式也称正则表达式，正规表

5、达式（regular expression），是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。14定义（正规式和它所表示的正规集）： 设字母表为，辅助字母表=，。1. 和都是上的正规式，它们所表示的正规集分别为和 ；2. 任何a ，a是上的一个正规式，它所表示的正规集为a；153. 假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1 e2, e1e2, e1也都是正规式，它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L

6、(e2)和(L(e1)。4. 仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。16正规式中的符号其中的“”读为“或”（也有使用“+”代替 “” 的）； “ ”读为“连接”； “”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“ ”、“” 。连接符“ ”一般可省略不写。“”、“ ”和“” 都是左结合的。17例令=a，b， 上的正规式和相应的正规集的例子有：正规式 正规集a aab a,bab ab(ab)(ab) aa,ab,ba,bba ,a,a, 任意个a的串18 正规式 正规集 (a b)

7、,a,b,aa,ab 所有由a 和b组成的串(a b) (aa bb)(a b) 上所有含有两个相继 的a或两个相继的b组成的串19 讨论下面两个例子例4.1 令 =l，d，则 上的正规式 r=l(l d) 定义的正规集为: l,ll,ld,ldd,其中l代表字母,d代表数字,正规式 即是 字母(字母|数字) ,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和多数程序设计语言允许的的标识符的词法规则.例4.2 =d， ，e，+，-,则 上的正规式d ( dd )(e(+ - )dd )表示的是无符号数的集合，其中d为0 9的数字。比如2、21.59、3.6e2、4

8、71.88e-1等都是该正规集中的元素。 程序设计语言的单词都能用正规式来定义20正规式的等价若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如： e1= (a b)， e2 = b a又如： e1= b(ab) , e2 =(ba) b e1= (a b) , e2 =(a b ) 21正规式服从的代数规律设r,s,t为正规式，正规式服从的代数规律有：1. r s=s r “或”服从交换律2. r (s t)=(r s) t “或”的可结合律3. (rs)t=r(st) “连接”的可结合律4. r(s t)=rs rt (s t)r=sr tr 分配律5. r

9、=r, r =r 是“连接”的恒等元素 零一律6. r r=r r = r rr “或”的抽取律 224.3 有限自动机 有限自动机(也称有穷自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有限自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。 有限自动机分为两类： 确定的有限自动机(Deterministic Finite Automata) 不确定的有限自动机(Nondeterministic Finite Automata) 23关于有限自动机我们将讨论如下题目确定的有限自动机DFA不确定的有限自动机NFANFA的确定化

10、DFA的最小化24确定的有限自动机DFADFA定义：一个确定的有限自动机（DFA）M是一个五元组：M=（K，f，S，Z）其中1. K是一个有穷集，它的每个元素称为一个状态；2. 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；25DFA定义(续）3. f是转换函数，是在KK上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4. SK是唯一的一个初态；5. Z K是一个终态集，终态也称可接受状态或结束状态。26一个DFA 的例子：DFA M=（S，U，V，Q，a，b，f

11、，S，Q）其中f定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q27DFA可以表示成一个状态图一个DFA可以表示成一个状态图(或称状态转换图)。假定DFA M含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=”或标以“-”，终态结点用双圈表示或标以“+”，若 f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧；28 DFA 的状态图表示bSUVQaaaba，bb29DFA还可以用一个矩阵表示一个

12、DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头“=”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。30DFA 的矩阵表示abSUVUQVVUQQQQ字符状态0001以后我们 用*表示终态书上：用0表示非终态 用1表示终态31 为了说明DFA如何作为一种识别机制，我们还要理解下面的定义 *上的符号串t在DFA M上运行一个输入符号串t，（将它表示成Tt1的形式，其中T，t1 *）在DFA M=（K，f，S，Z）上运行的定义为： f（Q， Tt1）=f（f（Q，T），t1

13、） 其中QK 扩充转换函数f为 K*K上的映射，且： f（ki， ）= ki32*上的符号串t被DFA M接受M=（K，f，S，Z）若t *，f(S，t)=P，其中S为 M的开始状态，P Z，Z为终态集。则称t为DFA M所接受（识别）.33例：证明t=baab被下图的DFA所接受。bSUVQabba, baaf（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属于终态。得证。34DFA M所能接受的符号串的全体记为L(M)，对于任何两个有限自动机M和M，如果L(M)=L(M)，则称M与

14、M是等价的。 结论： 上一个符号串集V 是正规的，当且仅当存在一个 上的确定有限自动机M，使得V=L(M)。35DFA的确定性表现在：转换函数f: KK是一个单值函数，也就是说，对任何状态kK，和输入符号a，f(k,a)唯一地确定了下一个状态。从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。36例：DFA M=(0,1,2,3,a,b,f,0,3)其中： f（0,a)=1; f（0,b)=2 f（1,a)=3; f（1,b)=2 f（2,a)=1; f（2,b)=3 f（3,a)=3; f（3,b)=3问：有几个状态,几个输

15、入字符？并画出其转换图。该自动机可识别符号串abaab和abab吗？37解：有0，1，2，3共四个状态。输入字符为a,b两个。其状态转换图如下：012abababa,b3对于符号串abaab，可被识别。对于符号串abab，不能被识别。38不确定的有限自动机NFA定义 NFA M= K， ，f，S，Z ，其中K为状态的有穷非空集， 为有穷输入字母表，f为K * 到K的子集（2 K）的一种映射（即K *2k ），S K是非空初始状态集，Z K为终止状态集.显然，NFA也可以表示成一张状态转换图。假定NFA含有m个状态、n个输入字符，那么，这张图含有m个状态结点，每个结点可以射出若干条箭弧和别的结点

16、相连接，每条箭弧用*上的一个字（不一定要不同的字而且可以是空字）作标记（称为输入字），整张图至少含有一个初态和若干个（可以是0个）终态结点。某些结点既可以是初态也可以是终态结点。39例子 NFA M=（S，P，Z，0，1，f，S，P，Z），其中 ： f（S，0）=P f（Z，0）=P f（P，1）=Z f（Z，1）=P f（S，1）=S，ZSPZ00111140矩阵表示01SPS,ZP Z*ZPP41f为K * 到K的子集（2 K）的一种映射具有转移的不确定的有限自动机 123abc42有如下定理:对任何一个具有 转移的不确定的有限自动机 NFA N，一定存在一个不具有 转移的不确定的有限自动

17、机NFA ，使得L(M)=L(N)。 与上例等价的一个NFA:2acbb31acacbb123abc43类似DFA, 对NFA M= K， ，f，S，Z 也有如下定义:*上的符号串t在NFA M上运行一个输入符号串t，（我们将它表示成Tt1的形式，其中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所接受（识别）44 *上的符号串t被NFA M接受也可以这样理解 对于中的任何一个串t，若存在一条从某一初态结点到某一终态结点的道路，且这条道路上所有

18、弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结点又是终态结点，或者存在一条从某个初态结点到某个终态结点的道路，其上所有弧的标记均为，那么空字可为M所接受。45举例0001111010001110000001不能识别：000110046NFA M所能接受的符号串的全体记为L(M)结论： 上一个符号串集V 是正规的，当且仅当存在一个 上的不确定的有限自动机M，使得V=L(M)。47例：(0|1)*(000|111)(0|1)*48 定理：DFA是NFA的特例，对每个NFA N一定存在一个DFA ，使得 L(M)=L(N)。对

19、每个NFA N存在着与之等价的DFA M。 有一种算法，将NFA转换成接受同样语言的DFA，这种算法称为子集法。 与某一NFA等价的DFA不唯一。49从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是： DFA的每一个状态对应NFA的一组状态. DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。50定义对状态集合I的几个有关运算：1. 状态集合I的-闭包： 表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。 状态集合I的任何状态S都属于-cl

20、osure(I)。2. Ia：从I中的状态经过一条a弧(前后可跳过任意条弧)而到达的状态的全体。51状态集合I的有关运算的例子若I=1, 则 -closure(I)=1,2；若I=5, 则 -closure(I)=5,6,2；若I=1,2, 则 Ia=2,3,4,5,6,7,8；(备注：不需要掌握书上讲的move集合)12534678aaa52NFA转换为DFA的思想：u将从状态S出发经过任意条 弧所能到达的状态作为DFA的初态S；u从S出发，把遇到输入符号a所转移到的后继状态集作为DFA的新状态；u如此重复，直到不再有新的状态出现为止。53 NFA确定化算法: 假设NFA N=(K, ,f,

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

22、. Se，其中Si Sk. Se S且Si , Sk,. Se Kt55 NFA的确定化 例子47356210aaaabbbb56若要将上图的NFA转换为DFA，步骤如下：4（1）构造一张表，它共有+1列；4（2）第一行第一列为 -closure(0)；4（3）求Ia、Ib并检查，未在第一列出现过者，填入下行首列；4（4）重复步骤（3）；4（5）将状态子集重新命名。5747356210aaaabbbb-closure(0)I S A B A C B B A D *C C E *D F D *E F D *F C E 58 等价的DFAaCDBAEFSbaaaaabbbbbabF59确定有限自动

23、机的化简 说一个有限自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。 所谓有限自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。60 DFA的最小化就是寻求最小状态DFA最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t等价，满足：(或可区别：不满足）一致性(或兼容性)同是终态或同是非终态；蔓延性(或传播性)从s出发读入某个a a和从 t出发读入某个a到达的状态等价。

24、61 例：C和F是等价的。因为C和F同是终态, C和F读入a都到达C,读入b都到达E，所以C和F等价。aCDBAEFSbaaaaabbbbbabF62最小状态DFA对于一个DFA M =（K,f, k0,kt)，存在一个最小状态DFA M =（K,f, k0,kt)，使L(M)=L(M). 63“分割法”DFA的最小化算法的核心 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。结论：终态和非终态是可区别的（不等价），因为从终态可以识别到达终态，而从非终态则不能识别到达终态。 64 DFA的最小化算法 DFA M =（K,f,

25、 k0, kt）,最小状态DFA M 1. 构造状态的一初始划分： 终态kt 和非终态K- kt两组(group) 2. 对根据最小化原则，构造新划分new 3. 如new =,则令 final= 并继续步骤4，否则:=new重复2 . 4. 为final中的每一组选一代表，这些代表构成M的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M中有一转换f(k,a)=r，M 的开始状态是含有S0的那组的代表，M 的终态是含有F的那组的代表 5. 去掉M中的死状态.65DFA最小化算法的核心分割法。步骤如下：4（1）将所有状态分成两个子集：终态集和非终态集；4（2）把等价的状态构成一个子集

26、，若不等价继续划分；4（3）结束后，重新标号或从每个子集中选一个状态做代表。66IIaIbSABACBBAD*CCE* DFD* EFD* FCEDFA的最小化例子 M=S,A,BC,D,E,F S,A,Ba=A,C 不包含于第1次划分出的任意集合 S,A,B不等价，继续得到第2次划分为：S,BA S,Bb =B,D 不包含于第2次划分出的任意集合 S,B不等价，继续得到第3次划分为：SAB C,D,E,Fa=C,F C,D,E,Fb=D,E C,D,E,F等价故最后结果为：M=SABC,D,E,FaCDBAEFSbaaaaabbbbbabF67IIaIbSABACBBAC*CCCDFA的最小

27、化例子(续) 因C,D,E,F等价，故从C,D,E,F中选C作为代表，出现D,E,F的地方一律用C代替，如下：aCDBAEFSbaaaaabbbbbabF最小化后DFA的为：CBASaaabbbba例子4画出能够识别C语言注释/* */的DFA4状态1：注释开始状态。4状态2：进入注释体前的中间状态。4状态3：表明目前正在注释体中的状态。4状态4：离开注释前的中间状态。4状态5：注释结束状态，即接受状态。 1/2534/*othersothers有限自动机的一些应用4用于某些重要软件的设计和构造设计和检查数字电路行为的软件;扫描如网页族等大规模文本以发现字、词或其它结构的出现频率的软件;验证所

28、有只有有限多个不同状态的系统的软件，这类系统包括通信协议和信息安全交换协议。4文献举例：基于协议分析状态机的入侵检测系统有限自动机在BBS信息监测系统中的运用70定理： 由任意正规文法G定义的语言必然能被一个NFA M所接受。 即L（G）L（M） 4.4 正规文法和有限自动机的转换71定理：定理：由任意正规文法由任意正规文法G定义的语言必然能被一个定义的语言必然能被一个NFA M所所接受。即接受。即L（G）L（M）构造方法：构造方法： 设正规文法设正规文法G（VN，VT，P，S），），构造一个与构造一个与G等价的等价的有限自动机有限自动机NFA M（K， ，f，S，Z），），其中：其中： (1

29、) KVN U Z，Z为一个新增加的终态为一个新增加的终态； (2) =VT (即字母表与即字母表与G的终结符集相同的终结符集相同)； (3) 开始符号开始符号S作为开始状态作为开始状态S；f的定义为：的定义为：当当A aB P，则构造：则构造： f（A，a）= B当当A a P, 则构造：则构造： f（A，a）= Z当当A P, 则构造：则构造： f（A， ）= Z72例：设有正规文法G=(S,A ,a,b, P,S)，其中P： SaA AaA|bS|a 试构造与G等价的有限自动机M。解： 设NFA M=(K, , f, S, Z)K=S,A,Z =a,b S = S Z =Z转换函数：n对

30、于产生式SaA，有f(S,a)=An对于产生式AaA，有f(A,a)=An对于产生式AbS，有f(A,b)=Sn对于产生式Aa， 有f(A,a)=ZSAZ开始aaab73 设正规文法G( S，A，B，a，b，P，S ) P： S aA | bB | aA aA | aS | bBB bB | b | a构造相应的 NFA M。74定理：设有限自动机 M 接受的语言为L(M)则存在正规文法G，它产生的语言L(G)L(M)。证明思路：构造一个正规文法G，使它接受由NFA M定义的语言。构造方法： 设 M（K， ，f，S，Z），构造一个正规文法G（VN，VT，P，S），其中VNK， SSP定义为：

31、若f（A，a）B ，则A aB 在P中 对终态 Z，增加一产生式： Z 75）例：设有DFA M =(A,B,C,D, a,b, f , A, D ) 其中转换函数如图所示， 试构造与之等价的正规文法G。解：构造正规文法G=(VN,VT,P,S) VN=A,B,C,D VT=a,b S=A 产生式集合Pf(A,a)=B， AaBf(A,b)=C， AbCf(B,a)=D， BaDf(B,b)=B， BbBf(C,a)=C， CaCf(C,b)=D， CbDD Z， D ABCDaaabbb开始构造的文法G:GA: AaB|bC BaD|bB CaC|bD D 76课堂练习4构造同NFA M等价

32、的正规文法G。4解：bAaBbCDabbaGA：A aB|bD B bC C aA|bD| D aB|bD|774.5 正规式和有限自动机的等价性 词法分析程序的自动构造方法，基于有限自动机和正规表达式的等价性，即： 1.对于上的一个NFA M，可以构造一个上的正规式R,使得L(R)=L(M)。2.对于上的一个正规式R，可以构造一个上的NFA M，使的L(M)=L(R)。1、在M上加两个结点S、Z，从S结点用弧到M的所有初态，从M的所有终态用到Z结成与M等价的M，M只有一个初态S和一个终态Z。03214a, ba, ba, bbbaaS03412Zaa, ba, ba, babb2、逐步消去M中的所有结点，直至剩下S和Z结点，在消去过程中，逐步用正规式来标记弧，消去规则如下：R1R2123R1R21312R1R2R1|R2121R1R323R2R1R2*R313继续消去S03412Zaa, ba, ba, babbS042Zaaa|ba| ba|bbb81继续消去S042Zaaa|ba| ba|bbbS0Zaa(a|b)*a|bbb(a|b)*82继续消去S0Zaa(a|b)*a|bbb(a|b)*SZ(a|b)*(aa|bb)(a|b)*83（1）对NFA M构造一个广义的状态图，其中只有一个