实验Yacc与Lex快速入门

1编译原理电子教案韶关学院计算机系程细柱LexLex与与Yacc Yacc 快速入门快速入门授课教师：授课教师：程细柱程细柱系别：系别：计算机科学系计算机科学系2编译原理电子教案韶关学院计算机系程细柱Lex Lex 和和 Yacc Yacc 介绍介绍 lex 和和 yacc 是什么是什么vLex:Lexical Analyzar,是一种生成扫描器的工具。是一种生成扫描器的工具。Yacc:Yet Another Compiler Compiler vlex 和和 yacc 是是自动编译代码的工具自动编译代码的工具，适合于解析简单，适合于解析简单的语言。的语言。vlex 和和 yacc 是一对配对工具。是一对配对工具。lex 将文件分解为成组将文件分解为成组的的“记号（记号（tokens）”，大体上类似于单词。，大体上类似于单词。yacc 接接受成组的记号，并将它们装配为高层次的结构，类似受成组的记号，并将它们装配为高层次的结构，类似于句子。于句子。vyacc 设计用来处理设计用来处理 lex 的输出，不过您也可以编写自的输出，不过您也可以编写自己的代码来完成此任务。同样，己的代码来完成此任务。同样，lex 的输出很大程度的输出很大程度上设计用于为某类解析器提供数据。上设计用于为某类解析器提供数据。3编译原理电子教案韶关学院计算机系程细柱实验工具简介总揽实验工具简介总揽(1/2)LEXYACC代码产生支撑函数4编译原理电子教案韶关学院计算机系程细柱实验工具简介总揽实验工具简介总揽(2/2)5编译原理电子教案韶关学院计算机系程细柱实验工具简介-LEXLex：一个词汇分析器生成器：一个词汇分析器生成器。当当 Lex 接收到文件或文本形式的输入时，它试图将文接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。它一次读入一个输入字符，本与常规表达式进行匹配。它一次读入一个输入字符，直到找到一个匹配的模式。如果能够直到找到一个匹配的模式。如果能够找到一个匹配的找到一个匹配的模式模式，Lex 就执行相关的动作就执行相关的动作（可能包括返回一个标（可能包括返回一个标记）。另一方面，如果记）。另一方面，如果没有没有可以匹配的常规表达式，可以匹配的常规表达式，将会将会停止停止进一步的处理，进一步的处理，Lex 将将显示一个错误消息显示一个错误消息。程序有三个部分，用程序有三个部分，用%符号隔开。符号隔开。第一部分和最后第一部分和最后一个部分一个部分是普通而是普通而古老的古老的 C 代码代码。中间中间是有趣的一部是有趣的一部分。它分。它由一系列规则构成由一系列规则构成，lex 将这些规则翻译为词汇将这些规则翻译为词汇分析器。每一个规则依次包含一个正则表达式以及该分析器。每一个规则依次包含一个正则表达式以及该正则表达式得到匹配时要运行的一些代码。任何没有正则表达式得到匹配时要运行的一些代码。任何没有得到匹配的文本则简单地拷贝到标准输出。得到匹配的文本则简单地拷贝到标准输出。6编译原理电子教案韶关学院计算机系程细柱Lex 的常规表达式（的常规表达式（1）字符字符 含义含义 A-Z,0-9,a-z 构成了部分模式的字符和数字。构成了部分模式的字符和数字。.匹配任意字符，除了匹配任意字符，除了 n。-用来指定范围。例如：用来指定范围。例如：A-Z 指从指从 A 到到 Z 之间的所有之间的所有字符。字符。一个字符集合。匹配括号内的一个字符集合。匹配括号内的 任意任意 字符。如果第一字符。如果第一个字符是个字符是 那么它表示否定模式。例如：那么它表示否定模式。例如：abC 匹配匹配 a,b 和和 C中的任何一个。中的任何一个。*匹配匹配 0个个或者多个上述的模式。或者多个上述的模式。+匹配匹配 1个个或者多个上述模式。或者多个上述模式。?匹配匹配 0个或个或1个个上述模式。上述模式。$作为模式的最后一个字符匹配一行的结尾。作为模式的最后一个字符匹配一行的结尾。7编译原理电子教案韶关学院计算机系程细柱Lex 的常规表达式（的常规表达式（2）字符字符 含义含义 指出一个模式可能出现的次数。指出一个模式可能出现的次数。例如：例如：A1,3 表示表示 A 可能出现可能出现1次或次或3次。次。用来转义元字符。同样用来覆盖字符在此表中用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义，只取字符的本意。定义的特殊意义，只取字符的本意。否定。否定。|表达式间的逻辑或。表达式间的逻辑或。字符的字面含义。元字符具有。字符的字面含义。元字符具有。/向前匹配。如果在匹配的模版中的向前匹配。如果在匹配的模版中的“/”后跟有后后跟有后续表达式，只匹配模版中续表达式，只匹配模版中“/”前面的部分。如：前面的部分。如：如果输入如果输入 A01，那么在模版，那么在模版 A0/1 中的中的 A0 是匹是匹配的。配的。()将一系列常规表达式分组。将一系列常规表达式分组。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个或多个个或多个 chars 变量变量(variable)(字符字符)+(数字数字)*(字字符符)*(数字数字)*10编译原理电子教案韶关学院计算机系程细柱Lex 编程编程Lex 编程可以分为三步：编程可以分为三步：以以 Lex 可以理解的格式指定模式相关的动作。可以理解的格式指定模式相关的动作。在这一文件上运行在这一文件上运行 Lex，生成扫描器的，生成扫描器的 C 代码。代码。编译和链接编译和链接 C 代码，生成可执行的扫描器。代码，生成可执行的扫描器。Lex 的输入格式的输入格式 一个一个 Lex 程序分为三个段：程序分为三个段：第一段：是第一段：是 C 和和 Lex 的全局声明的全局声明第二段：包括模式（第二段：包括模式（C 代码）代码）第三段：是补充的第三段：是补充的 C 函数。函数。这些段以这些段以%来分界。来分界。11编译原理电子教案韶关学院计算机系程细柱（1）C 和和 Lex 的全局声明的全局声明 这一段中我们可以增加这一段中我们可以增加 C 变量声明。变量声明。%int wordCount=0;/*保存统计出来的字数保存统计出来的字数*/%chars A-Za-z numbers (0-9)+delim nt whitespace delim+words chars+%两个百分号标记指出了两个百分号标记指出了 Lex 程序中这一段的结束程序中这一段的结束和三段中第二段的开始。和三段中第二段的开始。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 有一套可供有一套可供使用的函数和变量。使用的函数和变量。其中之一就是其中之一就是 yywrap。一。一般来说，般来说，yywrap()的定义如下例的定义如下例。void main()yylex();/*start the analysis*/printf(No of words:%dn,wordCount);int yywrap()return 1;14编译原理电子教案韶关学院计算机系程细柱Lex 变量变量 Lex 有几个函数和变量提供了不同的信息，可以用来编译有几个函数和变量提供了不同的信息，可以用来编译实现复杂函数的程序。下表中列出了一些变量和函数，以实现复杂函数的程序。下表中列出了一些变量和函数，以及它们的使用。及它们的使用。yyinFILE*类型。类型。它指向它指向 lexer 正在解析的当前文件。正在解析的当前文件。yyoutFILE*类型。类型。它指向记录它指向记录 lexer 输出的位置。输出的位置。缺缺省情况下，省情况下，yyin 和和 yyout 都指向标准输入和输出。都指向标准输入和输出。yytext匹配模式的文本存储在这一变量中（匹配模式的文本存储在这一变量中（char*）。）。yyleng给出匹配模式的长度。给出匹配模式的长度。yylineno 提供当前的行数信息。（提供当前的行数信息。（lexer不一定支持。）不一定支持。）15编译原理电子教案韶关学院计算机系程细柱Lex 函数函数yylex()这一函数开始分析。这一函数开始分析。它由它由 Lex 自动生成。自动生成。yywrap()这一函数在文件（或输入）的末尾调用。如果函这一函数在文件（或输入）的末尾调用。如果函数的返回值是数的返回值是1，就停止解析。，就停止解析。因此它可以用因此它可以用来解析多个文件。代码可以写在第三段，这来解析多个文件。代码可以写在第三段，这就能够解析多个文件。就能够解析多个文件。方法是使用方法是使用 yyin 文件文件指针（见上表）指向不同的文件，直到所有指针（见上表）指向不同的文件，直到所有的文件都被解析。最后，的文件都被解析。最后，yywrap()可以返回可以返回 1 来表示解析的结束。来表示解析的结束。yyless(int n)这一函数可以用来送回除了前这一函数可以用来送回除了前n 个字符外的所有个字符外的所有读出标记。读出标记。yymore()这一函数告诉这一函数告诉 Lexer 将下一个标记附加到当前将下一个标记附加到当前标记后。标记后。16编译原理电子教案韶关学院计算机系程细柱例：识别例：识别PL/0单词的单词的LEX程序程序%#include#include “”#include “”#include “”extern int level;int cc=0;%IDENT a-zA-Z a-zA-Z0-9*NUMBER 0-90-9*%17编译原理电子教案韶关学院计算机系程细柱“cc+;“t“tablize();/*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编译原理电子教案韶关学院计算机系程细柱NUMBER int n;cc+=yyleng;sscanf(yytext,”%d”,&n);=n;return NUMBER;IDENT Symbol *s;cc+=yyleng;if(s=lookup(yytext)=0)s=install(yytext,VARIABLE,level,0);if(s-type=C)=s-adr;else =s;return s-type;%19编译原理电子教案韶关学院计算机系程细柱int yywrap()return 1;20编译原理电子教案韶关学院计算机系程细柱实验工具简介实验工具简介-YACC-YACC yacc：另一个编译器的编译器：另一个编译器的编译器 将输入拆分为一连串的记号。现在您需要一些将输入拆分为一连串的记号。现在您需要一些方法来识别高层次的模式。这就是方法来识别高层次的模式。这就是 yacc 要做要做的：的：yacc 让您可以描述希望怎样处理记号。让您可以描述希望怎样处理记号。21编译原理电子教案韶关学院计算机系程细柱1 1.E-E+E E-E+E2.E-E 2.E-E*E E3.E-id 3.E-id 1.x+y 1.x+y*z shift z shift 2 x.+y 2 x.+y*z reduce(r3)z reduce(r3)3 E.+y 3 E.+y*z shift z shift 4 E+.y 4 E+.y*z shift z shift 5 E+y.5 E+y.*z reduce(r3)z reduce(r3)6 E+E.6 E+E.*z shift z shift 7 E+E 7 E+E*.z shift .z shift 8 E+E 8 E+E*z.reduce(r3)z.reduce(r3)9 E+E 9 E+E*E.reduce(r2)emit E.reduce(r2)emit multiply multiply 10 E+E.reduce(r1)emit 10 E+E.reduce(r1)emit add add 11 E.accept 11 E.accept Input:x+y Input:x+y*z z22编译原理电子教案韶关学院计算机系程细柱23编译原理电子教案韶关学院计算机系程细柱 用用 Yacc 编写语法编写语法 如同如同 Lex 一样一样,一个一个 Yacc 程序也用双百分号程序也用双百分号分为三段。它们是：声明、语法规则和分为三段。它们是：声明、语法规则和 C 代代码。码。24编译原理电子教案韶关学院计算机系程细柱 C 与与 Yacc 的声明的声明C 声明可能会定义动作中使用的类型和声明可能会定义动作中使用的类型和变量，以及宏。还可以包含头文件。每变量，以及宏。还可以包含头文件。每个个 Yacc 声明段声明了终端符号和非终端声明段声明了终端符号和非终端符号（标记）的名称，还可能描述操作符号（标记）的名称，还可能描述操作符优先级和针对不同符号的数据类型。符优先级和针对不同符号的数据类型。lexer(Lex)一般返回这些标记。所有这些一般返回这些标记。所有这些标记都必须在标记都必须在 Yacc 声明中进行说明。声明中进行说明。25编译原理电子教案韶关学院计算机系程细柱 终端和非终端符号终端和非终端符号 终端符号终端符号:代表一类在语法结构上等效的标记。终端符代表一类在语法结构上等效的标记。终端符号有三种类型：号有三种类型：命名标记命名标记:这些由这些由%token 标识符来定义。按照惯例，标识符来定义。按照惯例，它们都是大写。它们都是大写。字符标记字符标记:字符常量的写法与字符常量的写法与 C 相同。例如相同。例如,?就是就是一个字符标记。一个字符标记。字符串标记字符串标记:写法与写法与 C 的字符串常量相同。例如，的字符串常量相同。例如，就是一个字符串标记。就是一个字符串标记。非终端符号非终端符号:是一组非终端符号和终端符号组成的符号。是一组非终端符号和终端符号组成的符号。按照惯例，它们都是小写。按照惯例，它们都是小写。在例子中，在例子中，file 是一个非终是一个非终端标记而端标记而 NAME 是一个终端标记。是一个终端标记。26编译原理电子教案韶关学院计算机系程细柱这意味着表达式可以是几种这意味着表达式可以是几种格式中的任意一种；例如，格式中的任意一种；例如，一个变量、一个加号或者一一个变量、一个加号或者一个数字都可以是一个表达式个数字都可以是一个表达式。管道字符（。管道字符（|）表明可供）表明可供选择。选择。lexer 生成的符号称生成的符号称为为 终结符（终结符（terminals）或或者者 记号（记号（tokens）。从它。从它们装配而来的内容称为们装配而来的内容称为 非非终结符（终结符（non-terminals）。所以，在这个例子中，。所以，在这个例子中，NUMBER 是一个终结符；是一个终结符；lexer 正是生成这种结果。正是生成这种结果。相反，相反，value 是一个非终结是一个非终结符，它是通过装配终结符而符，它是通过装配终结符而创建出来的。创建出来的。27编译原理电子教案韶关学院计算机系程细柱 yacc 可以识别出记号的模式；例如，如上面例子可以识别出记号的模式；例如，如上面例子中所示，它可以识别出一个表达式可能由一个值、中所示，它可以识别出一个表达式可能由一个值、一个加号或者减号以及另一个值构成。它还可以一个加号或者减号以及另一个值构成。它还可以采取动作；当解析器达到表达式中的那个条件点采取动作；当解析器达到表达式中的那个条件点时，封装在时，封装在 中的代码块将会被执行。例如，有中的代码块将会被执行。例如，有人可能会编写：人可能会编写：expression:value+value printf(Matched a+expression.n);28编译原理电子教案韶关学院计算机系程细柱你可能会觉得你可能会觉得 YYSTYPE 有点奇怪。但是类似有点奇怪。但是类似 Lex,Yacc 也有一套变量也有一套变量和函数可供用户来进行功和函数可供用户来进行功能扩展。能扩展。YYSTYPE 定定义了用来将值从义了用来将值从 lexer 拷拷贝到解析器或者贝到解析器或者 Yacc 的的 yylval（另一个（另一个 Yacc 变变量）的类型。默认的类型量）的类型。默认的类型是是 int。由于字符串可以由于字符串可以从从 lexer 拷贝，类型被重拷贝，类型被重定义为定义为 char*。29编译原理电子教案韶关学院计算机系程细柱 Yacc 语法规则语法规则vYacc 语法规则具有以下一般格式：语法规则具有以下一般格式：vresult:components /*action to be taken in C*/;v在这个例子中，在这个例子中，result 是规则描述的非终是规则描述的非终端符号。端符号。Components 是根据规则放在一是根据规则放在一起的不同的终端和非终端符号。起的不同的终端和非终端符号。如果匹配如果匹配特定序列的话特定序列的话 Components 后面可以跟随后面可以跟随要执行的动作。要执行的动作。30编译原理电子教案韶关学院计算机系程细柱 考虑如下的例子：考虑如下的例子：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编译原理电子教案韶关学院计算机系程细柱附加附加 C 代码代码现在让我们看一下语法文件的最现在让我们看一下语法文件的最后一段，附加后一段，附加 C 代码。（这一代码。（这一段是可选的，如果有人想要略过段是可选的，如果有人想要略过它的话：）一个函数如它的话：）一个函数如 main()调用调用 yyparse()函数（函数（Lex 的的 yylex()等效函数）。等效函数）。一般来说一般来说，Yacc 最好提供最好提供 yyerror(char msg)函数的代码。函数的代码。当解析器遇当解析器遇到错误时调用到错误时调用 yyerror(char msg)。错误消息作为参数来传。错误消息作为参数来传递。递。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;%#include y.tab.h#include y.tab.h#include#include%0-9+yylval=atoi(yytext);0-9+yylval=atoi(yytext);return INTEGER;return INTEGER;33编译原理电子教案韶关学院计算机系程细柱 一个程序通常在每次返回一个标记时都要调用一个程序通常在每次返回一个标记时都要调用 yylex()函数。只有在文件结束或者出现错误标记时才会终止。函数。只有在文件结束或者出现错误标记时才会终止。一个由一个由 Yacc 生成的解析器调用生成的解析器调用 yylex()函数来获得标函数来获得标记。记。yylex()可以由可以由 Lex 来生成或完全由自己来编写。来生成或完全由自己来编写。对于由对于由 Lex 生成的生成的 lexer 来说，要和来说，要和 Yacc 结合使用，结合使用，每当每当 Lex 中匹配一个模式时都必须返回一个标记。中匹配一个模式时都必须返回一个标记。因因此此 Lex 中匹配模式时的动作一般格式为：中匹配模式时的动作一般格式为：pattern /*do smthg*/return TOKEN_NAME;于是于是 Yacc 就会获得返回的标记。当就会获得返回的标记。当 Yacc 编译一个带编译一个带有有 杁杁 标记的标记的.y 文件时，会生成一个头文件，它对每文件时，会生成一个头文件，它对每个标记都有个标记都有#define 的定义。的定义。如果如果 Lex 和和 Yacc 一起使一起使用的话，头文件必须在相应的用的话，头文件必须在相应的 Lex 文件文件.lex 中的中的 C 声声明段中包括。明段中包括。34编译原理电子教案韶关学院计算机系程细柱实验题目范例说明实验题目范例说明 实验题目出现问题说明实验题目出现问题说明(1)字符数，单词数没有统计出来字符数，单词数没有统计出来(2)最好是文件读写处理最好是文件读写处理35编译原理电子教案韶关学院计算机系程细柱几个重要问题 最长子串匹配规则问题 文件读写问题 细节问题36编译原理电子教案韶关学院计算机系程细柱%#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);return 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 的变量意义