实验Yacc与Lex快速入门.ppt

《实验Yacc与Lex快速入门.ppt》由会员分享，可在线阅读，更多相关《实验Yacc与Lex快速入门.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1编译原理电子教案韶关学院计算机系程细柱实验Yacc与Lex快速入门 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望2编译原理电子教案韶关学院计算机系程细柱Lex Lex 和和 Yacc Yacc 介绍介绍lex 和和 yacc 是什么是什么vLex:Lexical Analyzar,是一种生成扫描器的工具。是一种生成扫描器的工具。Yacc:Yet Another Compiler Compiler vlex 和和 yacc 是是自动编译代码的工具自动编译代码的工

2、具，适合于解析简单，适合于解析简单的语言。的语言。vlex 和和 yacc 是一对配对工具。是一对配对工具。lex 将文件分解为成组的将文件分解为成组的“记号（记号（tokens）”，大体上类似于单词。，大体上类似于单词。yacc 接受接受成组的记号，并将它们装配为高层次的结构，类似于成组的记号，并将它们装配为高层次的结构，类似于句子。句子。vyacc 设计用来处理设计用来处理 lex 的输出，不过您也可以编写自的输出，不过您也可以编写自己的代码来完成此任务。同样，己的代码来完成此任务。同样，lex 的输出很大程度的输出很大程度上设计用于为某类解析器提供数据。上设计用于为某类解析器提供数据。3

3、编译原理电子教案韶关学院计算机系程细柱实验工具简介总揽实验工具简介总揽(1/2)LEXYACC代码产生支撑函数4编译原理电子教案韶关学院计算机系程细柱实验工具简介总揽实验工具简介总揽(2/2)5编译原理电子教案韶关学院计算机系程细柱实验工具简介-LEXLex：一个词汇分析器生成器：一个词汇分析器生成器。当当 Lex 接收到文件或文本形式的输入时，它试图将文接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。它一次读入一个输入字符，本与常规表达式进行匹配。它一次读入一个输入字符，直到找到一个匹配的模式。如果能够直到找到一个匹配的模式。如果能够找到一个匹配的找到一个匹配的模式模式，Le

4、x 就执行相关的动作就执行相关的动作（可能包括返回一个标（可能包括返回一个标记）。另一方面，如果记）。另一方面，如果没有没有可以匹配的常规表达式，可以匹配的常规表达式，将会将会停止停止进一步的处理，进一步的处理，Lex 将将显示一个错误消息显示一个错误消息。程序有三个部分，用程序有三个部分，用%符号隔开。符号隔开。第一部分和最后一第一部分和最后一个部分个部分是普通而是普通而古老的古老的 C 代码代码。中间中间是有趣的一部分。是有趣的一部分。它它由一系列规则构成由一系列规则构成，lex 将这些规则翻译为词汇分析将这些规则翻译为词汇分析器。每一个规则依次包含一个正则表达式以及该正则器。每一个规则依

5、次包含一个正则表达式以及该正则表达式得到匹配时要运行的一些代码。任何没有得到表达式得到匹配时要运行的一些代码。任何没有得到匹配的文本则简单地拷贝到标准输出。匹配的文本则简单地拷贝到标准输出。6编译原理电子教案韶关学院计算机系程细柱Lex 的常规表达式（的常规表达式（1）字符字符 含含义 A-Z,0-9,a-z 构成了部分模式的字符和数字。构成了部分模式的字符和数字。.匹配任意字符，除了匹配任意字符，除了 n。-用来指定范用来指定范围。例如：。例如：A-Z 指从指从 A 到到 Z 之之间的所有的所有字符。字符。一个字符集合。匹配括号内的一个字符集合。匹配括号内的 任意任意 字符。如果第一字符。如

