词法分析及词法分析程序

词法分析及词法分析程序第一页，共五十四页，2022年，8月28日设计扫描器应注意的问题词法分析（3型）语法分析（2型）单词的(Class,Value)二元组表示标识符的长度限制和按“尽可能长”的识别策略超前搜索与回退<,<=,<<,<<=程序3-1输入缓冲注释与空白的删除第二页，共五十四页，2022年，8月28日状态转换图有向图结点表示状态一个初态，箭头指示若干个终态，双圆圈指示边表示转移边上的字符表示转移时应满足的条件字符串的识别0132abcdd第三页，共五十四页，2022年，8月28日右线性文法=>状态转换图设G=(VN,VT,P,S)是一右线性文法,令|VN|=K，1)则所要构造的状态转换图共有K+1个状态.2)VN中的每个符号分别表示K个状态

2.1)G的开始符S为初态状态3)终止状态,用F(VN)标记F是新加(状态）节点第四页，共五十四页，2022年，8月28日右线性文法=>状态转换图aA->aBABA->aAFaA->ε消除ε，重用上述规则AF[other]A若A为起始符（G[A]）A第五页，共五十四页，2022年，8月28日产生式的消除SAXFabc[other]YeSAXFabcYeS->aAA->b|bX

X->c|eYS->aAA->bXX->c|ε|eY第六页，共五十四页，2022年，8月28日状态图=>右线性文法文法G[0]0->a1S->aA1->d1A->dA1->bA->b0->cS->c0->c2S->cB，2有出弧2->dB->d0132abcdd第七页，共五十四页，2022年，8月28日左线性文法=>状态转换图设G=(VN,VT,P,S)是一左线性文法,令|VN|=K，1)则所要构造的状态转换图共有K+1个状态.2)VN中的每个符号分别表示K个状态

2.1)G的开始符S为终止状态3)起始状态,用R(VN)标记R是新加(状态）节点第八页，共五十四页，2022年，8月28日左线性文法=>状态转换图aA->BaBAA->ε的消除消除ε，重用上述规则RA[other]若A为起始符（G[A]）AA->aRAa不存在这种转换第九页，共五十四页，2022年，8月28日状态图=>左线性文法文法G[3]1->aAa1->1dAAd3->1bSAb2->cBc3->2dSBd0132abcdd第十页，共五十四页，2022年，8月28日状态矩阵状态矩阵Bij=B[Si,aj]=Sk当前状态，扫视字符，语义动作，后续状态程序3-2第十一页，共五十四页，2022年，8月28日识别无符号数的状态矩阵第十二页，共五十四页，2022年，8月28日语义动作中的返回值ICON、FCON分别为整型数、浮点型数的值；一般说来，无符号数具有形式dmdm-1…d0.d-1…d-nEdd

即dmdm-1…d0d-1…d-n*10^(dd-n);程序3-3关于状态无符号数识别矩阵第十三页，共五十四页，2022年，8月28日DFA的形式定义DFA:DeterministicFiniteAutomata一个DFAM定义为M=(K,,f,S0,Z)，其中1)K={状态i}2)=字母表，即{输入字符i}3)f:K×->K，f为函数，表示某状态接受某个字母所到达的状态，如：f(p,a)=q,p,qK,a4)S0K，S0为初态5)ZK，且Z，Z为终态集合第十四页，共五十四页，2022年，8月28日DFA例子0132abcdd左侧的状态图，在数学上称作DFA，其形式化定义为M=(K,,f,S0,Z)K={0,1,2,3}={a,b,c,d}

源状态输入目的状态0a10C21d11b32d3f:

S0=0Z={2,3}

第十五页，共五十四页，2022年，8月28日函数f的推广定义f^

f^:K×*->K，表示某状态接受一个字母串（而不是一个字母）所到达的状态，f^的定义依赖于f的定义，f^递归定义如下：1）f^(p,)=p,ifpK，即任意一状态p接受（串长为0）的输入，状态不变2）f^(p,aw)=f^(f(p,a),w),ifpK,a,w*第十六页，共五十四页，2022年，8月28日函数f的推广定义f^:例子对于x=adb,x*，那么从状态0可以迁移到的状态p可以这样求出：P=f^(0,adb)=f^(f(0,a),db)=f^(1,db)=f^(f(1,d),b)=f^(1,b)=f^(f(1,b),)=f^(3,)=30132abcdd因为从初态0接受输入字母串adb后，迁移到f^(0,adb)=3Z，所以adb为DFA所识别

