编译原理课件：第三章词法分析 (2)

资源描述

《编译原理课件：第三章词法分析 (2)》由会员分享，可在线阅读，更多相关《编译原理课件：第三章词法分析 (2)（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”引号引号“和和”之间任意不含引号本身的字符串之间任意不含引号本身的字符串词

2、法分析器词法分析器语法分析器语法分析器符号表符号表记号记号(token)取下一个记号取下一个记号源程序源程序第三章第三章词法分析词法分析v上节复习正则式用来表示简单的语言，叫做正则集正则式正则式定义的语言定义的语言备注备注 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 第三章第三章词法分析词法分析v上节复习正则定义 d1 r1 d2 r2 . . . dn rn各个各个di的名字都

3、不同的名字都不同每个每个ri都是都是 d1, d2, , di-1 上的正则式上的正则式第三章第三章词法分析词法分析v上节复习正则定义 letter_ A | B | | Z | a | b | | z | _ digit 0 | 1 | | 9 id letter_( (letter_ | |digit) )* 91011开始开始letterother*letter或或digitreturn(install_id()3.2 词法记号的描述与识别词法记号的描述与识别 v上节复习状态转换图051624837return(relop, LE)return(relop, NE)return(rel

4、op, 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动作动作2 pn动作动作n3.5词法分析器的生成器词法分析器的生成器v例

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+)?3.5词法分析器的生成器词法分析器的生成器v例例翻译规则部分翻译规则部分ws/* * 没有没有动作，也不返回作，也不返回 * */whilereturn (WHILE);doreturn (DO);id

6、yylval = install_id ( ); return (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

7、例例辅助过程部分辅助过程部分installId ( ) /* * 把把词法法单元装入符号表并返回指元装入符号表并返回指针。yytext指向指向该词法法单元的第一个字符，元的第一个字符，yyleng给出的它的出的它的长度度* */installNum ( ) /* * 类似似上上面面的的过程程，但但词法法单元元不不是是标识符符而而是是数数 * */3.5词法分析器的生成器词法分析器的生成器v例例翻译规则部分翻译规则部分ws/* * 没有没有动作，也不返回作，也不返回 * */whilereturn (WHILE);doreturn (DO);idyylval = install_id ( );

8、return (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例例翻译规则部分翻译规则部分ws/* * 没有没有

9、动作，也不返回作，也不返回 * */whilereturn (WHILE);doreturn (DO);idyylval = install_id ( ); return (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);“

10、 = ”yylval = GE; return (RELOP);3.5词法分析器的生成器词法分析器的生成器3.3 有有限限自自动动机机 3.3.1 不确定的有限自动机（简称不确定的有限自动机（简称NFA）一个数学模型，它包括：一个数学模型，它包括：1、有限的状态集合、有限的状态集合S2、输入符号集合、输入符号集合 3、转换函数、转换函数move : S ( ) P(S)4、状态、状态s0是唯一的开始状态是唯一的开始状态5、F S是接受状态集合是接受状态集合识别语言识别语言(a|b)*ab 的的NFA12开始开始a0abb输输入入符符号号ab00,10122状状态态 NFA的转换表的转

11、换表3.3 有有限限自自动动机机识别语言识别语言(a|b)*ab 的的NFA12开始开始a0abb3.3 有有限限自自动动机机 v例例识别aa* *| |bb* *的的NFA12开始开始a0abb34 3.3.2 确定的有限自动机（简称确定的有限自动机（简称DFA) ) 一个数学模型，包括：一个数学模型，包括：1、有限的状态集合、有限的状态集合S2、输入字母集合、输入字母集合 3、转换函数、转换函数move : S S，且可以是部分函数且可以是部分函数4、唯一的开始状态、唯一的开始状态 s05、接受状态接受状态集合集合F S12开始开始a0abbab识别语言识别语言(a|b

12、)*ab 的的DFA3.3 有有限限自自动动机机 3.3 有有限限自自动动机机 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 |

13、 b)* a b 的DFADFANFA3.3 有有限限自自动动机机 v例例 DFA，识别，识别0,1上能被上能被5整除的二进制数整除的二进制数已读过已读过尚未读尚未读已读部分的值已读部分的值某时刻某时刻10101110005读进读进01010 1110005 2 = 10读进读进110101 1100010 2 + 1= 215个状态即可，分别代表已读部分的值除以个状态即可，分别代表已读部分的值除以5的余数的余数v例例 DFA，识别，识别0,1上能被上能被5整除的二进制数整除的二进制数0123开始开始410010101013.3 有有限限自自动动机机 10102 = 10101