6、果第一个字符是个字符是 那么它表示否定模式。例如：那么它表示否定模式。例如：abC 匹配匹配 a,b 和和 C中的任何一个。中的任何一个。*匹配匹配 0个个或者多个上述的模式。或者多个上述的模式。+匹配匹配 1个个或者多个上述模式。或者多个上述模式。?匹配匹配 0个或个或1个个上述模式。上述模式。$作作为模式的最后一个字符匹配一行的模式的最后一个字符匹配一行的结尾。尾。7编译原理电子教案韶关学院计算机系程细柱Lex 的常规表达式（的常规表达式（2）字符字符 含含义 指出一个模式可能出指出一个模式可能出现的次数。的次数。例如：例如：A1,3 表示表示 A 可能出可能出现1次或次或3次。次。用来用

7、来转义元字符。同元字符。同样用来覆盖字符在此表中定用来覆盖字符在此表中定义的特殊意的特殊意义，只取字符的本意。，只取字符的本意。否定。否定。|表达式表达式间的的逻辑或。或。字符的字面含字符的字面含义。元字符具有。元字符具有。/向前匹配。如果在匹配的模版中的向前匹配。如果在匹配的模版中的“/”后跟有后后跟有后续表达式，只匹配模版中表达式，只匹配模版中“/”前面的部分。如：前面的部分。如：如果如果输入入 A01，那么在模版，那么在模版 A0/1 中的中的 A0 是匹是匹配的。配的。()将一系列常将一系列常规表达式分表达式分组。8编译原理电子教案韶关学院计算机系程细柱常规表达式举例常规表达式举例常常

8、规表达式表达式 含含义 jokers 匹配匹配 jokes 或或 joker。A1,2shis+匹配匹配 AAshis,Ashis,Ashiss,Ashisss。(Ab-e)+匹配在匹配在 A 出出现位置后跟随的从位置后跟随的从 b 到到 e 的的所有字符中的所有字符中的 1 个或个或 多个。多个。9编译原理电子教案韶关学院计算机系程细柱标记声明举例标记声明举例标记 相关表达式相关表达式 含含义 数字数字(number)(0-9)+1个或多个数字个或多个数字字符字符(chars)A-Za-z任意字符任意字符空格空格(blank)一个空格一个空格字字(word)(chars)+1个或多个个或多个

9、 chars 变量量(variable)(字符字符)+(数字数字)*(字符字符)*(数字数字)*10编译原理电子教案韶关学院计算机系程细柱Lex 编程编程Lex 编程可以分为三步：编程可以分为三步：以以 Lex 可以理解的格式指定模式相关的动作。可以理解的格式指定模式相关的动作。在这一文件上运行在这一文件上运行 Lex，生成扫描器的，生成扫描器的 C 代码。代码。编译和链接编译和链接 C 代码，生成可执行的扫描器。代码，生成可执行的扫描器。Lex 的输入格式的输入格式 一个一个 Lex 程序分为三个段：程序分为三个段：第一段：是第一段：是 C 和和 Lex 的全局声明的全局声明第二段：包括模式

10、（第二段：包括模式（C 代码）代码）第三段：是补充的第三段：是补充的 C 函数。函数。这些段以这些段以%来分界。来分界。11编译原理电子教案韶关学院计算机系程细柱（1）C 和和 Lex 的全局声明的全局声明 这一段中我们可以增加这一段中我们可以增加 C 变量声明。变量声明。%int wordCount=0;/*保存统计出来的字数保存统计出来的字数*/%chars A-Za-z numbers (0-9)+delim nt whitespace delim+words chars+%两个百分号标记指出了两个百分号标记指出了 Lex 程序中这一段的结束和程序中这一段的结束和三段中第二段的开始。三段

11、中第二段的开始。12编译原理电子教案韶关学院计算机系程细柱（2）Lex 的模式匹配规则的模式匹配规则words wordCount+;/*increase the word count by one*/whitespace /*do nothing*/numbers /*one may want to add some processing here*/%13编译原理电子教案韶关学院计算机系程细柱（3）C 代码代码 Lex 编程的第三段，也就是最后一段覆盖了编程的第三段，也就是最后一段覆盖了 C 的函数声明（有时是主函数）。的函数声明（有时是主函数）。Lex 有一套可供有一套可供使用的函数和变

