《川师编译原理课件》由会员分享，可在线阅读，更多相关《川师编译原理课件（53页珍藏版）》请在金锄头文库上搜索。
1、吉首大学：莫礼平第四章第四章 词法分析词法分析教学目的教学目的：让学生了解词法分析程序的：让学生了解词法分析程序的 概念的设计原则，单词的描述工具，掌握概念的设计原则，单词的描述工具，掌握 正规文法、正规式、有穷自动机的相关概正规文法、正规式、有穷自动机的相关概 念及相互转换念及相互转换; ;学会使用学会使用LEXLEX语言构造简语言构造简 单词法分析器。单词法分析器。教学重点教学重点：正规文法、正规式、有穷自：正规文法、正规式、有穷自 动机动机课时分配课时分配：9 9学时。学时。教学过程教学过程：吉首大学：莫礼平4.1 4.1 词法分析程序的设计词法分析程序的设计通常将词法分析程序（扫描器）
2、设计为通常将词法分析程序（扫描器）设计为子子 程序程序形式，当语法分析程序需要单词时，形式，当语法分析程序需要单词时， 则调用该子程序。则调用该子程序。扫描器的输出格式扫描器的输出格式 单词通常可分为单词通常可分为5 5类：类： (1)(1)基本字基本字( (关键字、保留字关键字、保留字) )：具有特殊：具有特殊 含义的标识符，不作他用，有分隔语法含义的标识符，不作他用，有分隔语法 的作用；的作用；吉首大学：莫礼平(2)(2)标识符：标识符：表示各种名字；表示各种名字； (3)(3)常量：常量：整型、实型、布尔型、整型、实型、布尔型、 字符型；字符型； (4)(4)运算符：运算符：算术、逻辑、
3、关系运算术、逻辑、关系运 算符；算符； (5)(5)界符：界符：包括包括. .，; ;，( (，) )，: :，, ,等等 ，有时也把运算符称作界符。，有时也把运算符称作界符。吉首大学：莫礼平扫描器的设计扫描器的设计把扫描器当作语法分析的一个过把扫描器当作语法分析的一个过 程，当语法分析需要一个单词时程，当语法分析需要一个单词时 ，便调用扫描器。，便调用扫描器。扫描器从初态出发，当识别一个扫描器从初态出发，当识别一个 单词后便进入终态，同时送出单词后便进入终态，同时送出二二 元组元组。吉首大学：莫礼平扫描后输出扫描后输出二元组二元组形式的单词序列形式的单词序列 二元组：（单词种别，单词自身值或
4、指针）二元组：（单词种别，单词自身值或指针）例：若规定标识符、常数、基本字、运算例：若规定标识符、常数、基本字、运算 符、界符的种别用整数编码分别为符、界符的种别用整数编码分别为1 1、2 2、3 3 、4 4、5 5，则对程序段，则对程序段 ： “ “ if if k=7 then k=7 then a:=b ; ” a:=b ; ” 则其经扫描器扫描后输出的单词符号及其则其经扫描器扫描后输出的单词符号及其 二元组为二元组为： 吉首大学：莫礼平基本字if (3, if) 标识符k (1,指向k的符号表入口的指针 ) 等号= (4, =) 常数7 （2，7）基本字then (3, then)标
5、识符a (1, 指向a的符号表入口的指针)赋值号:= (4, :=)标识符b (1, 指向b的符号表入口的指针)分号； (5, ;)吉首大学：莫礼平4.24.2 单词的描述工具单词的描述工具3 3型文法，又称右线性文法或正规文法型文法，又称右线性文法或正规文法 ( (Regular Grammars),Regular Grammars),其表达式形如：其表达式形如： AaBAaB或或AaAa正规文法描述的语言是正规文法描述的语言是V VT T* *上的正规集上的正规集绝大部份程序设计语言的单词都能用正绝大部份程序设计语言的单词都能用正 规文法来描述规文法来描述4.2.1 4.2.1 正规文法正
6、规文法吉首大学：莫礼平4.2.2 4.2.2 正规式和正规集正规式和正规集正规式也称正规表达式，是表示正规集正规式也称正规表达式，是表示正规集 的工具，递归定义如下：的工具，递归定义如下：(1)(1) 和和都是字母表都是字母表 上的正规式，表示上的正规式，表示 正规集为正规集为 和和(2)(2) a a , ,a a是是 上的正规式，表示正规集上的正规式，表示正规集 aa 吉首大学：莫礼平(3)(3)假定假定e1e1、e2e2都是都是 上的正规式，对上的正规式，对 应正规集为应正规集为L(e1)L(e1)、L(e2),L(e2),则则( (e1)e1)、 e1|e2e1|e2、e1.e2e1.
7、e2、e1*e1*也是正规式，分别也是正规式，分别 表示的正规集为表示的正规集为L(e1),L(e1)L(e1),L(e1) L(e2),L(e1).L(e2),L(e2),L(e1).L(e2),和和L(e1)*L(e1)*(4)(4)仅有有限次运用上述步骤产生的表仅有有限次运用上述步骤产生的表 达式才是达式才是 上的正规式，仅由这些正上的正规式，仅由这些正 规式产生的字集才是规式产生的字集才是 上的正规集上的正规集吉首大学：莫礼平例：设例：设 =0=0，11，则有，则有正规式正规式正规集正规集0 000 0|10|100，11 01010101 1*1* ，1 1，1111， 111.11
8、1. (0|1)*(0|1)* ,0,1,01,10,0,1,01,10 吉首大学：莫礼平设设r,s,tr,s,t为正规式，则正规式服从如下的代数规为正规式，则正规式服从如下的代数规 则：则：r|s=s|r (r|s=s|r (或或 满足交换律满足交换律) )r|(s|t)=(r|s)|t (r|(s|t)=(r|s)|t (或或 满足结合律满足结合律) )r(st)=(rs)t ( r(st)=(rs)t (连接连接 满足结合律满足结合律) )r(s|t)=rs | rt ( r(s|t)=rs | rt (分配律分配律) )r r=r=r (=r=r (是连接的恒等元素是连接的恒等元素)
9、)注意：注意：rsrs sr r|(st)sr r|(st) rs | rtrs | rt吉首大学：莫礼平正规式和正规文法之间的转换正规式和正规文法之间的转换 将将 = =VTVT上的正规式上的正规式r r换成正规文法换成正规文法G=(VN, VT,P,S)G=(VN, VT,P,S) 方法如下：方法如下： (1)(1)令令Sr Sr (2)(2)对形如对形如AxyAxy的产生式，可分解成的产生式，可分解成AxB ,By AxB ,By (3)(3)对形如对形如Ax*yAx*y的产生式，可分解成为的产生式，可分解成为AxA, AxA, AyAy (4)(4)对形如对形如Ax|y Ax|y 的产
10、生式，可分解为的产生式，可分解为 Ax Ax ,Ay,Ay反复利用上述规则，直至所有产生式中最多只含一反复利用上述规则，直至所有产生式中最多只含一 个终结符个终结符 吉首大学：莫礼平例：将例：将R=a(a|d)*R=a(a|d)*转换成相应的正规文法转换成相应的正规文法. . 解：步骤如下：解：步骤如下：(1)Sa(a|d)*(1)Sa(a|d)* (2)SaB (2)SaB , , B(a|d)B , BB(a|d)B , B (3)S(3)SaB , BaB ,BdB, BaB , BaB ,BdB, B 相应的正规文法如相应的正规文法如(3)(3)式所示，即式所示，即 GS:GS:S S
11、aB aB BaB|dB| BaB|dB| 吉首大学：莫礼平将正规文法将正规文法G=(VG=(VN N, V, VT T,P,S),P,S)换成换成 = =V VT T上的正规式上的正规式r r的转换规则的转换规则(1)(1)将产生式将产生式AxB By AxB By 合写为合写为 A=xyA=xy；(2)(2)将产生式将产生式AxA Ay AxA Ay 合写为合写为 A=x*yA=x*y；(3)(3)将产生式将产生式Ax Ax Ay Ay 合写为合写为A= A= x|yx|y反复利用上述规则，直至只剩下一反复利用上述规则，直至只剩下一 个由开始符定义的产生式，且该产生个由开始符定义的产生式，
12、且该产生 式右部不含一个非终结符式右部不含一个非终结符 吉首大学：莫礼平例：将正规文法例：将正规文法 GS: SdA S eB AaA Ab GS: SdA S eB AaA Ab BbB Bc BbB Bc 换成正规式。换成正规式。 解：步骤如下：解：步骤如下： (1)(1)由由AaA, Ab AaA, Ab ，将将A A转换成转换成a*ba*b；由由BbB, B cBbB, B c，将将 B B转换成转换成b*cb*c； (2)(2)由由 SdA, S eB SdA, S eB ，将将S S可转换成可转换成 ( (da*b)|(eb*c)da*b)|(eb*c) 故所求正规式为故所求正规式
13、为R=R=( (da*b)|(eb*c)da*b)|(eb*c)吉首大学：莫礼平4.3 4.3 有穷自动机有穷自动机有穷自动机有穷自动机 ( (Finite Automata):Finite Automata):可准确的可准确的 识别正规集。识别正规集。分类分类: :(1) (1)确定的有穷自动机确定的有穷自动机 ( (Deterministic Finite Automata ,Deterministic Finite Automata ,简称简称DFA)DFA)(2) (2)不确定的有穷自动机不确定的有穷自动机 ( (Nondeterministic Finite Automata ,Nondeterministic Finite Automata ,简称简称 NFA)NFA)吉首大学：莫礼平4.3.1 4.3.1 确定的有穷自动机确定的有穷自动机( (DFA)DFA)DFA M=(K,DFA M=(K, , ,f,S,Zf,S,Z), ),其中其中 (1)K(1)K是一有穷状态集是一有穷状态集 (2)(2) 是一有穷字母表，称输入符号字母是一有穷字母表，称输入符号字母 表表 (3)(3)f f是转换函数，是在是转换函数，是在KK KK上的映射上的映射
