Flex Bison 使用教程.docx

Flex&Bison运用教程运用说明 本文须要读者对C语言有肯定的了解作为基础 本文中所涉和的例子可以用本站供应的'全自动化MakefiIe'一文中供应的MakefilC进行编译 读者假如在1.inux1.可以干脆运用,Wind。WS用户须要CygwinO环境 本文中的工具，须要用户安装flex和bison软件包1.介谿编译器是软件开发中的核心部件，其作用是其他任何软件所不能取代的。编译器在工作过程中，往往完成如下的任务：1 .读取源代码并且获得程序的结构描述2 .分析程序结构，并且生成相应的目标代码在UNlX早期时代，编写一个编译器是一件特别耗时的工作。人们为了简化开发过程，开发了1.eX和YACe程序来解决第一个任务，依据用户描述的语审，生成能够解决问题的C/C+语言代码，供开发者运用。1 .将源代码文件分解为各种词汇（1.CX）2 .找到这些词汇的组成方式（YACC）要么是3Iabj-OZl一个带范国的字符类，符合任何满意宣，'b；从丁到'o'还有ZA-Z一个取反的字符类，比如任何字母除了大写字母。A-Znl任何字符除了大写字母和换行r*零个或更多r,r可以是随意正则表达式r+一个或更多rr?零个或最多一个rr2,5任何2到5个rr2,2个或更多rr4正好4个rname对name的扩展"xyz'foo'符合正则表达式xyz)"foo的字符串X假如X是一个'a',b,'f',宣，T,t,或者R则依据ASCn码x转义符进行处理，否则，其他的'X'将用来做取消处理符处理0一个ASCII码空字符123内容为八进制123的char型x2a内容为十六进制0x2a的char型(r)符合一个r,括号是用来越过优先级的rs正则表达式r,紧跟着一个要么是r要么是S处理，干脆进入C文件#include<stdio.h>%/词法规则段代码01234567891+printf("NUMBER");/数字类型字符申a-zA-Z+printf("WO");/单词类型字符串(WORD)printf("RD');%/协助C语言函数代码(干脆写C语言，无须括号，我们这里无内容)下面我们首先运用ICX程序生成所需的状态机代码：flex-otest.ctest.l#从正则表达式声称对应的C语言代码，留意-。后不要方空格(flexbug?)gcctest.c-otest-Ifl#从C语言代码生成二进制，从而运行，-Ifl说明链接Iibf1.a库文件./test#运行刚刚生成的二进制下面我们来对刚生成的二进制进行试枝，以弄清晰Hex究竟是做什么的，在test程序中输入以卜内容，按KCtrl-D可以退出test程序：3505hellowhatis3505通过这些试验，信任您已经明白了FleX的用途，每当一个正则表达式符合时，flex生成的代码就会自动调用对应的函数，或者运行对应的程序。卜.面我们对这个例子进行一些深化探讨，处理一个类似C语言的程序配置脚本代码。首先，一个演示脚本如下：logging;categorylame-serversnull;categorycnamenull;)；zone"."typehint;file"etcbinddb.root"在这个脚本中，我们可以看到一系列的词汇类型： 单词(WoRD),比如zone','type' 文件名O,ttretcbinddb.root, 引号(QUoTE),比如文件名两边的 左花括号QBRACE),T 右花括号(EBRACE),'分号（SEMlCo1.ON我们修改后的1.eX代码如下:%#include<stdio.h>%a-zA-Za-zA-Z0-9*printf("WORD")；/*字符串*/a-zA-Z0-9/.-+Printfr")；/*文件名*/"printf("QUOTE");/*引号"*/1Printf("OBRACE");/*左花括号7!printf("EBRACE");/*右花括号7printf("SEMICO1.ON")；/*分号711printf("n");/*换行*/ltl÷/*忽视空白字符*/%intyywra(void)/*当词法分析器到了文件末尾做什么7return1;/*返回1,说明停止前进，O则接着*/voidyyerror(char*s)/*错误信息打印函数*/fprintf(stderr,"%sn",s);returnO;intmain(intargc,char*argv)FI1.E*fp;fp=fopen(argvl1.V);*首先打开耍被处理的文件(参数1)*/yyin=fp；*yyi11是IeX默认的文件输入指针，则不处理限制台输入*/yylex();/*调用IeX的工作函数，从这里起先，Iex的词法分析器起先工作7fclose(fp);return0;到这里，我们已经完全可以对一个包含各种类型词组的源代码文件进行分析，得出其中各类型词组的排列依次。在一个规范的基于语法的源代码中，词组的依次从肯定意义上来说，就是语法。对于源代码，IeX的处理实力也就到这里为止，但是我们并没有完全展示IeX的全部功能，读者假如彳爱好，可以接着深化阅读本文提供的参考文献。如何进行语法分析？我们在卜面的章节中讲起先讲解并描述Bison的塔本运用方法，以和如何运用Bison进行语法分析。3.Bison入门3.1.基砒理论Bison采纳与YACC相同的描述语宫，这种语言是BNF语法(BaCkUSNaurForm)的一种，最早被JohnBackus和PeterNaur用于A1.GO1.60语言的开发工作。BNF语法可以用来表达与内容无关的，基于语法的语言，几乎全部的现代编程语言都可以用BNF进行描述。作为一个例子，个进行加法和乘法的数学表达式语法可以如下表达：E:E+'EE:EEE:id在这三句中，E在BiSon语言中代表表达式，一个表达式可以是一个数字,也可以是一个变量名称，也可以是儿个变量名称的组合，比如：11+2aa+b*c而以上三句Bison语言就能够表达这些语法结构32.Bison初探我们在下面作一个计算器，通过这个实例让大家明白Flex和Bison的相互关系和如何共同工作,首先，建立test211.l文件，并输入以卜.内容：/*计算器的词法分析器描述，FleX语言*/%/*干脆翻译为C语言*/include<stdlib.h>/*包含标准库文件*/voidyyerror(char*);/*这是我们上面用到的错误报告函数*/#include"test2yy.h"/*这个头文件由BiSOn自动生成*/%0-9+yylval=atoi(yytcxt);*yytext是flex内部用于指向当前词汇的字符串指针*/returnINTEGER;*INTEGER是从test2yy.h中包含过来的，在BiSon中定义*/-+nreturn*yytext;It；/*跳过空白字符*/.yyerrorC'invalidcharacter")；/*产生一个错误，说明是无效字符7%intyywrap(void)return1;*文件结束时退出*/以上就是计算器运用的FIeX语言，描述了我们将会遇到的各种词汇的格式，比如0-9+说明白，只有连续的从0'到9的字符中，才被分析为INTEGER类型，假如遇到制表符、空格等，干腌忽视，遇到加减符号则返回字符指针，其它的则报告语法错误。下面是我们的BiSOn语法文件test2yy.y:/*注：您先抄写，注解见下文7%#includc<stdio.h>intyylex(void);voidyyerror(char*);*Flex语言中INTEGER定%!%tokenINTEGER义在此7%program:programexpr'n'printf("%dn",$2);expr:INTEGER$=$1；Iexpr,+'expr1$-$1+$3;/*(1)*/expr-expr$=$1-$3;*/%voidyyerror(char*s)fprintf(stderr,'%sn",s);intmain(void)(yyparse();return0;编译过程：flex-otest211.ctest211.1bison-otest2yy.ctest2yy.y-d#留意-d,用于产生对应的头文件gcctest2yy.ctest211.c-otest2在这个例子中，我们遇到了很多没书见过的用法，BiSOn的书写格式基本与FleX的相同，只是规则的定义语法不同C其中，$N(N为数字)代表语法描述中，第N个词汇的内容，比如中的$1代表中左边的expr,$3代表右边expr的内容，其中的N是指当前语法的词汇依次，从1起先计数而$则代表这一段语法处理完后的结果，每一个语法对应的处理都有输入$N和输出$。该例子中还有一个特别的地方,就是第归调用，在Bison中，语法规则可以是第归的,这也是BiSOn之处(或者说是YACC的强大之处)。举个例子：program:programexpr,11'printf("%dn",$2);Iy这里，program的定义就是任何符合program的表达式后面紧接着CXPr和壮，扫描到该表达式后，将expr处理的结果打印到屏幕。最终的I是“或者”的意思，也就是说Program也可以是空的，什么都不写，分号代表该语义定义结束。有了第归之后，BiSon才可以说是一个能够应对任何状况的语法分析器，当然，这里还须要读者对以上所供应代码进行深化的探讨和分析，考虑清晰后，会发觉无论是C语言，还是BiSOn,第归恒久是一个奇妙的解决方案C3.3. 计算卷程序的深化探讨以匕我们设计的计算器只能进行加减计算，并且里面还方一些软件缺陷，对于一个好用的计算器来说，我们必需能够支持：1 .变量定义2 .变量赋值3 .变量与数字马上处理于是我们假想设计出来的计算器能有如下的操作过程(输入和输出)：输入：3*(4+5)结果：27输入：X=3*(4+5)输入：y=5输入：X结果：27输入：y结果：5输入：x+2*y结果：37这样看，这个计算器的功能已经相当强大了，卜.面我们着手实现，首先修改匕面例子的FIeX文件为如下：%#include<stdlib.h>voidyyerror(char*);#include"test2yy.h"%a-z)/*变量类型词汇，眼制：变量只能用一个字符*/yylval=*yytext-,a'returnVARIAB1.E;0-9+*整数7yylval=atoi(yytext);returnINTEGER;+-()=*n)return*yytext;*数学计算符号*/It；*跳过空白符号*/%intyywrap(void)(return1;5面是我们新的BiSon文件：%tokenINTEGERVARIAB1.E%left'+''-'%left'*','%voidyyerror(char*);intyylex(void);intsym(26;%program:programstatement'rfstatement:exprprintf("%dn",$1);$=sym$l;$=$1+$3;?=$1-$3;$=$1*$3;$=$1/$3;$=$2;IVARIAB1.E'=,exprexpr:INTEGERIVARIAB1.EIexpr'+'exprIexpr,-'exprIexpr'*"exprIexpr7'exprI'Cexpr'),%voidyyerror(char*s)fprintf(stderr,'%sn",s);returnO;intmain(void)yyparse();returnO;现在我们对该例子中引入的新功能介绍，%left,%right,%token都是用来声明词汇的，区分在于，tokcn声明的词汇与左右优先级无关，而left的处理时，先处理左边的，right先处理右边的，例如遇到字符串”1-2-5",究竟是处理为'(1-2)-5",还是处理为"1-(2-5)"?%left处理为前者，而right处理为后者(注：第一个计算器代码中就有这个缺陷，比如执行1-2+3,得到的结果就是-4,作为一个练习，读者可以运用这里讲解的%left自行更正)。4.Flex和Bison育级应用在卜.面的例子中，我们便写了一个更高级的计算器程序，其操作实例如卜Nx=0;vhile(x<3)rint(x);x=x+1;typcdefstructintoper;*operator*/intnops;*numberofoperands*/structnodeTypeTag*opl;*operands(expandable)*/IOprNodeType;typedefstructnodeTypeTag;nodcEnumtype;*typeofnode*/*unionmustbelastentryinnodeType*/*becauseOperNodeTypemaydynamicallyincrease*/unionConNodeTypecon;idNodcTypeid;OprNodeTypeopr;*constants*/*identifiers*/*operators*/nodeType;externintsym26;下面是FICX语软文件test311.l:%#include<stdlib.h>#include"test3.h"#include"test3yy.h"voidyyerror(char*);%a-zl1yylval.slndex=*yytext-'a'returnVARIAB1.E;0-91+yylval.iValue=atoi(yytext);returnINTEGER;-<>=+*j.return*yytext;">="returnGE;"<="return1.E;"=B,returnEQ;"!="returnNE;"while""ifreturnWHI1.E;returnIF;"else"returnE1.SE;"prinfreturnPRINT;(tn+;*ignorewhitespace*/yyerror("Unknowncharacter");%intyywrap(void)return1;然后是我们的Bison文件test3yy.y:%#include<stdio.h>#include<stdlib.h>#include<stdarg.h>#include"test3.h"*prototypes*/nodeType*opr(intoper,intnops,.);nodcType*id(inti);nodeType*con(intvalue);voidfreeNodc(nodcType*p);intyylex(void);voidyyerror(char*s);intsym26;%)%unionintiValue;*integervalue*/charslndex;*symboltableindex*/nodcType*nPtr;*nodepointer*/%token<iValue>INTEGER%token<slndcx>VARIAB1.E%tokenWHI1.EIFPRINT%nonassocIFX%nonassocE1.SE%leftGE1.EEQNE'>',<'%left'+',-'%left'*'''%nonassocUMINUS%type<nPtr>stmtexprstmtj%program:exit(O);function>function:functionstmtex($2);freeNode($2);stmt:S$=opr(;',2,NU1.1.,NU1.1.);$=opr(PRINT,1,$2);)!$=opr('<2,id($l),$3);$=opr(WHI1.E,2,$3,$5);IexprIPRINTexprIVARIAB1.E'=,exprIWHI1.E'('expr')"stmtIF'(,expr')'stmt%precIFxl$=opr(IF,2,$3,$5);IIF'('expr')'stmtE1.SEstmt$=opr(IF,3,$3,$5,$7);ITStmtJist',StmtJist:stmtIStmtJiststmt>expr:INTEGERIVARIAB1.EI'-,expr%precUMINUSIexpr,+'expr$=$1；$S=opr('',$=COn($1);$-id($l);$=opr(UMINUS,1,$2);$=opr('+',2,$1,$3);Iexpr'-,exprIexpr,*'exprIexpr,'exprIexpr'<'exprIexpr,>'exprIexprGEexprIexpr1.EexprIexprNEexprIexprEQexprI'Cexpr'),!$=opr('-,2,$1,$3);)$=opr(T2,$l,$3);!$=opr(',2,$=opr('<',2,$1,$3);!$=opr('>',2,$1,$3);$=opr(GE,2,$=opr(1.E,2,$l,$3);!$=opr(NE,2,$l,$3);$=opr(EQ,2,$l,$3);$=$2;%#dcfineSIZEOF,NODETYPE(char*)p->con-(char*)p)nodeType*con(intvalue)nodeType*p;size_tnodeSize;*allocatenode*/nodeSize=SIZEOF_NODETYPE+Sizeof(ConNodeType);returnp;nodeType*opr(intoper,intnops,.)vajistap;nodeType*p;size_tnodeSize;inti;*allocatenode*/nodeSize=SIZEOF_NODETYPE+sizeof(oprNodeType)+(nops-1)*sizeof(nodeType*);if(p=malloc(nodeSize)=NU1.1.)yyerror("outofmemory");*copyinformation*/p->type=typepr;p->opr.oper=oper;p->opr.nops=nops;va_start(ap,nops);for(i=O;i<nops;i+)p->opr.op(i=va-arg(ap,nodeTypc*);va_end(ap);returnp;voidfreeNode(nodeType*p)inti;if(!p)return;if(p->type=typepr)for(i=0;i<p->opr.nops;i+)freeNode(p->opr.opi);free(p);voidyyerror(char*s)fprintf(stdout,%sn",s);intmain(void)jyparse();returnO;上面的FICX和Bison代码所作的工作是依据语法建立语意描述树结构。持续我们上面计算器的例子，我们写出如何翻译这些语言的实现部分(对生成的树进行第归分析)：/include<stdio.h>#include"test3.h"#include"test3yy.h"intex(nodeType*p)if(!p)return0;switch(p->type)casetypeCon:returnp->con.value;casetypcld:returnsym(p->id.i;casetypcpr:switch(p->opr.oper)caseWHI1.E:while(ex(p->opr.opOJ)ex(->or.ol);return0;caseIF:if(ex(p->opr.op0)ex(->or.ol);elseif(p->opr.nops>2)ex(->or.o2);return0;casePRINT:printf("%dn",ex(p->opr.op0);return0;caseex(p->opr.op01);returnex(p->opr.opl);case'=':returnsymp->opr.op0->id.i=ex(->or.ol);caseUMINUS:return-ex(p->opr.op(0);case'+':returncx(p->opr.op(0)+ex(p->opr.opl);casereturncx(p->opr.op0)-cx(p->opr.opl);casereturnex(p->opr.op0)*ex(p->opr.opl);case',:returncx(p->opr.op(0)/ex(p->opr.opl);case,<,:returnex(p->opr.op0)<ex(p->opr.opl);case,>,:returncx(p->opr.op0)>ex(p->opr.opl);caseGE:returnex(p->opr.op0)>=ex(p->opr.opl);case1.E:returnex(p->opr.op0)<=ex(p->opr.opl);caseNE:returnex(p->opr.op0)!=ex(p->opr.opl);caseEQ:returncx(p->opr.op0)=ex(p->opr.opl);一般实际的编译器都是以汇编代码输出的，所以我们在这里进行一些深化探讨，得出了另一个版本的ex函数实现，能够实现汇编代码的输出(compiler.c):#include<stdio.h>#include"test3.h"#include"tcst3yy.h"staticintIbl;intex(nodeType*p)intlbll,lb!2;if(!p)return0;switch(p->type)casetypeCon:printf("tpusht%dn",p->con.value);break;casetypeld:printf(ntpusht%cn",p->id.i+'a');break;casetypepr:switch(p->opr.oper)caseWHI1.E:printf("1.%03d:n",Ibll=Ibl+);ex(p->opr.op0);printf("tjst1.%03dn,lbl2=Ibl+);ex(p->opr.op(l);printf("tjzt1.%03dn",lbll);printf("1.%O3d:n",lbl2);break;caseIF:ex(p->opr.op0);if(p->opr.nops>2)*ifelse*/printf("tjst1.%03dn",Ibll=Ibl+);ex(p->opr.opl);printf("tjmpt1.%03dn",lbl2=Ibl+);printf("1.%03d11lbll);ex(->or.o2);printf("1.%03d11,;lbl2);else*if7printf("tjst1.%03dn",Ibll=Ibl+);ex(p->opr.opl);printf("1.%03d:n-',lbll);break;easePRINT:ex(p->opr.op0);printf("tprintn");break;case'=,:ex(p->opr.opl);printf("tpopt%cn"fp->opr.op0->id.i+'a');break;caseUMINUS:ex(p->opr.op0);rintf("tnegn");break;default:ex(->or.o0);ex(p->opr.opl);switch(p->opr.oper)case'+,:printf("taddn");break;caseprintf("tsubn");break;case'*':printf("tmuln");break;caseprintf("tdivn");break;case'<':Printf("tcomp1.Tn");break;case'>':printf("tcompGTn");break;caseGE:printf("tcompGEn");break;case1.E:printf("tmp1.En");break;caseNE:printf("tcompNEn");break;caseEQ:printf("tcompEQn");break;return0;运用方法：取消interpreters的编译，取而代之用COmPiIer.c即可。关于这个计算器的代码分析，清等待后续，(未完待续)分考文献1. Flex手册(见manflex)2. Bison手册(见manbison)3. berthubert,1.exandYCCpromer/HOWTO,4. TomNiemann,ACompactGuideTo1.EX&YACC,epaperpress5.