编译原理：第三章词法分析

第三章词法分析(LexicalAnalysis)主要内容：单词的描述工具：正规文法和正规式单词识别系统：有穷自动机词法分析程序的设计学习目标:掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换，NFA到DFA的转换、DFA的化简理解：正规文法、正规式、DFA的概念、NFA的概念3.1 词法分析程序的设计3.3 单词的形式化描述工具3.4 有穷自动机3.5 正则式和有穷自动机的等价性3.6由DFA构造词法分析程序3.1词法分析程序的设计确定词法分析器的接口确定单词分类和Token结构由DFA构造词法分析程序特殊问题的处理回顾:词法分析的主要任务是：从左到右逐个字符地扫描源程序，产生一个个单词(Token)，同时检查源程序中的词法错误。执行词法分析的程序称为词法分析程序或扫描程序(Scanner)。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。1 确定词法分析器的接口

确定词法分析器是作为语法分析的一个子程序还是作为独立一遍词法分析作为独立一遍 将字符流的源程序变成单词序列，输出到一个中间文件上，做为语法分析的输入。词法分析作为语法分析的子程序 每当语法分析程序需要一个单词时，则调用该子程序，从源程序中分析和返回一个单词独立词法分析器语法分析Token序列源程序附属词法分析器语法分析调用Token源程序2 确定单词分类和Token结构

设计词法分析器的首要任务是，对于源语言的单词进行仔细的分析，并列出所有可能的不同单词，然后再确定单词的内部表示

程序设计语言中的单词，一般可分为以下几类：1．基本字（关键字）：如begin，end，if等2．标识符：用来表示常量、变量、过程等的名字3．常数：各种类型的常数，如15，3.14，TRUE4．运算符：如+，—，*，/5．界符：如逗号，分号，括号等单词的机内表示二元式（单词种别，单词自身的值） 种别是语法分析需要的信息 自身值是编译其他阶段需要的信息种别编码(常用整数编码)方法一：按单词的5大种类每种一个码，例如标识符为l，常数为2，基本字为3，运算符为4，界符为5。方法二：每个基本字一个编码；所有标识符为一个编码；常数按类型分类，每类一个编码；每个运算符一个编码；每个界符一个编码。单词自身值对常数,基本字,运算符,界符就是他们本身的值对标识符,将标识符的属性登记在符号表中,“自身值”是指向该标识符所在符号表中位置的指针.例如源程序ifi=5thenx:=y;

种别编码：标识符为l，常数为2，基本字为3，运算符为4，界符为5词法分析后输出的单词序列是:(3,‘if’) (1,指向i的符号表入口)(4,‘=’)(2,‘5’)(3,‘then’)(1,指向x的符号表入口)(4,‘:=’)(1,指向y的符号表入口) (5,‘;’)3.3单词的形式化描述工具作用:描述单词的构成规则工具有:正规文法(RegularGrammar)

正规式(RegularExpression)3.3.1正规文法

多数程序设计语言单词的构成规则都能用正规文法(3型文法)描述正规文法回顾 文法的任一产生式α→β的形式都为A→aB或A→a，其中A，B∈VN

，a∈VT。 正规文法描述的是VT*上的正规集例如:

用l表示a~z中的任一英文字母，d表示0~9中任一数字描述标识符的正规文法为

<标识符>→l｜l<字母数字> <字母数字>→l｜d｜l<字母数字>｜d<字母数字>描述无符号整数的正规文法

<无符号整数>→d｜d<无符号整数>3.3.2正规式(正则表达式)

RegularExpression由正规式所表示的字符串的集合为正规集正规式与它所表示的正规集的递归定义 给定字母表∑ε和φ都是∑上的正规式，它所表示的正规集分别为｛ε｝和Ф；任何ａ∈∑，ａ是∑上的正规式，它所表示的正规集为｛ａ｝；假定ｅ1和ｅ2都是∑上的正规式，他们所表示的正规集分别为Ｌ(ｅ1)和Ｌ(ｅ2)，那么，以下也都是正规式和它们所表示的正规集：正规式r正规集L(r)(ｅ1)Ｌ(ｅ1)ｅ1｜ｅ2Ｌ(ｅ1)∪Ｌ(ｅ2)ｅ1.ｅ2Ｌ(ｅ1)Ｌ(ｅ2)ｅ1＊(Ｌ(ｅ1))＊仅由有限次使用上述三步定义的表达式才是∑上的正规式，仅由这些正规式所表示的字集才是∑上的正规集。说明:算符的优先顺序为:‘＊’>‘.’>‘｜’ ‘.’和‘｜’都是左结合例子：令={a，b}，上的正规式和相应的正规集有 正规式 正规集

