大连理工大学编译原理.

温故知新正规式计算机实现状态转换图不确定有限自动机确定有限自动机等价子集构造法最简确定有限自动机等价非形式化描述的语言状态列举法合并不可区别状态手工实现用正规式语法结构来指导构造过程？词法分析器的生成器Lex是LEXicalcompiler的缩写，是Unix环境下非常著名的工具,主要功能是生成一个词法分析器的C源码,描述规则采用正规式。描述词法分析器的文件*.l，经过lex编译后，生成一个lex.yy.c的文件，然后由C编译器编译生成一个词法分析器。LEX源程序经过LEX处理，并经过编译，可以生成一个词法分析器。这个词法分析器的作用就好像有限自动机一样，可以用来识别和产生单词符号。2.5词法分析器的生成器2.5词法分析器的生成器用Lex建立词法分析器的步骤Lex编译器Lex源程序lex.llex.yy.cC编译器lex.yy.ca.outa.out输入流记号序列2.5词法分析器的生成器LEX将用户输入的表达式和动作序列转化为宿主语言的源程序，经过编译后的程序即是词法分析程序，被称为yylex。LEX不是一种完整的语言，但是它可以嵌入到其他程序设计语言的源程序中。嵌入到LEX中的程序设计语言被称为宿主语言。宿主语言用来处理LEX的输出代码，同时也可以由用户添加一些必要的代码辅以词法分析。目前，LEX支持的宿主语言通常是C语言。2.5词法分析器的生成器Lex程序包括三个部分声明％％翻译规则％％辅助过程Lex程序的翻译规则p1{动作1}p2{动作2}……pn{动作n}2.5词法分析器的生成器例---声明部分%{/*常量LT,LE,EQ,NE,GT,GE,WHILE,DO,ID,NUMBER,RELOP的定义*/%}/*正规定义*/delim[\t\n]ws{delim}+letter[AZaz]digit[09]id{letter}({letter}|{digit})*number{digit}+(\.{digit}+)?(E[+\]?{digit}+)?2.5词法分析器的生成器例---翻译规则部分{ws}{/*没有动作，也不返回*/}while{return(WHILE);}do{return(DO);}{id}{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);}2.5词法分析器的生成器例---辅助过程部分install_id(){/*把词法单元装入符号表并返回指针。yytext指向该词法单元的第一个字符，yyleng给出的它的长度*/}install_num(){/*类似上面的过程，但词法单元不是标识符而是数*/}用Lex定义常规表达式.匹配任意字符，除了\n-指范围[A-Za-z0-9]$行的结尾{}模式可能出现的次数，例如A{1,3}表示可能出现1次或3次^(1)行的开始；(2)否定,操作符^只能出现在左中括号后的第一个字符位置处[^abc]*|?+等常用的闭包，逻辑或等操作2.5词法分析器的生成器Lex中重要的外部变量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词法分析器的生成器Lex中识别规则二义性处理能匹配最多字符的规则优先能匹配相同数目的字符的规则，书写顺序在前的优先eg：integerkeywordaction...;[a−z]+identifieraction...;当输入为integers时，匹配[a−z]+Lex中识别规则二义性处理Lex程序分割输入流同时不搜索每个表达式的所有可能匹配。每个字符计算一次且仅一次。例如，计算she和he在输入文本中的出现次数：shes++heh++\n|/*规则同下一行*/.;在这里最后两个规则忽略除了he和she的所有东西。然而，因为she包含he，Lex不识别包含在she中的he的情况。Lex中识别规则二义性处理假设需要计算输入文本中she中he的个数she{s++;REJECT;}he{h++;}\n|/*规则同下一行*/.;因为she包括he，Lex通常不识别she中的he，因为一旦它处理过she，这些字符就过去了。有时候，用户希望阻止这种选择。动作REJECT表示“进行下一次选择”。它使得当当前规则被执行后，其他的规则可以第二次被选择。因此输入指针的位置会被调整。2.5词法分析器的生成器简单的例子删除输入中每行结尾处所有空白符%%[\t]+$;如果要将字符串中的空格或者制表符转换为单个空格，需要增加一条规则：%%[\t]+$;[\t]+printf(“”);2.5词法分析器的生成器intnum_lines=0,num_chars=0;%%\n++num_lines;++num_chars;.++num_chars;%%main(){yylex();printf(#oflines=%d,#ofchars=%d\n,num_lines,num_chars);}上机实验例子example.l2.5词法分析器的生成器helloworldwoaitiananmenhelloworldilove上机实验例子example.llex.yy.exe#oflines=3,#ofchars=49上机作业1、下载“软件学院编译原理实践.zip”，阅读教程中有关PL/0词法分析器的源代码。2、下载“Lex_一个词法分析器的生成器(全文).doc”，阅读有关Lex的内容。3、下载“Lex和Yacc简明教程.pdf”，阅读教程中有关Lex和Yacc的内容。4、下载“lex_实验.zip”，按照“flex说明.txt”要求完成如下上机题：1、编写一个词法分析器，它针对输入文件，实现以下功能：1）每遇到你的学号，就输出你的名字，对于其他的串原样输出。2）统计输入文件中字母的数目。例如：（以肖永跃的上机题为例）：输入文件如下所示：200213001helloworldwoaitiananmenhelloworldilove200213001输出应该如下所示：肖永钦helloworldwoaitiananmenhelloworldilove肖永钦#ofids=11,#ofchars=66下载“第二次上机作业_词法分析”文档上机作业本章要点源程序字符流顺序组合词法单元词法记号模式非形式化描述形式化描述正规式字母组合串语言集合集合字母表名字连接指数和LUM连接LM闭包L*正闭包L+计算机实现状态转换图不确定有限自动机确定有限自动机等价子集构造法最简确定有限自动机状态列举法合并不可区别状态手工实现正规式语法结构Lex作业答案习题2.3①首尾均为0的二进制串②0，1组成的二进制串，包括空串③倒数第3位为0的二进制串④包含且仅包含3个1的二进制串⑤1的个数和0的个数均为偶数的二进制串1、DFA，接受0和1的个数都是偶数的字符串312011110000开始偶0偶1奇0奇1奇0偶1偶0奇1巩固与提高2、叙述正规式(00|11)((01|10)(00|11)(01|10)(00|11))描述的语言。答案：所有由偶数个0和偶数个1构成的串。分析：该正规式的一个重要特点是，它是两个字符一组来考虑的。正规式(00|11)表示的串的长度是偶数，每两个字符一组的话，不是00就是11。再看正规式(01|10)(00|11)(01|10)，它表示的串由01或10开始，中间有若干组00或11，最后出现01或10。这样的串仍然由偶数个0和偶数个1构成，只不过第一组是01或10的话，那么一定还要有一组01或10才能保证它们的偶数性。显然，正规式(01|10)(00|11)(01|10)(00|11)表示的串也仍然是由偶数个0和偶数个1构成。这样，可以判断题目所给的正规式表示的语言的每个句子都是由偶数个0和偶数个1构成。11000011010011000011100110反过来还需要考虑，任何由偶数个0和偶数个1构成的串是否都在这个语言中。这实际上是问，每个这样的串，其结构是否都符合正规式(00|11)((01|10)(00|11)(01|10)(00|11))所做的刻划。我们可以这样叙述由偶数个0和偶数个1构成的串，从左向右，每两个字符一组地考察它1.由若干个（强调一下，可以是零个）00或11开始（这由正规式(00|11)描述）；2．一旦出现一个01或10，那么经过若干个00或11后，一定会出现一个01或10。这第二个01或10的后面可能还有若干个00或11，一直到串的结束，或者到再次出现01或10为止。如果串没有结束的话，就是重复出现这里所描述的结构（所以这由((01|10)(00|11)(01|10)(00|11))描述）。因此正规式(00|11)((01|10)(00|11)(01|10)(00|11))描述的是偶数个0和偶数个1构成的串。110000110100110000111001103、写出语言“所有相邻数字都不相同的非空数字串”的正规定义。答案：no_0-89no_0-7(8|no_0-88)(no_0-88)(no_0-8|)|no_0-8no_0-6(7|no_0-77)(no_0-77)(no_0-7|)|no_0-7no_0-5(6|no_0-66)(no_0-66)(no_0-6|)|no_0-6no_0-4(5|no_0-55)(no_0-55)(no_0-5|)|no_0-5no_0-3(4|no_0-44)(no_0-44)(no_0-4|)|no_0-4no_0-2(3|no_0-33)(no_0-33)(no_0-3|)|no_0-3no_0-1(2|no_0-22)(no_0-22)(no_0-2|)|no_0-2no_0(1|no_0-11)(no_0-11)(no_0-1|)|no_0-1answer(0|no_00)(no_00)(no_0|)|no_04、将下图的DFA极小化。aastart0123abbbbb4DFA0123aabbabbbstart45aaa,b加入死状态后的DFA1、加入死状态2、合并不可区分状态先把状态集分成非接受状态集{0,1,2,3,5}和接受状态集{4}这两个子集。1．集合{4}不能再分解，我们看集合{0,1,2,3,5}。move({0,1,2,3,5},a)={1,2,5}move({0,1,2,3,5},b)={3,4,5}由于b转换的结果{3,4,5}不是最初划分的某个集合的子集，因此{0,1,2,3,5}需要再分，由于状态1和状态2的b转换都到状态4。因此状态集合的进一步划分是：{1,2}，{0,3,5}和{4}2．由于move({1,2},a)={2,5}move({1,2},b)={4}move({0,3,5},a)={1,5}move({0,3,5},b)={3,5}显然{1,2}和{0,3,5}需要再分，分别分成：{1}和{2}以及{0,3}和{5}3．由于move({0,3},a)={1}move({0,3},b)={3}因此不需要再分。这样状态0和状态3合并成一个状态，我们取0为代表，再删去死状态5，就得到该题的结果。正确做法！012bbbb4aastart最简DFA最初的划分是{0,1,2,3}和{4