词法分析江西师大计算机课件

1、1第三章第三章 词法分析词法分析 3.1 词法分析器的作用词法分析器的作用 3.2 词法单元的规约词法单元的规约 3.3 词法单元的识别词法单元的识别 3.5 有穷自动机有穷自动机 3.6 从正则表达式到自动机从正则表达式到自动机23.1 词法分析词法分析l主要任务主要任务是读入源程序的输入字符、将是读入源程序的输入字符、将它们组成它们组成单词单词，生成并输出一个，生成并输出一个词法单元词法单元序列，每个词法单元对应于一个序列，每个词法单元对应于一个单词单词。词法分析程序的其他任务词法分析程序的其他任务：滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，追踪换行

2、标志，复制出错源程序，宏展开，宏展开，3 词法单元词法单元由一个词法单元名和一个可选由一个词法单元名和一个可选的属性值组成。的属性值组成。 模式模式描述了一个词法单元的描述了一个词法单元的单词单词可能具可能具有形式。有形式。 单词单词是源程序中的一个字符序列，它和是源程序中的一个字符序列，它和某个词法单元的模式匹配，并被词法分某个词法单元的模式匹配，并被词法分析器识别为该词法单元的一个实例。析器识别为该词法单元的一个实例。包括保留字、标识符、运包括保留字、标识符、运算符、标点符号和常量等。算符、标点符号和常量等。4 词法分析器通常还要和词法分析器通常还要和符号表符号表进行交互。进行交互。当词法

3、分析器发现了一个标识符的当词法分析器发现了一个标识符的单词单词时，它将此时，它将此单词单词添加到符号表中。添加到符号表中。 在某种情况下，词法分析器会从符号表在某种情况下，词法分析器会从符号表中读取有关标识符种类的信息，以确定中读取有关标识符种类的信息，以确定向语法分析器传送哪个词法单元。向语法分析器传送哪个词法单元。5 符号表符号表：是一种供编译器用于保存有关：是一种供编译器用于保存有关源程序构造的各种信息的数据结构。源程序构造的各种信息的数据结构。 这些信息在编译器的分析阶段被逐步收这些信息在编译器的分析阶段被逐步收集并放入符号表，它们在综合阶段用于集并放入符号表，它们在综合阶段用于生成目

4、标代码。生成目标代码。 符号表的每个条目中包含与一个标识符符号表的每个条目中包含与一个标识符相关的信息，比如它们的字符串，类型、相关的信息，比如它们的字符串，类型、存储位置和其他相关信息。存储位置和其他相关信息。67 词法分析是编译过程中的一个阶段，词法分析是编译过程中的一个阶段，在语法分析前进行在语法分析前进行 。也可以和语法分。也可以和语法分析结合在一起作为一遍，由语法分析析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前程序调用词法分析程序来获得当前单词单词供语法分析使用。供语法分析使用。8 单词单词的描述工具的描述工具-正则表达式正则表达式 单词单词的识别系统的识别系统-有

5、穷自动机有穷自动机 设计词法分析程序设计词法分析程序93.2 词法单元的规约词法单元的规约 串和语言串和语言 字母表：一个有限的符号集合。字母表：一个有限的符号集合。 串：是该字母表中符号的一个有穷序列。串：是该字母表中符号的一个有穷序列。 语言：是某个给定字母表上一个任意的可数语言：是某个给定字母表上一个任意的可数的串集合。的串集合。 空集空集 和仅包含空串的集合和仅包含空串的集合 都是语言。都是语言。10串的相关术语串的相关术语 串串s的长度：记为的长度：记为|s|,指指s中符号出现的中符号出现的次数。次数。 串串s的前缀：从的前缀：从s的尾部删除的尾部删除0个或多个个或多个符号后得到的串

6、。符号后得到的串。 串串s的后缀：从的后缀：从s的开始删除的开始删除0个或多个个或多个符号后得到的串。符号后得到的串。 串串s的子串：删除的子串：删除s的某个前缀和某个后的某个前缀和某个后缀之后得到的串。缀之后得到的串。11 串s的真前缀、真后缀、真子串分别是的真前缀、真后缀、真子串分别是s的既不等于的既不等于 ，也不等于，也不等于s本身的前缀、本身的前缀、后缀和子串。后缀和子串。 串串s的子序列：从的子序列：从s中删除中删除0个或多个符号个或多个符号后得到的串，这些被删除的符号可能不后得到的串，这些被删除的符号可能不相邻。如：相邻。如：baan是是banana的一个子序列。的一个子序列。12