12、量。使用的函数和变量。其中之一就是其中之一就是 yywrap。一。一般来说，般来说，yywrap()的定义如下例的定义如下例。void main()yylex();/*start the analysis*/printf(No of words:%dn,wordCount);int yywrap()return 1;14编译原理电子教案韶关学院计算机系程细柱Lex 变量变量Lex 有几个函数和变量提供了不同的信息，可以用来编译有几个函数和变量提供了不同的信息，可以用来编译实现复杂函数的程序。下表中列出了一些变量和函数，以实现复杂函数的程序。下表中列出了一些变量和函数，以及它们的使用。及它们的使

13、用。yyinFILE*类型。型。它指向它指向 lexer 正在解析的当前文件。正在解析的当前文件。yyoutFILE*类型。型。它指向它指向记录 lexer 输出的位置。出的位置。缺缺省情况下，省情况下，yyin 和和 yyout 都指向都指向标准准输入和入和输出。出。yytext匹配模式的文本存匹配模式的文本存储在在这一一变量中（量中（char*）。）。yyleng给出匹配模式的出匹配模式的长度。度。yylineno 提供当前的行数信息。（提供当前的行数信息。（lexer不一定支持。）不一定支持。）15编译原理电子教案韶关学院计算机系程细柱Lex 函数函数yylex()这一函数开始分析。一函

14、数开始分析。它由它由 Lex 自自动生成。生成。yywrap()这一函数在文件（或一函数在文件（或输入）的末尾入）的末尾调用。如果函用。如果函数的返回数的返回值是是1，就停止解析。，就停止解析。因此它可以用因此它可以用来解析多个文件。代来解析多个文件。代码可以写在第三段，可以写在第三段，这就就能能够解析多个文件。解析多个文件。方法是使用方法是使用 yyin 文件指文件指针（见上表）指向不同的文件，直到所有的文上表）指向不同的文件，直到所有的文件都被解析。最后，件都被解析。最后，yywrap()可以返回可以返回 1 来来表示解析的表示解析的结束。束。yyless(int n)这一函数可以用来送回

15、除了前一函数可以用来送回除了前n 个字符外的所有个字符外的所有读出出标记。yymore()这一函数告一函数告诉 Lexer 将下一个将下一个标记附加到当前附加到当前标记后。后。16编译原理电子教案韶关学院计算机系程细柱例：识别例：识别PL/0单词的单词的LEX程序程序%#include#include “code.h”#include “symbol.h”#include “y.tab.h”extern int level;int cc=0;%IDENT a-zA-Z a-zA-Z0-9*NUMBER 0-90-9*%17编译原理电子教案韶关学院计算机系程细柱“cc+;“t“tablize()

16、;/*adjust cc to tab-position*/“n“cc=0;line_copy();/*copy a line of input file*/“cc+;return GT;“=“cc+;return ET;“#“cc+;return NT;“,“cc+;return colon;“.“cc+;return Period;“(“cc+;return Lparen;“)“cc+;return Rparen;“=“cc+;cc+;return GE;“:=“cc+;cc+;return ASGN;“;“cc+;return Semicolon;18编译原理电子教案韶关学院计算机系程细

17、柱NUMBER int n;cc+=yyleng;sscanf(yytext,”%d”,&n);yylval.numder=n;return NUMBER;IDENT Symbol *s;cc+=yyleng;if(s=lookup(yytext)=0)s=install(yytext,VARIABLE,level,0);if(s-type=C)yylval.numder=s-adr;else yylval.sym=s;return s-type;%19编译原理电子教案韶关学院计算机系程细柱int yywrap()return 1;20编译原理电子教案韶关学院计算机系程细柱实验工具简介实验工具

