【教学课件】第二章词法分析.ppt

《【教学课件】第二章词法分析.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第二章词法分析.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 词法分析词法分析：x :=y +z *60.0 ;id1:=id2+id3*60.0;词法的双重含义：1.规定单词形成的规则，也被称为构词规则或词法规则。它的作用相当于立法，规定什么样的输入序列是语言所允许的合法单词。2.根据构词规则识别输入序列，也被称为词法分析。它的作用相当于执法，根据规则识别出合法的单词和指出非法的输入序列。本章主要内容：1.与词法分析有关的基本概念和相关问题2.模式的形式化描述正规式3.记号的识别有限自动机（NFA，DFA）4.词法分析器的构造从正规式到DFA5.上机作业第一部分：函数绘图语言的词法分析器12.1词法分析中的若干问题2.1.1 记号、模式与单词单

2、词的基本分类：关键字(保留字)kw(key word,or reserved word)标识符 id(identifier)字面量 literal特殊符号 ks(key symbol,or special symbol)例2.1 语句position:=initial+rate*60记号id ks id ks id ks number注意：称识别出id而不是rate或initial问题：根据什么识别这些词法的基本单位（词法元素）？22.1.1 记号、模式与单词（续1）三个术语：模式(patten)：产生和识别元素的规则 记号(token)：按照某个模式(或规则)识别出的元素(一组)单词(lex

3、eme)：被识别出的元素自身的值(一个)，也称为词值 记号的类别单词举例模式的非形式化描述const(01)const constif(03)ififrelation(81),=,=,=或=或=id(82)pi,count,D2字母打头的字母数字串 num(83)3.1416,0,6.02E23 任何数值常数 literal(84)“core dumped”双引号之间的任意字符串 Comment x is an integer括号之间的任意字符串 返回32.1.2 记号的属性 记号是按照某个模式识别出的元素。再考察赋值句position:=initial+rate*60position、ini

4、tial和rate均为标识符，即它们的种类均是id。问题：当识别出一个id时，如何判定是哪个id？同样，当识别出一个relations时，究竟是=还是 25 由三个记号组成类别属性82 81 83“mycount”5 25记号的类别 单词举例 记号的非形式化描述relation(81),=,=,=或=或=id(82)pi,count,D2 字母打头的字母数字串num(83)3.1416,0,6.02E23 任何数值常数注意：5与25的区别（根据记号的类别）25与“25”的区别（如何区别？）42.1.3 词法分析器的作用与工作方式 特征：编译器中唯一与源程序打交道的部分 任务：1.滤掉源程序中的

5、无用成分，如注释、空格、回车等2.处理与具体平台有关的输入(如文件结束符的不同表示等)3.识别记号，并交给语法分析器。根据模式识别记号4.调用符号表管理器或出错处理器，进行相关处理 工作方式：1.单独一遍扫描2.作为语法分析器的子程序3.并行方式52.2 模式的形式化描述 2.2.1 字符串与语言 从词法分析的角度看程序设计语言，它是由记号组成的集合。从本章开始，我们用定义的方式表示一些重要的概念，目的是希望同学们深刻理解并牢固记忆这些基本概念。由于不同的教材（或出版物）对相同的概念有不同的称谓，因此希望同学们掌握概念的实质，而不是死记几个名词术语。62.2.1 字符串与语言（续1）定义2.1

6、 语言L是有限字母表上有限长度字符串的集合。字母表是组成字符串的所有字符的集合。换句话说，字符串中的所有字符取自字母表。定义中强调两个有限，因为计算机的表示能力有限：1.字母表是有限的，即字母表中元素是有限多个；2.字符串的长度是有限的，即字符串中字符个数是有限多个。由于字符串的有序性，使得以字符串作为元素的集合，与一般意义下的集合有所不同，反映在集合运算上，强调了有序。7字符串的基本概念（表2.2）2.2.1 字符串与语言（续1）表示、术语|S|S1S2 Sn S的前缀X S的后缀X S的子串X S的真前缀、真后缀、真子串 S的子序列X|abc|=3|=0“abc”“def”=“abcdef