7、相关运算相关运算 串的连接运算串的连接运算:xy 空串是连接运算的单位元：空串是连接运算的单位元： 符号串集合的乘积：符号串集合的乘积： 例：符号串集合例：符号串集合A=ab,aa;B=ba,bb; 乘积乘积AB=abba,abbb,aaba,aabbsss,|ByAxxyAB13例：x=ab abababxababxabxx3210,串的方幂运算：串的方幂运算：ss，sisii100,并且对依此类推,321sssssssss例：A=a,b,cd,B=bc,ad,则,cdadcdbcbadbbcaadabcAB 14（自反）闭包：（自反）闭包：*称为称为的闭包，若的闭包，若*表示表示上上的所有

8、有穷长的串的集合，可表示为：（其中用的所有有穷长的串的集合，可表示为：（其中用U代表逻辑代表逻辑或或运算）运算）正闭包：正闭包：+称为的称为的正闭包，可表示为正闭包，可表示为 2* 32*例：例： =a,b+=a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb,. *= U +15语言是由句子组成的集合，是由一组符语言是由句子组成的集合，是由一组符号所构成的集合。字母表号所构成的集合。字母表上的一个语上的一个语言是言是上的一些符号串的集合上的一些符号串的集合 (字母表字母表上的每个语言是上的每个语言是* 的一个子集的一个子集)。 集合集合B=a,aa

9、,aaa, 是字母表是字母表上的一个语言上的一个语言或记作或记作w|w*且且w=an,n1 例：例： =a,b16有关语言的运算有关语言的运算是一个语言。是一个语言。 即即 是一个语言。是一个语言。 设设L是（是（上的）一个语言上的）一个语言,M是（是（上的）一个语言，上的）一个语言，则语言则语言L和和M的并，交，差，补是一个语言。的并，交，差，补是一个语言。 A.语言语言L和和M的并表示为的并表示为 LM，是一个语言，是一个语言，满，满足足: w|w is in L or is in M 如：如： L1 =a,b,y,z M1 =1,28,9 L1M1 =a,b, y,z，1,28,9 17

10、 B.语言L和M的连接是一个语言，记为 LM=st |sL且 tM 如： L1M1 =a1,b1,y1,z1,a2,b2a9z9 有L = L=L C. L的n次连接Ln= LL.L D. 语言L的闭包记为 L* L* = L0 L1 L2 . L0= ， Ln = L Ln-1 = Ln-1 L,n118如：（L1M1）* =a,b, y,z，1,28,9 ，a,1a,xyz,6789st. E. 语言L的正闭包记为 L+， L+= L1 L2 L3 .L+ = LL* = L*L L* = L+ 19例令例令L表示字母表表示字母表A，B，,Z,a,b,z,令令D表示数位的字母表表示数位的字

11、母表0，1，9，也可把，也可把L和和D看成所有串长度为看成所有串长度为1的语言。的语言。 LUD是字母和数位的集合。也可是说是包是字母和数位的集合。也可是说是包含含62个长度为个长度为1的串组成的语言。的串组成的语言。 LD： L4： L*： L（LUD）*： D+：20有穷自动机（有穷自动机（FA）自动机：按一定步骤识别每个字符的算法。自动机：按一定步骤识别每个字符的算法。有穷自动机作为一种识别装置，它能准确地识有穷自动机作为一种识别装置，它能准确地识别正规集，即识别正规式所表示的集合别正规集，即识别正规式所表示的集合.应用应用有穷自动机这个理论，为词法分析程序的自动有穷自动机这个理论，为词

12、法分析程序的自动构造寻找有效的方法和工具。构造寻找有效的方法和工具。确定有穷自动机确定有穷自动机DFADFA（P40P40）不确定有穷自动机不确定有穷自动机NFA NFA （P42P42）21确定的有穷自动机确定的有穷自动机DFADFA定义：定义：一个确定的有穷自动机（一个确定的有穷自动机（DFA）M是一个五是一个五元组：元组：M=（K，f，S，Z）其中）其中1.K1.K是一个有穷集，它的每个元素称为一个状是一个有穷集，它的每个元素称为一个状态；态；2.2.是一个有穷字母表，它的每个元素称为是一个有穷字母表，它的每个元素称为一个输入符号，所以也称一个输入符号，所以也称为输入符号表；为输入符号表

