编译原理第三章 词法分析及词法分析程序.ppt_第1页
编译原理第三章 词法分析及词法分析程序.ppt_第2页
编译原理第三章 词法分析及词法分析程序.ppt_第3页
编译原理第三章 词法分析及词法分析程序.ppt_第4页
编译原理第三章 词法分析及词法分析程序.ppt_第5页
已阅读5页,还剩49页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、编译原理前后文无关文法和语言,设计扫描器应注意的问题,词法分析(3型) 语法分析(2型) 单词的(Class, Value)二元组表示 标识符的长度限制和按“尽可能长”的识别策略 超前搜索与回退 , =, , = 程序3-1 输入缓冲 注释与空白的删除,状态转换图,有向图 结点表示状态 一个初态,箭头指示 若干个终态,双圆圈指示 边表示转移 边上的字符表示转移时应满足的条件 字符串的识别,0,1,3,2,a,b,c,d,d,右线性文法=状态转换图,设G=(VN,VT,P,S)是一右线性文法,令|VN|=K, 1) 则所要构造的状态转换图共有K+1个状态. 2) VN中的每个符号分别表示K个状态

2、 2.1) G的开始符S为初态状态 3) 终止状态,用F(VN)标记,右线性文法=状态转换图,产生式的消除,S,A,X,F,a,b,c,other,Y,e,S,A,X,F,a,b,c,Y,e,S - aA A - b|bX X - c|eY,S - aA A - bX X - c|eY,状态图=右线性文法,左线性文法=状态转换图,设G=(VN,VT,P,S)是一左线性文法,令|VN|=K, 1) 则所要构造的状态转换图共有K+1个状态. 2) VN中的每个符号分别表示K个状态 2.1) G的开始符S为终止状态 3) 起始状态,用R(VN)标记,左线性文法=状态转换图,不存在这种转换,状态图=左

3、线性文法,0,1,3,2,a,b,c,d,d,状态矩阵,状态矩阵Bij=BSi, aj=Sk 当前状态,扫视字符,语义动作,后续状态 程序3-2,识别无符号数的状态矩阵,语义 动作中的返回值ICON、FCON分别为整型数、浮点型数的值; 一般说来,无符号数具有形式 dmdm-1d0.d-1d-nEdd 即dmdm-1d0d-1d-n*10(dd-n); 程序3-3,关于状态无符号数识别矩阵,DFA的形式定义,DFA: Deterministic Finite Automata 一个DFA M定义为M=(K, , f, S0, Z),其中 1) K=状态i 2) =字母表,即输入字符i 3) f

4、 : K - K,f为函数,表示某状态接受某个字母所到达的状态,如:f(p,a) =q, p,qK, a 4) S0 K, S0为初态 5) Z K,且Z ,Z为终态集合,DFA例子,左侧的状态图,在数学上称作DFA,其形式化定义为,M=(K, , f, S0, Z),K=0 , 1 , 2 , 3 =a , b , c , d ,f:,S0=0 Z=2 , 3,函数f的推广定义f,f : K * - K,表示某状态接受一个字母串(而不是一个字母)所到达的状态, f的定义依赖于f的定义, f递归定义如下: 1) f(p, ) = p, if p K,即任意一状态p接受(串长为0)的输入,状态不

5、变 2) f(p, aw) = f( f(p,a), w), if p K, a , w *,函数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, ) = 3,因为从初态0接受输入字母串adb后,迁移到f(0,adb)= 3 Z,所以adb为DFA所识别,DFA所识别的语言,令M 为一DFA,我们: 定义L(M)=x | f(S0, x) Z, x * L(M)称为DF

6、A M所识别的语言 有定理:L(M) = L(G),其中M为一DFA,G为一正规文法,DFA关键特征,状态迁移映射f是入射函数即 f(x) f(y) 蕴含 x y 即对任意状态结点p,其出弧上的字母各不相同且不为 从状态图角度,如出现下述情况的状态结点,则不是DFA(而是NFA),Why?,NFA的形式定义,一个NFA M定义为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 ,映射f的推广定义f

7、,f : (K) * - (K), 表示某状态集合接受一个字母串(而不是一个字母)所到达的状态集合, f递归定义如下(依赖于f): f(p, ) = p f(p,a) =,f(p,aw) = f(f(p,a), w),其中,p,p1,p2 K, a , w *,属于什么?,NFA所识别的语言,令N 为一NFA,我们: 定义L(N)=x | f(S0, x) Z , x * L(N)称为NFA N所识别的语言 有定理:L(N) = L(M) = L(G),其中N为一NFA,M为一DFA,G为一正规文法,NFA例子 写状态迁移表f,为什么是NFA,对每状态结点,按出弧上的字母写出状态迁移表,C行可

8、以不填,f : K - (K),NFA例子 接受串,f : K - (K),当前状态 余留输入 后续状态 选择状态,S ababb A,C A or C ?,注意,NFA识别输入符号串时有一个试探过程,为了能走到终态,往往要走许多弯路(带回溯),这影响了NFA的效率。,解决办法?,NFA与DFA的等价性,定理3.1 对于字母表上的任一NFA N,必存在与M等价的DFA M,使L(N)=L(M),有了该定理,为提高NFA识别字符串的效率提供了tips: 将NFA转换为DFA, 即NFA的确定化,基本idea: DFA的 f : K - K NFA的f : K - (K),将其改造为 f : (K

9、) - (K),并证明f是入射函数 且f接收的串与f接收的串相同,例子,带有动作的NFA例子,a b c ,S0 S0 S1, S2,S1 S1, S3,S2 S2 S3,S3,带有动作的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, ),带有动作的NFA的确定化,1) 令K=-closure(S0)(给出M的初态q0) 2) 对于K中任一尚未标记的状态qi=Si1,Si2,Sim,Sik K,作