14、112 = 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的变换的变换子集构造法子集构造法1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA

15、到达状态到达状态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开始开始 0ab ab6782345 v 例例 (a|b)*ab，NFA如下，把它变换为如下，把它变

16、换为DFA3.3 有有限限自自动动机机 19开始开始 0ab ab6782345 输入符号输入符号ab状态状态 3.3有有限限自自动动机机19开始开始 0ab ab6782345 输入符号输入符号abA状态状态 A = 0, 1, 2, 4, 7 3.3有有限限自自动动机机19开始开始 0ab ab6782345 输入符号输入符号abAB状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 3.3有有限限自自动动机机19开始开始 0ab ab6782345 输入符号输入符号abABB状态状态 A = 0, 1, 2, 4, 7 B = 1, 2,

17、 3, 4, 6, 7, 8 3.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 3.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 3.3有有限限自自动动机机19开始开始 0ab ab6782345 输入符号输入符号abABCBBC状态

18、状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 3.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 3.3有有限限自自动动机机19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCD状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4,

19、6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 3.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 3.3有有限限自自动动机机19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCBCDBC状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7,

20、8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 3.3有有限限自自动动机机19开始开始 0ab ab6782345 输入符号输入符号abABCBBDCBCDBC状态状态 BD开始开始aAabbabCba3.3有有限限自自动动机机19开始开始 0ab ab6782345 BD开始开始aAabbabCba12开始开始a0abbab识别语言识别语言(a|b)*ab 的的自动机自动机3.3有有限限自自动动机机19开始开始 0ab ab6782345 BD开始开始aAabbabCba12开始开始a0abbab子集构造法不一定得到最简子集构造法不一定得到最简D

21、FA3.3有有限限自自动动机机识别语言识别语言(a|b)*ab 的的自动机自动机3.3.4 DFA的化简的化简v每一个正则式可以由一个状态数最少的每一个正则式可以由一个状态数最少的DFA识别，且这个识别，且这个DFA唯一唯一v死状态死状态在转换函数由部分函数改成全函数表示时引入在转换函数由部分函数改成全函数表示时引入死状态对所有输入符号都转换到本身死状态对所有输入符号都转换到本身3.3有有限限自自动动机机BD开始开始aAabbaa, bCbaEb3.3.4 DFA的化简的化简v死状态死状态在转换函数由部分函数改成全函数表示时引入在转换函数由部分函数改成全函数表示时引入死状态对所有输入符号都转换

22、到本身死状态对所有输入符号都转换到本身左图需要引入死状态左图需要引入死状态E ；右图无须引入死状态；右图无须引入死状态BD开始开始aAabbabCba3.3有有限限自自动动机机v可区别的状态可区别的状态A和和B是可区别的状态是可区别的状态从从A出发，读过单字符出发，读过单字符b构成的串，到达非接受构成的串，到达非接受状态状态C，而从，而从B出发，读过串出发，读过串b，到达接受状态，到达接受状态DA和和C是不可区别的状态是不可区别的状态无任何串可用来像上面这样无任何串可用来像上面这样区别它们区别它们BD开始开始aAabbabCba3.3有有限限自自动动机机v方法方法1. A, B, C, D