13、；22DFA定义3.3.f是转换函数，是在是转换函数，是在KK上的映射，即，上的映射，即，如如 f（ki，a）=kj，（，（kiK，kjK）就就意味着，当前状态为意味着，当前状态为ki，输入符为，输入符为a时，将转时，将转换为下一个状态换为下一个状态kj，我们把，我们把kj称作称作k ki的一个后的一个后继状态；继状态；4.SKK是唯一的一个初态；是唯一的一个初态；5.5.Z K是一个终态集，终态也称可接受状态是一个终态集，终态也称可接受状态或结束状态。或结束状态。23一个DFA 的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定义为：f（S，a）=Uf（V，a）=Uf（S，b

14、）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q24 DFA 的状态图表示l 一个一个DFA可以表示成一个状态图可以表示成一个状态图 (或称状或称状态转换图态转换图)。l假定假定DFA M含有含有m个状态，个状态，n个输入字符；个输入字符；l那么这个状态图含有那么这个状态图含有m个结点，每个结点最个结点，每个结点最多有多有n个弧射出；个弧射出；l整个图含有唯一一个初态结点和若干个终整个图含有唯一一个初态结点和若干个终态结点；态结点；l初态结点冠以箭头初态结点冠以箭头“ ”；终态结点用双；终态结点用双圈表示；圈表示；l若若 f(ki,a)=kj，则从状态结点

15、，则从状态结点ki到状态结点到状态结点kj画标记为画标记为a的弧；的弧； 25状态状态转换边转换边接受接受(终止终止)状态状态开始状态开始状态26判断字符串判断字符串abaabb,babb是否是否能被接受？能被接受？27例例1:确定有限自动机确定有限自动机dfa1表示所有正整数的集合。表示所有正整数的集合。 符号集符号集 = 0,1,2,.,9 ； 状态集合状态集合SS= S0 , S1 ； 开始状态开始状态 S0； 转换函数转换函数 :SS SS； (S0 ,d) = S1, (S1 ,d)= S1，其中，其中d ； 终止终止(接受接受)状态集状态集: S1 ；dd 确定有穷自动机确定有穷自

16、动机dfa1的状态转换图表示的状态转换图表示S0S128例例2： 实数可表示为实数可表示为d1d2.dn . d1d2.dm 。dd.dd确定有限自动机状态转换图确定有限自动机状态转换图 2 10329例例3：接受第二个位置上的数字为：接受第二个位置上的数字为2的所有正整数的所有正整数的确定有穷自动机的确定有穷自动机dfa2(包括所有一位的包括所有一位的)。 d2d 图图 确定有穷自动机确定有穷自动机dfa230例例3：考虑可带下划线的标识符集：考虑可带下划线的标识符集IDE， 其中其中L表示字母，表示字母，D表示数字。表示数字。 _L,DL,DL确定有限自动机确定有限自动机dfa331DFA

17、 的矩阵表示的矩阵表示 一个一个DFA还可以用一个矩阵表示，该还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列矩阵元素表示相应状态行和输入字符列下的新状态，即下的新状态，即k行行a列为列为f(k,a)的值。的值。abSUVUQVVUQQQQ字符字符状态状态3233不确定的有穷自动机不确定的有穷自动机NFA 一个不确定的有穷自动机（一个不确定的有穷自动机（NFA）M是一个五是一个五元组：元组：M=（K，f，S，Z） 有输入有输入 上的转换动作；上的转换动作；S1 S2 对每个状态对每个状态s和每个输入符号和每个输入符号