a {a} ab {a,b} ab {ab} a {,a,aa,…任意个a的串} (ab)(ab) L(r)={a,b}{a,b}={aa,ab,ba,bb}

(ab) {,a,b,aa,ab……所有由a和b 组成的串}正规式 正规集a|bc* L(a|bc*)={a}∪({b}{,c,cc,…}) ={a}∪{b,bc,bcc…}={a,b,bc,bcc…}正规式的等价性 若两个正规式e1和e2所表示的正规集相同，则说e1和e2等价程序中的单词都能用正则式来定义令l为a~z的字母，d为0~9的数字e1=l(l|d)* e1表示标识符集合e2=dd* e2表示无符号整数注： <标识符>→l｜l<字母数字><字母数字>→l｜d｜l<字母数字>｜d<字母数字>

正规式比正规文法更简洁，容易理解单词的构成规律，且可以从正规式自动地构造识别程序，所以通常用正规式作为单词的描述工具提问∑={a,b,c}为以下正规集构造正规表达式每个字符串恰好包含一个b的正规集每个字符串最多包含一个b的正规集正规表达式的应用查找，替换、验证字符串，例如：验证密码的合法性长度：6-12个字符必须至少包含一个大写字母必须至少包含一个小写字母必须至少包含一个数字正规表达式的应用验证URL必须以http或者https，或者ftp开头，后跟随://必须匹配一个合理的域名可以包含一个端口号(:80)可以包含数字、字母、.

-？\3.3.3正规文法和正规式间的转换等价性：对任意一个正规文法，存在一个定义同一语言的正规式对任意一个正规式，存在一个定义同一语言的正规文法将∑上的一个正则式r转换成文法G=(VN,VT,S,P)VT=∑,首先形成产生式S->r,S为G的开始符不断利用下面的规则做变换,直到每个产生式最多含有一个终结符为止原产生式变换后产生式规则1A->xyA->xBB->y规则2A->x*yA->xAA->y规则3A->x|yA->xA->y其中B为一新非终结符例:将R=a(a|d)*转换成相应的正规文法令转换成文法G=(VN,VT,S,P)其中VT={a,d}，文法开始符为S首先形成S->a(a|d)*,然后变换S->aA A->(a|d)*A->(a|d)A A->εA->aA,A->dA 最终有产生式：S->aA，A->ε，A->aA，

A->dA将正规文法转换成正规式将每条产生式改写为正规式用代入法解正规式方程组最后只剩下一个开始符号定义的正则式,其中不含非终结符正则文法到正则式的转换规则:文法产生式正则式规则1A->xBB->yA=xy规则2A->xA|yA=x*y规则3A->xA->yA=x|y例：将文法G[S]转换成正规式

G：S→aA|aA→dA|d先由产生式得: S=aA|a A=d*d将A代入S中得: S=ad*d|a利用正则式变换得 S=a(d*d|ε)=ad*说明:d*d|ε =(ε|d|dd|…)d|ε =d|dd|…|ε=d* 所求正规式为ad*3.4有穷自动机(也称有限自动机)

FiniteAutomata作用:有穷自动机是描述算法的数学方法在词法分析中它作为一种识别装置（描述识别过程），能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合分类:

确定的有穷自动机

(DeterministicFiniteAutomata)

不确定的有穷自动机

(NondeterministicFiniteAutomata)金银岛游戏海盗岛金银岛船难湾步枪山死人岛暴徒岛走私谷金银岛游戏金银岛暴徒岛步枪山海盗岛船难湾死人岛走私谷有穷自动机和正规表达式的关系例：描述标识符的正规表达式是：令letter=a|b|…|z，digit=0|1|…|9标识符为：letter(letter|digit)*识别这样的标识符的过程可以用有穷自动机描述如下：状态：是识别过程中的一些位置，表示有多少模式已经被识别转换：记录从一个状态到另一个状态的转换开始状态：识别过程的开始位置终止状态：表示识别过程的结束一个字符串被识别的过程可以用识别过程中用到的状态和转换序列来表示例如：字符串“xtemp=5”中标识符“xtemp”的识别过程为：13letterletterdigit2other122222xtemp3=定义:

