编译原理陈意云词法分析实用教案

1、2.1 词法(cf)记号及属性 2.1.1 词法(cf)记号、模式、词法(cf)单元 记号名 词法(cf)单元例举模式的非形式描述 if if 字符i, f for for字符f, o, r relation , = , = , 或 0） 第5页/共72页第五页，共73页。2.2 词法记号的描述(mio sh)与识别 语言(yyn)(yyn)的运算 并：L L M = s | s M = s | s L L 或 s s M M 连接：LM = st | s LM = st | s L L 且 t t M M 幂：L0L0是 ，LiLi是Li -1L Li -1L 闭包：L L = L0 = L

2、0 L1 L1 L2 L2 正闭包： L+ = L1 L+ = L1 L2 L2 例 L: A, B, , Z, a, b, , z , D: 0, 1, , 9 L: A, B, , Z, a, b, , z , D: 0, 1, , 9 L L D, LD, L6, L D, LD, L6, L* *, L(L , L(L D ) D )* *, D+ , D+ 第6页/共72页第六页，共73页。2.2 词法记号( j ho)的描述与识别 2.2.2 正规式正规式用来(yn li)表示简单的语言，叫做正规集正规式定义的语言备注aa a (r) | (s)L(r)L(s) r和s是正规式(r

3、)(s)L(r)L(s) r和s是正规式(r)*(L(r)* r是正规式(r)L(r) r是正规式(a) (b)*)| (c)可以写成ab*| c 第7页/共72页第七页，共73页。2.2 词法(cf)记号的描述与识别 正规式的例子 = a, b = a, b a | ba | ba, ba, b (a | b) (a | b )(a | b) (a | b )aa, ab, ba, bbaa, ab, ba, bb aa | ab | ba | bbaa | ab | ba | bbaa, ab, ba, bbaa, ab, ba, bb a a* *由字母a a构成的所有(suyu)(su

4、yu)串集 (a | b)(a | b)* *由a a和b b构成的所有(suyu)(suyu)串集 复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11) ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) (01 | 10) ) ) 句子：0100110100001000001011100101001101000010000010111001第8页/共72页第八页，共73页。2.2 词法(cf)记号的描述与识别 2.2.3 正规(zhnggu)定义对正规(zhnggu)式命名，使表示简洁 d1 r1 d2 r2 . . .

5、 dn rn各个di的名字都不同每个ri都是 d1, d2, , di-1 上的正规(zhnggu)式第9页/共72页第九页，共73页。2.2 词法记号( j ho)的描述与识别 正规定义的例子 C语言的标识符是字母(zm)、数字和下划线组成的串 letter_ A | B | | Z | a | b | | z | _ digit 0 | 1 | | 9 id letter_(letter_ |digit)* 第10页/共72页第十页，共73页。2.2 词法(cf)记号的描述与识别 正规定义的例子 无符号(fho)数集合，例1946,63E8,E6digit 0 | 1 | | 9digit

6、s digit digit*optional_fraction .digits|optional_exponent ( E ( + | | ) digits ) | numberdigits optional_fraction optional_exponent 简化表示number digit+ (.digit+)? (E(+|)? digit+)?第11页/共72页第十一页，共73页。2.2 词法记号( j ho)的描述与识别 正规定义的例子(l zi)（进行下一步讨论的例子(l zi)）while whiledo dorelop | = | = | | | =letter A | B |

7、 | Z | a | b | | z id letter (letter | digit )*number digit+ (.digit+)? (E (+ | )? digit+)? delim blank | tab | newline ws delim+第12页/共72页第十二页，共73页。2.2 词法记号( j ho)的描述与识别 2.2.4 转换(zhunhun)图关系算符的转换(zhunhun)图051624837return(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)return(relop, GT)r

