编译原理 陈意云课件 第二章.ppt

第二章第二章 词法分析词法分析本章内容本章内容词法分析器：把构成源程序的字符流翻译成词法分析器：把构成源程序的字符流翻译成记号流，记号流，还完成和用户接口的一些任务还完成和用户接口的一些任务围绕词法分析器的自动生成展开围绕词法分析器的自动生成展开介绍正规式、状态转换图和有限自动机概念介绍正规式、状态转换图和有限自动机概念词法分析器词法分析器语法分析器语法分析器符号表符号表记号记号(token)取下一个记号取下一个记号源程序源程序2.1 词法记号及属性词法记号及属性 2.1.1 词法记号、模式、词法单元词法记号、模式、词法单元 记号名记号名词法单元例举词法单元例举模式的非形式描述模式的非形式描述 if if 字符字符i,f for for字符字符f,o,r relation ,=,=,或或 0）2.2 词法记号的描述与识别词法记号的描述与识别 语言的运算语言的运算并：并：L M=s|s L 或或 s M 连接连接：LM=st|s L 且且 t M幂：幂：L0是是，Li是是Li-1L 闭包：闭包：L =L0 L1 L2 正闭包：正闭包：L+=L1 L2 例例L:A,B,Z,a,b,z,D:0,1,9 L D,LD,L6,L*,L(L D)*,D+2.2 词法记号的描述与识别词法记号的描述与识别 2.2.2 正规式正规式正正规规式式用来表示简单的语言，用来表示简单的语言，叫做叫做正规集正规集正规式正规式定义的语言定义的语言备注备注 a a a (r)|(s)L(r)L(s)r和和s是正规式是正规式(r)(s)L(r)L(s)r和和s是正规式是正规式(r)*(L(r)*r是正规式是正规式(r)L(r)r是正规式是正规式(a)(b)*)|(c)可以写成可以写成ab*|c 2.2 词法记号的描述与识别词法记号的描述与识别 正规式的例子正规式的例子 =a,ba|ba,b(a|b)(a|b)aa,ab,ba,bbaa|ab|ba|bbaa,ab,ba,bba*由字母由字母a构成的所有串集构成的所有串集(a|b)*由由a和和b构成的所有串集构成的所有串集复杂的例子复杂的例子(00|11|(01|10)(00|11)(01|10)句子：句子：010011010000100000101110012.2 词法记号的描述与识别词法记号的描述与识别 2.2.3 正规定义正规定义对正规式命名，使表示简洁对正规式命名，使表示简洁 d1 r1 d2 r2.dn rn各个各个di的名字都不同的名字都不同每个每个ri都是都是 d1,d2,di-1 上的正规式上的正规式2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例子C语言的标识符是字母、数字和下划线组成的串语言的标识符是字母、数字和下划线组成的串 letter_ A|B|Z|a|b|z|_ digit 0|1|9 id letter_(letter_|digit)*2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例子 无符号数集合，例无符号数集合，例1946,11.28,63E8,1.99E 6digit 0|1|9digits digit digit*optional_fraction .digits|optional_exponent (E(+|)digits)|numberdigits optional_fraction optional_exponent 简化表示简化表示number digit+(.digit+)?(E(+|)?digit+)?2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子（进行下一步讨论的例子）正规定义的例子（进行下一步讨论的例子）while whiledo dorelop|=|=|=letter A|B|Z|a|b|z id letter(letter|digit)*number digit+(.digit+)?(E(+|)?digit+)?delim blank|tab|newline ws delim+2.2 词法记号的描述与识别词法记号的描述与识别 2.2.4 转换图转换图关系算符的转换图关系算符的转换图051624837return(relop,LE)return(relop,NE)return(relop,LT)return(relop,GE)return(relop,GT)return(relop,EQ)开始开始=*otherother2.2 词法记号的描述与识别词法记号的描述与识别 标识符和关键字的转换图标识符和关键字的转换图91011开始开始letterother*letter或或digitreturn(installId()2.2 词法记号的描述与识别词法记号的描述与识别 无符号数的转换图无符号数的转换图 number digit+(.digit+)?(E(+|)?digit+)?开始开始1912131415161718digitdigitdigitdigitdigitdigitother.E+/Edigitotherotherreturn(installNum()*2.2 词法记号的描述与识别词法记号的描述与识别 空白空白的转换图的转换图delim blank|tab|newline ws delim+2122开始开始delimother*delim202.3 有有 限限 自自 动动 机机 2.3.1 不确定的有限自动机（简称不确定的有限自动机（简称NFA）一个数学模型，它包括：一个数学模型，它包括：1、有限的状态集合、有限的状态集合S2、输入符号集合、输入符号集合 3、转换函数、转换函数move:S ()P(S)4、状态、状态s0是唯一的开始状态是唯一的开始状态5、F S是接受状态集合是接受状态集合识别语言识别语言(a|b)*ab 的的NFA12开始开始a0abb输输 入入 符符 号号ab00,10122状状 态态 NFA的转换表的转换表2.3 有有 限限 自自 动动 机机 识别语言识别语言(a|b)*ab 的的NFA12开始开始a0abb2.3 有有 限限 自自 动动 机机 例例 识别识别aa*|bb*的的NFA12开始开始a0abb34 2.3.2 确定的有限自动机（简称确定的有限自动机（简称DFA)一个数学模型，包括：一个数学模型，包括：1、有限的状态集合、有限的状态集合S2、输入字母集合、输入字母集合 3、转换函数、转换函数move:S S，且可以是部分函数且可以是部分函数4、唯一的开始状态、唯一的开始状态 s05、接受状态接受状态集合集合F S12开始开始a0abbab识别语言识别语言(a|b)*ab 的的DFA2.3 有有 限限 自自 动动 机机 2.3 有有 限限 自自 动动 机机 例例 DFA，识别，识别0,1上能被上能被5整除的二进制数整除的二进制数已读过已读过尚未读尚未读已读部分的值已读部分的值某时刻某时刻10101110005读进读进01010 1110005 2=10读进读进110101 1100010 2+1=215个状态即可，分别代表已读部分的值除以个状态即可，分别代表已读部分的值除以5的余数的余数例例 DFA，识别，识别0,1上能被上能被5整除的二进制数整除的二进制数0123开始开始410010101012.3 有有 限限 自自 动动 机机 10102=10101112=710例例 DFA,接受接受 0和和1的个数都是偶数的字符串的个数都是偶数的字符串0000 3 211奇奇0奇奇1奇奇0偶偶1 1011开始开始偶偶0偶偶1偶偶0奇奇12.3 有有 限限 自自 动动 机机 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合2、读了输入、读了输入a1 a2 an后后，NFA能到达的所有状态：能到达的所有状态：s1,s2,sk，则则 DFA到达状态到达状态s1,s2,sk 12a开始开始 0abb00,1aba0,2b2.3 有有 限限 自自 动动 机机 未画完未画完19开始开始 0ab ab6782345 例例(a|b)*ab，NFA如下，把它变换为如下，把它变换为DFA2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号ab状态状态 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abA状态状态 A=0,1,2,4,7 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abAB状态状态 A=0,1,2,4,7 B=1,2,3,4,6,7,8 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABB状态状态 A=0,1,2,4,7 B=1,2,3,4,6,7,8 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCB状态状态 A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBC状态状态 A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBC状态状态 A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBDC状态状态 A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7 D=1,2,4,5,6,7,9 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCD状态状态 A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7 D=1,2,4,5,6,7,9 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCBCD状态状态 A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7 D=1,2,4,5,6,7,9 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCBCDBC状态状态 A=0,1,2,4,7 B=1,2,3,4,6,7,8 C=1,2,4,5,6,7 D=1,2,4,5,6,7,9 2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCBCDBC状态状态 BD开始开始aAabbabCba2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 BD开始开始aAabbabCba12开始开始a0abbab识别语言识别语言(a|b)*ab 的的自动机自动机2.3 有有 限限 自自 动动 机机 19开始开始 0ab ab6782345 BD开始开始aAabbabCba12开始开始a0abbab识别语言识别语言(a|b)*ab 的的自动机自动机子集构造法不一子集构造法不一定得到最简定得到最简DFA2.3 有有 限限 自自 动动 机机 BD开始开始aAabbaa,bCbaEb2.3.4 DFA的化简的化简死状态死状态在转换函数由部分函数改成全函数表示时引入在转换函数由部分函数改成全函数表示时引入左图需要引入死状态左图需要引入死状态E；右图无须引入死状态；右图无须引入死状态BD开始开始aAabbabCba2.3 有有 限限 自自 动动 机机 可区别的状态可区别的状态A和和B是可区别的状态是可区别的状态 从从A出发，读过单字符出发，读过单字符b构成的串，到达非接受构成的串，到达非接受状态状态C，而从，而从B出发，读过串出发，读过串b，到达接受状态，到达接受状态DA和和C是不可区别的状态是不可区别的状态 无任何串可用来像上面这样无任何串可用来像上面这样区别它们区别它们BD开始开始aAabbabCba2.3 有有 限限 自自 动动 机机 方法方法1.A,B,C,Dmove(A,B,C,a)=Bmove(A,B,C,b)=C,D2.A,C,B,Dmove(A,C,a)=Bmove(A,C,b)=CBD开始开始aAabbabCba12开始开始a0abbab2.3 有有 限限 自自 动动 机机 从正规式建立识别器的步骤从正规式建立识别器的步骤从正规式构造从正规式构造NFA（本节介绍）本节介绍）用语法制导的算法，它用正规式语法结构来指导用语法制导的算法，它用正规式语法结构来指导构造过程构造过程把把NFA变成变成DFA（子集构造法，已介绍）子集构造法，已介绍）将将DFA化简化简（合并不可区别状态，也已介绍）（合并不可区别状态，也已介绍）2.4 从正规式到有限自动机从正规式到有限自动机首先构造识别首先构造识别 和字母表中一个符号的和字母表中一个符号的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换i开始开始 识别正规式识别正规式 的的NFAafif开始开始识别正规式识别正规式a的的NFA2.4 从正规式到有限自动机从正规式到有限自动机构造识别主算符为选择的正规式的构造识别主算符为选择的正规式的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换 fi开始开始识别正规式识别正规式s|t 的的NFAN(s)N(t)2.4 从正规式到有限自动机从正规式到有限自动机构造识别主算符为连接的正规式的构造识别主算符为连接的正规式的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换识别正规式识别正规式 st 的的NFAiN(s)f开始开始N(t)2.4 从正规式到有限自动机从正规式到有限自动机构造识别主算符为闭包的正规式的构造识别主算符为闭包的正规式的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换N(s)f开始开始识别正规式识别正规式 s*的的NFAi 2.4 从正规式到有限自动机从正规式到有限自动机对于加括号的正规式对于加括号的正规式(s)，使用使用N(s)本身作为本身作为它的它的NFA2.4 从正规式到有限自动机从正规式到有限自动机本方法产生的本方法产生的NFA有有下列性质下列性质N(r)的状态数最多是的状态数最多是r中符号和算符总数的两倍中符号和算符总数的两倍N(r)只只有有一一个个接接受受状状态态，接接受受状状态态没没有有向向外外的的转转换换2.4 从正规式到有限自动机从正规式到有限自动机19开始开始 0ab ab6782345 本方法产生的本方法产生的NFA有有下列性质下列性质N(r)的的每每个个状状态态有有一一个个用用 的的符符号号标标记记的的指指向向其其它它结点的转换，或者最多两个指向其它结点的结点的转换，或者最多两个指向其它结点的 转换转换2.4 从正规式到有限自动机从正规式到有限自动机19开始开始 0ab ab6782345 2.4 从正规式到有限自动机从正规式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 从正规式到有限自动机从正规式到有限自动机 19开始开始 0 ab678ab2345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 从正规式到有限自动机从正规式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 从正规式到有限自动机从正规式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 从正规式到有限自动机从正规式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 从正规式到有限自动机从正规式到有限自动机19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 从正规式到有限自动机从正规式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解(a|b)*ab的两个的两个NFA的比较的比较 12开始开始a 0abb手工构造手工构造:算法构造算法构造:2.4 从正规式到有限自动机从正规式到有限自动机19开始开始 0ab ab6782345 小结：从正规式建立识别器的步骤小结：从正规式建立识别器的步骤从正规式构造从正规式构造NFA把把NFA变成变成DFA将将DFA化简化简存在其它办法存在其它办法2.4 从正规式到有限自动机从正规式到有限自动机 用用Lex建立词法分析器的步骤建立词法分析器的步骤Lex编译器编译器Lex源程序源程序lex.llex.yy.cC编译器编译器lex.yy.ca.outa.out输入流输入流记号序列记号序列2.5 词法分析器的生成器词法分析器的生成器Lex程序包括三个部分程序包括三个部分 声明声明 翻译规则翻译规则 辅助过程辅助过程Lex程序的翻译规则程序的翻译规则 p1动作动作1 p2动作动作2 pn动作动作n2.5 词法分析器的生成器词法分析器的生成器例例声明部分声明部分%/*常量常量LT,LE,EQ,NE,GT,GE,WHILE,DO,ID,NUMBER,RELOP的定义的定义*/%/*正规定义正规定义*/delim t n wsdelim+letterA Za zdigit0 9idletter(letter|digit)*numberdigit+(.digit+)?(E+?digit+)?2.5 词法分析器的生成器词法分析器的生成器例例翻译规则部分翻译规则部分ws/*没有没有动动作，也不返回作，也不返回*/whilereturn(WHILE);doreturn(DO);idyylval=install_id();return(ID);numberyylval=install_num();return(NUMBER);“”yylval=LT;return(RELOP);“=”yylval=LE;return(RELOP);“=”yylval=EQ;return(RELOP);“”yylval=NE;return(RELOP);“”yylval=GT;return(RELOP);“=”yylval=GE;return(RELOP);2.5 词法分析器的生成器词法分析器的生成器例例辅助过程部分辅助过程部分installId()/*把把词词法法单单元装入符号表并返回指元装入符号表并返回指针针。yytext指向指向该词该词法法单单元的第一个字符，元的第一个字符，yyleng给给出的它的出的它的长长度度*/installNum()/*类类似似上上面面的的过过程程，但但词词法法单单元元不不是是标标识识符符而而是数是数*/2.5 词法分析器的生成器词法分析器的生成器词词法法分分析析器器的的作作用用和和接接口口，用用高高级级语语言言编编写写词法分析器等内容词法分析器等内容掌掌握握下下面面涉涉及及的的一一些些概概念念，它它们们之之间间转转换换的的技巧、方法或算法技巧、方法或算法非形式描述的语言非形式描述的语言 正规式正规式正规式正规式 NFA非形式描述的语言非形式描述的语言 NFANFA DFADFA 最简最简DFA非形式描述的语言非形式描述的语言 DFA（或最简或最简DFA）本本 章章 要要 点点叙叙述述下下面面的的正正规规式式描描述述的的语语言言，并并画画出出接接受受该语言的最简该语言的最简DFA的状态转换图的状态转换图(1|01)*0*描述的语言是，所有不含子串描述的语言是，所有不含子串001的的0和和1的串的串 3start001.1012刚读过的不是刚读过的不是0连续读过一个连续读过一个0连续读过连续读过不少于两个不少于两个0例例 题题 1bbbaabbaabbstartabbaaaaabababbabaababababababbbabaabb例例 题题 2用状态转换图表示接受用状态转换图表示接受(a|b)a(a|b)(a|b)的的DFA写写出出语语言言“所所有有相相邻邻数数字字都都不不相相同同的的非非空空数数字串字串”的正规定义的正规定义123031357106798035790123answer (0|no_0 0)(no_0 0)(no_0|)|no_0 no_0 (1|no_0-1 1)(no_0-1 1)(no_0-1|)|no_0-1.no_0-8 9 将这些正规定义逆序排列就是答案将这些正规定义逆序排列就是答案例例 题题 3下面下面C语言编译器编译下面的函数时，报告语言编译器编译下面的函数时，报告parse error before elselong gcd(p,q)long p,q;if(p%q=0)/*then part*/return q此处遗漏分号此处遗漏分号else/*else part*/return gcd(q,p%q);例例 题题 4现在少了第一个注释的结束符号后，反而不现在少了第一个注释的结束符号后，反而不报错了报错了long gcd(p,q)long p,q;if(p%q=0)/*then part return qelse/*else part*/return gcd(q,p%q);例例 题题 4第一次第一次 2.3,2.4(f)(g)第二次第二次 2.7(c)(d)，2.8(仅为仅为2.7(c)，2.11，2.15习习 题题