7、”“abc”3=“abcabcabc”“abc”的前缀可以是：，a，ab,abc“abc”的前缀可以是：，c，bc,abc“abc”的子串可以是：，a，b,c,“abc”的真前缀可以是：a，ab？“abdf”是“abcdef”的一个子序列（S中去掉0或若干个不一定连续的字符后形成的字符串）举例8字符串集合的运算（表2.3）2.2.1 字符串与语言（续2）表示、术语 X=LM X=LM X=LM X=L*X=L+空集合，即元素个数为0的集合空串作为唯一元素的集合 X是集合L和M的并:X=s|sL or sM X是集合L和M的交:X=s|sL and sM X是集合L和M的连接:X=st|sL a

8、nd tM X是集合L的(星)闭包:X=L0L1L2.X是集合L的正闭包:X=L1L2L3.若 L=a,b,M=c,d则 LM=ac,bc,ad,bd (而LM=)L*=,a,b,aa,bb,ab,ba,aaa,.L+=a,b,aa,bb,ab,ba,aaa,.意义92.2.2 正规式与正规集 定义2.2 令是一个有限字母表，则上的正规式及其表示的集合递归定义如下:1.是正规式，它表示集合L()=2.若a是上的字符，则a是正规式，它表示集合L(a)=a 3.若正规式r和s分别表示集合L(r)和L(s)，则 （a）r|s是正规式，表示集合L(r)L(s)，（b）rs是正规式，表示集合L(r)L(

9、s)，（c）r*是正规式，表示集合(L(r)*，（d）(r)是正规式，表示的集合仍然是L(r)。（加括弧改变优先级、结合性）可用正规式描述的语言称为正规语言或正规集。102.2.2 正规式与正规集（续1）若正规式的优先级和结合性做下述约定:1.三种运算均具有左结合性质；2.优先级从高到低顺序排列为:闭包运算、连接运算、或运算。则正规式中不必要的括号可以被省略。例如，(a)|(b)*)(c)可以简化成a|b*c。正规式的等价 不同算术表达式可以表示同一个数，如3+5、5+3、2+6等均表示8。不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系。运算的优先级与结合性112.2.2

10、 正规式与正规集（续2）定义2.3 若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q。例2.3 设字母表=a，b，c，则上部分正规式和正规集如下：正规式 对应正规集 a，b，c a|b，b|aa(a|b)*例2.4 令 L(x)=a，b，L(y)=c，d，则 L(x|y)=a，b，c，d L(y|x)=a，b，c，d a，b，c ab=a，b a，aa，ab，aba，abb，aab，.，a为首的ab字符串，a，b，c，aa，ab，ac，ba，bb，bc，abc，.122.2.2 正规式与正规集（续3）正规式的代数性质（表2.4）r|s=s|r(rs)t=r(st)r|(s|t)

11、=(r|s)|tr=r=rr(s|t)=rs|rtr*=(r+|)(s|t)r=sr|tr r*=r*利用正规式的等价性可以化简复杂的正规式。正规式的等价性判定可以采用两种方法：根据定义，证明不同的正规式表示同一集合（例2.4）根据下述正规式的代数性质进行运算 正规式等价的判定（证明）时刻将正规表达式与算数表达式联系着理解132.2.3 记号的说明 正规式可以严格地规定记号的模式，用正规式说明记号的公式为：记号记号=正规式正规式可以读作为 “（左边）记号定义为（右边）正规式”，或者 “记号是正规式”例如 id=a(a|b)*可以读作为“id定义为a(a|b)*”通常在不引起混淆的情况下，也把说

