3词法分析

第三章词法分析词法分析的任务是：从左至右逐个字符地对源程序进行扫描，识别出一个个地单词，将识别出的单词表示成二元组（类号，内码）。一、词法分析器的功能和输出形式1、功能：输入源程序，输出单词符号，并翻译成（类号，内码）。2、单词符号：一个程序设计语言的基本词法符号。3、单词符号的分类：（1）关键字（2）标识符（3）常数（4）运算符（5）界符§3.1对于词法分析器的要求1、预处理：将要进行词法分析的源程序去掉多余的空格，注释，且在每个句子末尾加#后供词法分析用。§3.2词法分析器的设计2、单词符号的识别——超前搜索——根据语言的文法，即词法规则来识别。Pascal语言的词法规则如下：（1）标识符→字母|标识符(字母|数字)（2）整数→数字|整数数字（3）有符号整数→(+|-|ε)整数（4）无符号整数→整数|整数.整数|整数E有符号整数|整数.整数E有符号整数（5）界符→+|-|*|/||……（6）双界符→|:=|=|=|/*|……0134256:==；；01245631100031=12字母字母Pascal标识符0*其它Pascal运算符和界符数字34数字数字Pascal整数013465270dddddddEE+–7**Pascal实数其它其它其它其它实验一：将某门语言的关键字按字典顺序编上类号存入一张表格中，能从键盘随意输入一个标识符，输出该标识符的类号。实验二：编写一个词法分析程序，对某源程序文件进行词法分析，将其中的所有单词经词法分析后变为由类号构成的目标文件。program();constass=10;beginread(A,B);C:=A+B;if(AB)C=45;elseD=60;end注：可以自己书写一段pascal源程序（用记事本），但必须包含所有类型的单词（关键字，界符，算术运算符，关系运算符，常数，标识符）1、正规文法根据Chomsky对形式语言的定义，正规文法的产生式形式为：A→αB,A→α,或者A→Bβ,A→β其中α,β∈VT*,A,B∈VN.2、正规集由正规文法所产生的语言称作正规集。3、正规式Re（Regularexpression）a）定义：设A是非空的有限字母表,A={αi|i=1,2,……n},则1)ε,φ,αi都是正规式;2)若α,β是正规式,则α|β,α·β,α*,β*也是正规式;3)正规式只能通过有限次使用1),2)规则而获得.§3.3正规式和有限自动机一、正规文法、正规集和正规式例1字母表=a,b正规式α正规集L(α)aba,b(ab)(ab)aa,ab,ba,bb}ba*上所有以b为首后跟任意多个a的字（句子）。a(ab)*上所有以a为首的字(句子).b）正规式的等价：若两个正规式所表示的正规集相同，则等价。例2证明b(ab)*=(ba)*b注:1）Re涉及三种运算符“|”或者，“·”连接，“*”闭包，优先级*·|。2）仅由字母表A={αi|i=1，2…k}上的正规式α所组成的语言称作正规集。3）正规式，正规集表示的都是由正规文法产生的语言，只是形式不同。恒等式说明rs=sr“”是可交换的r(st)=(rs)t“”是可结合的r(st)=(rs)t连接是可结合的r(st)=rsrt(st)r=srtr分配律r=rr=r对连接，是单位元素r*=(r+)“*”和之间的关系r**=r*“*”是幂等的4、正规式的代数性质5、正规式和正规文法的联系。正规文法G可直接求得对应语言的正规式，反之亦可。例3、求语言L(a)={aibjck|i,j,k=1}的产生文法，再由相应文法转换成正规式。文法产生式:(0)SaSaB(1)BbBbC(2)CcCc正规式：a+b+c+二、有限自动机FA(FiniteAutomata)1.实例2.DFA3.NFA4.NFA确定化为DFA5.DFA的化简(minDFA)6.正规式与有限自动机之间的关系7.正规文法与有限自动机之间的关系=80;0134256eniL字母字母字母字母数字数字数字==；；0124563Line=80;id,‘Line’=,num,‘80’;,数字数字字母字母11==0003;;1输入带输出有限自动机1)定义：一个确定的有限自动机M（记作DFAM）是（DeterministicFiniteAutomata）一个五元组Ｍ＝（S，Σ，s0，δ，F），其中（ａ）S是一个有限状态集合。（ｂ）Σ是一个有穷字母表，它的每个元素称为一个输入符号。（ｃ）s0∈S，s0称为初始状态且是唯一的初态。（ｄ）ＦS，Ｆ称为终结状态集合。(终态可不止一个)（ｅ）δ是一个从S×Σ到S的单值映射δ(si，ａ)＝sj（si，sj∈S，ａ∈Σ）表示当前状态为si，输入符号为a时，自动机将转换到下一个状态sj，sj称为si的一个后继。2、DFA例1设DFAＭ＝({0,1,2,3},{ａ,ｂ},0,δ,{3})其中:δ（０，ａ）＝１，δ（１，ａ）＝3δ（２，ａ）＝１，δ（３，ａ）＝３δ（０，ｂ）＝２，δ（１，ｂ）＝２δ（２，ｂ）＝３，δ（３，ｂ）＝３2)一个ＤＦＡ有三种表示：（1）转换函数；（2）转移矩阵；（3）状态转换图。ab012132213333转移矩阵0132aaaabbbb3状态转换图易存储例2设DFAＭ＝（{s0,s1,s2,s3},{0,1},s0,δ,{s0}），其中δ画成如下状态转换图:0s1s3s2101100s001问字符串110101,01001均能被此DFA识别吗?3)DFAM接受的语言对于所有Σ*中的任何字α，如果存在一条从初态结点到某一终态结点的通路，且这条通路上所有标记符连接成的字等于α，则称α可为DFAM所识别（接受）。注：（1）每读一个字符，读头前进一格，状态前至下一状态，我们称它作了一步动作，记作“”，“k”表k步，“+”表一步或一步以上。“*”表0步或0步以上。（2）能被M所接受的字符串的集合成称为M所能识别的语言，记作L(M)。注：（3）不能被M接受的字符串有两种情况：a）读完输入串，状态不停在终态即(s0,α)*(s’,ε)且s‘∈F。b）在读过程中出现不存在的映射，使自动机无法继续工作例3构造一个DFAＭ，它接受字母表{a,b,c}上以a或b开始的字符串，或以c开始但所含的a不多于1个的字符串。例4构造一个自动机，使它能够识别{0,1}上以00结尾的字符串。1）定义：非确定的有限自动机M（记作NFAM）是（NondeterministicFiniteAutomata）一个五无组Ｍ＝（S，Σ，s0，f，F），其中（a）S，Σ，同DFAM。（b）S0S，S0称为非空初态集，它不能为空。（c）ＦS，Ｆ为可空终态集。（d）f是一个从S×Σ到2S的映射，即f:S×Σ→2S注:1)NFAM的状态转换图至少含有一个初态结点以及若干个(可为0个)终态结点。2)某些结点既可以是初态结点也可以是终态结点.3)对于Σ*中的任何一个字α,若存在一条从某一初态结点到某一终态结点的通路,且这条路上所有弧的标记字依次序连接成的字(忽略那些标记为ε的弧)等于α,则称α可为NFAM所识别.3、NFA注:4)若M的某些结点既是初态结点又是终态结点,或者存在一条从某个初态结点到某个终态结点ε通路,则空串ε可为NFAM所识别.5)映射f可理解为“一箭多雕”。q0q110001q1例5给出正规式（a|b）*a（a|b）的NFA。例6设NFAＭ＝（{q0,q1},{0,1},{q0},δ,{q1}），其中δ画成如下状态转换图，将其确定化为DFA。4、NFA确定化为DFA定理:任何一个NFAm，都存在一个DFAm’，使L(m’)=L(m)证明思想：用m’的一个状态对应m的一个状态集合，用这种方法，能从一个NFAm构造一个DFAm’，称作子集构造法。子集法:由NFAM(S，Σ，f，s0，F），构造一个等价的DFAM(Q，Σ，δ，I0，F）算法如下：1）I0=s0（初态）（Q中开始仅包含初态I0）；2）设Ii={s0，…，sj}∈Q，（对字母表中任一字符）求f（Ii，a）=（si，…sk）=It，若It∈Q，则Q=Q∪{It}；a3）重复（2），直到不产生新状态为止。4）取F={I|I∈Q，且I∩F≠φ}例7设有一NFA其状态转换图如下，试为其构造DFA。SAs3B000|111Z10|1C00|1例8设有一NFA其状态转换图如下，试为其构造DFA。x3s3εy1aa|b24a|babbε—closure(I)的定义和算法a）—closure(I)的定义—closure(I)由两部分组成：（1）若s∈I，则s∈—closure(I)（2）若s∈I，那么从s出发经过任意段的ε弧而能到达的任意状态s’都属于—closure(I)b）用—closure(I)确定化NFA与子集法的差别仅在于将原状态子集改为由—closure(I)求得。5、确定的有限自动机的化简（DFA的化简）1）何谓确定的有限自动机的化简所谓一个DFAm=(,Q,q0,F,)的化简是指寻找一个状态数比较少的DFAm’,使L(m)=L(m’)。而且可以证明，存在一个最少状态的DFAm’,使L(m)=L(m’)。2）等价状态的定义设p,qQ，若对任何w*,(p,w)F当且仅当(q,w)F，F为终态集或F中的状态不可区分，则称p和q是等价状态；否则，称p和q是可区别的。注意：（1）等价状态定义了状态集合上的等价关系。因此，状态集合能被划分成等价类；（2）两个状态p和q等价应满足如下条件：•一致性条件，p和q必须同时或为接受状态或为非接受状态；•蔓延性条件，对于a，（p,a)=r,（q,a)=s,r和s必须等价;相反,r和s不等价,p和q不等价。判定两个状态p和q不等价，只要找到一个w*，使（p,w)F且（q,w)F，或者相反。w称为判别序列。三.求minDFA的算法：3）求minDFA的算法：（1）首先把状态集S分为终态集和非终态集。这就是基本划分：∏0={I01，I02}。设I01属于非终态集，I02属于终态集。（2）假定经过K次划分后，已含有m个子集，记作∏k={Ik1，…，Ikm}。这些子集到现在为止都是可区分的然后继续考察这些子集是否还可划分。设任取一子集Iki={S1，S2，…，St}，若存在一输入字符a，使得f(Iki,a)不全包含在Iki的某子集中.或者f(S1,a)=t1,f(S2,a)=t2,而t1,t2,分属于∏k的不同子集.这说明在∏k中有不等价的状态,它应该还可一分为二.对所有子集Ikm,所有读入字符a做一遍才完成此次划分.（3）重复步骤2,直至所含子集数不再增加为止.到此∏中的每个子集是不可再分了.（4）对每个子集任取一个状态为代表,若该子集包含原有的初态,则此代表状态便为最小化后M的初态;若该子集包含原有的终态,则此代表状态便为最小化后M的终态.aq1q2q3q6q4q5q7baaaaaabbbbbbq1q2q3Iaaaabbb,b例8经确定化，最小化的结果例9将如下NFA确定化，并求minDFA。SBs3ZAεaCa|babε为正规式(a|b)*a(a|b)构造一个确定的有限自动机。s36、正规式与有限自动机之间的关系定理1.∑上的NFAM所能识别的语言L(M)可以用∑上的正规式来表示.证明：对于∑上的NFAM构造一个Reα首先引进3条FA替换规则：1s332β(1)α替换成13αβs31s32β(2)α替换成12s31s33γ(3)β替换成13α|ββγ*s31s33γ(3’)β替换成13γ*β小结：NFAM对状态图进行变换求Re的步骤：1、在原状态图上增加两个结点x,y，从x结点用ε弧将其连接到M的初态，从M的所有终态结点引ε弧到y结点。2、利用3条替换规则逐步消去M中的结点与弧线，直至状态图中仅剩下x,y两个结点