教学课件：《编译原理》.ppt

1、编译原理第一章 编译概述 编译器和解释器编译器和解释器 编译器的功能分解和组织结构编译器的功能分解和组织结构 编译器的伙伴程序编译器的伙伴程序 编译器的实现途径编译器的实现途径 编译技术的作用编译技术的作用1.编译器和解释器编译器和解释器程序设计语言的历史程序设计语言的历史 机器语言机器语言：能够被计算机的硬件系统直 接执行的指令程序。汇编语言：将硬件指令用一些助记符表 示。如ADD表示加法操作，SUB表示减法操作等等 高级语言：使用便于理解的自然语言。1.编译器和解释器编译器和解释器翻译程序翻译程序(器器)：接受某种语言的源语言程序后，：接受某种语言的源语言程序后，将它改造成另一种逻辑上等价

2、的目标语言程序。将它改造成另一种逻辑上等价的目标语言程序。l汇编程序汇编程序：源语言为汇编语言，目标语言为机器语：源语言为汇编语言，目标语言为机器语言的翻译程序。言的翻译程序。l编译程序（器）编译程序（器）：源语言为高级语言，目标语言是：源语言为高级语言，目标语言是低级语言（汇编或机器语言）的翻译程序。低级语言（汇编或机器语言）的翻译程序。高级语言程序（源程序）低级语言程序（目标程序）编译程序（器）1.编译器和解释器编译器和解释器解释程序解释程序(器器)：是语言的另一种实现方式。接受所输入的用程序语言(源语言)编写的程序(源程序)，然后直接解释执行源程序。相当于源程序的抽象执行机。解释程序（器

3、）高级语言程序（源程序）数据计算结果1.编译器和解释器编译器和解释器编译器和解释器的比较编译器和解释器的比较编译器编译器解释器解释器程序规模程序规模规模较大规模较大中小规模中小规模内部形式内部形式机器代码机器代码(低级低级)数据结构数据结构(高级高级)运行机构运行机构硬件硬件CPU软件系统软件系统运行速度运行速度相对较快相对较快相对较慢相对较慢2.编译器的功能分解和组织结构编译器的功能分解和组织结构表 处 理 错 误 处 理 目标代码生成中间代码优化中间代码生成语义分析语法分析词法分析目标程序源程序2.编译器的功能分解和组织结构编译器的功能分解和组织结构 编译器的前端：编译器的前端：一般包括词

4、法分析、语法分析、一般包括词法分析、语法分析、符号表构造、语义分析、中间代码生成、代码优符号表构造、语义分析、中间代码生成、代码优化和错误处理等。此部分工作的特点是不依赖于化和错误处理等。此部分工作的特点是不依赖于具体机器。具体机器。编译器的后端编译器的后端：主要是指中间代码到目标代码生：主要是指中间代码到目标代码生成的阶段。此部分紧密地依赖于中间代码和目标成的阶段。此部分紧密地依赖于中间代码和目标机机 遍遍：对源程序或源程序的中间表示形式从头到尾：对源程序或源程序的中间表示形式从头到尾扫描一次，生成新的中间结果或目标程序扫描一次，生成新的中间结果或目标程序3.编译器的伙伴程序编译器的伙伴程序

5、编辑器编辑器(editor)除一般的文本编辑功能外，还除一般的文本编辑功能外，还可以对正在编辑的文本进行分析、提示、自动可以对正在编辑的文本进行分析、提示、自动提供关键字匹配等功能。提供关键字匹配等功能。预处理器预处理器(preprocessor)删除源程序中的注释、删除源程序中的注释、执行宏替换以及包含文件的嵌入等。执行宏替换以及包含文件的嵌入等。连接程序连接程序(linker)将不同的目标文件连接到一将不同的目标文件连接到一个可执行的文件中。个可执行的文件中。装入程序装入程序(loader)将程序加载到内存中，以便将程序加载到内存中，以便执行。执行。调试程序调试程序(debugger)在被

6、编译的程序中判定执在被编译的程序中判定执行错误的程序行错误的程序需预处理的源程序预处理器源程序编译程序目标汇编程序汇编程序可重定位的目标代码连接/装配程序绝对目标代码高级语言程序到可执行代码的转换过程4.编译器的实现途径 预处理方法预处理方法用于语言的扩充。设已有L语言的编译器，其扩充语言L1的编译器可通过语言转换程序将L1程序转换为L程序，利用L的编译器，从而实现L1的编译器。移植法移植法 同一语言的编译器在同一语言的编译器在不同机器间的移植。方法：a a 目标代码的转换目标代码的转换 b b 修改中间代码到目标代码的转换修改中间代码到目标代码的转换 自展法自展法 自我扩展，自己编写自己的编