18、a,可以有多条标可以有多条标号为号为a的边离开。的边离开。S3 S1 S2aa3435有穷自动机有穷自动机A所能接受的字符串集所能接受的字符串集L(A) L(A)=| S00 Si* ， Si* F特例：空字符串集特例：空字符串集36从从NFA到到DFA的转换的转换 DFA是是NFA的特例的特例.对每个对每个NFA N一定一定存在一个存在一个DFA ，使得，使得 L(M)=L(N)。对每个对每个NFA N存在着与之等价的存在着与之等价的DFA M。 有一种算法，将有一种算法，将NFA转换成接受同样语言转换成接受同样语言的的DFA.这种算法称为这种算法称为子集法子集法(造表法）造表法）. 与某一

19、与某一NFA等价的等价的DFA不唯一不唯一.37 空移环路的寻找和消除空移环路的寻找和消除3839 NFA到到DFA的构造思想是该的构造思想是该DFA的每一的每一个状态对应个状态对应NFA的一组状态，该的一组状态，该DFA使使用它的状态去记录在用它的状态去记录在NFA读入一个输入读入一个输入符号后可能达到的所有状态。符号后可能达到的所有状态。40S表示表示N的单个状态，而的单个状态，而T表示表示N的一个状态的一个状态集集41 I=1, -closure(I)=1,2； I=5, -closure(I)=5,6,2； move(1,2,a)=5,3,4 -closure(5,3,4)=2,3,4

20、,5,6,7,8；12534687aaa42IaIbi,1,21,2,31,2,41,2,31,2,3,5,6,f1,2,41,2,41,2,31,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,fSABACBBADCCEDFDEFDFCE4f35621iaaaabbbb43 等价的DFAaCDBAEFSbaaaaabbbbbabF4445最小化最小化DFA 从任意一个接受相同语言的从任意

21、一个接受相同语言的DFA出发，出发，通过分组合并等价的状态，我们总是可通过分组合并等价的状态，我们总是可以构建得到这个状态数最少的以构建得到这个状态数最少的DFA。 如果分别从状态如果分别从状态s和和t出发，沿着标号为出发，沿着标号为x的路径到达的两个状态中只有一个是接的路径到达的两个状态中只有一个是接受状态，我们就说受状态，我们就说串串x区分状态区分状态s和和t。 如果存在某个能够区分状态如果存在某个能够区分状态s和状态和状态t的的串，那么它们就是串，那么它们就是可区分的可区分的。46工作原理工作原理 将一个将一个DFA的状态集合分划成多个组，的状态集合分划成多个组，每个组中的各个状态之间相

22、互不可区分。每个组中的各个状态之间相互不可区分。 分割法分割法47 DFA的最小化算法的最小化算法 DFA M =DFA M =（K,f, kK,f, k0 0, , k, kt t),),最小状态最小状态DFA M 1.1.构造状态的一初始划分构造状态的一初始划分： 终态终态k kt t 和非终态和非终态K- K- k kt t两组两组(group) (group) 2.2.对对施施用过程用过程如图如图构造新划分构造新划分newnew48 3 3. 如如new new =, =,则令则令 finalfinal= = 并并继续步骤继续步骤4 4，否则否则:=newnew重复重复2 . 2 .

23、4.4.为为finalfinal中的每一组选一代表，这中的每一组选一代表，这些代表构成些代表构成M的状态。若的状态。若k是是一代表一代表且且f(k,af(k,a)=t,)=t,令令r r是是t t组的组的代表，则代表，则M中有一转换中有一转换f(k,a(k,a)=r)=r M M 的开始状态是含有的开始状态是含有S S0 0的那组的代的那组的代表表 M M 的终态是含有的终态是含有F F的那组的代表的那组的代表 4950首先将M的状态分成两个子集：一个由终态(可接受态)组成，一个由非终态组成，这个初始划分P0为：P0=(1，2，3，4，5，6，7)，显然第一个子集中的任何状态都与第二个子集中的

24、任何状态不等价。 P1=(1，23，45，6，7)P2=(1，2，3，4，5，6，7) P3=(1，2，3，4，5，6，7) 51 C和和D同是终态同是终态,读入读入a到达到达C和和F, C和和F同是终态同是终态, C和和F读入读入a都到达都到达C,读入读入b都到都到达达E. C和和D等价等价aCDBAEFSbaaaaabbbbbabF520:S,A,B C,D,E,F1:S,A,B C,D,E,F 2: CDBAEFSbaaaaaabbbbbbaA S,BbB SDBASaaabbbbaa53将上图将上图NFA确定化和最确定化和最小化。小化。54l说一个有穷自动机是化简了的，即是说，说一个有