第十七页，共五十四页，2022年，8月28日DFA所识别的语言令M为一DFA，我们：定义L(M)={x|f(S0,x)Z,x*}L(M)称为DFAM所识别的语言有定理：L(M)=L(G)，其中M为一DFA，G为一正规文法第十八页，共五十四页，2022年，8月28日DFA关键特征状态迁移映射f是入射函数即f(x)f(y)蕴含xy即对任意状态结点p，其出弧上的字母各不相同且不为从状态图角度，如出现下述情况的状态结点，则不是DFA（而是NFA）PQNaaQNPQPQWhy?第十九页，共五十四页，2022年，8月28日NFA的形式定义一个NFAM定义为M=(K,,f,S0,Z)，除f外其余成员与DFA相同，f定义为

f:K×->(K)，其中(K)为集合K的幂集合，即有|(K)|=2^|K|f表示某状态接受某个字母所到达的状态集合，如：f(p,a)={q,m}p,q,mK,a第二十页，共五十四页，2022年，8月28日映射f的推广定义f^f^:(K)×*->(K)，表示某状态集合接受一个字母串（而不是一个字母）所到达的状态集合，f^递归定义如下(依赖于f)：f^({p},)={p}f^({p},a)={p1,p2,...}iff(p,a)={p1,p2,…}iff(p,a)=f^({p},aw)=f^(f^({p},a),w)其中，p,p1,p2K,a,w*属于什么？第二十一页，共五十四页，2022年，8月28日NFA所识别的语言令N为一NFA，我们：定义L(N)={x|f(S0,x)Z,x*}L(N)称为NFAN所识别的语言有定理：L(N)=L(M)=L(G)，其中N为一NFA，M为一DFA，G为一正规文法第二十二页，共五十四页，2022年，8月28日NFA例子–写状态迁移表fSABCabaaa,bba为什么是NFA源状态输入目的状态集合->Sa{A,C}Aa{A,C}Ab{A,B}BaABbC[C]x对每状态结点，按出弧上的字母写出状态迁移表C行可以不填f:K×->(K)第二十三页，共五十四页，2022年，8月28日NFA例子–接受串源状态输入目的状态集合->Sa{A,C}Aa{A,C}Ab{A,B}BaABbC[C]xf:K×->(K)当前状态余留输入后续状态选择状态SababbA,CAorC?注意，NFA识别输入符号串时有一个试探过程，为了能走到终态，往往要走许多弯路（带回溯），这影响了NFA的效率。解决办法？第二十四页，共五十四页，2022年，8月28日NFA与DFA的等价性定理3.1

对于字母表上的任一NFAN，必存在与M等价的DFAM，使L(N)=L(M)

有了该定理，为提高NFA识别字符串的效率提供了tips：将NFA转换为DFA，即NFA的确定化基本idea:DFA的f:K×->KNFA的f:K×->(K)，将其改造为

f’:(K)×->(K)，并证明f’是入射函数且f’^接收的串与f^接收的串相同第二十五页，共五十四页，2022年，8月28日例子S0S1abba,bq0q2a,babq1b第二十六页，共五十四页，2022年，8月28日带有动作的NFA例子

abcS0{S0}{S1,S2}S1{S1,S3}S2{S2}{S3}S3

bS0S1S3aS2cb第二十七页，共五十四页，2022年，8月28日带有动作的NFA-闭包-closure(S0)={S0,S1,S2,S3}……f^(S,)=-closure(S)f^(S,wa)=-closure(f(f^(S,w),a))f(q,)通常不等于f^(q,)f(S0,)f^(S0,)第二十八页，共五十四页，2022年，8月28日带有动作的NFA的确定化1)令K’={-closure(S0)}(给出M’的初态q0)2)对于K’中任一尚未标记的状态qi={Si1,Si2,…,Sim}，SikK，作2.1)标记qi2.2)对于每个aΣ，置T=f({Si1,Si2,…,Sim},a)qj=-closure(T)2.3)若qj不在K’中，则将qj作为一个未加标记的状态添加到K’中，且把状态转移添加到M’。3)重复进行步骤2)，直到K’中不再含有未标记的状态为止，对于由此构造的K’，我们把那些至少含有一个Z中的元素的qi作为M’的终态。第二十九页，共五十四页，2022年，8月28日S0S1S3aS2cbb第三十页，共五十四页，2022年，8月28日DFA状态数最小化可区分状态ABa1a2ana1a2状态A,B被某一输入串w=a1a2..an所区分，指1）从其中一个状态出发读入w，到达终态，2）而从另一个状态出发进入非终态第三十一页，共五十四页，2022年，8月28日可区分状态的递归定义在一个DFA中，状态A与状态B可区分：1）A是终止状态，B是非终止状态 或B是终止状态，A是非终止状态2）对于字母a，有f(A,a)=C,f(B,a)=D2.1)C与D可区分2.2)C=NULL且DNULL且D可达终态或CNULL且C可达终态且D=NULL第三十二页，共五十四页，2022年，8月28日DFA状态数最小化-例子S0S1S3S2babbaaabS4ab第三十三页，共五十四页，2022年，8月28日复习一个DFAM=(K,,f,S0,Z)，函数f:K×->K表示某状态Ki接受某字母a后，到达状态Kj的转换。一个NFAM=(K,,f,S0,Z)，函数f:K×->(K)表示某状态Ki接受某字母a后，到达状态集合{K1,…,Kj}的转换。