23、move(A, B, C, a) = Bmove(A, B, C, b) = C, D2. A, C, B, Dmove(A, C, a) = Bmove(A, C, b) = CBD开始开始aAabbabCba12开始开始a0abbab3.3有有限限自自动动机机3.3.4 DFA的化简的化简v构造最简构造最简DFA：构造状态集合的初始划分构造状态集合的初始划分：两个子集：两个子集接受状态子集接受状态子集F和非接受状态子集和非接受状态子集S F3.3有有限限自自动动机机3.3.4 DFA的化简的化简v构造最简构造最简DFA：构造状态集合的初始划分构造状态集合的初始划分：两个子集：两个子集接受

24、状态子集接受状态子集F和非接受状态子集和非接受状态子集S F应用下面的过程构造应用下面的过程构造newvFor 中的每个子集中的每个子集G ，do begin把把G划分为若干子集，划分为若干子集，G的两个状态的两个状态 s 和和 t 在同一子集中，当且仅当在同一子集中，当且仅当对任意输入符号对任意输入符号 a ，s 和和 t 的的 a 转换都到转换都到的同一子集中的同一子集中在在new 中，用中，用G的划分代替的划分代替GvEnd3.3有有限限自自动动机机3.3.4 DFA的化简的化简v构造最简构造最简DFA：构造状态集合的初始划分构造状态集合的初始划分：两个子集：两个子集接受状态子集接受状

25、态子集F和非接受状态子集和非接受状态子集S F应用下面的过程构造应用下面的过程构造newvFor 中的每个子集中的每个子集G ，do begin把把G划分为若干子集，划分为若干子集，G的两个状态的两个状态 s 和和 t 在同一子集中，当且仅当在同一子集中，当且仅当对任意输入符号对任意输入符号 a ，s 和和 t 的的 a 转换都到转换都到的同一子集中的同一子集中在在new 中，用中，用G的划分代替的划分代替GvEnd如果如果new = ，则，则final = ；否则令；否则令 = new ，转上步，转上步3.3有有限限自自动动机机3.3.4 DFA的化简的化简v构造最简构造最简DFA：构造状

26、态集合的初始划分构造状态集合的初始划分：两个子集：两个子集接受状态子集接受状态子集F和非接受状态子集和非接受状态子集S F应用下面的过程构造应用下面的过程构造newvFor 中的每个子集中的每个子集G ，do begin把把G划分为若干子集，划分为若干子集，G的两个状态的两个状态 s 和和 t 在同一子集中，当且仅当在同一子集中，当且仅当对任意输入符号对任意输入符号 a ，s 和和 t 的的 a 转换都到转换都到的同一子集中的同一子集中在在new 中，用中，用G的划分代替的划分代替GvEnd如果如果new = ，则，则final = ；否则令；否则令 = new ，转上步，转上步在在fina

27、l的每个状态子集中选一个状态代表它，即为最简的每个状态子集中选一个状态代表它，即为最简DFA的状态的状态3.3有有限限自自动动机机v从正则式建立识别器的步骤从正则式建立识别器的步骤从正则式构造从正则式构造NFA（本节介绍）本节介绍）用语法制导的算法，它用正则式语法结构来指导用语法制导的算法，它用正则式语法结构来指导构造过程构造过程把把NFA变成变成DFA （子集构造法，已介绍）子集构造法，已介绍）将将DFA化简化简（合并不可区别状态，也已介绍）（合并不可区别状态，也已介绍）3.4从正则式到有限自动机从正则式到有限自动机v首先构造识别首先构造识别和字母表中一个符号的和字母表中一个符号的NFA

28、重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换i开始开始识别正则式识别正则式的的NFAafif开始开始识别正则式识别正则式a的的NFA3.4从正则式到有限自动机从正则式到有限自动机v构造识别主算符为选择的正则式的构造识别主算符为选择的正则式的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换 fi开始开始识别正则式识别正则式s | t 的的NFAN (s)N (t) 3.4从正则式到有限自动机从正则式到有限自动机v构造识别主算符为连接的正则式的构造识别主算符为连接的正则式的NFA重要特点：仅一个接受状态，它没有向