18、简介-YACC-YACCyacc：另一个编译器的编译器：另一个编译器的编译器 将输入拆分为一连串的记号。现在您需要一些将输入拆分为一连串的记号。现在您需要一些方法来识别高层次的模式。这就是方法来识别高层次的模式。这就是 yacc 要做的要做的：yacc 让您可以描述希望怎样处理记号。让您可以描述希望怎样处理记号。21编译原理电子教案韶关学院计算机系程细柱1 1.E-E+E E-E+E2.E-E*E2.E-E*E3.E-id 3.E-id 1.x+y*z shift 1.x+y*z shift 2 x.+y*z reduce(r3)2 x.+y*z reduce(r3)3 E.+y*z shif

19、t 3 E.+y*z shift 4 E+.y*z shift 4 E+.y*z shift 5 E+y.*z reduce(r3)5 E+y.*z reduce(r3)6 E+E.*z shift 6 E+E.*z shift 7 E+E*.z shift 7 E+E*.z shift 8 E+E*z.reduce(r3)8 E+E*z.reduce(r3)9 E+E*E.reduce(r2)emit 9 E+E*E.reduce(r2)emit multiply multiply 10 E+E.reduce(r1)emit 10 E+E.reduce(r1)emit add add 11

20、E.accept 11 E.accept Input:x+y*zInput:x+y*z22编译原理电子教案韶关学院计算机系程细柱23编译原理电子教案韶关学院计算机系程细柱用用 Yacc 编写语法编写语法 如同如同 Lex 一样一样,一个一个 Yacc 程序也用双百分号程序也用双百分号分为三段。它们是：声明、语法规则和分为三段。它们是：声明、语法规则和 C 代代码。码。24编译原理电子教案韶关学院计算机系程细柱C 与与 Yacc 的声明的声明C 声明可能会定义动作中使用的类型和变声明可能会定义动作中使用的类型和变量，以及宏。还可以包含头文件。每个量，以及宏。还可以包含头文件。每个 Yacc 声明

21、段声明了终端符号和非终端符声明段声明了终端符号和非终端符号（标记）的名称，还可能描述操作符优号（标记）的名称，还可能描述操作符优先级和针对不同符号的数据类型。先级和针对不同符号的数据类型。lexer(Lex)一般返回这些标记。所有这些标记一般返回这些标记。所有这些标记都必须在都必须在 Yacc 声明中进行说明。声明中进行说明。25编译原理电子教案韶关学院计算机系程细柱终端和非终端符号终端和非终端符号终端符号终端符号:代表一类在语法结构上等效的标记。终端符代表一类在语法结构上等效的标记。终端符号有三种类型：号有三种类型：命名标记命名标记:这些由这些由%token 标识符来定义。按照惯例，标识符来

22、定义。按照惯例，它们都是大写。它们都是大写。字符标记字符标记:字符常量的写法与字符常量的写法与 C 相同。例如相同。例如,?就是就是一个字符标记。一个字符标记。字符串标记字符串标记:写法与写法与 C 的字符串常量相同。例如，的字符串常量相同。例如，就是一个字符串标记。就是一个字符串标记。非终端符号非终端符号:是一组非终端符号和终端符号组成的符号。是一组非终端符号和终端符号组成的符号。按照惯例，它们都是小写。按照惯例，它们都是小写。在例子中，在例子中，file 是一个非终是一个非终端标记而端标记而 NAME 是一个终端标记。是一个终端标记。26编译原理电子教案韶关学院计算机系程细柱这意味着表达式

