《国防科大-编译原理-第三章优秀PPT.ppt》由会员分享，可在线阅读，更多相关《国防科大-编译原理-第三章优秀PPT.ppt（64页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、词法分析：输入源程序，依据词法规则识别及组合单词。词法分析：输入源程序，依据词法规则识别及组合单词。删去空格字符和注解。删去空格字符和注解。词法分析的任务是：从左到右逐个字符地对源程序进行词法分析的任务是：从左到右逐个字符地对源程序进行扫描扫描，产生一个个产生一个个单词单词符号，把源程序改造成单词符号串表示的中间符号，把源程序改造成单词符号串表示的中间程序。程序。3.1 3.1 对词法分析器的要求对词法分析器的要求词法分析器又名扫描器词法分析器又名扫描器(scanner)。3.1.1 3.1.1 词法分析器的功能和输出形式词法分析器的功能和输出形式单词符号的类别：单词符号的类别：1.关键字关键
2、字(保留字保留字)：begin、end、for、do 2.标识符：变量名、过程名、数组名等标识符：变量名、过程名、数组名等3.常数：无符号数、布尔常数、字符串常数等常数：无符号数、布尔常数、字符串常数等4.运算符：运算符：+、-、*、/等等5.界符界符:逗号、分号、括号、逗号、分号、括号、/*/、等等、等等几种常用的单词内部形式：几种常用的单词内部形式：1 1、按单词种类分类、按单词种类分类2 2、关键字、运算符和界符接受一符一类、关键字、运算符和界符接受一符一类3 3、标识符和常数的单词值又为指示字（指针值）、标识符和常数的单词值又为指示字（指针值）词法分析程序的输出形式词法分析程序的输出形
3、式-单词的内部形式单词的内部形式单词类别单词类别 单词值单词值通常用整数编码，通常用整数编码，编码原则：利于处理编码原则：利于处理单词符号的特征单词符号的特征或特性或特性单词名称单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数关键字分界符类别编码类别编码1234567单词值单词值内部字符串整数值数值0 或 1内部字符串关键字字串或内部编码分界符或内部编码例例1 1：按单词种类分类，关键字和分界符分别：按单词种类分类，关键字和分界符分别用公用一个类别编码用公用一个类别编码例例2 2：关键字、运算符和分界符接受一符一类：关键字、运算符和分界符接受一符一类单词名称单词名称标识符无符号常数
4、(整)无符号浮点数布尔常数字符串常数BEGINENDFORDO:+*,(类别编码类别编码123456789.20212223.单词值单词值内部字符串整数值数值0 或 1内部字符串-.-例：词法分析 while(i=j)i-;转换为单词序列:=,-单词序列的机器编码表示示例:3.1.2 实现方案实现方案：1.词法分析单独作为一遍2.词法分析程序作为单独的子程序优点优点:结构清晰、各遍功能单一结构清晰、各遍功能单一缺点：效率低缺点：效率低S.P.(字符串)词法分析词法分析S.P.(符号串)语法分析语法分析第一遍第一遍第二遍第二遍单词串单词串S.P.(字符串)词法分词法分析程序析程序语法分语法分析程
5、序析程序取单词取单词单词单词3、扫描缓冲区的支配：分成两个半区，互补运用单词定界：起点指示器起先位置 搜寻指示器终点位置2、预处理-预处理子程序：删除注释和其他一些非程序必要成分（空白符、跳格符、回车符、换行符）。将预处理结果放入扫描缓冲区3.2 3.2 词法分析器的设计词法分析器的设计3.2.1 3.2.1 输入、预处理输入、预处理1 1、输入源程序文本放入输入缓冲区。、输入源程序文本放入输入缓冲区。超前搜寻技术在单词识别中的应用：(在某些语言中，单词间可以没有空格或其他分隔符分隔，关键字也可作为变量名)关键字的识别:例IF(5.EQ.M)(对比IF(5)=9)标识符的识别:例DO99K=1
6、.10(对比DO99K=1,10)常数的识别：例123.34算符和界符的识别：例i+;3.2.2 3.2.2 扫描识别单词扫描识别单词扫描器的实现技术是词法分析器实现的核心技术，后面具体介绍，扫描器的实现技术是词法分析器实现的核心技术，后面具体介绍，本小节只简洁介绍其中的一项小技术：超前搜寻技术本小节只简洁介绍其中的一项小技术：超前搜寻技术3.2.3 3.2.3 状态转换图状态转换图概念概念：有限个结点的有向图表示方法表示方法：状态(结点)、初态、终态、状态转换(弧)用处用处：可用来识别某个字符串是否是某个正规语言的句子（如识别整常数的状态图可识别出32172是一个整常数)词法分析程序的设计：
7、词法分析程序的设计：词法规则词法规则 状态图状态图 词法分析程序词法分析程序L(M)=Bn|n0,其中 B=01,10，识别该语言句子的其状态图为：SUVZ111000例：输入字符串x=01101 和1001识别算法（自然语言描述）识别算法（自然语言描述）利用状态图可按如下步骤分析和识别字符串x：1、置初始状态为当前状态，从x的最左字符起先，重复步骤2，直到x右端为止。2、扫描x的下一个字符，在当前状态所射出的弧中找出标记有该字符的弧，并沿此弧过渡到下一个状态；假如找不到标有该字符的弧，那么x不是句子，过程到此结束；假如扫描的是x的最右端字符，并从当前状态动身沿着标有该字符的弧过渡到下一个状态
8、为终止状态Z，则x是句子。*标识符标识符 *无符号整数无符号整数运算符、分界符运算符、分界符S标非字母数字字母字母、数字数非数字数字数字+*，（）出错出错其他读字符读字符查保留字表查保留字表返回返回S出口出口出口出口出口出口字母、数字标识符标识符出口出口S标非字母数字字母无符号整数无符号整数出口出口S数非数字数字数字单字符分界符单字符分界符出口出口S+*，（）*n状态转换图的实现：n两种思路：n依据状态转换图的子图结构设计相应的程序结构，不同输入转入不同(状态)处理过程n实现状态转换表，程序在当前状态和当前输入驱动下进行状态转化工作n第一种：以输入处理为核心n状态对应一段处理程序，终态一般对应
9、的程序段有一个return语句，返回识别出来的单词。n不含回路的分支状态子图，对应一个switch()语句结构或一组if-else语句结构。n含回路的状态子图，对应一个while语句结构。n例如，图2-4(a)的状态i所对应的switch语句如下：例如，图3-4(a)的状态i所对应的switch语句如下：s=getchar();switch(s)case a-z:;/*实现状态j功能的语句*/case 0-9:;/*实现状态k功能的语句*/例如，图2-4(b)的状态i所对应的while语句如下：getchar();while(letter()|digit()getchar();/*实现状态j功
10、能的语句*/n其次种：以状态转换为核心n用变量s表示当前状态,token表示当前识别的单词。n用一个大的分支语句实现状态转换表功能，整个程序在表驱动下，循环读入字符，进行状态转换。其他类似以输入处理为核心。n以图2-3(a)为例,状态转换表n以图2-3(a)为例S=0;token=未定;While(1)Swich(S)Case 0:a=getchar();if (a是字母)S=1;else error;break;Case 1:a=getchar();if (a是字母或数字)S=1;else S=2;break;Case 2:回退一个字符;token=标识符;return token;n两种实
11、现方式比较：n前者效率高些n后者结构清晰一些3.2.3 状态图的实现示例状态图的实现示例构造词法分析程序构造词法分析程序1.单词及内部表示单词及内部表示:保留字和分界符接受一符一类保留字和分界符接受一符一类2.词法分析程序须要引用的公共（全局）变量和过程词法分析程序须要引用的公共（全局）变量和过程p443、词法分析程序算法、词法分析程序算法 p45图3-3 简洁词法分析的状态转换图 2.2.3 状态转换图的实现变量说明：(1)ch：字符变量，存放最新读入的源程序字符。(2)strToken：字符数组，存放构成单词符号的字符串。过程说明：(3)GetBC()：若ch中的字符为空白，则调用GetC
12、har()，直至ch为非空白符为止。(4)Concat()：将strToken中的字符串与ch中的字符连接并作为strToken中新的字符串。(5)Isletter()和IsDigit()：推断ch中的字符是否为字母和数字，是则返回true，否则返回false(6)Reserve()：按strToken中的字符串查表3.1中的前五项(即判别其是否为保留字)，若是保留字则返回它的编码，否则返回0值。(7)Retract()：扫描指针回退一个字符，同时将ch置为空白。(8)InsertID(),InsertcConst()：将标识符登录到符号表或将常数登录到常数表。(9)error()：出现非法字
13、符，显示出错信息。3.3 正规表达式与有限自动机正规表达式与有限自动机词法分析程序的设计：词法分析程序的设计：词法规则词法规则 状态图状态图 词法分析程序词法分析程序正规表达式正规表达式 非确定有限状态机非确定有限状态机 确定有限状态机确定有限状态机 化简化简3.3.1 正规表达式和正规集合的递归定义正规表达式和正规集合的递归定义有字母表有字母表,定义在定义在 上的正规表达式和正规集合递归定义如下上的正规表达式和正规集合递归定义如下:1.1.和和 都是都是 上的正规表达式上的正规表达式,它们所表示的正规集合分别为它们所表示的正规集合分别为:和和;2.2.任何任何a a ,a,a是是 上的正规表
14、达式上的正规表达式,它所表示的正规集合为它所表示的正规集合为:a;a;3.3.假定假定U U和和V V 上的正规表达式上的正规表达式,它们所表示的正规集合分别记为它们所表示的正规集合分别记为L(U)L(U)和和L(V),L(V),那么那么U|V,UU|V,UV V和和U U*也都是也都是 上的正规表达式上的正规表达式,它们所表示的它们所表示的 正规集合分别为正规集合分别为L(U)L(U)L(V)L(V)、L(U)L(U)L(V)L(V)和和L(U)L(U)*4.4.任何任何 上的正规表达式和正规集合均由上的正规表达式和正规集合均由1 1、2 2和和3 3产生。产生。正规表达式中的运算符：正规表
15、达式中的运算符：|-或（选择）或（选择）-连接连接 *-*-重复重复 （）（）-括号括号运算符的优先级：运算符的优先级：先先*,后后 ,最终最终|在正规表达式中可以省略在正规表达式中可以省略.正规表达式相等正规表达式相等 这两个正规表达式表示的语言相等这两个正规表达式表示的语言相等例：设例：设 =a,b,a,b,下面是定义在下面是定义在 上的正规表达式和正规集合上的正规表达式和正规集合正规表达式正规表达式ba*a(a|b)*(a|b)*(aa|bb)(a|b)*正规集合正规集合正规表达式的性质：正规表达式的性质：设设e1,e2和和e3均是某字母表上的正规表达式均是某字母表上的正规表达式,则有则
16、有:单位正规表达式单位正规表达式:e=e =e 交换律交换律:e1|e2=e2|e1结合律结合律:e1|(e2|e3)=(e1|e2)|e3 e1(e2e3)=(e1e2)e3安排律安排律:e1(e2|e3)=e1e2|e1e3 (e1|e2)e3=e1e3|e2e3 3.3.2 确定有限自动机（确定有限自动机（DFA）前面介绍状态图的形式化一个确定的有限自动机（DFA）M是一个五元式:M=(S,，S0，Z)其中其中:1.S 有限状态集有限状态集2.输入字母表输入字母表3.映射函数映射函数(也称状态转换函数也称状态转换函数)SS (s,a)=S ,S,S S,aS,a4.S0 初始状态初始状态
17、 S0 SS5.Z终止状态集终止状态集 Z S状态转移函数可用一矩阵来表示：输入 字符 状态 a b 0 1 2 1 3 2 2 1 3 3 3 3例如例如:M:M:（0,1,2,3,a,b,0,1,2,3,a,b,，0，3）（0，a）=1 （0，b）=2 （1，a）=3 （1，b）=2 （2，a）=1 （2，b）=3 （3，a）=3 （3，b）=3所谓确定的自动机，其确定性表现在状态转移函数是单值函数！一个一个DFADFA也可以用一状态转换图表示：也可以用一状态转换图表示：DFADFA的状态图表示的状态图表示：1032startaabba,b 输入 字符 状态 a b 0 1 2 1 3 2
18、 2 1 3 3 3 3baDFA MDFA M所接受的符号串：所接受的符号串：若存在一条初始状态到某一终止状态的路径，且这条路径上能若存在一条初始状态到某一终止状态的路径，且这条路径上能有弧的标记符号连接成符号串有弧的标记符号连接成符号串，则称则称为为DFA MDFA M（接受）识别接受）识别。DFA MDFA M所接受的语言为：所接受的语言为：L(M)=|L(M)=|(S0,)=S)=Sn,n,S Sn n ZZ3.3.3 非确定的有限自动机非确定的有限自动机(NFA)若若是一个多值函数，且输入可允许为是一个多值函数，且输入可允许为，则有限自动机是不确定的则有限自动机是不确定的,即在某个状
19、态下，对于某个输入字符存在多个后继状态即在某个状态下，对于某个输入字符存在多个后继状态.NFA的形式定义为:一个非确定的有限自动机NFA M是一个五元式:NFA M=(S,S0,F)其中 S有限状态集 输入符号.S0初态集 F终态集 转换函数 S*2S (2S-S的幂集S的子集构成的集合）NFA M所接受的语言为所接受的语言为:L(M)=|(S0,)=S SZ 例：NFA M=(1,2,3,4,a,b,c,d,1,4)符号 状态 a b c 1 4 2，3 2 2 4 3 3，4 4 上例题相应的状态图为：上例题相应的状态图为：1234startabacacM所接受的语言（用正规表达式）所接受
20、的语言（用正规表达式）R=aa b|ac c|符号符号 状态状态 a b c 1 4 2，3 2 2 4 3 3，4 4 nNFA和DFA的区分：n(1)NFA可以有若干个初始状态，而DFA仅有一个初始状态；n(2)NFA的状态转换函数f不是单值函数，而是一个多值函数，不能由当前状态和当前输入字符惟一地确定下一个要转换的状态。1 1、从正规式构造非确定有限自动机、从正规式构造非确定有限自动机 方法方法1 1：自底而上构造，运用：自底而上构造，运用P55P55的状态图的合并规则，的状态图的合并规则，从待分析的正规式从待分析的正规式 r r的最小结构单元起先逐步合并状的最小结构单元起先逐步合并状态
21、转换图构造态转换图构造NFM MNFM M。(证明过程事实上就是构造与正证明过程事实上就是构造与正规式等价的非确定有限自动机的算法。规式等价的非确定有限自动机的算法。)证明：证明：P55P553.3.4 从正规式起先构造与其等价的确定有限自动机从正规式起先构造与其等价的确定有限自动机方法方法2：自上而下构造，利用转换：自上而下构造，利用转换(分解分解)规则，逐步分解规则，逐步分解待分析的正规式待分析的正规式r为更简洁的结构，同时转换拓展转换为更简洁的结构，同时转换拓展转换图直至图直至NFM M。拓展转换图：状态转换图的弧上标识为正规表达式拓展转换图：状态转换图的弧上标识为正规表达式转换规则 对
22、正规表达式接受如下所示的三条转换规则来构造对正规表达式接受如下所示的三条转换规则来构造NFA MNFA M。逐步将逐步将初始拓展转换图初始拓展转换图运用三条转换规则不断运用三条转换规则不断加入新加入新结点，结点，分解分解正规表达式的结构正规表达式的结构，直至每条有向边上仅，直至每条有向边上仅标识有标识有的一个字母或的一个字母或为止，则为止，则NFA M构造完成构造完成初始拓展转换图初始拓展转换图n例 对给定正规表达式b*(dad)(bab)+构造其NFA M。图2-12 NFA M例：构造与例：构造与01*|101*|1等价的等价的NFANFA练习：构造与（练习：构造与（a|b)*(aa|bb
23、)(a|b)*a|b)*(aa|bb)(a|b)*等价等价的的NFANFA 2、NFA的确定化的确定化 证明：非确定的有限自动机与确定的有限自动机从功能上来说是等价的，也就是说，我们能够从：NFA MDFA M构造成一个使得 L(M)=L(M)为了使得NFA确定化，我们首先给出两个定义：定义1、集合I的-闭包：令令I是一个状态集的子集，定义是一个状态集的子集，定义-closure（I）为：）为：1）若）若sI，则，则s-closure（I）；）；2）若）若sI，则从，则从s动身经过随意条动身经过随意条弧能够到达的任何弧能够到达的任何 状态都属于状态都属于-closure（I）。）。状态集状态集
24、-closure（I）称为）称为I的的-闭包闭包我们可以通过一例子来说明状态子集的-闭包的构造方法例：如图所示的状态图：令I=1，求-closure（I）=？依据定义：-closure（I）=1，3156432aaa7a我们同样可以通过一例子来说明上述定义,仍接受前面给定的状态图为例-J是从状态子集I中的每个状态动身,经过标记为a的弧而达到的状态集合.-Ia-Ia是状态子集是状态子集,其元素为其元素为J J中的状态中的状态,加上从加上从J J中每一个中每一个状态动身通过状态动身通过弧到达的状态弧到达的状态定义2:令I是NFA M的状态集的一个子集,a 定义:Ia=-closure(J)其中J=
25、(s,a)SI例：令 I=1 Ia=-closure(J)=-closure(（1，a）=-closure(2，4）=2，4，6,7依据定义1，2，可以用子集法将下面的NFA M确定化，NFA M确定化算法：P491)改造M2)子集法：156432aaab7a 例例：（a|b)*(aa|bb)(a|b)*a|b)*(aa|bb)(a|b)*对应的对应的NFANFA用状态子集法构造图用状态子集法构造图3.43.4的状态转换矩阵：的状态转换矩阵：I Ia Ib I Ia Ib X,5,1X,5,1 5,3,1 5,4,1 5,3,1 5,4,1 5,3,1 5,3,1,2,6,Y 5,4,1 5,
26、3,1 5,3,1,2,6,Y 5,4,15,4,1 5,3,1 5,4,1,2,6,Y5,4,1 5,3,1 5,4,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y 5,3,1,2,6,Y 5,4,1,6,Y 5,3,1,2,6,Y 5,4,1,6,Y5,4,1,6,Y5,4,1,6,Y 5,3,1,6,Y 5,4,1,2,6,Y 5,3,1,6,Y 5,4,1,2,6,Y5,4,1,2,6,Y5,4,1,2,6,Y 5,3,1,6,Y 5,4,1,2,6,Y 5,3,1,6,Y 5,4,1,2,6,Y5,3,1,6,Y5,3,1,6,Y 5,3,1,2,6,Y 5,4,1,6,
27、Y 5,3,1,2,6,Y 5,4,1,6,Y状态子集重新命名后状态转换矩阵状态子集重新命名后状态转换矩阵 S a b S a b 0 0 1 2 1 2 1 3 2 1 3 2 2 1 5 2 1 5 3 3 3 4 3 4 4 4 6 5 6 5 5 5 6 5 6 5 6 6 3 4 3 4 未化简未化简DFADFA 目的：目的：找寻一个状态数比找寻一个状态数比M M少的有限自动机少的有限自动机MM，使得，使得 L(M)=L(M)L(M)=L(M)概念：概念：状态状态S S与与T T等价：等价：S S与与T T到达终态经过的字到达终态经过的字w w的集合相等。的集合相等。不等价则称不等价
28、则称S S、T T可区分。可区分。算法思想：算法思想：DFA M DFA M的状态最少化过程旨在将的状态最少化过程旨在将M M的状态分割成一些不相交的状态分割成一些不相交的子集，使得任何不同子集中的状态都是可区分的，而同一的子集，使得任何不同子集中的状态都是可区分的，而同一子集内的任何两个状态都是等价的，等价的状态可以合并为子集内的任何两个状态都是等价的，等价的状态可以合并为一个状态。一个状态。3、化简化简DFADFA最小化步骤n（1）把S的终态和非终态分开，形成两个子集，得基本划分。n（2）对含有m个状态子集的某个划分中的每个子集I(i)，考察是否可以接着划分，如I(i)中的状态在某输入a的
29、状况下转入N(N1)个不同的的子集中，则划分成N个不同的组。n（3）重复2直到的子集不能接着划分。3.4 3.4 例例：图：图3.83.8所示的化简：所示的化简：1032startaabba,b3.4 词法分析程序的自动生成器词法分析程序的自动生成器lex（lexical）lex的功能：的功能：lex源程序源程序S.P.字符串字符串lexL词法分析程序词法分析程序LS.P.单词字符串单词字符串下面我们介绍下面我们介绍lex源程序：源程序：3.4.1 lex源程序源程序一个一个lex源程序主要由三个部分组成源程序主要由三个部分组成:1.定义部分定义部分2.识别规则识别规则。3.用户子程序用户子程
30、序.每部分用每部分用%隔开隔开1.定义部分定义部分：定义部分包括正规定义式定义定义部分包括正规定义式定义正规定义式正规定义式是如下形式的是如下形式的lex语句：语句：D1 R1 D2 R2 Dn Rn 其中：其中：R1,R2，Rn 为正则表达式。为正则表达式。D1,D2，Dn 为正则表达式名字，称简名为正则表达式名字，称简名 例：标识符：例：标识符：letter A-Z ;相当于相当于A|B|.|Z digit 0-9 iden letter(letter|digit)*带符号整数：带符号整数：integer digitdigit*sign +|-signinteger signinteger
31、|integer2.识别规则识别规则：是一串如下形式的是一串如下形式的lex语句：语句：P1 A1 P2 A2 Pm AmPi：定义在定义在D1,D2,Dn上的正则表达式，也称上的正则表达式，也称词形词形。Ai：Ai为语句序列，它指出，在识别出词形为为语句序列，它指出，在识别出词形为Pi的单词以的单词以 后，词法分析器所应作的后，词法分析器所应作的动作动作。其基本动作是返回。其基本动作是返回 单词的类别编码和单词值。单词的类别编码和单词值。3、lex处理二义性问题的两条原则：处理二义性问题的两条原则：1.最长匹配原则最长匹配原则 在识别单词过程中，有一字符串在识别单词过程中，有一字符串 x x
32、 x x x 根据最长匹配原则，应识别为这是根据最长匹配原则，应识别为这是 一个符合一个符合Pk规则单词，而不是规则单词，而不是Pj和和Pi规则的单词。规则的单词。PjPiPk2.最优匹配原则最优匹配原则 如有一字符串，有两条规则可以同时匹配时，那么用规则如有一字符串，有两条规则可以同时匹配时，那么用规则序列中位于前面的规则相匹配，所以排列在前面的规则优先权序列中位于前面的规则相匹配，所以排列在前面的规则优先权最高最高%#include int lineno=0;%float dig+.?(dig+)?%float sscanf(yytext,%lf,&yylval);return NUMBE
33、R;%yywrap()return 1;4.例：例：lex源程序的部分代码：源程序的部分代码：定义部分，包括定义部分，包括include include 部分部分和正规定义部分和正规定义部分识别规则部分识别规则部分用户子函数用户子函数3.4.2 lex的实现的实现1、lex的功能的功能是依据是依据lex源程序构造一个词法分析程序，该词法分析器实质源程序构造一个词法分析程序，该词法分析器实质上是一个有限自动机。上是一个有限自动机。lex生成的词法分析程序有两部分组成生成的词法分析程序有两部分组成:词法分析程序词法分析程序状态转换矩阵状态转换矩阵(DFA)控制执行程序控制执行程序lex的功能是依据的功能是依据lex源程序生成状态转换矩阵和限制程序源程序生成状态转换矩阵和限制程序精品课件精品课件！精品课件精品课件！2、lex的工作过程的工作过程：扫描每条识别规则扫描每条识别规则Pi构造一相应的非确定有穷自动机构造一相应的非确定有穷自动机Mi将各条规则的有穷自动机将各条规则的有穷自动机Mi合并成一个新的合并成一个新的NFA M确定化确定化 NFADFA 即生成该即生成该DFA的状态转换矩阵和限制执行程序的状态转换矩阵和限制执行程序0P1startM1P2M2P3M3