第二章词法分析.

1第一章总结语言与语言的翻译编译器的基本组成编译器的分析/综合模式(编译器基础架构)扫描遍数编译器的编写词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词2第二章词法分析词法的双重含义规定单词形成的规则，被称为构词规则或词法规则。相当于立法，规定语言所允许的合法单词。根据构词规则识别输入序列，被称为词法分析。相当于执法，识别出合法的单词、指出非法的输入序列。主要内容词法分析中的若干问题模式的形式化描述记号的识别从正规式到词法分析器上机：DBMS的设计与实现—SQL的词法分析器x:=y+z*60.0;id1:=id2+id3*60.0;32.1词法分析中的若干问题记号、模式与单词单词的基本分类：关键字kw(keyword,orreservedword)标识符id(identifier)字面量literal特殊符号ks(keysymbol,orspecialsymbol)[例2.1]语句position:=initial+rate*60记号idksidksidksnumber注意：称识别出id而不是rate或initial问题：根据什么识别这些词法的基本单位（词法元素）？42.1词法分析中的若干问题三个术语：模式(pattern)：产生和识别元素的规则记号(token)：按照某个模式(或规则)识别出的元素(一组)单词(lexeme)：被识别出的元素自身的值(一个)，也称为词值记号的类别单词举例模式的非形式化描述const(01)constconstif(03)ififrelation(81),=,=,,,=,=,=,...id(82)pi,count,D2字母打头的字母数字串num(83)3.1416,0,6.02E23任何数值常数literal(84)“coredumped”双引号间的任意字符串Comment{xisaninteger}括号间的任意字符串52.1词法分析中的若干问题记号的属性记号是按照某个模式识别出的元素。赋值句position:=initial+rate*60position、initial和rate均为标识符，种类均是id。问题：当识别出一个id时，如何判定是哪个id？当识别出一个relation时，究竟是=还是？记号＝记号的类别＋记号的属性[例2.2]表达式mycount25由三个记号组成类别828183属性“mycount”525注意：5与25的区别（根据记号的类别）25与“25”的区别（如何区别？）记号的类别relation(81)id(82)num(83)62.1词法分析中的若干问题词法分析器的作用与工作方式词法分析器是编译器中唯一与源程序打交道的部分。滤掉源程序中的无用成分，如注释、空格、回车等；处理与平台有关的输入，如文件结束符的不同表示等；根据模式识别记号，并交给语法分析器；调用符号表管理器或出错处理器，进行相关处理。工作方式：单独扫描，作为语法分析器的子程序，并行工作词法分析器源程序记号流词法分析器语法分析器调用返回记号源程序语法树词法分析器源程序记号流语法分析器语法树72.2模式的形式化描述字符串与语言从词法分析的角度看程序设计语言，它是由记号组成的集合。定义2.1语言L是有限字母表∑上有限长度字符串的集合说明：1.字母表是字符的集合，这些字符可以组成字符串。2.两个有限（计算机的表达能力有限）：字母表是有限的；字符串的长度是有限的。[例2.3]字母表∑={a,b,c}，则其上的语言L={ε,a,b,c,aa,ab,ac,ba,bb,bc,...}82.2模式的形式化描述字符串的基本概念术语示例|S||abc|=3ε|ε|=0S1S2abcdef=abcdefSn(abc)3=abcabcabcS的前缀Xabc的前缀有：ε，a，ab,abcS的后缀Xabc的后缀有：ε，c，bc,abcS的子串Xabc的子串有：ε，a，b,c,…S的真前缀abc的真前缀有：a，abS的真后缀？S的真子串？S的子序列Xabdf是abcdef的一个子序列92.2模式的形式化描述若L={a,b},M={c,d}，则LM={ac,bc,ad,bd}，L∩M=ΦL*={ε,a,b,aa,bb,ab,ba,aaa,...}L+={a,b,aa,bb,ab,ba,aaa,...}术语意义Φ空集合{ε}空串是唯一元素X=L∪M并:X={s|s∈Lors∈M}X=L∩M交:X={s|s∈Lands∈M}X=LM连接:X={st|s∈Landt∈M}X=L*(星)闭包:X=L0∪L1∪L2∪...X=L+正闭包:X=L1∪L2∪L3∪...102.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(s)，（c）r*是正规式，表示集合(L(r))*，（d）(r)是正规式，表示的集合仍然是L(r)可用正规式描述的语言称为正规语言或正规集。112.2模式的形式化描述定义2.2说明：1.运算的优先级与结合性三种运算均具有左结合性质；优先级从高到低：闭包、连接、或。正规式中不必要的括号可以被省略。例如：(a)|(((b)*)(c))可以简化成a|b*c。2.正规式的等价不同算术表达式可以表示同一个数，如3+5、5+3、2+6等均表示8。不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系。122.2模式的形式化描述定义2.3若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q。[例2.4]设字母表∑={a，b，c}，则∑上有：正规式正规集a，b，c{a}，{b}，{c}a|b，b|a{a}∪{b}={a，b}a(a|b)*{a，aa，ab，aba，abb，aab，...}，a为首的ab串∑*{ε，a，b，c，aa，ab，ac，ba，bb，bc，...}[例2.5]令L(x)={a，b}，L(y)={c，d}，则L(x|y)={a，b，c，d}L(y|x)={a，b，c，d}132.2模式的形式化描述利用正规式的等价性可以化简复杂的正规式。正规式的等价性判定可以采用两种方法：根据定义，证明不同的正规式表示同一集合（例2.5）根据下述正规式的代数性质进行运算公理公理r|s=s|r(rs)t=r(st)r|(s|t)=(r|s)|tεr=r,rε=rr(s|t)=rs|rtr*=(r+|ε)(s|t)r=sr|trr**=r*142.2模式的形式化描述记号的说明自然语言对模式的非形式化描述很不精确，而正规式可以严格地规定记号的模式，用正规式说明记号的公式为：记号=正规式读作（左边）记号定义为（右边）正规式或者记号是正规式例如，id=a(a|b)*可以读作为id定义为a(a|b)*注：在不引起混淆的情况下，把说明记号的公式简称为正规式，或者规则。152.2模式的形式化描述[例2.6]记号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)(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)*)返回162.2模式的形式化描述简化正规式描述1.正闭包若r是表示L(r)的正规式，则r+是表示(L(r))+的正规式：r+=rr*=r*r，r*=r+|ε例如：(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)+2.可缺省若r是正规式，则r?是表示L(r)∪{ε}的正规式：r?=r|ε例如：E(+|-|ε)可改写为：E(+|-)?注：+、?、*具有相同的结合性和优先级引入？的原因在于字符ε无法使用键盘输入。172.2模式的形式化描述3.字符组若r是仅由|运算构成的正规式，则可改写为[r']，其中r'可以有如下两种形式：枚举：如[abc]，等价于a|b|c分段:如[0-9a-z]，等价于[0123456789abcdefghijklmnopqrstuvwxyz]4.非字符组若[r]是一个字符组形式的正规式，则[^r]是表示∑-L(r)的正规式。例如：若∑={a,b,c,d,e,f,g}，则L([^abc])={d,e,f,g}182.2模式的形式化描述辅助定义通俗地讲，辅助定义的作用是为复杂的或重复出现的正规式命名，并在以后的使用中用名字代替该正规式。辅助定义的形式与正规式一样：辅助定义名字=正规式注：1.辅助定义不与任何模式匹配；2.作为辅助定义的正规式仅供内部使用，而不用于说明记号。辅助定义：内部名=正规式规则：记号名=正规式192.2模式的形式化描述[例2.6]引入正规式的缩写形式和辅助定义式后，id和num的正规定义式可重写如下：char=[a-zA-Z]digit=[0-9]digits=digit+optional_fraction=(.digits)?optional_exponent=(E(+|-)?digits)?id=char(char|digit)*num=digitsoptional_fractionoptional_exponent对比原来20上次课总结词法的双重含义；模式、记号与单词；形式化描述：正规式与正规集；正规式描述；正规式简化表示、辅助定义212.3记号的识别－有限自动机模式的描述―正规式记号的识别―有限自动机（不确定、确定）不确定的有限自动机（NondeterministicFiniteAutomaton,NFA）定义2.4NFA是一个五元组（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记号的识别－有限自动机NFA两种直观的表示方式①状态转换图NFA中的每个状态，对应转换图中的一个节点；NFA中的每个move(si,a)=sj，对应转换图中的一条有向边；表示从节点si出发进入节点sj，字符a(或ε)是边上的标记。②状态转换矩阵每个矩阵元素M[si,a]中的内容，是从状态si出发，经字符a(或ε)所到达的下一状态sj；在转换矩阵中，一般以矩阵第一行所对应的状态为初态，而终态需要特别指出。...aijsisja状态转换图中如何表示呢？232.3记号的识别－有限自动机[例2.7]识别正规式(a|b)*abb所描述正规集的NFA的三种表示形式分别如下。(其中转换矩阵表示中0为初态，3为终态)S={0,1,2,3},Σ={a,b}move={m