4 语法分析上机

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,4,语法分析上机,语法分析器生成器,Yacc,Yacc,是一个语法分析器生成器，接受产生式表示的语法规则，生成识别产生式所描述语言的源程序，不同版本的,Yacc,支持不同的高级语言，如,C,、,C+,、,Java,等。,语法分析器,产生式,识别活前缀的,DFA,分析表,+,驱动器,人工编写,Yacc,转化,1,4,参考解决方案,利用,Yacc,构造语法分析器：,实质为如何设计产生式和语义动作,Yacc,源程序,*.y(,三段式,),：,定义,C,声明,符号定义,%,规则,语法规则产生式,语义动作,(C,代码,),%,用户子程序,C,源程序,2,2,注意：,不同版本的,Yacc,生成的文件不同,4,参考解决方案,Yacc,源程序,*.y(,三段式,),：,定义,C,声明,符号定义,%,规则,语法规则产生式,语义动作,(C,代码,),%,用户子程序,C,源程序,y.tab.c,结构：,(1),声明的,C,语言部分,(2),语法分析表,(3),语法分析驱动器,(,yyparser,(),(4),用户定义子程序,3,4,参考解决方案,实例,2,：算术运算表达式识别器,仅使用,Yacc,基本步骤：,使用,Parser Generator,创建一个工程,calc,编写,y,文件,myparser.y,；,编译,myparser.y,，生成,myparser.h,与,myparser.c,；,使用,VC+,创建,Win32 Console Application,工程,calc,配置该项目；,加入,myparser.h,与,myparser.c,，编译工程；,执行算术运算表达式识别器,；,注意：,每次修改,y,文件后，需要重新编译,y,文件，再重新编译,VC,工程,4,4,参考解决方案,myparser.y,源代码：,%,#include,%,%token NUMBER/,无优先级与结合性,%left+,-/,低优先级与左结合,%left*,/,高优先级与左结合,%,expr,:,expr,+,expr,printf,(,识别加法,!n);,|,expr,-,expr,printf,(,识别减法,!n);,|,expr,*,expr,printf,(,识别乘法,!n);,|,expr,/,expr,printf,(,识别除法,!n);,|(,expr,),printf,(,识别括号,!n);,|NUMBER,printf,(,识别数字,!n);,;,5,/C,声明,/,符号定义,%,token,%left,说明对应,实例,1,中的,define,/,语法规则产生式,/,语义动作,4,参考解决方案,%,int,main(void,),return,yyparse,();,int,yylex(void,),int,c;,while(c=,getchar,()=);/,过滤空格,if(,isdigit(c,)/,判断是否是数字,ungetc(c,stdin,);,scanf(%d,&,yylval,);,return NUMBER;,if(c=n)return 0;/,回车返回,0,，代表词法分析器读取完毕,return c;,6,/C,源程序,yyparse,(),：,yacc,自动生成的语法分析驱动器，根据语法规则进行自下而上分析（调用,yylex,进行词法分析），同时执行语义动作。,yylex,(),：用户自定义的词法分析驱动器。,yylval,：全局变量，用来存放识别出的输入序列。,4,参考解决方案,执行结果：每次输入一个算术运算表达式，输出分析结果,7,注意：,Yacc,自动调用,yylex,(),返回一个记号,4,参考解决方案,实例,3,：算术运算表达式识别器,同时使用,Lex,与,Yacc,基本步骤：,使用,Parser Generator,创建一个工程,calc2,编写,l,文件,mylexer.l,;,编写,y,文件,myparser.y,；,编译,mylexer.l,，生成,mylexer.h,与,mylexer.c,；,编译,myparser.y,，生成,myparser.h,与,myparser.c,；,使用,VC+,创建,Win32 Console Application,工程,calc2,配置该项目；,加入,mylexer.h,与,mylexer.c,，,myparser.h,与,myparser.c,，编译工程；,执行算术运算表达式识别器,；,注意：,每次修改,l,、,y,文件后，需要重新编译,l,、,y,文件，再重新编译,VC,工程,8,4,参考解决方案,mylexer.l,主要源代码：,digit0-9,digitsdigit+,optional_fraction,(.digits)?,optional_exponent,(E+-?digits)?,%,+;,/,过滤空格,digitsoptional_fractionoptional_exponent,return NUMBER;,+return+;,-return-;,*return*;,/return/;,(return(;,)return);,n return 0;,/,回车返回,0,，代表词法分析器读取完毕,9,4,参考解决方案,mylexer.y,主要源代码：,%token NUMBER/,无优先级与结合性,%left+,-/,低优先级与左结合,%left*,/,高优先级与左结合,%,expr,:,expr,+,expr,printf,(,识别加法,!n);,|,expr,-,expr,printf,(,识别减法,!n);,|,expr,*,expr,printf,(,识别乘法,!n);,|,expr,/,expr,printf,(,识别除法,!n);,|(,expr,),printf,(,识别括号,!n);,|NUMBER,printf,(,识别数字,!n);,;,%,int,main(void,),return,yyparse,();,10,/,符号定义,%,token,%left,说明对应,实例,1,中的,define,4,参考解决方案,执行结果：每次输入一个算术运算表达式，输出分析结果,11,注意：,Yacc,自动调用,Lex,返回一个记号,