《编译原理 备课 课件 Compiler Theory05 - Lex》由会员分享，可在线阅读，更多相关《编译原理 备课 课件 Compiler Theory05 - Lex（95页珍藏版）》请在金锄头文库上搜索。
1、 计算机科学与技术学院编译原理第三章 词法分析第三章 词法分析v上节复习记号名 词法单元例举模式的非形式描述 if if 字符i, f for for字符f, o, r relation , = , = , 或 = 或 = 或 id sum, count, D5由字母开头的字母数字串 number 3.1, 10, 2.8 E12任何数值常数 literal “seg. error”引号“和”之间任意不含引号本身的字符串 词法分析器语法分析器符号表记号(token)取下一个记号源程序第三章 词法分析v上节复习正则式用来表示简单的语言，叫做正则集正则式定义的语言备注aa a (r) | (s)L
2、(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 第三章 词法分析v上节复习正则定义 d1 r1 d2 r2 . . . dn rn各个di的名字都不同每个ri都是 d1, d2, , di-1 上的正则式第三章 词法分析v上节复习正则定义 letter_ A | B | | Z | a | b | | z | _ digit 0 | 1 | | 9 id letter_(letter_ |digit)* 91011开始letterother*letter或dig
3、itreturn(install_id()3.2 词法记号的描述与识别 v上节复习状态转换图051624837return(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)return(relop, GT)return(relop, EQ)开始=*otherotherv 用Lex建立词法分析器的步骤Lex编译器Lex源程序lex.llex.yy.cC编译器lex.yy.ca.outa.out输入流记号序列3.5词法分析器的生成器vLex程序包括三个部分 声明 翻译规则 辅助过程vLex程序的翻译规则 p1动作1 p2动作
4、2 pn动作n3.5词法分析器的生成器v例声明部分%/* 常量LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP的定义*/%/* 正则定义 */delim t n wsdelim+letterA Za zdigit09idletter(letter|digit)*numberdigit+( .digit+)?(E+?digit+)?3.5词法分析器的生成器v例翻译规则部分ws/* 没有动动作，也不返回 */whilereturn (WHILE);doreturn (DO);idyylval = install_id ( ); return
5、(ID);number yylval = 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);3.5词法分析器的生成器v例辅助过程部分installId ( ) /* 把词词法单单元装入符号表并返回指针
6、针。yytext指向该词该词 法单单元的第一个字符，yyleng给给出的它的长长度*/installNum ( ) /* 类类似上面的过过程，但词词法单单元不是标识标识 符而是数 */3.5词法分析器的生成器v例翻译规则部分ws/* 没有动动作，也不返回 */whilereturn (WHILE);doreturn (DO);idyylval = install_id ( ); return (ID);number yylval = install_num( );return (NUMBER);“ ”yylval = LT; return (RELOP); “ = ” yylval = LE;
7、 return (RELOP);“ = ”yylval = EQ; return (RELOP);“ ”yylval = NE; return (RELOP);“ ”yylval = GT; return (RELOP);“ = ”yylval = GE; return (RELOP);3.5词法分析器的生成器v例翻译规则部分ws/* 没有动动作，也不返回 */whilereturn (WHILE);doreturn (DO);idyylval = install_id ( ); return (ID);number yylval = install_num( );return (NUMBER
8、);“ ”yylval = LT; return (RELOP); “ = ” yylval = LE; return (RELOP);“ = ”yylval = EQ; return (RELOP);“ ”yylval = NE; return (RELOP);“ ”yylval = GT; return (RELOP);“ = ”yylval = GE; return (RELOP);3.5词法分析器的生成器3.3 有 限 自 动 机 3.3.1 不确定的有限自动机（简称NFA）一个数学模型，它包括：1、有限的状态集合S2、输入符号集合3、转换函数move : S ( ) P(S)4、状态
9、s0是唯一的开始状态5、F S是接受状态集合识别语言(a|b)*ab 的NFA12开始a0abb输入符号ab00,10122状 态 NFA的转换表3.3 有 限 自 动 机 识别语言(a|b)*ab 的NFA12开始a0abb3.3 有 限 自 动 机 v例 识别识别 aa*|bb*的NFA12开始a0abb343.3.2 确定的有限自动机（简称DFA) 一个数学模型，包括：1、有限的状态集合S2、输入字母集合3、转换函数move : S S，且可以是部分函数4、唯一的开始状态 s05、接受状态集合F S12开始a0abbab识别语言(a|b)*ab 的DFA3.3 有 限 自 动 机 3.3
10、 有 限 自 动 机 v例 模拟DFA输入：输入串x，以文件结束符eof结尾。一个DFA D，其开始状态S0, 结束状态集合是F。输出：如果D接受x，则回答yes，否则回答no3.3 有 限 自 动 机 v例 模拟DFA输入：输入串x，以文件结束符eof结尾。一个DFA D，其开始状态S0, 结束状态集合是F。输出：如果D接受x，则回答yes，否则回答no方法：vmove(s,c) 状态转移vnextchar()返回输入串x的下一个字符3.3 有 限 自 动 机 v例 识别 (a | b)* a b 的DFADFANFA3.3 有 限 自 动 机 v例 DFA，识别0,1上能被5整除的二进制数
11、已读过尚未读已读部分的值某时刻10101110005读进01010 1110005 2 = 10读进110101 1100010 2 + 1= 215个状态即可，分别代表已读部分的值除以5的余数v例 DFA，识别0,1上能被5整除的二进制数0123开始410010101013.3 有 限 自 动 机 10102 = 10101112 = 710v例 DFA,接受 0和1的个数都是偶数的字符串3.3 有 限 自 动 机 v例 DFA,接受 0和1的个数都是偶数的字符串0000 3 211奇0奇1奇0偶1 1011开始偶0偶1偶0奇13.3 有 限 自 动 机 3.3.3 NFA到DFA的变换 子
12、集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1 a2 an后， NFA能到达的所有状态：s1, s2, , sk，则 DFA到达状态s1, s2, , sk 12a开始 0abb00, 1aba0, 2b3.3 有 限 自 动 机 未画完3.3 有 限 自 动 机 3.3.3 NFA到DFA的变换 子集构造法3.3 有 限 自 动 机 3.3.3 NFA到DFA的变换 子集构造法： -closure(T)的计算3.3 有 限 自 动 机 3.3.3 NFA到DFA的变换 子集构造法：状态转换 表的构造19开始0abab6782345v 例 (a|b)*ab，NFA如下，把它
13、变换为DFA3.3 有 限 自 动 机 19开始0abab6782345输入符号ab状态 3.3有限自动机19开始0abab6782345输入符号abA状态 A = 0, 1, 2, 4, 7 3.3有限自动机19开始0abab6782345输入符号abAB状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 3.3有限自动机19开始0abab6782345输入符号abABB状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 3.3有限自动机19开始0abab6782345输入符号abABCB状态 A = 0, 1, 2
14、, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 3.3有限自动机19开始0abab6782345输入符号abABCBC状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 3.3有限自动机19开始0abab6782345输入符号abABCBBC状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 3.3有限自动机19开始0abab6782345输入符号abABCBBDC状态 A = 0
15、, 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 3.3有限自动机19开始0abab6782345输入符号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 3.3有限自动机19开始0abab6782345输入符号abABCBBDCBCD状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1
16、, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 3.3有限自动机19开始0abab6782345输入符号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 3.3有限自动机19开始0abab6782345输入符号abABCBBDCBCDBC状态 BD开始aAabbabCba3.3有限自动机19开始0abab6782345BD开始aAabbabCba12开始a0abbab识别语言(a|b)*ab 的自动机3.3有限自动机19开始0abab6782345BD开始aAabbabCba12开始a0abbab子集构造法不一定得到最简DFA3.3有限自动机识别语言(a|b)*ab 的自动机3.3.4 DFA的化简v每一个正则式可以由一个状态数最少的DFA识别，且这个DFA唯一v死状态在转换函数由部分函数改成全函数表示时引入死状态对所有输入符号都转换到本身3.3有限自动机BD开始aAabbaa, bCbaEb3.3