8、eturn(relop, EQ)开始=*otherother第13页/共72页第十三页，共73页。2.2 词法记号( j ho)的描述与识别 标识符和保留字的转换(zhunhun)图91011开始letterother*letter或digitreturn(installId( )第14页/共72页第十四页，共73页。2.2 词法(cf)记号的描述与识别 无符号(fho)数的转换图 number digit+ (.digit+)? (E (+ | )? digit+)?开始1912131415161718digitdigitdigitdigitdigitdigitother.E+/ Edigi

9、totherotherreturn( installNum( ) )*第15页/共72页第十五页，共73页。2.2 词法记号的描述(mio sh)与识别 空白(kngbi)(kngbi)的转换图 delim delim blank | tab | newline blank | tab | newline ws ws delim+ delim+2122开始delimother*delim20第16页/共72页第十六页，共73页。2.3 有 限 自 动 机 2.3.1 不确定的有限不确定的有限(yuxin)自动机（简称自动机（简称NFA）一个数学模型，它包括：一个数学模型，它包括：1、状态集合、

10、状态集合S2、输入符号集合、输入符号集合3、转换函数、转换函数move : S ( ) P(S)4、状态、状态s0是唯一的开始状态是唯一的开始状态5、F S是接受状态集合是接受状态集合识别(shbi)(shbi)语言(a|b)(a|b)* *ab ab 的NFANFA12开始a0abb第17页/共72页第十七页，共73页。状 态NFA的转换(zhunhun)表2.3 有 限 自 动 机 识别(shbi)(shbi)语言(a|b)(a|b)* *ab ab 的NFANFA12开始a0abb第18页/共72页第十八页，共73页。2.3 有 限 自 动 机 例 识别(shbi)aa(shbi)aa*

11、 *|bb|bb* *的NFANFA12开始a0abb34 第19页/共72页第十九页，共73页。1、状态集合S2、输入字母集合 3、转换函数move : S S，且可以是部分(b fen)函数4、唯一的开始状态 s05、接受状态集合F S12开始a0abbab识别(shbi)(shbi)语言(a|b)(a|b)* *ab ab 的DFADFA2.3 有 限 自 动 机 第20页/共72页第二十页，共73页。2.3 有 限 自 动 机 5个状态个状态(zhungti)即可，分别代表已读即可，分别代表已读部分的值除以部分的值除以5的余数的余数第21页/共72页第二十一页，共73页。0123开始(

12、kish)410010101012.3 有 限 自 动 机 10102 = 10101112 = 710第22页/共72页第二十二页，共73页。0000 3 211奇0奇1奇0偶1 1011开始偶0偶1偶0奇12.3 有 限 自 动 机 第23页/共72页第二十三页，共73页。 12a开始 0abb00, 1aba0, 2b2.3 有 限 自 动 机 未画完第24页/共72页第二十四页，共73页。19开始 0ab ab6782345 例 (a|b)*ab，NFA如下(rxi)，把它变换为DFA2.3 有 限 自 动 机 第25页/共72页第二十五页，共73页。19开始 0ab ab678234

13、5 状态(zhungti) 第26页/共72页第二十六页，共73页。19开始 0ab ab6782345 状态(zhungti) A = 0, 1, 2, 4, 7第27页/共72页第二十七页，共73页。19开始 0ab ab6782345 状态(zhungti) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8第28页/共72页第二十八页，共73页。19开始 0ab ab6782345 状态(zhungti) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 第29页/共72页第二十九页，共73页。19开始 0ab ab67

14、82345 状态(zhungti) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7第30页/共72页第三十页，共73页。19开始 0ab ab6782345 状态(zhungti) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 第31页/共72页第三十一页，共73页。19开始 0ab ab6782345 状态(zhungti) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5

15、, 6, 7 第32页/共72页第三十二页，共73页。19开始 0ab ab6782345 状态(zhungti) 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第33页/共72页第三十三页，共73页。19开始 0ab ab6782345 状态(zhungti) 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第34页/共72页第三十四页，共73页

16、。19开始 0ab ab6782345 状态(zhungti) 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第35页/共72页第三十五页，共73页。19开始 0ab ab6782345 状态(zhungti) 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第36页/共72页第三十六页，共73页。19开始 0ab ab6782345 状态(zhu

17、ngti) BD开始aAabbabCba第37页/共72页第三十七页，共73页。19开始 0ab ab6782345 BD开始aAabbabCba12开始a0abbab识别(shbi)(shbi)语言(a|b)(a|b)* *ab ab 的自动机第38页/共72页第三十八页，共73页。19开始 0ab ab6782345 BD开始aAabbabCba12开始a0abbab识别(shbi)(shbi)语言(a|b)(a|b)* *ab ab 的自动机子集构造(guzo)法不一定得到最简DFA第39页/共72页第三十九页，共73页。BD开始aAabbaa, bCbaEb2.3.4 DFA的化简的化

18、简死状态死状态在转换函数在转换函数(hnsh)由部分函数由部分函数(hnsh)改成全函数改成全函数(hnsh)表示时引入表示时引入左图需要引入死状态左图需要引入死状态E ；右图无须引入死状态；右图无须引入死状态BD开始aAabbabCba第40页/共72页第四十页，共73页。 可区别(qbi)的状态 A和B是可区别(qbi)的状态 从A出发，读过串b，到达非接受状态C，而从B出发，读过串b，到达接受状态D A和C是不可区别(qbi)的状态 无任何串可用来像上面这样区别(qbi)它们BD开始aAabbabCba第41页/共72页第四十一页，共73页。 方法(fngf) 1. A, B, C, D

19、 move(A, B, C, a) = B move(A, B, C, b) = C, D 2. A, C, B, D move(A, C, a) = B move(A, C, b) = CBD开始aAabbabCba12开始a0abbab第42页/共72页第四十二页，共73页。 从正规式建立识别器的步骤 从正规式构造NFANFA（本节介绍）用语法制导的算法，它用正规式语法结构来指导构造过程 把NFANFA变成DFA DFA （子集构造法，已介绍） 将DFADFA化简 （合并(hbng)(hbng)不可区别状态，也已介绍）第43页/共72页第四十三页，共73页。 首先构造识别和字母表中一个符号

20、的NFANFA 重要特点：仅一个接受状态，它没有(mi yu)(mi yu)向外的转换i开始 识别正规式 的NFAafif开始识别正规式a的NFA第44页/共72页第四十四页，共73页。 构造识别主算符为选择的正规式的NFANFA 重要(zhngyo)(zhngyo)特点：仅一个接受状态，它没有向外的转换 fi开始识别正规式s | t 的NFAN (s)N (t) 第45页/共72页第四十五页，共73页。 构造识别主算符为连接(linji)(linji)的正规式的NFANFA 重要特点：仅一个接受状态，它没有向外的转换iN (s)f开始识别正规式 st 的NFAN (t)第46页/共72页第四

21、十六页，共73页。 构造识别主算符为闭包的正规式的NFANFA 重要(zhngyo)(zhngyo)特点：仅一个接受状态，它没有向外的转换N (s)f开始识别正规式 s* 的NFAi 第47页/共72页第四十七页，共73页。 对于(duy)(duy)加括号的正规式(s)(s)，使用N(s)N(s)本身作为它的NFANFA第48页/共72页第四十八页，共73页。 本方法产生的NFA有下列性质 N(r)的状态数最多是r中符号和算符总数的两倍 N(r)只有(zhyu)一个接受状态，接受状态没有向外的转换19开始 0ab ab6782345 第49页/共72页第四十九页，共73页。 本方法产生的NFA

22、有下列性质(xngzh) N(r)的每个状态有一个用的符号标记的指向其它结点的转换，或者最多两个指向其它结点的转换19开始 0ab ab6782345 第50页/共72页第五十页，共73页。2.4 从正规(zhnggu)式到有限自动机 19开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解第51页/共72页第五十一页，共73页。2.4 从正规(zhnggu)式到有限自动机 19开始 0 ab678ab2345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解第52页/共72页第五十二页，共73页。2.4 从正规

23、(zhnggu)式到有限自动机 19开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解第53页/共72页第五十三页，共73页。2.4 从正规(zhnggu)式到有限自动机 19开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解第54页/共72页第五十四页，共73页。2.4 从正规(zhnggu)式到有限自动机 19开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解第55页/共72页第五十五页，共73页。2.4 从正规(zh

24、nggu)式到有限自动机19开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解第56页/共72页第五十六页，共73页。2.4 从正规(zhnggu)式到有限自动机 19开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解第57页/共72页第五十七页，共73页。(a|b)*ab的两个(lin)NFA的比较 12开始a 0abb手工(shugng)构造:算法(sun f)构造:19开始 0ab ab6782345 第58页/共72页第五十八页，共73页。 小结：从正规式建立识别器的步骤

25、 从正规式构造NFANFA 把NFANFA变成DFADFA 将DFADFA化简 存在(cnzi)(cnzi)其它办法第59页/共72页第五十九页，共73页。 用Lex建立( jinl)词法分析器的步骤Lex编译器Lex源程序lex.llex.yy.cC编译器lex.yy.ca.outa.out输入流记号序列第60页/共72页第六十页，共73页。 Lex程序包括三个部分 声明 翻译规则 辅助过程(guchng) Lex程序的翻译规则 p1动作1 p2动作2 pn动作n第61页/共72页第六十一页，共73页。 例声明部分(b fen)(b fen) % / /* * 常量LT, LE, EQ, N

26、E, GT, GE, WHILE, DO, ID, NUMBER, RELOPLT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP的定义* */ / % / /* * 正规定义 * */ / delimdelim t n t n wswsdelim+delim+ letterletterA A Za Za z z digitdigit0099 ididletter(letter|digit)letter(letter|digit)* * numbernumberdigit+( .digit+)?(E+digit+( .digit+)?(E+?

27、digit+)?digit+)?第62页/共72页第六十二页，共73页。 例翻译规则部分 wsws/* * 没有(mi yu)(mi yu)动作，也不返回 * */ whilewhilereturn (WHILE);return (WHILE); dodoreturn (DO);return (DO); ididyylval = install_id ( ); return (ID);yylval = install_id ( ); return (ID); numbernumberyylval = install_num( ); return (NUMBER);yylval = instal

28、l_num( ); return (NUMBER); “ ”yylval = LT; return (RELOP);yylval = LT; return (RELOP); “ = = ” yylval = LE; return (RELOP);yylval = LE; return (RELOP); “ = = ”yylval = EQ; return (RELOP);yylval = EQ; return (RELOP); “ ”yylval = NE; return (RELOP);yylval = NE; return (RELOP); “ ”yylval = GT; return (

29、RELOP);yylval = GT; return (RELOP); “ = = ”yylval = GE; return (RELOP);yylval = GE; return (RELOP);第63页/共72页第六十三页，共73页。 例辅助过程部分(b fen)(b fen) install_ id ( ) install_ id ( ) / /* * 把词法单元装入符号表并返回指针。yytextyytext指向该词法单元的第一个字符，yylengyyleng给出的它的长度* */ / install_num ( ) install_num ( ) / /* * 类似上面的过程，但词法单

30、元不是标识符而是数 * */ / 第64页/共72页第六十四页，共73页。 词法分析器的作用和接口，用高级语言编写词法分析器等内容 掌握下面涉及的一些概念，它们之间转换的技巧、方法(fngf)或算法 非形式描述的语言 正规式 正规式 NFA 非形式描述的语言 NFA NFA DFA DFA 最简DFA 非形式描述的语言 DFA（或最简DFA）第65页/共72页第六十五页，共73页。 叙述下面的正规(zhnggu)(zhnggu)式描述的语言，并画出接受该语言的最简DFADFA的状态转换图(1|01)(1|01)* * 0 0* * 描述的语言是，所有不含子串001001的0 0和1 1的串 3start001.1012刚读过的不是0连续读过一个0连续读过不少于两个0第66页/共72页第六十六页，共73页。bbbaabbaabbstartabbaaaaabababbabaababababababbbabaabb 用状态转换(zhunhun)图表示接收(a|b)a(a|b)(a|b)的DFA第67页/共72页第六十七页，共73页。 写出语言“所有相邻数字都不相同的非空