编译原理第4讲.ppt

温故知新温故知新正规式正规式计算机计算机计算机计算机实现实现实现实现状态转换图状态转换图不确定有不确定有不确定有不确定有限自动机限自动机限自动机限自动机确定有限确定有限确定有限确定有限自动机自动机自动机自动机等价等价等价等价子集构造法子集构造法子集构造法子集构造法最简确定最简确定最简确定最简确定有限自动有限自动有限自动有限自动机机机机等价等价等价等价非形式化非形式化非形式化非形式化描述的语描述的语描述的语描述的语言言言言状态列举法状态列举法状态列举法状态列举法合并不可区别状态合并不可区别状态合并不可区别状态合并不可区别状态手工实现手工实现手工实现手工实现用正规式语法结构来指导构造过程用正规式语法结构来指导构造过程用正规式语法结构来指导构造过程用正规式语法结构来指导构造过程？词法分析器的生成器词法分析器的生成器词法分析器的生成器词法分析器的生成器2.5词法分析器的生成器词法分析器的生成器 用用Lex建立词法分析器的步骤建立词法分析器的步骤Lex编译器编译器Lex源程序源程序lex.llex.yy.cC编译器编译器lex.yy.ca.outa.out输入流输入流记号序列记号序列2.5词法分析器的生成器词法分析器的生成器LexLex程序包括三个部分程序包括三个部分 声明声明声明声明 翻译规则翻译规则翻译规则翻译规则 辅助过程辅助过程辅助过程辅助过程Lex程序的翻译规则程序的翻译规则 p p1 1 动作动作动作动作11 p p2 2 动作动作动作动作22 p pn n 动作动作动作动作n n 2.5词法分析器的生成器词法分析器的生成器例例-声明部分声明部分%/*常常常常量量量量LT,LT,LE,LE,EQ,EQ,NE,NE,GT,GT,GE,GE,WHILE,WHILE,DO,DO,ID,ID,NUMBER,RELOPNUMBER,RELOP的定义的定义的定义的定义*/%/*正规定义正规定义正规定义正规定义*/delimdelimtntnwsws delimdelim+letterletterAA ZaZa zzdigitdigit00 99idid letter(letter|digitletter(letter|digit)*numbernumberdigitdigit+(.(.digitdigit+)?(E)?(E+?digit?digit+)?)?2.5词法分析器的生成器词法分析器的生成器例例-翻译规则部分翻译规则部分 wsws/*没有没有没有没有动动动动作，也不返回作，也不返回作，也不返回作，也不返回*/whilewhilereturn(WHILE);return(WHILE);dodoreturn(DO);return(DO);idid yylvalyylval=install_idinstall_id();return(ID);();return(ID);numbernumber yylvalyylval=install_numinstall_num();return);return(NUMBER);(NUMBER);“”“”yylvalyylval=LT;return(RELOP);=LT;return(RELOP);“=”“=”yylvalyylval=LE;return(RELOP);=LE;return(RELOP);“=”“=”yylvalyylval=EQ;return(RELOP);=EQ;return(RELOP);“”“”yylvalyylval=NE;return(RELOP);=NE;return(RELOP);“”“”yylvalyylval=GT;return(RELOP);=GT;return(RELOP);“=”“=”yylvalyylval=GE;return(RELOP);=GE;return(RELOP);2.5词法分析器的生成器词法分析器的生成器例例-辅助过程部分辅助过程部分install_id()install_id()/*把把把把词词词词法法法法单单单单元装入符号表并返回指元装入符号表并返回指元装入符号表并返回指元装入符号表并返回指针针针针。yytextyytext指向指向指向指向该词该词该词该词法法法法单单单单元的第一个字符，元的第一个字符，元的第一个字符，元的第一个字符，yylengyyleng给给给给出的它的出的它的出的它的出的它的长长长长度度度度*/install_numinstall_num()()/*类类类类似似似似上上上上面面面面的的的的过过过过程程程程，但但但但词词词词法法法法单单单单元元元元不不不不是是是是标标标标识识识识符符符符而而而而是是是是数数数数*/用用Lex定义常规表达式定义常规表达式.匹配任意字符，除了匹配任意字符，除了n-指范围指范围A-Za-z0-9$行的结尾行的结尾模式可能出现的次数，例如模式可能出现的次数，例如A1,3表示可表示可能出现能出现1次或次或3次次1.表示行的开始；表示行的开始；2.否定否定,操作符操作符只能出只能出现在左中括号后的第一个字符位置处现在左中括号后的第一个字符位置处abc，表示除了，表示除了abc外的其他字符。外的其他字符。*|?+等等常用的闭包，逻辑或等操作常用的闭包，逻辑或等操作2.5词法分析器的生成器词法分析器的生成器 LexLex中重要的外部变量中重要的外部变量 yytext:外部字符数外部字符数组组，其内容是当前被某，其内容是当前被某个个规则规则匹配的字符串匹配的字符串yyleng:当前当前yytext中的字符的个数中的字符的个数例：例：a-zA-Z+printf(“word=%s,length=%d”,yytext,yyleng)；另外另外a-zA-Z+printf(“%s”,yytext);可以可以简简写成写成a-zA-Z+ECHO;2.5词法分析器的生成器词法分析器的生成器 LexLex中识别规则二义性处理中识别规则二义性处理 能匹配最多字符的能匹配最多字符的规则优规则优先先能匹配相同数目的字符的能匹配相同数目的字符的规则规则，书书写写顺顺序序在前的在前的优优先先eg：integerkeywordaction.;integerkeywordaction.;azaz+identifieraction.;+identifieraction.;当输入为当输入为当输入为当输入为integersintegers时，匹配时，匹配时，匹配时，匹配 azaz+Lex中识别规则二义性处理假设需要计算输入文本中假设需要计算输入文本中she和和he的个数的个数shes+;REJECT;heh+;n|.;“|”表示本行采取的动作和下面一行采取的表示本行采取的动作和下面一行采取的动作相同。动作相同。2.5词法分析器的生成器词法分析器的生成器简单的例子简单的例子删除输入中每行结尾处所有空白符删除输入中每行结尾处所有空白符%t+$;如果要将字符串中的空格或者制表符转换为单如果要将字符串中的空格或者制表符转换为单个空格，需要增加一条规则：个空格，需要增加一条规则：%t+$;t+printf(“”);2.5词法分析器的生成器词法分析器的生成器简单的例子简单的例子在每行前面插入行号在每行前面插入行号 intyylineno=0;%(.*)nprintf(%4dt%s,yylineno+,yytext);%main()yylex();2.5词法分析器的生成器词法分析器的生成器 intint num_linesnum_lines=0,=0,num_charsnum_chars=0;=0;%n+n+num_linesnum_lines;+;+num_charsnum_chars;.+.+num_charsnum_chars;%main()main()yylexyylex();();printfprintf(#oflines=%d,#ofchars=%(#oflines=%d,#ofchars=%dndn,num_lines,num_charsnum_lines,num_chars););上机实验例子上机实验例子上机实验例子上机实验例子example.lexample.l2.5词法分析器的生成器词法分析器的生成器hello worldwo ai tian an men hello world i love上机实验例子上机实验例子上机实验例子上机实验例子example.lexample.llex.yylex.yy.exe.exe#of lines=3,#of chars=49作业作业1 1、从、从、从、从ftpftp下载下载下载下载“软件学院编译原理实践软件学院编译原理实践软件学院编译原理实践软件学院编译原理实践.zip.zip”，阅读教程中，阅读教程中，阅读教程中，阅读教程中有关有关有关有关PL/0PL/0词法分析器的源代码。词法分析器的源代码。词法分析器的源代码。词法分析器的源代码。2 2、从从从从ftpftp下载下载下载下载“LexLex和和和和YaccYacc简明教程简明教程简明教程简明教程.pdfpdf ”，了解，了解，了解，了解lexlex程序的程序的程序的程序的写法。写法。写法。写法。2 2、从、从、从、从ftpftp下载下载下载下载“lexlex_ _实验实验实验实验.zip.zip”，按照，按照，按照，按照 “flex flex 说明说明说明说明.txt”.txt”要要要要求完成如下上机题：求完成如下上机题：求完成如下上机题：求完成如下上机题：1 1、编写一个词法分析器，它针对输入文件，实现以下功能：、编写一个词法分析器，它针对输入文件，实现以下功能：、编写一个词法分析器，它针对输入文件，实现以下功能：、编写一个词法分析器，它针对输入文件，实现以下功能：1 1）每遇到你的学号，就输出你的名字，对于其他的串原样输出。）每遇到你的学号，就输出你的名字，对于其他的串原样输出。）每遇到你的学号，就输出你的名字，对于其他的串原样输出。）每遇到你的学号，就输出你的名字，对于其他的串原样输出。2 2）统计输入文件中字母数，单词数。）统计输入文件中字母数，单词数。）统计输入文件中字母数，单词数。）统计输入文件中字母数，单词数。例如：（以肖永跃的上机题为例）：例如：（以肖永跃的上机题为例）：例如：（以肖永跃的上机题为例）：例如：（以肖永跃的上机题为例）：输入文件如下所示：输入文件如下所示：输入文件如下所示：输入文件如下所示：200213001 hello world200213001 hello worldwowo aiai tiantian an men an men hello world i lovehello world i love200213001200213001输出应该如下所示：输出应该如下所示：输出应该如下所示：输出应该如下所示：肖永钦肖永钦肖永钦肖永钦 hello worldhello worldwowo aiai tiantian an men an menhello world i lovehello world i love肖永钦肖永钦肖永钦肖永钦#of ids=11,#of chars=66#of ids=11,#of chars=66本本章章要要点点源程序源程序字符流字符流顺顺序序组组合合词法词法单元单元词法词法记号记号模模式式非形式非形式化描述化描述形式化形式化描述描述正规式正规式字母字母组组合合串串语言语言集集合合集集合合字母表字母表名名字字连接连接 指数指数和和 LUM连接连接 LM闭包闭包 L*正闭包正闭包 L+计算机计算机计算机计算机实现实现实现实现状态状态转换转换图图不确不确不确不确定有定有定有定有限自限自限自限自动机动机动机动机确定确定确定确定有限有限有限有限自动自动自动自动机机机机等等等等价价价价子集构子集构子集构子集构造法造法造法造法最简最简最简最简确定确定确定确定有限有限有限有限自动自动自动自动机机机机状态列举法状态列举法状态列举法状态列举法合并不合并不合并不合并不可区别可区别可区别可区别状态状态状态状态手工手工手工手工实现实现实现实现正规式语正规式语正规式语正规式语法结构法结构法结构法结构Lex由偶数个由偶数个0和奇数个和奇数个1构成的所有构成的所有0和和1的串的串在上一题的基础上给出：even_0_even_1 (00|11|(01|10)(00|11)*(01|10)*由偶数个由偶数个0和奇数个和奇数个1构成的所有构成的所有0和和1的串的串 对于偶数个0和奇数个1构成的串，其第一个字符可能是0或1。如果是1，那么剩下的部分一定是偶数个0和偶数个1（即1 even_0_even_1）。如果是0，那么经过若干个偶数个0或偶数个1，一定会出现一个01或10，才能保证0的个数是偶数，1的个数是奇数。若串还没有结束，剩余部分一定是偶数个0和偶数个1。由偶数个由偶数个0和奇数个和奇数个1构成的所有构成的所有0和和1的串的串 答案 even_0_even_1 (00|11|(01|10)(00|11)*(01|10)*even_0_odd_1 1 even_0_even_1|0 even_0_even_1 (01|10)even_0_even_1写出语言“所有相邻数字都不相同的数字串”的正规定义每个句子先由若干个0把它分成若干段，如 123031357106678035590123可以看成123,0,313571,0,6678,0,3559,0,123由此可得到：answer (0|no_0 0)(no_0 0)(no_0|)|no_0 answer(0|no_0 0)(no_0 0)(no_0|)|no_0没有0的部分可以用1来切分no_0 (1|no_0-1 1)(no_0-1 1)(no_0-1|)|no_0-1 no_0-8 9no_0-7 (8|no_0-8 8)(no_0-8 8)(no_0-8|)|no_0-8no_0-6 (7|no_0-7 7)(no_0-7 7)(no_0-7|)|no_0-7no_0-5 (6|no_0-6 6)(no_0-6 6)(no_0-6|)|no_0-6no_0-4 (5|no_0-5 5)(no_0-5 5)(no_0-5|)|no_0-5no_0-3 (4|no_0-4 4)(no_0-4 4)(no_0-4|)|no_0-4no_0-2 (3|no_0-3 3)(no_0-3 3)(no_0-3|)|no_0-3no_0-1 (2|no_0-2 2)(no_0-2 2)(no_0-2|)|no_0-2no_0 (1|no_0-1 1)(no_0-1 1)(no_0-1|)|no_0-1answer (0|no_0 0)(no_0 0)(no_0|)|no_0 将下图的将下图的将下图的将下图的DFADFA极小化。极小化。极小化。极小化。a aa astartstart0 01 12 23 3a ab bb bb bb bb b4 4DFADFA0123aabbabbbstart45aaa,b加入死状态后的加入死状态后的加入死状态后的加入死状态后的DFADFA1 1、加入死状态、加入死状态、加入死状态、加入死状态2 2、合并不可区分状态、合并不可区分状态、合并不可区分状态、合并不可区分状态先把状态集分成非接受状态集先把状态集分成非接受状态集先把状态集分成非接受状态集先把状态集分成非接受状态集0,1,2,3,50,1,2,3,5和接受状态集和接受状态集和接受状态集和接受状态集44这两个子集。这两个子集。这两个子集。这两个子集。1 1集合集合集合集合44不能再分解，我们看集合不能再分解，我们看集合不能再分解，我们看集合不能再分解，我们看集合0,1,2,3,50,1,2,3,5。move move(0,1,2,3,5,a)=1,2,5(0,1,2,3,5,a)=1,2,5 move move(0,1,2,3,5,b)=3,4,5(0,1,2,3,5,b)=3,4,5由于由于由于由于b b 转换的结果转换的结果转换的结果转换的结果3,4,53,4,5不是最初划分的某个集合的子集，因此不是最初划分的某个集合的子集，因此不是最初划分的某个集合的子集，因此不是最初划分的某个集合的子集，因此0,1,2,3,50,1,2,3,5需要需要需要需要再分，由于状态再分，由于状态再分，由于状态再分，由于状态1 1和状态和状态和状态和状态2 2的的的的b b转换都到状态转换都到状态转换都到状态转换都到状态4 4。因此状态集合的进一步划分是：。因此状态集合的进一步划分是：。因此状态集合的进一步划分是：。因此状态集合的进一步划分是：1,21,2，0,3,50,3,5和和和和442 2由于由于由于由于move move(1,2,a)=2,5(1,2,a)=2,5 move move(1,2,b)=4(1,2,b)=4move move(0,3,5,a)=1,5 (0,3,5,a)=1,5 move move(0,3,5,b)=3,5(0,3,5,b)=3,5显然显然显然显然1,21,2和和和和0,3,50,3,5需要再分，分别分成：需要再分，分别分成：需要再分，分别分成：需要再分，分别分成：11和和和和22以及以及以及以及0,30,3和和和和553 3由于由于由于由于move move(0,3,a)=1(0,3,a)=1 move move(0,3,b)=3(0,3,b)=3因此不需要再分。这样状态因此不需要再分。这样状态因此不需要再分。这样状态因此不需要再分。这样状态0 0和状态和状态和状态和状态3 3合并成一个状态，我们取合并成一个状态，我们取合并成一个状态，我们取合并成一个状态，我们取0 0为代表，再删去死状态为代表，再删去死状态为代表，再删去死状态为代表，再删去死状态5 5，就得到该题的结果。，就得到该题的结果。，就得到该题的结果。，就得到该题的结果。正确做法！正确做法！正确做法！正确做法！012bbbb4aastart最简最简DFA最初的划分是最初的划分是最初的划分是最初的划分是0,1,2,30,1,2,3和和和和44。1 1状态集合的进一步划分是：状态集合的进一步划分是：状态集合的进一步划分是：状态集合的进一步划分是：1,21,2，0,30,3和和和和44 2 2忽略了死状态的影响，会认为它们都不需要再分忽略了死状态的影响，会认为它们都不需要再分忽略了死状态的影响，会认为它们都不需要再分忽略了死状态的影响，会认为它们都不需要再分 错误做法！错误做法！错误做法！错误做法！1 1、直接合并不可区分状态、直接合并不可区分状态、直接合并不可区分状态、直接合并不可区分状态0 01 1b bb ba aa astartstarta a4 4一个不正确的结果一个不正确的结果一个不正确的结果一个不正确的结果a aa astartstart0 01 12 23 3a ab bb bb bb bb b4 4DFADFA0,1,2,3 40 a-1 b-21 a-2 b-4 0,2,3 1 42 a-1 b-23 a-1 b-3 a aa astartstart0 01 13 32 2a aa ab bb bb bb b4 4DFADFAa ab b用状态转换图表示接收用状态转换图表示接收(a|b)*aa的的DFA*最简单的句子是aa 开始aa012用状态转换图表示接收(a|b)*aa 的DFA因为在第一个a前可以有若干个b，因此状态0有到自身的b转换。在最后两个字符都是a的串的末尾添加若干个a，能够保持串的这个性质。识别注释的识别注释的DFA第二次上机第二次上机目的：对循环语句和条件判断语句编写词法分析编译程序，只能通过一遍扫描完成。输入：x:=5;if(x0)then x:=2*x+1/3;else x:=2/x;#经词法分析后输出如下序列：（10,x）(18,:=)(11,5)(26,;)(2,if)(27,()