25词法分析器的自动生成课件.ppt

1、2023-1-301Principle of Compiling郭郭 一一 晶晶 厦门大学嘉庚学院厦门大学嘉庚学院2023-1-3022.5 词法分析器的自动生成词法分析器的自动生成l2.5.1 Lex的的定义定义l2.5.2 Lex的的格式格式l2.5.3 例子例子2023-1-3032.5 词法分析器的自动生成词法分析器的自动生成 由于不同高级语言中单词的结构大致相同,基本上都可用一组正规式描述,因而希望构造一自动生成系统:只要给出某高级语言单词的一组正规式及识别各类单词时应采取的语义动作,该系统便可自动产生该语言的词法分析程序。2023-1-304 LEX是美国Bell实验室研制的一个词

2、法分析程序的自动生成工具。对任一高级程序语言，用户必须用正规式正规式描述该语言的各个词法类(LEX的源程序的源程序)，LEX就可自动生成该语言的词法分析程序。LEX及其编译系统的作用如下:LEX源程序LEX编译系统词法分析程序L输入串词法分析程序L单词符号串2023-1-305l一种匹配的常规表达式可能会包含相关的动作，这一动作可能还包括返回一个标记(Token)。l当 Lex 接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。它一次读入一个输入字符，直到找到一个匹配的模式。如果能够找到一个匹配的模式，Lex 就执行相关的动作（可能包括返回一个标记）。另一方面，如果没有可以匹配的

3、常规表达式，将会停止进一步的处理，Lex 将显示一个错误消息。2023-1-306lLex 的的常规表达式常规表达式：l常规表达式是一种使用元语言的模式描述。表达式由符号组成，符号一般是字符和数字，但是 Lex 中还有一些具有特殊含义的其他标记。l下面定义了 Lex 中使用的一些标记并给出了几个典型的例子。2023-1-307l 字符字符 含义含义 lA-Z,0-9,a-z 构成了部分模式的字符和数字。l.匹配任意字符，除了 n。l-用来指定范围。例如：A-Z 指从 A 到 Z 之间 的所有字符。l 一个字符集合。匹配括号内的任意字符。如果第一个字符是 那么它表示否定。例:abC 匹配 a,b

4、,和 C中的任何一个。l*匹配 0个或者多个上述的模式。l+匹配 1个或者多个上述模式。l?匹配 0个或1个上述模式。2023-1-308l$作为模式的最后一个字符匹配一行的结尾。l 指出一个模式可能出现的次数。例如:A1,3 表示 A 可能出现1次或3次。若包含名称，则以该名称替换。l 用来转义元字符。同样用来覆盖字符在此表 中定义的特殊意义，只取字符的本意。l 否定。l|表达式间的逻辑或。l一些符号一些符号 字符的字面含义。l/向前匹配。如果在匹配的模版中的“/”后跟有 后续表达式，只匹配模版中“/”前面的部分。如：如果输入 A01，那么在模版 A0/1 中的 A0 是匹配的。l()将一系

5、列常规表达式分组。2023-1-309ljokers lA1,2shis+l数字(1个或多个数字)l字符(任意单个字符)l一个空格 匹配 jokes 或 joker匹配 AAshis,Ashiss(0-9)+A-Za-z 2023-1-3010lLEX源程序由用“%”分隔的三部分组成：l 正规式的辅助定义式、识别规则、用户子程序。lLEX源程序的书写格式：l 辅助定义式l%l 识别规则l%l 用户子程序l其中,一、三部分可省,识别规则不可省。l若用户子程序缺省,则第二个“%”可省;但若无辅助定义式,第一个“%”不能省。2023-1-3011l/*辅助定义辅助定义*/l%lint wordCou

6、nt=0;l%lchars A-za-z_.lnumbers (0-9)+ldelim ntlwhitespace delim+lwords chars+l%2023-1-3012lwords wordCount+;l /*increase the word count by one*/lwhitespace /*do nothing*/lnumbers /*one may want to add some processing here*/l%2023-1-3013lvoid main()ll yylex();/*start the analysis*/l printf(No of word

7、s:%dn,wordCount);llint yywrap()ll return 1;l2023-1-3014l0.开始运行，输入cmd回车；l1.用cd命令切换到bin目录下，输入 lex testa.lex(将在lex所在目录生成lex.yy.c)；l2.编译lex.yy.c，生成lexyy1.obj和lexyy1.exe，可一起移入test目录下；l3.用cd命令切换到test目录下，运行 lexyy1.exe a.txt(统计b.c的字数，并将结果输出到a.txt)。2023-1-3015l1.Lex模式只匹配输入字符或字符串一次(根据规则书写顺序)。l2.Lex执行当前的最长可能匹配

8、的动作。2023-1-3016 另一个简单的LEX源程序如下：(单词的类别编码用整数编码表示)Auxiliary Definitions /*辅助定义*/letterA|B|C|Z|a|b|c|z digit0|1|2|3|9%Recognition Rules /*识别规则*/1 while return(1,null)2 do return(2,null)3 if return(3,null)4 else return(4,null)5 switch return(5,null)2023-1-3017 6 return(6,null)7 return(7,null)8(return(8,n

9、ull)9)return(9,null)10+return(10,null)11 return(11,null)12*return(12,null)13/return(13,null)14=return(14,null)15；return(15,null)2023-1-3018 16 letter(letter|digit)*if(keyword(id)=0)return(16,null);return(id);else return(keyword(id)或 letter(letter|digit)*return(16,getSymbolTableEntryPoint()17 digit(d

10、igit)*val=int(id)；return(17,null)；return(val)或 digit(digit)*return(17,getConstTableEntryPoint()2023-1-3019 18(letter|digit|(|)|+|*|/|=|;)*return(18,null)；inslit(id)；return(pointer,lenth)该LEX源程序中用户子程序为空,其中识别规则A18中的过程inslit(id)是将字字符串常量符串常量id存放到字符表中,pointer指向存放该串的起始位置,lenth存放串长度。2023-1-3020 LEX可以用两种方式来使用：一种是将LEX作为一个单独的工具，用以生成所需的识别程序；另一种是将LEX和语法分析器自动生成工具(如YACC)结合起来使用，用以生成一个编译程序的扫描器和语法分析器。2023-1-3021