一个DFAM是一个五元组:M=（K，Σ，f，S，Z）K是一个有穷集，它的每个元素称为一个状态Σ是一个有穷字母表，它的每个元素称为一个输入字符f是转换函数，是在KX∑->K上的映射，f(ki,a)=kj意味着当前状态为ki、输入字符为a时，将转换到下一状态kjS∈K，是唯一的初态ZK,是一个终态集，终态也称为可接受状态或结束状态。3.4.1确定的有穷自动机（DFA）例DFAM=（{S，U，V，Q},{a，b},f,S,{Q}）其中f定义为：f（S，a）=U f（S，b）=Vf（V，a）=U f（V，b）=Qf（U，a）=Q f（U，b）=V f（Q，a）=Q f（Q，b）=QDFA表示成状态转换图(TransitionDiagram)每个状态对应图中的一个结点： 初态为唯一初态结点，用=〉标记； 终态对应终态结点，用双圈表示。若有f(ki,a)=kj，则从结点ki到结点kj画标记为a的弧。例DFAM=（{S，U，V，Q},{a，b},f,S,{Q}）f（S，a）=U f（S，b）=Vf（V，a）=U f（V，b）=Qf（U，a）=Q f（U，b）=V f（Q，a）=Q f（Q，b）=Q状态转换图表示为:bSUVQaaaba，bbDFA表示成状态转换矩阵(TransitionTable)例DFAM=（{S，U，V，Q},{a，b},f,S,{Q}）f（S，a）=U f（S，b）=Vf（V，a）=U f（V，b）=Qf（U，a）=Q f（U，b）=V f（Q，a）=Q f（Q，b）=Q字符状态0001行表示状态，用双箭头“=>”标明初态；否则第一行即是初态列表示输入字符相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值相应终态行在表的右端标以1，非终态标以0DFA识别(接受)的字符串对于Σ*中的任何字符串t，若存在一条从初态结到某一终态结的通路，且该通路上所有弧的标记符连接成的字符串等于t，则称t可以为DFAM所识别若DFAM的初态结同时又是终态结，则ε可为M所识别。bSUVQaaaba，bbbaab为DFA所接受DFAM所能接受的符号串的全体记为L(M).结论：

上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)

“确定性”的含义 转换函数f:K×Σ→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号a∈Σ，f(k,a)唯一地确定了下一个状态。3.4.2不确定的有穷自动机（NFA）NFA引入的原因构造识别语言全部单词的DFA时遇到的问题：在程序设计语言中，有许多种类的单词，每种单词都可以为其构造识别它的DFA为了构造识别全部单词的DFA，需要将各类单词相应的DFA合并在一起，构成一个DFA

如果没有系统的方法，要满足合并以后的有穷自动机为一个DFA是很困难的13letterletter,digit2[other]5digitdigit4[other]7<6=9<8>10<例：解决这个问题的办法将DFA扩充为NFA（在NFA中一个状态对应一个输入字符可以存在多个转换）构造能将NFA转换成DFA的算法NFA的定义一个不确定的有穷自动机M是一个五元组：

M=（K，Σ，f，S，Z），其中K是一个有穷集，它的每个元素称为一个状态；∑是一个有穷字母表，它的每个元素称为一个输入字符；f是一个从KX(∑∪{ε})至K的幂集的映射；SK，是一个非空初态集ZK，是一个终态集。NFA对DFA的扩充对字母表∑的扩充 扩充为(∑∪{ε})，所以NFA中可以有转换12ε对转换函数的扩充：一个状态对应一个输入字符可能存在多个转换，所以转换函数的值是K的子集而不是一个状态对初始状态的扩充：

NFA可以有多个初始状态例NFAM=（{S，P，Z},{0，1},f,{S，P},{Z}）其中f（S，0）={P} f（S，1）={S，Z}

f（Z，0）={P} f（Z，1）={P} f（P，1）={Z}矩阵表示:01S{P}{S,Z}P{}{Z}Z{P}{P}001SPZ00,1111状态图表示:NFA识别的字符串对于Σ*中的任何字符串t，若存在一条从某一初态结到某一终态结的通路，且该通路上所有弧的标记字依次连接成的串（不理睬那些标记为ε的弧）等于t，则称t可以被NFAM所识别。若M的某个初态结又是终态结，或者存在一条从某个初态结到某个终态结的ε通路，那么ε为M所识别。12ε3εabcNFAM所能接受的符号串的全体记为L(M)3.4.3NFA到DFA的转换NFA与DFA的等价性DFA是NFA的特例对于任何两个有穷自动机M和M’，如果L(M)=L(M’)，则称M与M’是等价的对于每个NFAM，存在一个与其等价的DFAM’ε合并 如果有，则把S2状态合并到S1状态。S1S2εijkmεaban（a）i,jmkaabn（b）转换需解决的问题：状态合并 将一个状态对应一个输入字符的所有转向状态合并0123aabc（a）01,23abc（b）从NFA构造DFA的算法—子集法

DFA用它的一个状态记录在NFA读入一个输入符号后可能达到的所有状态。 DFA的每个状态对应NFA的一个状态集合对状态集合I的有关运算：状态集合I的ε闭包ε_closure(I)

是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。εεεIIS2S2S1S1S3S3ε_Close(I)以下将ε_closure(I)简写为Closure(I)

