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

编编 译译 原原 理理 Principle of Compiling郭郭 一一 晶晶 厦门大学嘉庚学院厦门大学嘉庚学院6/16/20241编 译 原 理 Principle of Compi2.5 词法分析器的自动生成词法分析器的自动生成l2.5.1 Lex的的定义定义l2.5.2 Lex的的格式格式l2.5.3 例子例子6/16/202422.5 词法分析器的自动生成2.5.1 Lex的定义8/92.5 词法分析器的自动生成词法分析器的自动生成 由于不同高级语言中单词的结构大致相同,基本上都可用一组正规式描述,因而希望构造一自动生成系统:只要给出某高级语言单词的一组正规式及识别各类单词时应采取的语义动作,该系统便可自动产生该语言的词法分析程序。6/16/202432.5 词法分析器的自动生成 由于不同高级语 LEX是美国Bell实验室研制的一个词法分析程序的自动生成工具。对任一高级程序语言，用户必须用正正规规式式描述该语言的各个词法类(LEX的的源源程程序序)，LEX就可自动生成该语言的词法分析程序。LEX及其编译系统的作用如下:LEX源程序LEX编译系统词法分析程序L输入串词法分析程序L单词符号串6/16/20244 LEX是美国Bell实验室研制的一个词法分析2.5.1 Lex的的定义定义l一种匹配的常规表达式可能会包含相关的动作，这一动作可能还包括返回一个标记(Token)。l当 Lex 接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。它一次读入一个输入字符，直到找到一个匹配的模式。如果能够找到一个匹配的模式，Lex 就执行相关的动作（可能包括返回一个标记）。另一方面，如果没有可以匹配的常规表达式，将会停止进一步的处理，Lex 将显示一个错误消息。6/16/202452.5.1 Lex的定义一种匹配的常规表达式可能会包含相关的lLex 的的常规表达式常规表达式：l常规表达式是一种使用元语言的模式描述。表达式由符号组成，符号一般是字符和数字，但是 Lex 中还有一些具有特殊含义的其他标记。l下面定义了 Lex 中使用的一些标记并给出了几个典型的例子。6/16/20246Lex 的常规表达式：8/9/20236l 字符字符 含义含义 lA-Z,0-9,a-z 构成了部分模式的字符和数字。l.匹配任意字符，除了 n。l-用来指定范围。例如：A-Z 指从 A 到 Z 之间 的所有字符。l 一个字符集合。匹配括号内的任意字符。如果第一个字符是 那么它表示否定。例:abC 匹配 a,b,和 C中的任何一个。l*匹配 0个或者多个上述的模式。l+匹配 1个或者多个上述模式。l?匹配 0个或1个上述模式。6/16/20247 字符 l$作为模式的最后一个字符匹配一行的结尾。l 指出一个模式可能出现的次数。例如:A1,3 表示 A 可能出现1次或3次。若包含名称，则以该名称替换。l 用来转义元字符。同样用来覆盖字符在此表 中定义的特殊意义，只取字符的本意。l 否定。l|表达式间的逻辑或。l一些符号一些符号 字符的字面含义。l/向前匹配。如果在匹配的模版中的“/”后跟有 后续表达式，只匹配模版中“/”前面的部分。如：如果输入 A01，那么在模版 A0/1 中的 A0 是匹配的。l()将一系列常规表达式分组。6/16/20248$作为模式的最后一个字符匹配一行的结尾。8/9/202常规表达式举例常规表达式举例ljokers lA1,2shis+l数字(1个或多个数字)l字符(任意单个字符)l一个空格 匹配 jokes 或 joker匹配 AAshis,Ashiss(0-9)+A-Za-z 6/16/20249常规表达式举例jokers 匹配 jokes2.5.2 Lex的的格式格式lLEX源程序由用“%”分隔的三部分组成：l 正规式的辅助定义式、识别规则、用户子程序。lLEX源程序的书写格式：l 辅助定义式l%l 识别规则l%l 用户子程序l其中,一、三部分可省,识别规则不可省。l若用户子程序缺省,则第二个“%”可省;但若无辅助定义式,第一个“%”不能省。6/16/2024102.5.2 Lex的格式LEX源程序由用“%”分隔的三部分2.5.3 例子例子-字数统计程序字数统计程序 l/*辅助定义辅助定义*/l%lint wordCount=0;l%lchars A-za-z_.lnumbers (0-9)+ldelim ntlwhitespace delim+lwords chars+l%6/16/2024112.5.3 例子-字数统计程序/*辅助定义*/8/9/*识别规则识别规则*/lwords wordCount+;l /*increase the word count by one*/lwhitespace /*do nothing*/lnumbers /*one may want to add some processing here*/l%6/16/202412/*识别规则*/words wordCount+/*用户子程序用户子程序*/lvoid main()ll yylex();/*start the analysis*/l printf(No of words:%dn,wordCount);llint yywrap()ll return 1;l6/16/202413/*用户子程序*/void main()8/9/2023编译步骤编译步骤l0.开始运行，输入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)。6/16/202414编译步骤0.开始运行，输入cmd回车；8/9/2023注 意l1.Lex模式只匹配输入字符或字符串一次(根据规则书写顺序)。l2.Lex执行当前的最长可能匹配的动作。6/16/202415注 意1.Lex模式只匹配输入字符或字符串一次(根据规则书 另一个简单的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)6/16/202416 另一个简单的LEX源程序如下：8/9/202316 6 return(6,null)7 return(7,null)8(return(8,null)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)6/16/202417 6 r 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(digit)*val=int(id)；return(17,null)；return(val)或 digit(digit)*return(17,getConstTableEntryPoint()6/16/202418 16 letter(letter|digit)*18(letter|digit|(|)|+|*|/|=|;)*return(18,null)；inslit(id)；return(pointer,lenth)该LEX源程序中用户子程序为空,其中识别规则A18中的过程inslit(id)是将字符串常量字符串常量id存放到字符表中,pointer指向存放该串的起始位置,lenth存放串长度。6/16/202419 18(letter|digit|(LEX可以用两种方式来使用：一种是将LEX作为一个单独的工具，用以生成所需的识别程序；另一种是将LEX和语法分析器自动生成工具(如YACC)结合起来使用，用以生成一个编译程序的扫描器和语法分析器。6/16/202420 LEX可以用两种方式来使用：8/9/2023206/16/202421The End，谢谢!8/9/202321