29、外的转换重要特点：仅一个接受状态，它没有向外的转换识别正则式识别正则式 st 的的NFAiN (s)f开始开始N (t)3.4从正则式到有限自动机从正则式到有限自动机v构造识别主算符为闭包的正则式的构造识别主算符为闭包的正则式的NFA重要特点：仅一个接受状态，它没有向外的转换重要特点：仅一个接受状态，它没有向外的转换N (s)f开始开始识别正则式识别正则式 s* 的的NFAi 3.4从正则式到有限自动机从正则式到有限自动机v对于加括号的正则式对于加括号的正则式(s)，使用使用N(s)本身作为本身作为它的它的NFA3.4从正则式到有限自动机从正则式到有限自动机v本方法产生的本方法产生的NFA有有

30、下列性质下列性质N(r)的状态数最多是的状态数最多是r中符号和算符总数的两倍中符号和算符总数的两倍N(r)只只有有一一个个接接受受状状态态，接接受受状状态态没没有有向向外外的的转转换换3.4从正则式到有限自动机从正则式到有限自动机19开始开始 0ab ab6782345 v本方法产生的本方法产生的NFA有有下列性质下列性质N(r)的的每每个个状状态态有有一一个个用用的的符符号号标标记记的的指指向向其其它它结结点点的的转转换换，或或者者最最多多两两个个指指向向其其它它结结点点的的转转换换3.4从正则式到有限自动机从正则式到有限自动机19开始开始 0ab ab6782345 3.4 .4 从正

31、则式到有限自动机从正则式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解3.4 .4 从正则式到有限自动机从正则式到有限自动机 19开始开始 0 ab678ab2345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解3.4 .4 从正则式到有限自动机从正则式到有限自动机 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解3.4 .4 从正则式到有限自动机从正则式到有限自动机 19开始开始 0ab ab6

33、a|b)*ab的分解的分解 (a|b)*ab的两个的两个NFA的比较的比较 12开始开始a 0abb手工构造手工构造:算法构造算法构造:3.4从正则式到有限自动机从正则式到有限自动机19开始开始 0ab ab6782345 v小结：从正则式建立识别器的步骤小结：从正则式建立识别器的步骤从正则式构造从正则式构造NFA把把NFA变成变成DFA将将DFA化简化简3.4从正则式到有限自动机从正则式到有限自动机v直接从正则式到直接从正则式到DFADFA，不需要构造中间的，不需要构造中间的NFANFAv例：例：(a|b)*abb#(a|b)*abb#3.4从正则式到有限自动机从正则式到有限自动机v直接从正

34、则式到直接从正则式到DFADFA，不需要构造中间的，不需要构造中间的NFANFAv例：例：3.4从正则式到有限自动机从正则式到有限自动机v直接从正则式到直接从正则式到DFADFA，不需要构造中间的，不需要构造中间的NFANFAv例：例：3.4从正则式到有限自动机从正则式到有限自动机v直接从正则式到直接从正则式到DFADFA，不需要构造中间的，不需要构造中间的NFANFAv例：例：3.4从正则式到有限自动机从正则式到有限自动机v直接从正则式到直接从正则式到DFADFA，不需要构造中间的，不需要构造中间的NFANFAv例：例：3.4从正则式到有限自动机从正则式到有限自动机v直接从正则式到直接从正则

35、式到DFADFA，不需要构造中间的，不需要构造中间的NFANFAv例：例：3.4从正则式到有限自动机从正则式到有限自动机v直接从正则式到直接从正则式到DFADFA，不需要构造中间的，不需要构造中间的NFANFAv例：例：3.4从正则式到有限自动机从正则式到有限自动机3.4从正则式到有限自动机从正则式到有限自动机v直接从正则式到直接从正则式到DFADFA，不需要构造中间的，不需要构造中间的NFANFA3.4从正则式到有限自动机从正则式到有限自动机v直接从正则式到直接从正则式到DFADFAnullable, firstpos, lastpos, followposnullable, firstpo