Closure(I)=I{Sk|存在

SjSk，SjClosure(I)

，SkClosure(I)}ε注意：这是一个递归定义，通过多条ε边才能到达的状态也将被合并到closure中设I={0}，则ε_closure(I)={例NFA:ε100124536789ababbεεεεεεε}74,2,1,0,Ia子集。

I是状态集，由I中的状态出发，经过一条a弧可能到达的状态的集合称为

Move（I，a）则Ia=ε_closure(Move(I,a))Ib=ε_closure({例NFA:εε100124536789ababbεεεεεε设I={0,1,2,4,7}则Ia=ε_closure({})3,8={3,8,6,7,1,2,4}56,})={}5,7,2,1,4NFA确定化算法 为NFAN构造一个DFAM，使得L(M)=L(N)：对NFA的初始状态求-closure，得到DFA的初始状态，将其作为未被标记的加入DFA的状态集中重复2，直到DFA中没有未被标记的状态为止含有NFA终止状态的状态为DFA的终止状态从DFA的状态集中选一个未被标记的状态S，标记S，对字母表中的每个字符a，计算Sa子集

(-closure(move(S,a))，如果Sa是一个新的状态，则将其作为未被标记的加入DFA的状态集中，并增加转换SSaa{0,1,7,2,4}{5,6,7,1,2,4}=T2{8,3,6,7,1,2,4}=T1{10,5,6,7,1,2,4}{10,5,6,7,1,2,4}{8,3,6,7,1,2,4}=T1{9,5,6,7,1,2,4}{5,6,7,1,2,4}=T2{8,3,6,7,1,2,4}=T1{5,6,7,1,2,4}{9,5,6,7,1,2,4}{8,3,6,7,1,2,4}=T1{8,3,6,7,1,2,4}{5,6,7,1,2,4}{8,3,6,7,1,2,4}IbIaIεε100124536789ababbεεεεεεT0T1T2T3T400001重新命名DFA的状态得到DFA的状态转换矩阵和转换图如下:

Sab01211321231441240b213bbaaababa000013.3.4确定有穷自动机的化简识别a*的两个DFA，后者是最简的化简的任务:去掉多余状态，合并等价状态aaa多余状态：从开始状态出发，任何输入串都不能到达的状态。等价状态：两个状态s和t等价的条件是: 1一致性条件—状态s和t必须同为可接受状态或不可接受状态

2蔓延性条件—对于所有输入符号,状态s和状态t必须转换到等价的状态里可区别状态：不等价状态。如终态与非终态是可区别的。aCDBAEFSbaaaaabbbbbab例C和F同是终态,C和F读入a都到达C,读入b都到达E,所以C和F等价S和C不等价，因为C是终态，而S不是终态DFA的最小化算法——“分割法”

把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.例DBASaaabbbbaCDBAEFSbaaaaaabbbbbba1.将M的状态分成非终态和终态集 {S,A,B}{C,D,E,F}2寻找子集中不等价状态{S,A,B}=>{A}{S,B}=>{S}{A}{B}{C,D,E,F}3

令D代表{C,D,E,F}

abSABACBBADCCEDFDEFDFCEP={S,A,B,D}在等价状态子集中选一状态做代表，消去其他状态，把从消去状态射出和射入的弧都引到代表状态，子集中有初态，则代表状态也是初态3.5正规式和有穷自动机的等价性正规表达式DFA词法分析程序词法分析器的构造过程：NFADFA最简DFA正规表达式:单词的描述工具，描述单词的构成规则DFA：单词的识别系统，识别由正规表达式描述的字符串等价性1.对于∑上的一个NFAM，可以构造一个∑上的正规式R,使得L(R)=L(M)。2.对于∑上的一个正规式R，可以构造一个∑上的NFAM，使的L(M)=L(R)。从正则式构造NFA

“制导法”(InductiveMethod):

按正则式的结构指引构造过程正则式的基本语法结构的构造规则对于正规式

,构造的NFA为:yx对于正规式x,x∑构造的NFA为:yxxyx对于正规式,构造的NFA为:复合正则式e的构造规则 先构造如下的NFAyxe然后按下述三种情况进行分解，直至每条弧上标记一个字符e1Xye=e1|e2e2X1e1ye2e=e1e2X1εyεe1e=e1*例：为R=(a|b)*abb构造NFAM，使得L(M)=L(R)

X(a|b)*abbYX(a|b)*1a2bb3

YXε4ε1b3a2ba|b

YXε4ε1b3a2bab

Y正规文法,正规表达式,有穷自动机三者可等价相互转换描述工具识别工具3.6由DFA构造词法分析程序将状态转换图转换成词法分析代码特殊问题的处理

将状态转换图转换成词法分析代码{从状态1开始}ifthenextcharacterisaletterthen advanc