大连理工大学编译原理PPT

1、正规式正规式状态转换图状态转换图Lex是LEXical compiler的缩写，是Unix环境下非常著名的工具,主要功能是生成一个词法分析器的C源码,描述规则采用正规式。描述词法分析器的文件*.l，经过lex编译后，生成一个lex.yy.c 的文件，然后由C编译器编译生成一个词法分析器。LEX源程序经过LEX处理，并经过编译，可以生成一个词法分析器。这个词法分析器的作用就好像有限自动机一样，可以用来识别和产生单词符号。 Lex编译器编译器Lex源程序源程序lex.llex.yy.cC编译器编译器lex.yy.ca.outa.out输入流输入流记号序列记号序列LEX将用户输入的表达式和动作序列转

2、化为宿主语言的源程序，经过编译后的程序即是词法分析程序，被称为yylex。LEX不是一种完整的语言，但是它可以嵌入到其他程序设计语言的源程序中。嵌入到LEX中的程序设计语言被称为宿主语言。宿主语言用来处理LEX的输出代码，同时也可以由用户添加一些必要的代码辅以词法分析。目前，LEX支持的宿主语言通常是C语言。 用用 Lex 定义常规表达式定义常规表达式 .匹配任意字符，除了匹配任意字符，除了n-指范围指范围A-Za-z0-9$行的结尾行的结尾 模式可能出现的次数，例如模式可能出现的次数，例如A1,3表示表示可能出现可能出现1次或次或3次次(1)行的开始；行的开始；(2)否定否定,操作符操作符只

3、能出现只能出现在左中括号后的第一个字符位置处在左中括号后的第一个字符位置处abc * | ?+等等常用的闭包，逻辑或等操作常用的闭包，逻辑或等操作Lex程序分割输入流同时不搜索每个表达式的程序分割输入流同时不搜索每个表达式的所有可能匹配。每个字符计算一次且仅一次。所有可能匹配。每个字符计算一次且仅一次。例如，计算例如，计算she和和he在输入文本中的出现次数：在输入文本中的出现次数：在这里最后两个规则忽略除了在这里最后两个规则忽略除了he和和she的所有东西。的所有东西。然而，因为然而，因为she包含包含he，Lex不识别包含在不识别包含在she中的中的he的情况。的情况。因为因为she包括包

4、括he，Lex通常不识别通常不识别she中的中的he，因为一旦它处，因为一旦它处理过理过she，这些字符就过去了。，这些字符就过去了。 有时候，用户希望阻止这种选择。动作有时候，用户希望阻止这种选择。动作REJECT表示表示“进行进行下一次选择下一次选择”。它使得当当前规则被执行后，其他的规则可。它使得当当前规则被执行后，其他的规则可以第二次被选择。因此输入指针的位置会被调整。以第二次被选择。因此输入指针的位置会被调整。简单的例子简单的例子删除输入中每行结尾处所有空白符删除输入中每行结尾处所有空白符 % t+$ ;如果要将字符串中的空格或者制表符转换为单如果要将字符串中的空格或者制表符转换为单

5、个空格，需要增加一条规则：个空格，需要增加一条规则：% t+$ ; t+ printf(“ ”);hello worldwo ai tian an men hello world i love# of lines = 3, # of chars = 49下载“第二次上机作业_词法分析 ”文档源程序源程序字符流字符流顺顺序序组组合合词法词法单元单元词法词法记号记号模模式式非形式非形式化描述化描述形式化形式化描述描述正规式正规式字母字母组组合合串串语言语言集集合合集集合合字母表字母表名名字字连接连接 指数指数和和 LUM连接连接 LM闭包闭包 L*正闭包正闭包 L+ +状态状态转换转换图图Lex作

6、业答案作业答案 首尾均为0的二进制串 0，1组成的二进制串，包括空串 倒数第3位为0的二进制串 包含且仅包含3个1的二进制串 1的个数和0的个数均为偶数的二进制串312011110000开始开始偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇1巩固与提高巩固与提高。 11000011010011000011100110110000110100110000111001100123aabbabbbstart45aaa, b012bbbb4aastart最简最简DFA5、为正规式(a|b)*a(a|b)构造最简DFA(课后习题(2.12(a)三种方法：方法一： (1) 根据算法2.4构造NFA (2)

7、 根据算法2.2将NFADFA (3) 根据算法2.3将DFA简化方法二： (1) 直接构造NFA (2) 根据算法2.2将NFADFA A=0 B=0,1 C=0,1,2 D=0,2 (3) 根据算法2.3将DFA简化划分状态集A, B，C,D;A,B面临字母a时转到B,C，由于B,C分属于不同的状态集，故此状态集A,B需要进一步划分成AB;考虑C,D,它面临字母a时转到B,C，而B,C分属于不同的状态集，故此状态集C,D需要进一步划分成CD;由上面可以知道，最简的DFA包含四个状态集ABCD，这样前面的DFA就是最简的DFA。方法三： (1) 直接构造DFA按照课堂所讲述的号外方法，直接构

8、造DFA：任意的a,b串可以分属于以下几种情况:长度为1: a, b;长度大于等于1，末尾两位为ab, aa, ba, bb;画出DFA,其中 1: a, 2: b, 3: aa, 4: ab, 5: ba, 6: bb. (2) 根据算法2.3将DFA简化6、（习题2.17）一个C语言编译器编译下面的函数时，报告parse error before else。这是因为else的前面少了一个分号。但是如果第一个注释/* then part */误写成/* then part那么该编译器发现不了遗漏分号的错误。这是为什么？long gcd(p,q)long p,q; if (p%q = 0)/* then part */return q else/* else part */return gcd(q, p%q);【答案答案】 此时编译器认为/* then part return q else /* else part */是程序的注释，因此它不可能再发现else 前面的语法错误。分析分析