《第四章词法分析课件》由会员分享，可在线阅读，更多相关《第四章词法分析课件（78页珍藏版）》请在金锄头文库上搜索。
1、第四章 词法分析(Lexical Analysis) 主要内容：单词的描述工具：正规文法和正规式单词识别系统：有穷自动机词法分析程序的设计词法分析程序的自动构造原理学习目标:v掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换，NFA到DFA的转换、DFA的化简v理解：正规文法、正规式、DFA的概念、NFA的概念v了解：词法分析程序的自动构造工具4.1单词的描述工具4.2有穷自动机4.3正规式和有穷自动机的等价性4.4正则文法和有穷自动机间的转换4.5词法分析程序的设计4.6词法分析程序的自动构造工具4.1 单词的描述工具作用: 描述单词的构成规则,基于这类描述工具建立词法分析技术,
2、进而实现词法分析程序的自动构造.工具有: 正规文法 正规式(Regular Expression)4.1.1正规文法多数程序设计语言单词的语法都能用正规文法(3型文法)描述正规文法回顾文法的任一产生式的形式都为AaB或Aa，其中A ，BVN ，a VT 。正规文法描述的是VT*上的正规集例如 :用l表示az中的任一英文字母，d表示09中任一数字描述标识符的正规文法为llldld描述无符号整数的正规文法 dd4.1.2正规式(正则表达式)RegularExpression对于字母表，我们感兴趣的是它的一些特殊字集正规集。正规式是描述正规集的方便工具正规式与正规集的递归定义1.和都是上的正规式，它
3、所表示的正规集分别为和；2.任何，是上的正规式，它所表示的正规集为；3.假定1和2都是上的正规式，他们所表示的正规集分别为(1)和(2)，那么，以下也都是正规式和他们所表示的正规集；正规式正规式正规集正规集(1)(1)12(1) (2)1.2(1)(2)1 (1)说明:算符的优先顺序: . .和都是左结合4.仅由有限次使用上述三步定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。例子令=a，b， 上的正规式和相应的正规集有正规式正规集aaaba,babab(ab)(ab)aa,ab,ba,bba ,a,aa,任意个a串(ab) ,a,b,aa,ab 所有由a和b 组成的串正
4、规式的代数性质设 r，s，t 是正规式，正规式服从的代数规律是：1.rs = sr “或”满足交换律2.r(st) = (rs)t“或”的结合律3.(rs) t= r (st)“连接”的结合律4.r(st) = rsrt(rs) t=rtst分配律5.r=r=r是“连接”的恒等元素6.rr=r “或”的抽取律 r=rrr程序中的单词都能用正规式来定义 令l为az的字母，d为09的数字e1= l ( l | d)*e1表示标识符集合e2= dd* e2表示无符号整数注：llldld 正规式比正规文法更容易让人理解单词是按怎样的规律构成的，且可以从某个正规式自动地构造识别程序。4.1.3正规文法和
5、正规式间的转换等价性：对任意一个正规文法，存在一个定义同一语言的正规式对任意一个正规式，存在一个定义同一语言的正规文法1.将上的一个正规式r转换成文法G=(VN,VT,S,P)VT= ,首先形成产生式Sr,S为G的开始符不断利用下面的规则做变换,直到每个产生式最多含有一个终结符为止原产生式原产生式变换后产生式变换后产生式规则规则1 1AxyAxyAxB ByAxB By规则规则2 2AxAx* *y yAxA AyAxA Ay规则规则3 3Ax|yAx|yAx AyAx Ay其中B为一新非终结符例:将R=a(a|d)*转换成相应的正则文法令转换成文法G=(VN,VT,P,S)其中VT=a,d，
6、文法开始符为S首先形成Sa(a|d)*,然后变换SaAA(a|d)*A(a|d)A AAaA AdA最终有产生式：SaA ， A ， AaA， AdA2.将正规文法转换成正规式将每条产生式改写为正规式用代入法解正规式方程组最后只剩下一个开始符号定义的正规式,其中不含非终结符正规文法到正规式的转换规则:文法产生式文法产生式正正规规式式规则规则1 1 AxB ByAxB ByA=xyA=xy规则规则2 2 AxA|yAxA|yA=xA=x* *y y规则规则3 3 Ax AyAx AyA=x|yA=x|y例：将文法GS转换成正规式G：SaA|aAdA|d先由产生式得:S=aA|aA=d*d将A代入
7、S中得:S=ad*d|a利用正规式变换得S=a(d*d|)=ad*说明:d*d|=(|d|dd|)d|=d|dd|=d*所求正规式为ad*4.2有穷自动机(也称有限自动机)是一种识别装置作用:能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合意义:为词法分析程序的自动构造寻找特殊的方法和工具。分类:确定的有穷自动机(Deterministic Finite Automata)不确定的有穷自动机(Nondeterministic Finite Automata)4.2.1确定的有穷自动机（DFA）定义:一个DFA M是一个五元组:M=（K，f，S，Z）1.K是一个有穷集，它的每个
8、元素称为一个状态2.是一个有穷字母表，它的每个元素称为一个输入字符3.f是一个从K X K的单值部分映射。f(ki,a)=kj意味着当前状态为ki、输入字符为a时，将转换到下一状态kj4.SK，是唯一的初态5.Z K,是一个终态集，终态也称为可接受状态或结束状态。例DFA M=（S，U，V，Q,a，b,f,S,Q）其中f定义为： f（S，a）=Uf（S，b）=V f（V，a）=Uf（V，b）=Q f（U，a）=Qf（U，b）=V f（Q，a）=Qf（Q，b）=QDFA表示成状态转换图(TransitionDiagram)每个状态对应图中的一个结点：初态为唯一初态结点，用=标记；终态对应终态结点
9、，用双圈表示。若有f(ki,a)=kj，则从结点ki到结点kj画标记为a的弧。例 DFA M=（S，U，V，Q,a，b,f,S,Q） f（S，a）=Uf（S，b）=V f（V，a）=Uf（V，b）=Q f（U，a）=Qf（U，b）=V f（Q，a）=Qf（Q，b）=Q状态转换图表示为:bSUVQaaaba，bbDFA表示成状态转换矩阵例 DFA M=（S，U，V，Q,a，b,f,S,Q） f（S，a）=Uf（S，b）=V f（V，a）=Uf（V，b）=Q f（U，a）=Qf（U，b）=V f（Q，a）=Qf（Q，b）=Q字符状态0001行表示状态，用双箭头“=”标明初态；否则第一行即是初态列表
10、示输入字符相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值相应终态行在表的右端标以1，非终态标以0DFA识别(接受)的字符串对于*中的任何字符串t，若存在一条从初态结到某一终态结的通路，且该通路上所有弧的标记符连接成的字符串等于t，则称t可以为DFAM所识别若DFAM的初态结同时又是终态结，则可为M所识别。bSUVQaaaba，bbbaab为DFA所接受DFA M所能接受的符号串的全体记为L(M).结论： 上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得 V=L(M)确定性表现在:转换函数f:KK是一个单值函数，也就是说，对任何状态kK，和输入符号a，f(k,
11、a)唯一地确定了下一个状态。4.2.2不确定的有穷自动机（NFA）NFA的定义一个不确定的有穷自动机M是一个五元组： M=（K，f，S，Z），其中1.K是一个有穷集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个输入字符；3.f是一个从K X *至K的子集的映射；4.S K，是一个非空初态集5.Z K，是一个终态集。例 NFA M=（S，P，Z,0，1,f,S，P,Z）其中 f（S，0）=P f（S，1）=S，Z f（Z，0）=P f（Z，1）=P f（P，1）=Z矩阵表示:01SP S,ZPZZP P001SPZ00,1111状态图表示:说明：因为NFA的转换函数f为K
12、 * 到K的子集的一种映射，所以NFA中可以有转移例：123abcNFA识别的字符串对于*中的任何字符串t，若存在一条从某一初态结到某一终态结的通路，且该通路上所有弧的标记字依次连接成的串（不理睬那些标记为的弧）等于t，则称t可以被NFAM所识别。若M的某个初态结又是终态结，或者存在一条从某个初态结到某个终态结的通路，那么为M所识别。123abcNFA M 所能识别的符号串的全体记为L(M)NFA与DFA的等价性DFA是NFA的特例对于任何两个有穷自动机 M和M，如果L(M)=L(M)，则称M与M是等价的对于每个NFA M，存在一个与其等价的DFA M4.3.3NFA到DFA的转换从NFA构造
13、DFA的算法子集法字符状态000101SP S,ZPZZP PDFA的状态转换矩阵NFA的状态转换矩阵1.基本思想:让DFA 的每个状态对应NFA 的一个状态集合。即DFA用它的一个状态记录在NFA读入一个输入符号后可能达到的所有状态。001合并如果有，则把S2状态合并到S1状态。S1S2ijkmaban（a）i,jmkaabn（b）2.转换需解决的问题：状态合并0123aabc（a）01,23abc（b）3.对状态集合I的有关运算：状态集合I的闭包_closure(I)是状态集I中的任何状态S以及经任意条弧而能到达的状态的集合。IIS2S2S1S1S3S3_Closure(I)以下将_clo
14、sure(I)简写为Closure(I) Closure(I) =I Sk | 存在 Sj Sk，Sj Closure(I) ，Sk Closure(I) 注意：这是一个递归定义，通过多条边才能到达的状态也将被合并到closure中设I=0，则_closure( I )=例NFA :100124536789ababb74,2,1,0,Ia子集。I是状态集，由I中的状态出发，经过一条a弧可能到达的状态的集合称为Move（I，a），则Ia=_closure(Move(I,a)Ib = _closure( 例NFA :100124536789ababb设I=0,1,2,4,7则Ia = _closu
15、re( )3,8= 3, 8,6, 7,1,2,4 5 6, ) = 5, 7, 2,1, 44.NFA确定化算法假设NFA N=(K,f,K0,Kt)按如下办法构造一个DFA M=(S,d,S0,St)，使得L(M)=L(N)：1)M的状态集S由K的一些子集组成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的状态。2)M和N的输入字母表是相同的，即是；3)转换函数d(S1 S2,. Sj,a)= R1R2. Rt 其中R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4)S0=-closure(K0)为M的开始状态；5)St=Si S
16、k. Se，其中Si Sk. SeS且Si , Sk,. SeKt5.构造DFA的状态集的算法 假设NFA N=(K,F,K0,Kt) 构造的DFA为 M=(C,D,C0,Ct)，状态集C=(T1,T2,Ti),其中T1,T2,Ti都是状态集K的子集。1.开始，令_closure(K0)为C中唯一成员，并且它是未被标记的。2.while（C中存在尚未被标记的子集 T ）do标记 T；for （每个输入字符a） doU:= Ta ; （即_closure ( Move( T, a ) )）if （U不在C中） then将U做为未被标记的子集加入C中0,1, 7,2,45,6,7,1,2,4 T2
17、8,3,6,7,1,2,4 T110,5,6,7,1,2,410,5,6,7,1,2,4 T48,3,6,7,1,2,4 T19,5,6,7,1,2,45,6,7,1,2,4 T28,3,6,7,1,2,4 T15,6,7,1,2,49,5,6,7,1,2,4 T38,3,6,7,1,2,4 T18,3,6,7,1,2,45,6,7,1,2,4 T28,3,6,7,1,2,4 T1IbIaI100124536789ababbT0T1T2T3T4000016.重新命名DFA的状态得到DFA的状态转换矩阵和转换图如下: S a b0 1 21 1 32 1 23 1 44 1 240b213bba
18、aababa000014.2.4确定有穷自动机的化简化简的任务:去掉多余状态，合并等价状态多余状态：从开始状态出发无法到达的状态。等价状态：两个状态s和t等价的条件是:1.一致性条件状态s和t必须同为可接受状态或不可接受状态2.蔓延性条件对于所有输入符号,状态s和状态t必须转换到等价的状态里可区别状态：不等价状态。如终态与非终态是可区别的。aCDBAEFSbaaaaabbbbbab例C和F同是终态, C和F读入a都到达C,读入b都到达E,所以 C和F等价S和C不等价，因为C是终态，而S不是终态“分割法”DFA的最小化算法: 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是
19、可区别的，而同一子集中的任何两个状态都是等价的.例DBASaaabbbba,CDBAEFSbaaaaaabbbbbba1.将M的状态分成非终态和终态集S,A,B C,D,E,F2 寻找子集中不等价状态S,A,B=SA,B=SABC,D,E,F3令D代表C,D,E,F a bS A BA C BB A DC C ED F DE F DF C EP=S,A,B,D在等价状态子集中选一状态做代表，消去其他状态，把从消去状态射出和射入的弧都引到代表状态，子集中有初态，则代表状态也是初态4.3 正规式和有穷自动机的等价性等价性1.对于上的一个NFA M，可以构造一个上的正规式R,使得L(R)=L(M)。
20、2.对于上的一个正规式R，可以构造一个上的NFA M，使的L(M)=L(R)。从正规式构造NFA“语法制导”法:按正规式的语法结构指引构造过程正规式的基本语法结构的构造规则对于正规式 ,构造的NFA为:yx对于正规式x,x 构造的NFA为:yxxyx对于正规式,构造的NFA为:复合正规式e的构造规则先构造如下的NFAyxe然后按下述三种情况进行分解，直至每条弧上标记一个字符e1Xye=e1|e2e2X1e1ye2e=e1e2X1ye1e=e1*例：为R=(a|b)*abb构造NFA M，使得L(M)=L(R) X(a|b)*abbYX(a|b)*1a2bb3YX 4 1b3a2ba|bYX 4
21、 1b3a2babY4.4正规文法和有穷自动机间的转换从正规文法到NFA的转换方法设文法G=(VN,VT,P,S)相应NFA M=(K,f,K0,Z)则1.=VT2.K0=S3.增加一个新的状态T作为终态，Z=T,4.K=VNT5.f由以下方法求得： 若P中有AaB，则有f(A,a)=B； 若P中有Aa， 则有f(A,a)=T； 若P中有A，则有f(A,)=T；例：设文法G=(S,A,B, a,b, P, S)， 则有自动机M=(S,A,B,T, a,b,f,S, T)产生式产生式转换函数转换函数SaAf(S,a)=Af(S,a)=ASbBf(S,b)=Bf(S,b)=BS f(S,)=T f
22、(S,)=TAaBf(A,a)=Bf(A,a)=BAbAf(A,b)=Af(A,b)=ABaSf(B,a)=Sf(B,a)=SBbAf(B,b)=Af(B,b)=AB f(B,)=T f(B,)=T正规文法,正规表达式,有穷自动机三者可等价相互转换描述工具识别工具4.5词法分析程序的设计1.确定词法分析器的接口2.确定单词分类和Token结构3.特殊问题的处理4.用状态转换图构造词法分析程序回顾:词法分析的主要任务是：从左到右逐个字符地扫描源程序，产生一个个单词(Token)，同时检查源程序中的词法错误。执行词法分析的程序称为词法分析程序或扫描程序(Scanner)。单词是语言中具有独立意义的
23、最小单位，包括保留字、标识符、运算符、标点符号和常量等。 1.确定词法分析器的接口确定词法分析器是作为语法分析的一个子程序还是作为独立一遍词法分析作为独立一遍将字符流的源程序变成单词序列，输出到一个中间文件上，做为语法分析的输入。词法分析作为语法分析的子程序每当语法分析程序需要一个单词时，则调用该子程序，从源程序中分析和返回一个单词独立词法分析器语法分析Token序列源程序附属词法分析器语法分析调用Token源程序2.确定单词分类和Token结构设计词法分析器的首要任务是，对于源语言的单词进行仔细的分析，并列出所有可能的不同单词，然后再确定单词的内部表示 程序设计语言中的大部分单词，一般可分为
24、以下几类：1基本字（关键字）：如 begin，end，if等2标识符：用来表示常量、变量、过程等名字3常数：各种类型的常数，如 15，3.14，TRUE4运算符：如 +，*，/5界符：如逗号，分号，括号等单词的机内表示二元式（单词种别，单词自身的值）种别是语法分析需要的信息自身值是编译其他阶段需要的信息种别编码(常用整数编码)方法一：按单词的5大种类每种一个码，例如标识符为l，常数为2，基本字为3，运算符为4，界符为5。方法二：每个基本字一个编码；所有标识符为一个编码；常数按类型分类，每类一个编码；每个运算符一个编码；每个界符一个编码。单词自身值对常数,基本字,运算符,界符就是他们本身的值对标
25、识符,将标识符的名字登记在符号表中,“自身值”是指向该标识符所在符号表中位置的指针.例如源程序ifi=5thenx:=y;种别编码：标识符为l，常数为2，基本字为3，运算符为4，界符为5词法分析后输出的单词序列是:(3,if)(1,指向i的符号表入口)(4,=)(2,5)(3,then)(1,指向x的符号表入口)(4,:=)(1,指向y的符号表入口)(5,;)3.特殊问题的处理v标识符和保留字的区分事先构造保留字表，拼出的标识符单词先查保留字表，若有，则把它做为保留字处理v空格符和制表符(Tab)以及换行符的处理1.无用的空格符和制表符要删掉；2.字符串内的空格不能删；3.换行符不能删，对于错
26、误处理起作用。v复合型特殊符，如“:=”的处理读到“:”时不能判断是否为冒号，必须读下一字符。v括号类配对： “”和“”、左注释符和右注释符的配对。也可以把begin end ,if then, , ,( )等语法配对在词法分析中进行处理处理方法： 1.对每类括号设置一个计数器（初值=0）2.每当遇到左括号，则计数器加13.每当遇到右括号时，计数器减14.词法分析结束时，如果计数器0，则表明括号不匹配。4. 用状态转换图构造词法分析程序可通过状态转换图来实现词法分析程序的构造，步骤：画状态转换图。由正规文法构造状态转换图由正规表达式构造状态转换图将正规文法或正规表达式转换成DFA（经历NFA的
27、构造，将NFA确定化，DFA最小化的过程），将DFA以状态转换图的形式表现出来。按状态转换图写出词法分析程序对于状态图中的每一状态构造一段代码具体构造程序时：开始结点开始结点是一个单词识别的开始，单词开始符是非空白字符，首先把非空白字符读入ch，再按该字符的特征进入不同种类单词的识别GetChar()；/*从输入串读一个字符，放入 ch中*/GetBC()；/*检查ch中字符是否空白，若是则调用GetChar，直至ch中为非空白字符*/If(ch=) beginendelseif(ch=) beginend else错误处理；不含回路的分叉结点，对应switch语句或一组ifthenelse语
28、句ijk数字字母/l例：状态结点i 对应的程序段 GetChar()； If (IsLetter() 状态j 的对应程序段; else If (IsDigit() 状态k 的对应程序段; else If（ch=/）状态l 的对应程序段; else 错误处理;其中： IsLetter和IsDigit：布尔函数，分别判别ch字符是否为字母或数字含回路的状态结点，对应一个while语句其它ij字母或数字例：状态结点i 对应的程序段 GetChar()； While (IsLetter() or IsDigit()GetChar()；状态j 对应的程序段终态结点，一般对应一个return(code，v
29、alue)语句，code是单词种别码，value是单词自身值，意为返回调用者：v当词法分析作为语法分析的子程序，返回到语法分析v当词法分析作为独立一遍，返回进行新的单词识别4.6词法分析程序的自动构造工具1.自动构造工具的基本思想上述构造过程由计算机来完成就称为词法分析程序的自动构造。能完成上述任务的程序称为词法分析程序的自动构造工具。 单词结构的正规式描述NFADFA状态转换表控制程序（词法分析程序）（源程序）2.LEXLex是词法分析器的自动生成器作用:构造各种语言的词法分析程序。lex指的是LEX的编译系统LEX源程序LEX编译系统词法分析器（C语言形式）输入串词法分析器单词符号串LEX
30、源程序是对一个词法分析程序的说明和描述，在逻辑上分成两部分：一组正规式：表示单词构成规则。每个正规式相应的“动作”（C代码）：识别出单词时应采取的动作。3.LEX程序的一般描述LEX程序由三部分组成 (1) 说明部分 (2) 转换规则 (3) 辅助过程格式为：说明部分%转换规则%辅助过程(1) 说明部分包括变量说明、常量说明和正规定义。正规定义形如：d1r1d2r2dnrn其中di是为ri起的名字，ri是字母表中字符及前面定义过的dj(ji)组成的正规式，最终可转换为字母表上的正规式。di用作转换规则中的正规表达式的成分。(2) 转换规则形如:P1action1P2action2 Pnacti
31、onn其中Pi是由字母表的字符及di组成的正规式，最终可转换成字母表上的正规式。每个action是一段C程序代码，指出识别出Pi所描述的单词后，词法分析器所应采取的动作（如查填符号表，返回种别码及单词的自身值等）。(3) 辅助过程为了使action部分更简洁，action中用到的一些过程可放在辅助过程部分，这些过程可以单独编译后合成到词法分析器中。例如：识别标识符,数字,和+-*/运算符的lex源程序lex.lNUM0-90-9*辅助定义部分IDa-za-z0-9*%#include%识别规则部分NUMprintf(Aninteger:%dn,atoi(yytext);IDprintf(Ani
32、dentifier:%sn,yytext);+|-|*|/printf(Anoperator:%sn,yytext);%用户子程序main(intargc,char*argv)if(argc0)yyin=fopen(argv0,r);elseyyin=stdin;yylex();在UNIX中运行lex源程序lex.l得到词法分析器1.$lexlex.l在当前目录下产生文件2.$cclex.yy.cll得到可运行的目标代码a.out3.$./a.out输入字符串为“123+str”得到AnInteger:123AnOperator:+AnIdentifier:str本章小结：两个工具：正规文法和正规式一个识别系统：有穷自动机词法分析程序的设计
