实验Yacc与Lex快速入门.ppt

Lex与Yacc 快速入门,授课教师：程细柱,系别：计算机科学系,Lex 和 Yacc 介绍,lex 和 yacc 是什么Lex:Lexical Analyzar,是一种生成扫描器的工具。Yacc:Yet Another Compiler Compiler lex 和 yacc 是自动编译代码的工具，适合于解析简单的语言。lex 和 yacc 是一对配对工具。lex 将文件分解为成组的“记号（tokens）”，大体上类似于单词。yacc 接受成组的记号，并将它们装配为高层次的结构，类似于句子。yacc 设计用来处理 lex 的输出，不过您也可以编写自己的代码来完成此任务。同样，lex 的输出很大程度上设计用于为某类解析器提供数据。,实验工具简介总揽(1/2),实验工具简介总揽(2/2),实验工具简介-LEX,Lex：一个词汇分析器生成器。当 Lex 接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。它一次读入一个输入字符，直到找到一个匹配的模式。如果能够找到一个匹配的模式，Lex 就执行相关的动作（可能包括返回一个标记）。另一方面，如果没有可以匹配的常规表达式，将会停止进一步的处理，Lex 将显示一个错误消息。程序有三个部分，用%符号隔开。第一部分和最后一个部分是普通而古老的 C 代码。中间是有趣的一部分。它由一系列规则构成，lex 将这些规则翻译为词汇分析器。每一个规则依次包含一个正则表达式以及该正则表达式得到匹配时要运行的一些代码。任何没有得到匹配的文本则简单地拷贝到标准输出。,Lex 的常规表达式（1）,Lex 的常规表达式（2）,常规表达式举例,标记声明举例,Lex 编程Lex 编程可以分为三步：以 Lex 可以理解的格式指定模式相关的动作。在这一文件上运行 Lex，生成扫描器的 C 代码。编译和链接 C 代码，生成可执行的扫描器。Lex 的输入格式 一个 Lex 程序分为三个段：第一段：是 C 和 Lex 的全局声明第二段：包括模式（C 代码）第三段：是补充的 C 函数。这些段以%来分界。,（1）C 和 Lex 的全局声明 这一段中我们可以增加 C 变量声明。%int wordCount=0;/*保存统计出来的字数*/%chars A-Za-z numbers(0-9)+delim nt whitespace delim+words chars+%两个百分号标记指出了 Lex 程序中这一段的结束和三段中第二段的开始。,（2）Lex 的模式匹配规则words wordCount+;/*increase the word count by one*/whitespace/*do nothing*/numbers/*one may want to add some processing here*/%,（3）C 代码 Lex 编程的第三段，也就是最后一段覆盖了 C 的函数声明（有时是主函数）。Lex 有一套可供使用的函数和变量。其中之一就是 yywrap。一般来说，yywrap()的定义如下例。void main()yylex();/*start the analysis*/printf(No of words:%dn,wordCount);int yywrap()return 1;,Lex 变量,Lex 有几个函数和变量提供了不同的信息，可以用来编译实现复杂函数的程序。下表中列出了一些变量和函数，以及它们的使用。,Lex 函数,例：识别PL/0单词的LEX程序,%#include#include“code.h”#include“symbol.h”#include“”extern int level;int cc=0;%IDENT a-zA-Z a-zA-Z0-9*NUMBER 0-90-9*%,“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;,NUMBER int n;cc+=yyleng;sscanf(yytext,”%d”,%,int yywrap()return 1;,实验工具简介-YACC,yacc：另一个编译器的编译器 将输入拆分为一连串的记号。现在您需要一些方法来识别高层次的模式。这就是 yacc 要做的：yacc 让您可以描述希望怎样处理记号。,1.E-E+E2.E-E*E3.E-id,1.x+y*z shift 2 x.+y*z reduce(r3)3 E.+y*z shift 4 E+.y*z shift 5 E+y.*z reduce(r3)6 E+E.*z shift 7 E+E*.z shift 8 E+E*z.reduce(r3)9 E+E*E.reduce(r2)emit multiply 10 E+E.reduce(r1)emit add 11 E.accept,Input:x+y*z,用 Yacc 编写语法 如同 Lex 一样,一个 Yacc 程序也用双百分号分为三段。它们是：声明、语法规则和 C 代码。,C 与 Yacc 的声明C 声明可能会定义动作中使用的类型和变量，以及宏。还可以包含头文件。每个 Yacc 声明段声明了终端符号和非终端符号（标记）的名称，还可能描述操作符优先级和针对不同符号的数据类型。lexer(Lex)一般返回这些标记。所有这些标记都必须在 Yacc 声明中进行说明。,终端和非终端符号终端符号:代表一类在语法结构上等效的标记。终端符号有三种类型：命名标记:这些由%token 标识符来定义。按照惯例，它们都是大写。字符标记:字符常量的写法与 C 相同。例如,?就是一个字符标记。字符串标记:写法与 C 的字符串常量相同。例如，就是一个字符串标记。非终端符号:是一组非终端符号和终端符号组成的符号。按照惯例，它们都是小写。在例子中，file 是一个非终端标记而 NAME 是一个终端标记。,这意味着表达式可以是几种格式中的任意一种；例如，一个变量、一个加号或者一个数字都可以是一个表达式。管道字符（|）表明可供选择。lexer 生成的符号称为 终结符（terminals）或者 记号（tokens）。从它们装配而来的内容称为 非终结符（non-terminals）。所以，在这个例子中，NUMBER 是一个终结符；lexer 正是生成这种结果。相反，value 是一个非终结符，它是通过装配终结符而创建出来的。,yacc 可以识别出记号的模式；例如，如上面例子中所示，它可以识别出一个表达式可能由一个值、一个加号或者减号以及另一个值构成。它还可以采取动作；当解析器达到表达式中的那个条件点时，封装在 中的代码块将会被执行。例如，有人可能会编写：expression:value+value printf(Matched a+expression.n);,你可能会觉得 YYSTYPE 有点奇怪。但是类似 Lex,Yacc 也有一套变量和函数可供用户来进行功能扩展。YYSTYPE 定义了用来将值从 lexer 拷贝到解析器或者 Yacc 的 yylval（另一个 Yacc 变量）的类型。默认的类型是 int。由于字符串可以从 lexer 拷贝，类型被重定义为 char*。,Yacc 语法规则Yacc 语法规则具有以下一般格式：result:components/*action to be taken in C*/;在这个例子中，result 是规则描述的非终端符号。Components 是根据规则放在一起的不同的终端和非终端符号。如果匹配特定序列的话 Components 后面可以跟随要执行的动作。,考虑如下的例子：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）的值。,附加 C 代码现在让我们看一下语法文件的最后一段，附加 C 代码。（这一段是可选的，如果有人想要略过它的话：）一个函数如 main()调用 yyparse()函数（Lex 的 yylex()等效函数）。一般来说，Yacc 最好提供 yyerror(char msg)函数的代码。当解析器遇到错误时调用 yyerror(char msg)。错误消息作为参数来传递。,Lex 与 Yacc 结合起来,定义节%规则节%支撑函数节,%token INTEGER,#ifndef YYSTYPE#define YYSTYPE int#endif#define INTEGER 258 extern YYSTYPE yylval;,%#include y.tab.h#include%0-9+yylval=atoi(yytext);return INTEGER;,LEX的.l文件,一个程序通常在每次返回一个标记时都要调用 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 声明段中包括。,实验题目范例说明,实验题目出现问题说明(1)字符数，单词数没有统计出来(2)最好是文件读写处理,几个重要问题,最长子串匹配规则问题文件读写问题细节问题,%#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规则,字符数应该加上单词长度,回车为一个字符,#endif#ifndef TRUE#define TRUE 1#endif%/*char c;int done=FALSE;ECHO;dowhile(c=input()!=*)if(c=a%,如果输入的字符不是*,若小写字母则转换成大写字母输出到文件中,如果不是小写字母则原样输出,输出*,main()FILE*fp1=fopen(in.c,r);FILE*fp2=fopen(out.c,w);yyin=fp1;yyout=fp2;yylex();,细节问题,Include的位置在定义时是%而不是%Lex 的变量意义,