25、穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。个最小的与之等价的有穷自动机。l所谓有穷自动机的多余状态，是指这样的所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个入串也不能到达的那个状态；或者从这个状态没有通路到达终态。状态没有通路到达终态。55 识别识别DFA中可达状态的算

26、法：中可达状态的算法： 标记开始状态标记开始状态S。 给定任意标记过的状态给定任意标记过的状态A，如果对某个输入，如果对某个输入符号存在从状态符号存在从状态A到到B的转换，则标记每一的转换，则标记每一个这样的状态个这样的状态B。 重复上步，直到不再有可标记的状态为止。重复上步，直到不再有可标记的状态为止。 当该算法终止时，每一个未标记的状态当该算法终止时，每一个未标记的状态就是不可达状态。就是不可达状态。消除不可达状态消除不可达状态56确定有限自动机的程序实现确定有限自动机的程序实现 1.通过状态转换表通过状态转换表T 2.通过状态转换图直接转向通过状态转换图直接转向5758abijkLi :

27、 switch(CurrentChar) case a : goto Lj ; case b : goto Lk ; default : Error( ); 图图 用直接转向方法实现用直接转向方法实现DFA(a) Li : switch(CurrentChar ) case Eof : Accept ; case a : goto Lj ; case b : goto Lk ; default : Error( ) ; abjki59 正则表达式正则表达式,是定义正规集的数学工具。正是定义正规集的数学工具。正则（规）表达式（则（规）表达式（regular expression）是说明是说明单词

28、单词的模式的模式(pattern)的一种重要的的一种重要的表示法（记号），我们用以描述表示法（记号），我们用以描述单词单词符号。符号。 正则表达式：描述所有通过对某个字母表正则表达式：描述所有通过对某个字母表上的符号应用并、连接和闭包这些运算符上的符号应用并、连接和闭包这些运算符而得到的语言。而得到的语言。正则表达式正则表达式60 R字母表字母表上正则表达式的集合上正则表达式的集合L(R) R所表示的语言，即符号串的集合所表示的语言，即符号串的集合(1) 是是 正则表达式，即正则表达式，即R 。其中。其中L()= 。(2) 是正则表达式，即是正则表达式，即 R 。其中。其中L( )= 。(3)

29、 c 是正则表达式，即是正则表达式，即c R 。其中。其中L(c)= c 。设设A和和B是是 正则表达式，即正则表达式，即A R ，B R ，则有，则有 ( A ) R ，L( (A) )= L(A) A | B R ，L( A | B )= L(A) L(B) A B R ，L( A B )= L(A ) L(B) A* R ，L( A*)= L(A)*61令令 =a，b， 上的正则表达式和相上的正则表达式和相应的正规集的例子应的正规集的例子 a a b ab (a b)(a b) a (a b) (a b) (aa bb)(a b) aa,babaa,ab,ba,bb ,a,aa, 任意个

30、任意个a的串的串 ,a,b,aa,ab,bb 所有由所有由 a和和b组成的串组成的串 所有含有两个相继的所有含有两个相继的a或两个或两个相继的相继的b组成的串组成的串62令令 =l，d，则，则 上的正规式上的正规式 r=l(l d) 定义的正规集为定义的正规集为: l,ll,ld,ldd,其中其中l代表字母代表字母,d代表数字代表数字,正规式正规式 即是字母即是字母(字母字母|数字数字) ,它表示的正规集中的每个元素它表示的正规集中的每个元素的模式是的模式是“字母打头的字母数字串字母打头的字母数字串”,就是就是Pascal和和 多多数程序设计语言允许的的标识符的词法规则数程序设计语言允许的的标识符的词法规则. =d，.，e，+，-, 则则 上的正规式上的正规式 d (.dd )(e(+ - )dd ) 程序设计语言的单词都能用正规式来定义程序设计语言的单词都能用正规式来定义. .表示的是无符号数的集合。表示的是无符号数的集合。63RealC = D+.D+假设有假设有D = 0,1, ., 9 ，则，则 实常数的集合实常数的集合RealC可用可用 正则表达式定义为如下正则表达式定义为如下: 64 0打头的任意0、1串所对应的正则表达式是什么？ 0（0|1）* =0、1每个1都有0直接跟在右边。 0*（100*）*