7、译器。工具法工具法 利用编译阶段各个部分的自动生成工具自动生成。理论法理论法 利用形式化描述理论，实现自动化。5.编译技术的作用 理解语言，编写出高效的代码理解语言，编写出高效的代码 灵活设计实现自定义语言灵活设计实现自定义语言 提高软件设计技术提高软件设计技术 应用于涉及元级操作的实现应用于涉及元级操作的实现 其它领域其它领域第二章 一个微小的编译器z 小语言小语言ToyLToyL的定义的定义z ToyLToyL语言词法分析器语言词法分析器z ToyLToyL语言语法分析器语言语法分析器z ToyLToyL语言解释器语言解释器z ToyLToyL语言编译器语言编译器1.小语言ToyL的定义

8、Prog:=begin SL end SL :=S|S;SL S :=id:=E|write(E)|read(id):=E|write(E)|read(id)E :=U|U+E|U U|U+E|U*E E U :=id|num id|num 程序例：程序例：beginbegin x1:=0.5;x1:=0.5;z1:=x1+55;z1:=x1+55;write(z1+5.5);write(z1+5.5);read(x1);read(x1);z1:=z1+x1 z1:=z1+x1 endend1.小语言ToyL的定义2.ToyL语言词法分析器语言词法分析器 任务：从程序文本中分离出单词，并确任务