12、明记号的公式简称为正规式，或者规则。142.2.3 记号的说明（续1)例2.5 记号relation、id和num分别是Pascal的关系运算符、标识符和无符号数，它们的正规式表示如下所示。relation=|=|=|=id=(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)num=(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|

13、5|6|7|8|9)*)(|E(+|-|)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|0|1|2|3|4|5|6|7|8|9)*太繁琐了！152.2.3 记号的说明（续2）(a)正闭包 若r是表示L(r)的正规式，则r+是表示(L(r)+的正规式，且下述等式成立:r+=rr*=r*r，r*=r+|+与*具有相同的运算结合性和优先级例如：(0|1

14、|2|3|4|5|6|7|8|9)()(0|1|2|3|4|5|6|7|8|9)*可以化简为：(0|1|2|3|4|5|6|7|8|9)+正规式的简化表示162.2.3 记号的说明（续3）(b)可缺省 若r是正规式，则r?是表示L(r)的正规式，且下述等式成立:r?=r|?也可以与*具有相同的运算结合性和优先级注意：引入算符？的主要目的是为了回避不可以直接通过键盘输入的字符。例如：E(+|-|)可以改写为：E(+|-)?172.2.3 记号的说明（续4）(c)字符组 若r是仅由|运算构成的正规式，则可改写为r，其中r可以有如下两种形式：枚举:如abc，它等价于：a|b|c 分段:如0-9a-z

15、，它等价于：0123456789abcdefghijklmnopqrstuvwxyz(d)非字符组 若r是一个字符组形式的正规式，则r是表示-L(r)的正规式。例如：若=a,b,c,d,e,f,g，则 L(abc)=d,e,f,g 182.2.3 记号的说明（续5）通俗地讲，辅助定义的作用是为复杂的或重复出现的正规式命名，并在以后的使用中用名字代替该正规式。辅助定义的形式与正规式一样：名字=正规式 引入辅助定义 但是辅助定义不与任何模式匹配。换句话说，作为辅助定义的正规式仅供内部使用，而不用于说明记号。辅助定义：内部名=正规式规则：记号名=正规式192.2.3 记号的说明（续6）例2.6 引入

16、正规式的缩写形式和辅助定义式后，id和num的正规定义式可重写如下。char =a-zA-Zdigit =0-9digits =digit+optional_fraction=(.digits)?optional_exponent=(E(+|-)?digits)?id =char(char|digit)*num=digits optional_fraction optional_exponent对比：id=(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|

17、V|W|X|Y|Z)(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|0|1|2|3|4|5|6|7|8|9)*num=(0|1|2|3|4|5|6|7|8|9)()(0|1|2|3|4|5|6|7|8|9)*(|.(0|1|2|3|4|5|6|7|8|9)()(0|1|2|3|4|5|6|7|8|9)*)(|E(+|-|)()(0|1|2|3|4|5|6|7|8|9)()(0|1|2|3|4|5|6|7|8|9)*)20上次课主要内容

18、/根据情况修改词法分析器的主要工作；记号、模式与单词；模式的形式化描述：正规式与正规集；记号的说明：正规式描述。num=(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)(|E(+|-|)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)212.3 记号的识别有限自动机 模式的描述正规式记号的识别有限自动机（确定、不确定）2.3.1 不确定的有限自动机（Nondeterministic Finite Automaton,NFA）

19、定义2.4 NFA是一个五元组（5-tuple）：M=（S，move，s0，F），其中（1）S是有限个状态（state）的集合；（2）是有限个输入字符（包括）的集合；（3）move是一个状态转移函数，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态sj；（4）s0是唯一的初态（也称开始状态）；（5）F是终态集（也称接受状态集），它是S的子集，包含了所有的终态。222.3.1 不确定的有限自动机（续1）状态转换图：用一个有向图来直观表示NFA NFA中的每个状态，对应转换图中的一个节点；NFA中的每个move(si,a)=sj，对应转换图中的一条有向边；表示从节点

20、si出发进入节点sj，字符a(或)是边上的标记。直观的表示方式232.3.1 不确定的有限自动机（续2）每个矩阵元素Msi,a中的内容，是从状态si出发，经字符a(或)所到达的下一状态sj；在转换矩阵中，一般以矩阵第一行所对应的状态为初态，而终态需要特别指出。状态转换矩阵：用一个矩阵来直观表示NFA。矩阵中，状态对应行，字符对应列；242.3.1 不确定的有限自动机（续3）例2.7 识别正规式(a|b)*abb所描述正规集的NFA的三种表示形式分别如下。(其中转换矩阵表示中0为初态，3为终态)定义：S=0,1,2,3,=a,bmove=move(0,a)=0,move(0,a)=1,move(

21、0,b)=0,move(1,b)=2,move(2,b)=3 s0=0,F=3状态转换矩阵状态转换图252.3.1 不确定的有限自动机（续4）记号在NFA中的表现（NFA如何识别记号）对字符串，从初态开始，经一系列状态转移到达终态。例如：对于字符串abb，有定义：move(0,a)=1,move(1,b)=2,move(2,b)=3转换矩阵：m0,a=0,1,m1,b=2,m2,b=3转换图：0a1b2b3 显然，转换图最直观，即每一个记号，实质上是从初态开始到某个终态的路径上的标记。move=move(0,a)=0,move(0,a)=1,move(0,b)=0,move(1,b)=2,mo

22、ve(2,b)=3262.3.1 不确定的有限自动机（续5）例2.8 识别表2.1中记号relation、id和num的转换图 relation=|=|=|=id=char(char|digit)*最长匹配原则272.3.1 不确定的有限自动机（续6）optional_fraction=(.digits)?optional_exponent=(E(+|-)?digits)?num=digits optional_fraction optional_exponent282.3.1 不确定的有限自动机（续7）NFA（识别记号）的特点 NFA识别记号的最大特点是它的不确定性，即在当前状态下对同一字符

23、有多于一个的下一状态转移。具体体现：定义：move函数是1对多的；状态转换图：同一状态有多于一条边标记相同字符转移到不同的状态；状态转换矩阵：Msi,a是一个状态的集合292.3.1 不确定的有限自动机（续8）S=0,1,2,3,=a,b s0=0,F=3move=move(0,a)=0,move(0,a)=1,move(0,b)=0,move(1,b)=2,move(2,b)=3正规式：(a|b)*abbmove函数是1对多的转换图：同一状态有多于一条边标记相同字符转移到不同的状态转换矩阵：Msi,a是一个状态的集合定义：302.3.1 不确定的有限自动机（续9）反复试探所有路径，直到到达终

24、态，或者到达不了终态。不确定性识别记号的困惑 识别输入序列时，在当前状态下遇到同一字符，应转移到哪个下一状态？例2.9 在正规式(a|b)*abb的NFA上识别输入序列abb和abab：非终态，不接受，试探下一路径终态，接受 NFA识别输入序列的一般方法312.3.1 不确定的有限自动机（续10）1.只有尝试了全部可能的路径，才能确定一个输入序列不被接受，而这些路径的条数随着路径长度的增长成指数增长。2.识别过程中需要进行大量回溯，时间复杂度升高且算法趋于复杂。NFA识别记号存在的问题问题：是否可以构造这样的有限自动机，它识别正规式所描述的字符串，且在任何一个状态下遇到同一字符最多有一个状态转

25、移？322.3.2 确定的有限自动机（Deterministic Finite Automaton,DFA）定义2.5 DFA是NFA的一个特例，其中：（1）没有状态具有状态转移(-transition)，即状态转换图中没有标记的边；（2）对每个状态s和每个字符a，最多有一个下一状态。与NFA相比，DFA的特征（确定性）定义：move（si,a)函数是1对1的；转换图：从一个节点出发的边上标记均不相同；转换矩阵：Msi,a是一个状态。且字母表不包括。332.3.2 确定的有限自动机（续1）对NFA施加两条限制：限制1：没有状态转移限制2：同一状态下没有重复字符的状态转移例2.10 正规式(a|

26、b)*abb的DFA和识别输入序列abb和abab：识别abb：0a1b2b3，状态，接受识别abab：0a1b2a1b2，？342.3.2 确定的有限自动机（续2）将在DFA上识别输入序列的过程形式化为算法，该算法被称为模拟器（模拟DFA的行为）或驱动器（用DFA的数据驱动分析动作）。算法与DFA一起，即构成识别记号的词法分析器的核心。它的最大特点是算法与模式无关，仅DFA与模式相关。352.3.2 确定的有限自动机（续3）s:=s0；ch:=nextchar；-初值while cheof-循环loopend loop;if-返回then return“yes”;else return“no

27、”;end if;用算法2.1识别abb：1.s=0,ch=a2.s=1,ch=b3.s=2,ch=b4.s=3,ch=eof5.yes用算法2.1识别abab：1.s=0,ch=a2.s=1,ch=b3.s=2,ch=a4.s=1,ch=b5.s=2,ch=eof6.no输入 DFA D和输入字符串x(eof)。D的初态为s0，终态集为F。输出 若D接受x，回答“yes”，否则回答“no”。方法 用下述过程识别x：算法2.1 模拟DFAs:=move(s,ch);ch:=nextchar;s is in F362.3.3 有限自动机的等价 定义2.6 若有限自动机M和M识别同一正规集，则称M和M是等价的，记为M=M。特别提示：正规式与有限自动机从两个侧面表示正规集。正规式是描述，自动机是识别。因此，当它们表示相同集合时，均存在等价的问题。想一想，有几种可能的等价？37结束（月 日）38