实验Yacc与Lex快速入门

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,39,编译原理电子教案,韶关学院计算机系程细柱,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),LEX,YACC,代码产生支撑函数,实验工具简介总揽(2/2),实验工具简介-LEX,Lex：一个词汇分析器生成器,。,当 Lex 接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。它一次读入一个输入字符，直到找到一个匹配的模式。如果能够,找到一个匹配的模式,，Lex,就执行相关的动作,（可能包括返回一个标记）。另一方面，如果,没有,可以匹配的常规表达式，将会,停止,进一步的处理，Lex 将,显示一个错误消息,。,程序有三个部分，用,%,符号隔开。,第一部分和最后一个部分,是普通而,古老的 C 代码,。,中间,是有趣的一部分。它,由一系列规则构成,，lex 将这些规则翻译为词汇分析器。每一个规则依次包含一个正则表达式以及该正则表达式得到匹配时要运行的一些代码。任何没有得到匹配的文本则简单地拷贝到标准输出。,Lex 的常规表达式（1）,字符,含义,A-Z, 0-9, a-z,构成了部分模式的字符和数字。,.,匹配任意字符，除了 n。,-,用来指定范围。例如：A-Z 指从 A 到 Z 之间的所有字符。, ,一个字符集合。匹配括号内的,任意,字符。如果第一个字符是 那么它表示否定模式。例如：abC 匹配 a, b 和 C中的任何一个。,*,匹配,0个,或者多个上述的模式。,+,匹配,1个,或者多个上述模式。,?,匹配,0个或1个,上述模式。,$,作为模式的最后一个字符匹配一行的结尾。,Lex 的常规表达式（2）,字符,含义, ,指出一个模式可能出现的次数。 例如：A1,3 表示 A 可能出现1次或3次。,用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义，只取字符的本意。,否定。,|,表达式间的逻辑或。,字符的字面含义。元字符具有。,/,向前匹配。如果在匹配的模版中的“/”后跟有后续表达式，只匹配模版中“/”前面的部分。如：如果输入 A01，那么在模版 A0/1 中的 A0 是匹配的。,( ),将一系列常规表达式分组。,常规表达式举例,常规表达式,含义,jokers,匹配 jokes 或 joker。,A1,2shis+,匹配 AAshis, Ashis, Ashiss, Ashisss。,(Ab-e)+,匹配在 A 出现位置后跟随的从 b 到 e 的所有字符中的 1 个或 多个。,标记声明举例,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 有几个函数和变量提供了不同的信息，可以用来编译实现复杂函数的程序。下表中列出了一些变量和函数，以及它们的使用。,yyin,FILE* 类型。 它指向 lexer 正在解析的当前文件。,yyout,FILE* 类型。 它指向记录 lexer 输出的位置。 缺省情况下，yyin 和 yyout 都指向标准输入和输出。,yytext,匹配模式的文本存储在这一变量中（char*）。,yyleng,给出匹配模式的长度。,yylineno,提供当前的行数信息。（lexer不一定支持。）,Lex 函数,yylex(),这一函数开始分析。 它由 Lex 自动生成。,yywrap(),这一函数在文件（或输入）的末尾调用。如果函数的返回值是1，就停止解析。 因此它可以用来解析多个文件。代码可以写在第三段，这就能够解析多个文件。 方法是使用 yyin 文件指针（见上表）指向不同的文件，直到所有的文件都被解析。最后，yywrap() 可以返回 1 来表示解析的结束。,yyless(int n),这一函数可以用来送回除了前n 个字符外的所有读出标记。,yymore(),这一函数告诉 Lexer 将下一个标记附加到当前标记后。,例：识别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*,%,“ “ 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”,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;,%,int yywrap(),return 1;,实验工具简介-YACC,yacc：另一个编译器的编译器,将输入拆分为一连串的记号。现在您需要一些方法来识别高层次的模式。这就是 yacc 要做的：yacc 让您可以描述希望怎样处理记号。,1,.,E - E + E,2. E - E * E,3. 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 的字符串常量相同。例如，=a,else putc( c ,yyout) ;,putc(c,yyout);,while(c=input( ) = * ),putc( c,yyout ) ;,if(c=a,else putc( c,yyout ) ;,if (c = /) done = TRUE;, while (!done);,%,如果输入的字符不是*,若小写字母则,转换成大写字母输出到文件中,如果不是小写字母则原样输出,输出*,main(),FILE *fp1=fopen(in.c,r);,FILE *fp2=fopen(out.c,w);,yyin=fp1;,yyout=fp2;,yylex();,细节问题,Include的位置,在定义时是,%,%,而不是,%, %,Lex 的变量意义,