36、s, lastpos, followposv直接从正则式到直接从正则式到DFADFA，不需要构造中间的，不需要构造中间的NFANFAv例：例：3.4从正则式到有限自动机从正则式到有限自动机v 用用Lex建立词法分析器的步骤建立词法分析器的步骤Lex编译器编译器Lex源程序源程序lex.llex.yy.cC编译器编译器lex.yy.ca.outa.out输入流输入流记号序列记号序列3.5词法分析器的生成器词法分析器的生成器vLex程序包括三个部分程序包括三个部分声明声明翻译规则翻译规则辅助过程辅助过程vLex程序的翻译规则程序的翻译规则 p1动作动作1 p2动作动作2 pn动作动作n3.5

37、词法分析器的生成器词法分析器的生成器v例例声明部分声明部分%/* * 常量常量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+)?3.5词法分析器的生成器词法分析器的生成器v例例翻译规则部分翻译规则部分ws/* * 没有没有动作，也不返回作，也不返回 * */whilereturn (WHI

38、LE);doreturn (DO);idyylval = install_id ( ); return (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.

39、5词法分析器的生成器词法分析器的生成器v例例辅助过程部分辅助过程部分installId ( ) /* * 把把词法法单元装入符号表并返回指元装入符号表并返回指针。yytext指向指向该词法法单元的第一个字符，元的第一个字符，yyleng给出的它的出的它的长度度* */installNum ( ) /* * 类似似上上面面的的过程程，但但词法法单元元不不是是标识符符而而是是数数 * */3.5词法分析器的生成器词法分析器的生成器v例例翻译规则部分翻译规则部分ws/* * 没有没有动作，也不返回作，也不返回 * */whilereturn (WHILE);doreturn (DO);idyylva

40、l = install_id ( ); return (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例例翻译规

41、则部分翻译规则部分ws/* * 没有没有动作，也不返回作，也不返回 * */whilereturn (WHILE);doreturn (DO);idyylval = install_id ( ); return (ID);number yylval = install_num( );return (NUMBER);“ ”yylval = LT; return (RELOP); “ = ” yylval = LE; return (RELOP);“ = ”yylval = EQ; return (RELOP);“ ”yylval = NE; return (RELOP);“ ”yylval =

42、GT; return (RELOP);“ = ”yylval = GE; return (RELOP);3.5词法分析器的生成器词法分析器的生成器3.5词法分析器的生成器词法分析器的生成器v词法分析器生成工具的设计3.5词法分析器的生成器词法分析器的生成器v词法分析器生成工具的设计v例：a 模式P1的动作A1abb 模式P2的动作A2a*b+ 模式P3的动作A33.5词法分析器的生成器词法分析器的生成器v词法分析器生成工具的设计v例：a 模式P1的动作A1abb 模式P2的动作A2a*b+ 模式P3的动作A33.5词法分析器的生成器词法分析器的生成器v词法分析器生成工具的设计v例：a 模式P1

43、的动作A1abb 模式P2的动作A2a*b+ 模式P3的动作A3v词词法法分分析析器器的的作作用用和和接接口口，用用高高级级语语言言编编写写词法分析器等内容词法分析器等内容v掌掌握握下下面面涉涉及及的的一一些些概概念念，它它们们之之间间转转换换的的技巧、方法或算法技巧、方法或算法非形式描述的语言非形式描述的语言正则式正则式正则式正则式 NFA非形式描述的语言非形式描述的语言 NFANFA DFADFA 最简最简DFA非形式描述的语言非形式描述的语言 DFA（或最简或最简DFA）本本章章要要点点v叙叙述述下下面面的的正正则则式式描描述述的的语语言言，并并画画出出接接受受该语言的最简该语言的最简

展开阅读全文

编译原理课件：第三章词法分析 (2)

最新文档