23、可以是几种这意味着表达式可以是几种格式中的任意一种；例如，格式中的任意一种；例如，一个变量、一个加号或者一一个变量、一个加号或者一个数字都可以是一个表达式。个数字都可以是一个表达式。管道字符（管道字符（|）表明可供选）表明可供选择。择。lexer 生成的符号称为生成的符号称为 终结符（终结符（terminals）或者或者 记号（记号（tokens）。从它们。从它们装配而来的内容称为装配而来的内容称为 非终非终结符（结符（non-terminals）。所以，在这个例子中，所以，在这个例子中，NUMBER 是一个终结符；是一个终结符；lexer 正是生成这种结果。正是生成这种结果。相反，相反，va

24、lue 是一个非终结是一个非终结符，它是通过装配终结符而符，它是通过装配终结符而创建出来的。创建出来的。27编译原理电子教案韶关学院计算机系程细柱yacc 可以识别出记号的模式；例如，如上面例子可以识别出记号的模式；例如，如上面例子中所示，它可以识别出一个表达式可能由一个值、中所示，它可以识别出一个表达式可能由一个值、一个加号或者减号以及另一个值构成。它还可以采一个加号或者减号以及另一个值构成。它还可以采取动作；当解析器达到表达式中的那个条件点时，取动作；当解析器达到表达式中的那个条件点时，封装在封装在 中的代码块将会被执行。例如，有人可中的代码块将会被执行。例如，有人可能会编写：能会编写：e

25、xpression:value+value printf(Matched a+expression.n);28编译原理电子教案韶关学院计算机系程细柱你可能会觉得你可能会觉得 YYSTYPE 有点奇怪。但是类似有点奇怪。但是类似 Lex,Yacc 也有一套变量也有一套变量和函数可供用户来进行功和函数可供用户来进行功能扩展。能扩展。YYSTYPE 定义定义了用来将值从了用来将值从 lexer 拷贝拷贝到解析器或者到解析器或者 Yacc 的的 yylval（另一个（另一个 Yacc 变变量）的类型。默认的类型量）的类型。默认的类型是是 int。由于字符串可以由于字符串可以从从 lexer 拷贝，类型

26、被重拷贝，类型被重定义为定义为 char*。29编译原理电子教案韶关学院计算机系程细柱Yacc 语法规则语法规则vYacc 语法规则具有以下一般格式：语法规则具有以下一般格式：vresult:components /*action to be taken in C*/;v在这个例子中，在这个例子中，result 是规则描述的非终是规则描述的非终端符号。端符号。Components 是根据规则放在一是根据规则放在一起的不同的终端和非终端符号。起的不同的终端和非终端符号。如果匹配如果匹配特定序列的话特定序列的话 Components 后面可以跟随后面可以跟随要执行的动作。要执行的动作。30编译原理

27、电子教案韶关学院计算机系程细柱考虑如下的例子：考虑如下的例子：param:NAME EQ NAME printf(tName:%stValue(name):%sn,$1,$3);|NAME EQ VALUE printf(tName:%stValue(value):%sn,$1,$3);如果上例中序列如果上例中序列 NAME EQ NAME 被匹配，将执行相应的被匹配，将执行相应的 括号中的动作。括号中的动作。这里另一个有用的就是这里另一个有用的就是$1 和和$3 的使的使用用,它们引用了标记它们引用了标记 NAME 和和 NAME（或者第二行的（或者第二行的 VALUE）的值。）的值。31编

28、译原理电子教案韶关学院计算机系程细柱附加附加 C 代码代码现在让我们看一下语法文件的最现在让我们看一下语法文件的最后一段，附加后一段，附加 C 代码。（这一段代码。（这一段是可选的，如果有人想要略过它是可选的，如果有人想要略过它的话：）一个函数如的话：）一个函数如 main()调调用用 yyparse()函数（函数（Lex 的的 yylex()等效函数）。等效函数）。一般来说，一般来说，Yacc 最好提供最好提供 yyerror(char msg)函数的代码。函数的代码。当解析器遇当解析器遇到错误时调用到错误时调用 yyerror(char msg)。错误消息作为参数来传。错误消息作为参数来传