9、：从程序文本中分离出单词，并确定其类别定其类别 ToyL语言单词的种类：语言单词的种类：整数：整数：numnum 变量：变量：idid 保留字：保留字：begin,end,read,write,begin,end,read,write,运算符：运算符：+，*，:=:=格式符：空格，回车，换行，文件结束符格式符：空格，回车，换行，文件结束符EOFEOF 分隔符：分隔符：(,),;(,),;2.ToyL语言词法分析器语言词法分析器 单词的内部表示单词的内部表示Token:(class,seman)begin:(BEGIN,“begin”)end:(END,“end”)read:(READ,”rea

10、d”)write:(WRITE,“write”)num:(NUM,digit(num)id:(ID,name(id)+:(PLUS,“+”)*:(MULT,“*”):=:(ASSIG,“:=”)(:(OPEN,“(”):(CLOSE,“)”);:(SEMI,“;”)eof:(EOF,“0”)2.ToyL语言词法分析器语言词法分析器 词法分析过程：词法分析过程：读当前字符流，直至文件结束。如果是：读当前字符流，直至文件结束。如果是：(1)标识符时判断是保留字还是变量标识标识符时判断是保留字还是变量标识 符，构造符，构造Token表示表示 (2)数字时判断是整型还是实型，构造数字时判断是整型还是实

11、型，构造 Token表示表示 (3)构造其它合法的符号的构造其它合法的符号的Token表示表示 (4)遇到非法符号则报错。遇到非法符号则报错。2.ToyL语言词法分析器语言词法分析器假设有ToyL语言程序文本:begin x:=10;read(y);x:=x+y end则经过词法分析后的Token表示如下。01(BEGIN,begin)09(CLOSE,)02(IDEN,x)10(SEMI,;)03(ASS,:=)11(IDEN,x)04(NUMB,10)12(ASS,:=)05(SEMI,;)13(IDEN,x)06(READ,read)14(PLUS,+)07(OPEN,()15(IDEN

12、,y)08(IDEN,y)16(END,end)3.ToyL语言语法分析器语言语法分析器 任务：检查源程序是否是合法的单词序列，若任务：检查源程序是否是合法的单词序列，若有错误，则指出错误的位置和性质。有错误，则指出错误的位置和性质。构造语法构造语法短语的表示形式（语法树）短语的表示形式（语法树）输入：是词法分析后所得的输入：是词法分析后所得的TokenToken序列。序列。说明：语法分析只用到单词的说明：语法分析只用到单词的TokenToken表示，并表示，并不改变单词的不改变单词的TokenToken表示。表示。3.ToyL语言语法分析器语言语法分析器 三个函数：三个函数：next_tok

13、en(tk)、token(CLASS)、back_token()只读而不检查的只读而不检查的Token函数函数next_token(tk)读并检查的读并检查的Token 函数函数token(CLASS)将程序文件的指针倒退到已读单词的第一字符将程序文件的指针倒退到已读单词的第一字符位置上的回溯函数位置上的回溯函数back_token()。为了能倒退。为了能倒退到已读单词的位置上，每当读新单词时，把当到已读单词的位置上，每当读新单词时，把当前单词的文件位置保存到前单词的文件位置保存到old_fp中。中。3.ToyL语言语法分析器语言语法分析器void prog_parser()token(BEG

14、IN);while(tk.class!=END)next_token(tk);switch(tk.class)case READ:token(OPEN);token(IDEN);token(CLOSE);break;case WRITE:token(OPEN);expr_parser();token(CLOSE);break;case IDEN:token(ASS);expr_parser();break;default:error()token(SEMI);token(END);return;3.ToyL语言语法分析器语言语法分析器 void expr_parser()1000next_to

15、ken(tk);if(tk.class!=NUMB&tk.class!=IDEN)error();2000next_token(tk);if(tk.class=PLUS|tk.class=MULT)goto 1000;3000back_token();return;4.ToyL语言解释器语言解释器 虚拟存储器：为存放变量的值需要开辟一个空间，不妨称此空间为存储器空间，或简称存储器(Memory)。它可用变量名和值的对偶表来表示。虚拟输入器：为描述read(x)语句解释执行过程，需要设置程序的输入数据所在的介质，我们称其为输入介质，或简称为虚拟输入器，并记为Inp。可用整型数组来模拟 虚拟输出器

16、：为描述Write(E)语句解释执行过程，需要设置程序的输出数据所在的介质，我们称其为输出介质，或简称为虚拟输出器，并记为Out。也用整型数组来模拟4.ToyL语言解释器语言解释器 表达式处理需要的数据结构和符号约定表达式处理需要的数据结构和符号约定 DS :DS :数据栈数据栈 OS :OS :运算符栈运算符栈 RE :RE :剩余表达式剩余表达式 Push(s,a):Push(s,a):将将a a压入栈压入栈s s Pop(s,i):Pop(s,i):从栈从栈s s中弹出中弹出i i个元素个元素无括号表达式无括号表达式求值求值算法思想算法思想 运算分量运算分量N/I N/I :push(D

17、S,N/I)运算符运算符 :L:if OStop=then push(OS,)if OStop then push(OS,)else goto L；RE=#:while OStop do DStop 表示表达式的最终值表示表达式的最终值 ProcessProcessd1=pop(DS,1);d2=pop(DS,1);op=pop(OS,1);v=d2 op d1;push(DS,v);4.ToyL语言解释器语言解释器interpreter()(一遍扫描解释器一遍扫描解释器)rp=0;op=0;pp=0;mp=-1;dsp=-1;osp=0;OS0=HEAD;token(BEGIN);while

18、(tk.class!=END)next_token(tk；switch(tk.class)case READ:token(OPEN);token(IDEN);update(tk.seman,read_num()token(CLOSE);break;case WRITE:token(OPEN);write_num(evaluate_expr();token(CLOSE);break;case IDEN:token(ASS);update(tk.seman,evaluate_expr();break;default:error()next_token(tk)5.ToyL语言编译器语言编译器 目标代

19、码功能：目标代码功能：把表达式的值计算出来，把表达式的值计算出来，并存到某临时变量，我们称此临时变量并存到某临时变量，我们称此临时变量为结果变量。为结果变量。目标代码例：目标代码例：CODE(10)CODE(10):(-,-,10,T:(-,-,10,T1 1)CODE(x):(-,-,x,T CODE(x):(-,-,x,T1 1)CODE(a+10 CODE(a+10*x):(x):(*,10,x,T,10,x,T1 1)(+,a,T (+,a,T1 1,T,T2 2)表达式代码生成中用到的数据结构和辅助函数表达式代码生成中用到的数据结构和辅助函数 DSDS同前同前 OSOS同前同前 RE

20、RE同前同前 CODECODE代码部分代码部分 格局组成格局组成：（DS,OS,RE,CODE)DS,OS,RE,CODE)初始格局：初始格局：DS,OS,CODE=,REDS,OS,CODE=,RE为初始表达式为初始表达式 终止格局：终止格局：DSDS只含一个元素（表达式的结果变量）。只含一个元素（表达式的结果变量）。OS,REOS,RE为空，为空，CODECODE为被生成的代码部分为被生成的代码部分 函数函数NewTemp:NewTemp:自定义函数，每调用一次，它将返回一自定义函数，每调用一次，它将返回一个新临时变量。个新临时变量。表达式代码生成算法思想 算法思想与表达式求值的思想基本一

21、致算法思想与表达式求值的思想基本一致 区别只在于区别只在于ProcessProcess部分部分 我们只需把我们只需把ProcessProcess中中求值求值的部分改为的部分改为代码生代码生成成部分即可部分即可:T:=NewTemp T:=NewTemp 生成代码生成代码:（,DStop-1,DStop,T),DStop-1,DStop,T),/=OStopOStop pop(DS,2)pop(DS,2)pop(OS,1)pop(OS,1)push(DS,T)push(DS,T)第三章有穷自动机与词法分析器第三章有穷自动机与词法分析器 词法分析基础词法分析基础 有穷自动机有穷自动机 正则表达式正

22、则表达式 词法分析器的设计和构造词法分析器的设计和构造1.词法分析的基础词法分析的基础 词法分析器功能：词法分析器功能：读源程序的字符序列读源程序的字符序列,逐个拼出单词逐个拼出单词,并并构造相应的内部表示构造相应的内部表示TOKEN.TOKEN.同时检查源程序同时检查源程序中的词法错误中的词法错误.引入引入TokenToken的原因：的原因：编译程序总是用某种程序语言书写的程编译程序总是用某种程序语言书写的程序，语言的操作对象只能是该语言规定的各序，语言的操作对象只能是该语言规定的各种数据。而编译程序的操作对象是程序中的种数据。而编译程序的操作对象是程序中的各种语法单位，因此，必须把它们表示

23、成某各种语法单位，因此，必须把它们表示成某种数据结构形式。种数据结构形式。词法分析器的两种形式词法分析器的两种形式CharList 独 立词法分析器语法分析TokenList 附 属词法分析器语法分析callTokenCharListv Token Token定义定义 TokenToken表示最小的语义单位表示最小的语义单位-单词的信息。即单词的信息。即 单词内部表示的数据结构形式。单词内部表示的数据结构形式。单词不是程序设计语言中的语法概念，是编译程单词不是程序设计语言中的语法概念，是编译程序中引进的一个概念。是最小的语义单位，不能序中引进的一个概念。是最小的语义单位，不能分割分割 Toke

24、nToken中需要记录有关单词的信息：中需要记录有关单词的信息：单词的标志码单词的标志码($($id,$intC,id,$intC,)标识单词的种类标识单词的种类-词法信息词法信息 单词的特征属性（标识符名，符号表地址等）单词的特征属性（标识符名，符号表地址等）-语义信息语义信息v 标识符和常量的处理标识符和常量的处理：词法信息可确定，语义信息形式的确定词法信息可确定，语义信息形式的确定：a a 语义信息的长度有限制时，直接用语义信息的长度有限制时，直接用 标识符或常量本身标识符或常量本身 b b 没有长度限制时，构造标识符或常没有长度限制时，构造标识符或常 量表，语义信息中为其在表中的地量表

25、，语义信息中为其在表中的地 址（字符串空间址（字符串空间节省存贮空间）节省存贮空间）v 保留字的处理保留字的处理：识别保留字的方法：识别保留字的方法：1.建立保留字表；顺序、散列、散列顺序建立保留字表；顺序、散列、散列顺序 2.拼写的同时进行判断拼写的同时进行判断 自动机自动机 v 运算符的处理运算符的处理：不区分，统一成一类不区分，统一成一类 区分，每个运算符为一类区分，每个运算符为一类v 空格符和制表符以及换行符的处理空格符和制表符以及换行符的处理 1.无用的空格符和制表符要删掉；无用的空格符和制表符要删掉；2.字符串内的空格不能删；字符串内的空格不能删；3.换行符不能删。用于错误定位换行

26、符不能删。用于错误定位v 复合型特殊符，如复合型特殊符，如“:=”的处理的处理 读到读到“:”时不能判断是否为冒号，必须读下时不能判断是否为冒号，必须读下 一字符。一字符。v 括号类配对预检括号类配对预检括号类：括号类：begin begin end,if end,if then,()then,()处理方法：处理方法：对每类括号设置一个计数器（初值对每类括号设置一个计数器（初值=0=0）每当遇到开括号，则计数器加每当遇到开括号，则计数器加1 1 每当遇到闭括号时，计数器减每当遇到闭括号时，计数器减1 1 词法分析结束时，如果计数器词法分析结束时，如果计数器 0 0，则，则 表明括号不匹配。表明

27、括号不匹配。v 字符串空间字符串空间目的：减少冗余，节省空间，提高访问速度目的：减少冗余，节省空间，提高访问速度方法：字符数组存放字符串，描述字符串信息：方法：字符数组存放字符串，描述字符串信息：下标下标 长度长度 v词法错误校正词法错误校正 词法错误种类：词法错误种类：语言不允许的符号：语言不允许的符号：#括号类配对错误：括号类配对错误：单词的后继符错（偶尔）：单词的后继符错（偶尔）：词法错误校正：词法错误校正：a a 删除已被读过的字符，并重新扫删除已被读过的字符，并重新扫 描未被读过的字符描未被读过的字符 b b 删除已读过的第一个字符，重新删除已读过的第一个字符，重新 扫描它的后继部分

28、的字符。扫描它的后继部分的字符。校正后的标示校正后的标示v词法分析的结束词法分析的结束 程序结束标志程序结束标志endend 文件结束符文件结束符Eof.Eof.2.2.有穷自动机有穷自动机FAFA 描述程序设计语言中的单词字，进一步为词描述程序设计语言中的单词字，进一步为词法法分析程序的自动构造寻找特殊的方法和工具。分析程序的自动构造寻找特殊的方法和工具。主要内容：主要内容：确定有限自动机确定有限自动机DFADFA 确定有限自动机确定有限自动机DFADFA的实现的实现 非确定有限自动机非确定有限自动机NFANFA NFA NFA到到DFADFA的转换的转换 DFA DFA的化简的化简 确定有

29、限自动机确定有限自动机DFADFA 确定有限自动机（确定有限自动机（DFADFA：Deterministric Deterministric Finite Automata)Finite Automata)为一个五元组为一个五元组(,SS,SSS,S0 0,f f,TS),TS)，其中：其中：是一个有穷字母表，它的每个元素称为一个是一个有穷字母表，它的每个元素称为一个输入字符；输入字符；SSSS是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；S S0 0 SSSS是唯一的一个初始状态；是唯一的一个初始状态；f f是在是在SSSS SSSS上的转换函数上的转换函数

30、 TSTS SSSS，是一个终止状态集，又称为接受状态是一个终止状态集，又称为接受状态集集DFADFA的两种表示方式的两种表示方式 状态转换图：状态转换图：结点表示状态，转换边表示转换函数，边结点表示状态，转换边表示转换函数，边 的箭头方向指向转换函数中定义的转换方的箭头方向指向转换函数中定义的转换方 向。标识出初始状态和终止状态。向。标识出初始状态和终止状态。状态转换表：状态转换表：可用二维数组描述。标识出初始状态和终可用二维数组描述。标识出初始状态和终 止状态。止状态。Trans（S SI I，a）S SJ J一个DFA的例子 DFA M=(a,b,S,U,V,Q,S,f,Q),其中其中

31、f 定义为：定义为：f(S,a)=U f(V,a)=U f(S,b)=V f(V,b)=Q f(U,a)=Q f(Q,a)=Q f(U,b)=V f(Q,1)=QSUVQabbabaa,b状态转换图 字符字符状态状态a ab bS SU UV VU UQ QV VV VU UQ QQ QQ QQ Q状态转换表DFADFA接受的字符串接受的字符串 对于对于*中的任何字符串中的任何字符串t,t,若存在一条从初始若存在一条从初始结点到某一终止结点的路径结点到某一终止结点的路径，且这条路上所且这条路上所有弧的标记符连接成的字符串等于有弧的标记符连接成的字符串等于t,t,则称则称t t可为可为DFA M

32、DFA M所所接受（识别）接受（识别）。DFA M DFA M 所能接受的字符串的全体记为所能接受的字符串的全体记为L(M).L(M).DFADFA的确定性的确定性 初始状态唯一。初始状态唯一。转换函数转换函数f:SSf:SSSSSS是一个单值函数，也就是一个单值函数，也就是说，对任何状态是说，对任何状态S S SS,SS,和输入符号和输入符号a a ,f(S,a)f(S,a)唯一地确定了下一个状态。即至多确唯一地确定了下一个状态。即至多确定一个状态。定一个状态。没有空边。即没有输入为没有空边。即没有输入为（）DFADFA的实现的实现1 1 状态转换表的形式：状态转换表的形式：1.1.当前状态

33、当前状态StateState置为初始状态置为初始状态 2.2.读一个字符读一个字符 CurrentCharCurrentChar 3.3.如果如果CurrentCharCurrentChar EofEof并且并且 T(State,CurrentChar)T(State,CurrentChar)errorerror 则当前状态转为新的状态则当前状态转为新的状态T(State,Current)T(State,Current)，读下一字符。重复第读下一字符。重复第3 3步工作。步工作。4.4.如果当前字符为如果当前字符为EofEof并且当前状态属于终止状态，并且当前状态属于终止状态，则接受当前字符串

34、，程序结束。否则报错则接受当前字符串，程序结束。否则报错 特点：特点：程序短小，但占用存储空间多程序短小，但占用存储空间多bDFADFA的实现的实现2 2 状态转换图的形式：状态转换图的形式：每个状态对应一个带标号的每个状态对应一个带标号的casecase语句语句 转向边对应转向边对应gotogoto语句语句 特点：特点：程序长，但占用存储空间少程序长，但占用存储空间少 ijkaLi:case CurrentChar of a ：goto Lj b :goto Lk other :Error()非确定有限自动机非确定有限自动机NFANFA 定义定义1 1：一个非确定有限自动机一个非确定有限自动

35、机(NFA)ANFA)A是是一个五元组一个五元组A=(A=(,SS,S,SS,S0 0,f,TS).,f,TS).其中其中 是字母表是字母表 SS SS是状态集是状态集 S S0 0是初始状态集是初始状态集 f f是转换函数，但不要求是单值的是转换函数，但不要求是单值的 f:SS f:SS ()2 2SSSS TS TS是终止状态集是终止状态集非确定有限自动机非确定有限自动机NFANFA 定义定义2 2：设设A A是一个是一个NFANFA，A=(A=(,SS,S,SS,S0 0,f,TS),f,TS)则定义则定义L(A)L(A)为从任意初始状态到任意终止状为从任意初始状态到任意终止状态所接受的

36、字符串。态所接受的字符串。L(A)=L(A)=|s s0 0 s s,s,s0 0 S S0 0 s s TS 定义定义3 3：设设A A1 1和和A A2 2是同一个字母表上的自动机，是同一个字母表上的自动机，如果有如果有L(AL(A1 1)=L(A)=L(A2 2),),则称则称A A1 1和和A A2 2等价。等价。NFANFA到到DFADFA的转换的转换 定理定理1 1 对于每一个非确定自动机对于每一个非确定自动机A,A,存在一个存在一个确定自动机确定自动机A A,使得使得L(A)=L(AL(A)=L(A).).转换转换：符号合并符号合并 同一状态的不同输出边标有相同的字符。同一状态的

37、不同输出边标有相同的字符。合并合并 含有含有 边边 NFANFA到到DFADFA的转换的转换 符号合并符号合并：A A：NFA,ANFA,A:FA:FA 1.1.令令A A的初始状态为的初始状态为S S0 0=S=S1 1,S,S2 2,S Sk k,其中其中S S1 1S Sk k是是A A的全部初始状态。的全部初始状态。2.2.若若S S=S=S1 1,S,Sm m 是是A A的一个状态，的一个状态，a a则定义则定义 f f(S(S,a)=f(S,a)=f(S1 1,a),a)f(Sf(S2 2,a),a)f(Sf(Sm m,a),a)3.3.重复步骤直至不出现新的状态为止。重复步骤直至

38、不出现新的状态为止。4.4.若若S S=S=S1 1,S,Sn n 是是A A的一个状态的一个状态,且存且存 在一个在一个S Si i是是A A的终止状态，则令的终止状态，则令S S为为A A 的终止状态。的终止状态。NFANFA到到DFADFA的转换的转换 合并合并 （Close(S)Close(S)）1.1.对对S S状态寻找状态寻找 边，如果有令边，如果有令SsSsSS 2.2.对任意状态对任意状态SiSi Ss,Ss,如果有：如果有：f(Si,f(Si,)=)=SjSj则则 消除消除 边：边：Ss=SSs=Ss s SjSj 重复上述操作直至没有重复上述操作直至没有 边边 3.3.对对

39、a a f(f(SsSs,a)=,a)=f(f(SkSk,a a)Ss=S1,Ss=S1,Sm,k=1,Sm,k=1,m.,m.4.4.如果如果SsSs中包含中包含初始状态则初始状态则SsSs也为初始状态，也为初始状态，如果有终止状态，则如果有终止状态，则SsSs为终止状态。为终止状态。NFANFA到到DFADFA的转换的转换NFANFA到到DFADFA的转换过程的转换过程:1.NFA1.NFA初始状态集的初始状态集的 合并集作为合并集作为DFADFA的初始状的初始状 态。态。2.2.对对DFADFA中一状态中一状态S S，对对a a,进行符号合并和进行符号合并和 合并得到的状态设为合并得到的

40、状态设为S S,定义定义DFADFA的转换函的转换函数为数为f(S,a)=Sf(S,a)=S.3.3.直至没有新状态产生为止。直至没有新状态产生为止。将如下的将如下的NFA转化为转化为DFAbbbaa012435678910DFADFA的化简（极小化）的化简（极小化）状态等价状态等价 对对DFADFA中的两个状态中的两个状态S S1 1和和S S2 2，如果将，如果将它们看作是初始状态，所接受的符号串它们看作是初始状态，所接受的符号串相同，则定义相同，则定义S S1 1和和S S2 2是等价的。是等价的。方法方法:状态分离法状态分离法 初始化为两个不等价状态集组：非终初始化为两个不等价状态集组

41、：非终止状态组和终止状态组。止状态组和终止状态组。对每组中的某个状态分离出与之不等对每组中的某个状态分离出与之不等价的状态组，直至所有状态组内部状态价的状态组，直至所有状态组内部状态都等价为止。都等价为止。3.正则表达式正则表达式 描述程序设计语言中单词的一种简单而描述程序设计语言中单词的一种简单而且数学化工具。且数学化工具。表示符号串的构成模式表示符号串的构成模式 正则表达式正则表达式r r定义了一个符号串集合定义了一个符号串集合rs,rs,rsrs内的每个符号串都与内的每个符号串都与r r所定义的模式所定义的模式相匹配，相匹配，rsrs称为由称为由r r生成的语言生成的语言L(r)L(r)

42、正则表达式中出现的所有符号构成的集正则表达式中出现的所有符号构成的集合为该正则表达式的字母表合为该正则表达式的字母表，用用 表示。表示。正则表达式正则表达式主要内容：主要内容：基本概念基本概念 正则表达式定义及一些性质正则表达式定义及一些性质 正则定义正则定义 扩充的正则表达式及程序设计语言中扩充的正则表达式及程序设计语言中单词的定义单词的定义 正则表达式的局限性。正则表达式的局限性。正则表达式正则表达式 基本概念：基本概念：字母表：字母表：非空有限集，非空有限集，其元素称为符号或字母，其元素称为符号或字母.符号串：符号串：符号的有限序列，也称为符号的有限序列，也称为字字。或或 表示表示空串空

43、串 空串集空串集 不同于空集不同于空集 。符号串长度：符号串长度：符号串中字符的个数符号串中字符的个数.|.|符号串连接：符号串连接：和和 都是符号串，则都是符号串，则为符号串的连接为符号串的连接 特别有：特别有：=符号串集的乘积：符号串集的乘积：A A和和B B是符号串的集合，则称是符号串的集合，则称 AB=AB=|A A，B B 特别有：特别有：A=AA=A=A=A，其中其中表示空集。表示空集。符号串的方幂：符号串的方幂：设设A A是符号串的集合，则称是符号串的集合，则称A Ai i为符号为符号串集串集A A的方幂，其中的方幂，其中i i是非负整数。是非负整数。A A0 0=A A1 1

44、=A ,A=A ,A2 2 =A A=A A A AK K=AA.A(k=AA.A(k个个)符号串集合的正闭包：符号串集合的正闭包：A A+=A=A1 1 A A2 2 A A3 3.符号串集合的星闭包：符号串集合的星闭包：A A*=A=A0 0 A A1 1 A A2 2 A A3 3.正则表达式及其一些性质正则表达式及其一些性质 为给定的字母表，则每个为给定的字母表，则每个 上的正则表达上的正则表达式将定义式将定义 上的一个字符串集。上的一个字符串集。用用R R 表示表示 上的正则表达式上的正则表达式，用用L(RL(R)表示表示R R 所表示的字所表示的字符串集合符串集合 。即：函数。即：

45、函数L L表示表示 正则表达式正则表达式字符串集的映射。字符串集的映射。则则R R 的定义及其含义如下：的定义及其含义如下：是 正则表达式，即R。其中L()=。是 正则表达式，即 R。其中L()=。c 是 正则表达式，即c R。其中 L(c)=c。A和B是 正则表达式，即A R，B R，则有(A)R，L(A)=L(A)A|BR，L(A|B)=L(A)L(B)A BR，L(A B)=L(A)L(B)A*R，L(A*)=L(A)*正则表达式例正则表达式例 =a,b.a,b.正则表达式e1.ab*2.a(a|b)*L(e)1.上所有以a为首后跟任意多个（包括0个）b的字符串集2.上所有以a为首的字符

46、串集正则表达式的性质正则表达式的性质q A|B=B|A|的可交换性q A|(B|C)=(A|B)C|的可结合性q A(B C)=(A B)C 连接的可结合性q A(B|C)=A B|A C 连接的可分配性q (A|B)C=A C|B C 连接的可分配性q A*=A*幂的等价性q A=A=A 是连接的恒等元素 扩充的正则表达式扩充的正则表达式 一次或多次重复一次或多次重复:A+任何符号任何符号:“”在字母表中任何符号在字母表中任何符号.|.符号范围符号范围:0-9 a-z A-Z 不在给定范围内的符号不在给定范围内的符号:(a|b|c)或或L La L Labc 0或或1次次(可选可选):r?=

47、(|r)正则定义正则定义 为较长的正则表达式提供一个简化了的为较长的正则表达式提供一个简化了的名字。如要为一个或多个数字序列写一名字。如要为一个或多个数字序列写一个正则表达式，则可写作：个正则表达式，则可写作：（0|1|2|0|1|2|9)(0|1|2|9)(0|1|2|9)9)*或写作或写作 digit digitdigit digit*其中其中 digit=digit=0|1|2|0|1|2|9|9就是名字就是名字digitdigit的正则定义，表示为：的正则定义，表示为：digit digit 0|1|2|0|1|2|9|9程序设计语言中单词的程序设计语言中单词的正则表达式定义正则表达式

48、定义 保留字保留字 如如 BeginBeginbeginbegin 标识符标识符 letter=a-zletter=a-z，A-ZA-Z digit=0-9digit=0-9 identifier=letter(letter|digit)identifier=letter(letter|digit)*数字数字 整数整数IntInt1-9Digit1-9Digit*|0|0 实数实数realrealIntInt.IntInt 特殊符号特殊符号+|-|+|-|正则表达式的局限性正则表达式的局限性正则表达式不能用于描述配对或嵌套的结正则表达式不能用于描述配对或嵌套的结构构正则表达式不能用于描述重复串

49、正则表达式不能用于描述重复串 例：例：w c w|w是是a和和b的串的串无法用正则表达无法用正则表达式表示（保证两边式表示（保证两边w是相同的）。是相同的）。正则表达式与有限自动机等价正则表达式与有限自动机等价定理：对任一确定有限自动机定理：对任一确定有限自动机A A，存在一正存在一正 则表达式则表达式e,e,使得使得L(A)=L(e),L(A)=L(e),反之亦然。反之亦然。关系图：关系图：DFA正则表达式NFA正则表达式到NFA的转换规则：13a b12a|b13 b*123ab12ab123bl首先扩展转换图：XW123ab12ab12313a b12a|b13a b*cabc4.词法分

50、析器的工作过程词法分析器的工作过程词法分析器（Scanner）输入流词法描述（正则表达式）NFADFATokenListerror词法分析器的设计词法分析器的设计 人工构造词法分析器过程：人工构造词法分析器过程：1.1.确定词法分析器的接口，即确定词法分析确定词法分析器的接口，即确定词法分析 器是作为语法分析的一个子程序还是作为器是作为语法分析的一个子程序还是作为 独立一遍。独立一遍。2.2.确定单词分类和确定单词分类和TokenToken结构。结构。3.3.根据根据2 2步，构造每一类单词的描述步，构造每一类单词的描述 正则表达式正则表达式NFANFADFADFA。4.4.根据根据3 3步设