一个带动作的NFAM=(K,,f,S0,Z)，函数

f:K×{}->(K)表示某状态Ki接受某字母a或空串后，到达状态集合{K1,…,Kj}的转换。第三十四页，共五十四页，2022年，8月28日试描述下述文法所产生的语言的特点G[S]=(VN={S,<alpha>,<digit>},VT={A…Z,a…z,0…9},P,S),其中P={SS<alpha>，SS<digit>，S<alpha>，<alpha>A，…，<alpha>z，<digit>0，…，<digit>9}第三十五页，共五十四页，2022年，8月28日上述正规文法产生的语言的特点是由字母开头，后接0个或多个字母和(或)数字的符号串即标识符的定义如果使用型如字母(字母|数字)*的式子来表示上述符号串构成的集合，那么这样的式子就称为正规表达式(正则式，RegularExpression)，相应的符号串集合则称为该表达式对应的正规集。第三十六页，共五十四页，2022年，8月28日正规表达式及正规集的定义正规式正规集1.空集2.{}3.a，a{a}4.(r)•(s)Lr•Ls (r)|(s)LrLs (r)*

Lr*

[r]=((r)|())Lr{}(r)+=(r)•((r)*)Lr+第三十七页，共五十四页，2022年，8月28日算符优先级与正规式化简

算符优先级从高到低依次为(),[],*,+,•,|

如((r)•((s)*))|(r)，可化简为

r•s*|r

又因为连接符•通常可省略不写，再化简为rs*|r第三十八页，共五十四页，2022年，8月28日正规式与正规集的例子={a,b}第三十九页，共五十四页，2022年，8月28日正规式与正规集的多对一关系给定一个正规式，它唯一确定一个正规集；反之不然。即一个正规集可由多个不同的正规式表示。我们称两个正规式等价，当且仅当它们所描述的正规集相同。例如a|b与b|a,(a|b)*与(b|a)*等等第四十页，共五十四页，2022年，8月28日正规式的基本等价公理A1.r|s=s|r A2.r|r=r

A3.r|=r A4.(r|s)|t=r|(s|t)A5.(rs)t=r(st) A6.r(s|t)=rs|rtA7.(s|t)r=sr|tr A8.r=r=A9.r=r=r A10.r*=(|r)*=|rr*第四十一页，共五十四页，2022年，8月28日由正规文法构造正规式1/4使用正规式描述下述右线性文法产生的语言SaS|b SaS|bS|c(或S(a|b)S|c)SabS|c总结出规律:SS|对应的正规式是*第四十二页，共五十四页，2022年，8月28日由正规文法构造正规式2/4使用正规式描述下述左线性文法产生的语言SSa|b SSa|Sb|c(或SS(a|b)|c)SSab|c总结出规律:SS|对应的正规式是*第四十三页，共五十四页，2022年，8月28日由正规文法构造正规式3/4如果将“|”用“+”替换，“”用“=”替换，那么可以将产生式转换为方程的形式，于是对上述两个规律，我们得到论断：论断3.1

方程X=X+（对应SS|），有解X=*论断3.2

方程X=X+（对应SS|），有解X=*第四十四页，共五十四页，2022年，8月28日由正规文法构造正规式4/4于是，对文法G[S]SaS|bA|b AaS……我们可以将所有产生式的运算符“|”用“+”替换，“”用“=”替换，再以我们习掼的线性方程组求解方法来求解S对应的正规式。第四十五页，共五十四页，2022年，8月28日例子1)SaS|bA|b,AaS2)SaA,AbA|aB|b,BaA3)SbS|aA,AaA|bB,BaA|bC|