10、2.1)标记qi 2.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的终态。,DFA状态数最小化,可区分状态,a1,a2,an,a1,a2,状态A,B被某一输入串w=a1a2.an所区分,指 1)从其中一个状态出发读入w,到达终态, 2)而从另一个状态出发进入非终态,可区分状态的递归定义,在一个DFA中,状态A与状态B可区分:,1)A是终止

11、状态,B是非终止状态 或 B是终止状态,A是非终止状态,2)对于字母a,有f(A,a)=C, f(B,a)=D 2.1) C与D可区分,2.2) C=NULL 且 D NULL且D可达终态 或 C NULL且C可达终态 且 D=NULL,DFA状态数最小化-例子,S0,S1,S3,S2,b,a,b,b,a,a,a,b,a,b,复习,一个DFA M=(K, , f, S0, Z),函数f : K - K表示某状态Ki接受某字母a后,到达状态Kj的转换。 一个NFA M=(K, , f, S0, Z),函数f : K - (K)表示某状态Ki接受某字母a后,到达状态集合K1, , Kj的转换。 一

12、个带动作的NFA M=(K, , f, S0, Z),函数 f : K - (K)表示某状态Ki接受某字母a或空串后,到达状态集合K1, , Kj的转换。,试描述下述文法所产生的语言的特点,GS=(VN=S, , , VT=AZ, az, 09, P, S), 其中P= S S, S S, S , A, z, 0, 9 ,上述正规文法产生的语言的特点是 由字母开头,后接0个或多个字母和(或)数字的符号串 即标识符的定义 如果使用型如 字母(字母|数字)* 的式子来表示上述符号串构成的集合,那么这样的式子就称为正规表达式(正则式,Regular Expression),相应的符号串集合则称为该表

13、达式对应的正规集。,正规表达式及正规集的定义,正规式 正规集,1. 空集,2. ,3. a,a a,4. (r)(s) Lr Ls (r)|(s) Lr Ls (r)* Lr*,r=(r)|() Lr (r)+=(r)(r)*) Lr+,算符优先级与正规式化简,算符优先级从高到低依次为 (), , *,+, , | 如( (r) ( (s)* ) ) | ( r ),可化简为 r s*|r 又因为连接符通常可省略不写, 再化简为rs*|r,正规式与正规集的例子,=a,b,正规式与正规集的多对一关系,给定一个正规式,它唯一确定一个正规集;反之不然。 即一个正规集可由多个不同的正规式表示。 我们称

14、两个正规式等价,当且仅当它们所描述的正规集相同。 例如a|b与b|a, (a|b)*与 (b|a)*等等,正规式的基本等价公理,A1. r|s=s|rA2. r|r=r A3. r|=r A4. (r|s)|t=r|(s|t) A5. (rs)t=r(st) A6. r(s|t)=rs|rt A7. (s|t)r=sr|trA8. r = r = A9. r = r =rA10. r*=(|r)*=|rr*,由正规文法构造正规式1/4,使用正规式描述下述右线性文法产生的语言 S aS | b S aS | bS | c (或S (a|b)S | c ) S abS | c 总结出规律: S S

15、 | 对应的正规式是 *,由正规文法构造正规式2/4,使用正规式描述下述左线性文法产生的语言 S Sa | b S Sa | Sb | c (或S S(a|b) | c ) S Sab | c 总结出规律: S S | 对应的正规式是 *,由正规文法构造正规式3/4,如果将“ | ”用 “ + ”替换,“ ” 用 “ = ” 替换,那么可以将产生式转换为方程的形式,于是对上述两个规律,我们得到论断: 论断3.1 方程X= X + (对应S S | ),有解 X= * 论断3.2 方程X= X + (对应 S S | ),有解 X= *,由正规文法构造正规式4/4,于是,对文法GS SaS |

16、bA | b AaS 我们可以将所有产生式的运算符“ | ”用 “ + ”替换,“ ” 用 “ = ” 替换,再以我们习掼的线性方程组求解方法来求解S对应的正规式。,例子,1) SaS|bA|b, AaS 2) SaA, AbA|aB|b, BaA 3) SbS|aA, AaA|bB, BaA|bC|b, CbS|aA,练习,1) SaS|bA|c, AbS 2) SaA, AaA|bB|c, BcS,由正规式构造FAThompson法,当n=0 r= r= r=a,根据正规式所含运算符个数n递归给出。,r= r1|r2,r1,S01,r2,S02,s0,Sf,不再是初态,不再是终态,Sf1,Sf2,r=r1r2,r1,S01,Sf1,r2,S02,Sf2,r=r*,S01,Sf1,s,Sf,例子与练习,例子: 1)a(b|aa)*b 2)( (0*|1) (1*0) )* 练习: 1) ab|c* 2) (b|aa|ac|aaa|aac)*,综合练习1,对文法GS=(S, A, B, a, b

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论