29、递。递。32编译原理电子教案韶关学院计算机系程细柱Lex Lex 与与 Yacc Yacc 结合起来结合起来定义节定义节%规则节规则节%支撑函数节支撑函数节 Token定义C codeSample%token%token INTEGERINTEGER#ifndef YYSTYPE#ifndef YYSTYPE#define YYSTYPE int#define YYSTYPE int#endif#endif#define INTEGER 258#define INTEGER 258 extern YYSTYPE yylval;extern YYSTYPE yylval;y.tab.hy.tab

30、.c%#include y.tab.h#include y.tab.h#include#include%0-9+yylval=atoi(yytext);0-9+yylval=atoi(yytext);return INTEGER;return INTEGER;LEX的.l文件33编译原理电子教案韶关学院计算机系程细柱一个程序通常在每次返回一个标记时都要调用一个程序通常在每次返回一个标记时都要调用 yylex()函数。只有在文件结束或者出现错误标记时才会终止。函数。只有在文件结束或者出现错误标记时才会终止。一个由一个由 Yacc 生成的解析器调用生成的解析器调用 yylex()函数来获得标记。函

31、数来获得标记。yylex()可以由可以由 Lex 来生成或完全由自己来编写。来生成或完全由自己来编写。对于对于由由 Lex 生成的生成的 lexer 来说，要和来说，要和 Yacc 结合使用，每当结合使用，每当 Lex 中匹配一个模式时都必须返回一个标记。中匹配一个模式时都必须返回一个标记。因此因此 Lex 中匹配模式时的动作一般格式为：中匹配模式时的动作一般格式为：pattern /*do smthg*/return TOKEN_NAME;于是于是 Yacc 就会获得返回的标记。当就会获得返回的标记。当 Yacc 编译一个带编译一个带有有 杁杁 标记的标记的.y 文件时，会生成一个头文件，它

32、对每文件时，会生成一个头文件，它对每个标记都有个标记都有#define 的定义。的定义。如果如果 Lex 和和 Yacc 一起一起使用的话，头文件必须在相应的使用的话，头文件必须在相应的 Lex 文件文件.lex 中的中的 C 声明段中包括。声明段中包括。34编译原理电子教案韶关学院计算机系程细柱实验题目范例说明实验题目范例说明实验题目出现问题说明实验题目出现问题说明(1)字符数，单词数没有统计出来字符数，单词数没有统计出来(2)最好是文件读写处理最好是文件读写处理35编译原理电子教案韶关学院计算机系程细柱几个重要问题最长子串匹配规则问题文件读写问题细节问题36编译原理电子教案韶关学院计算机系

33、程细柱%#includeint lineno=0;int charno=0;int wordno=0;%charac a-zA-Z0-9word a-zA-Z0-9+line.*n%word+wordno;charno+=yyleng;.+charno;line+lineno;+charno;%int main()yylex();printf(The number of character is:%dn,charno);printf(The number of words is:%dn,wordno);printf(The number of lines is:%dn,lineno);retu

34、rn 0;line nLong substring规则字符数应该加上单词长度回车为一个字符37编译原理电子教案韶关学院计算机系程细柱#endif#ifndef TRUE#define TRUE 1#endif%/*char c;int done=FALSE;ECHO;dowhile(c=input()!=*)if(c=a&c=a&c=z)putc(toupper(c),yyout);else putc(c,yyout);if(c=/)done=TRUE;while(!done);%如果输入的字符不是*,若小写字母则转换成大写字母输出到文件中如果不是小写字母则原样输出输出*38编译原理电子教案韶关学院计算机系程细柱main()FILE*fp1=fopen(in.c,r);FILE*fp2=fopen(out.c,w);yyin=fp1;yyout=fp2;yylex();39编译原理电子教案韶关学院计算机系程细柱细节问题Include的位置在定义时是%而不是%Lex 的变量意义