实验四用语法分析器生成工具实现语法分析器.docx
《实验四用语法分析器生成工具实现语法分析器.docx》由会员分享,可在线阅读,更多相关《实验四用语法分析器生成工具实现语法分析器.docx(13页珍藏版)》请在冰点文库上搜索。
实验四用语法分析器生成工具实现语法分析器
魏陈强23020092204168
实验4用语法分析器生成工具实现语法分析器
一、实验目的
掌握移进-归约技术语法分析技术,利用语法分析器生成工具Yacc/Bison实现语法分析器的构造。
二、实验内容
利用语法分析器生成工具Yacc/Bison编写一个语法分析程序,与词法分析器结合,能够根据语言的上下文无关文法,识别输入的单词序列是否文法的句子。
源语言的文法定义见教材附录A.1,p394,要求实现完整的语言。
三、实验要求
1.个人完成,提交实验报告。
2.实验报告中给出采用测试源代码片断,及其对应的最右推导过程(形式可以自行考虑)。
例如,程序片断
四、实验思路
本实验在linux环境下编写。
首先使用lex工具,编写词法分析器,对于识别出的token,比如id类的,则return(ID);单个字符的,比如‘>’,则return(‘>’),其他类似。
然后生成lex.yy.c文件。
接着使用yacc工具,编写语法分析器,在*.y文件中调用#include”lex.yy.c”,main(intargc,char**argv)函数中调用yyparse(),并给出yyerror()的处理方式。
这样,就能将lex和yacc结合起来。
生成y.tab.c文件后,gcc编译,生成a.out可执行文件。
执行./a.out<1.txt,即可对1.txt文档中的程序进行语法分析。
五、详细代码
1)lex.l
%optionnoyywrap
%{
#include
#include
#include
#include
%}
delim[\t\n]
ws{delim}+
letter[A-Za-z]
digit[0-9]
%%
{ws}{}
"if"{printf("IF");return(IF);}
"else"{printf("ELSE");return(ELSE);}
"int"{printf("INT");return(BASIC);}
"float"{printf("FLOAT");return(BASIC);}
"break"{printf("BREAK");return(BREAK);}
"do"{printf("DO");return(DO);}
"while"{printf("WHILE");return(WHILE);}
"true"{printf("TRUE");return(TRUE);}
"index"{printf("INDEX");return(INDEX);}
"bool"{printf("BOOL");return(BASIC);}
"char"{printf("CHAR");return(BASIC);}
"real"{printf("real");return(REAL);}
"false"{printf("FLASE");return(FALSE);}
[a-zA-Z_][a-zA-Z0-9_]*{printf("ID");return(ID);}
[+-]?
[0-9]+{printf("NUM");return(NUM);}
[+-]?
[0-9]*[.][0-9]+{printf("NUM");return(NUM);}
"<"{printf("LT");return('<');}
"<="{printf("LE");return(LE);}
"="{printf("=");return('=');}
"=="{printf("EQ");return(EQ);}
"!
="{printf("NE");return(NE);}
">"{printf("GT");return('>');}
">="{printf("GE");return(GE);}
"+"{printf("+");return('+');}
"-"{printf("-");return('-');}
"["{printf("[");return('[');}
"]"{printf("]");return(']');}
"{"{printf("{");return('{');}
"}"{printf("}");return('}');}
"("{printf("(");return('(');}
")"{printf(")");return(')');}
";"{printf(";");return(';');}
","{printf(",");return(',');}
"&&"{printf("&&");return(AND);}
"||"{printf("||");return(OR);}
%%
2)yacc.y
%{
#include
#include
%}
%tokenNUM
%tokenID
%tokenIFWHILEDOBREAKREALTRUEFALSEBASICELSEINDEXGELENEEQANDOR
%%
program:
block{printf("program-->block\n");}
;
block:
'{'declsstmts'}'{printf("block-->{declsstmts}\n");}
;
decls:
|declsdecl{printf("decls-->declsdecl\n");}
;
decl:
typeID';'{printf("decl-->typeid;\n");}
;
type:
type'['NUM']'{printf("type-->type[num]\n");}
|BASIC{printf("type-->basic\n");}
;
stmts:
|stmtsstmt{printf("stmts-->stmtsstmt\n");}
;
stmt:
matched_stmt{printf("stmt-->matched_stmt\n");}
|open_stmt{printf("stmt-->open_stmt\n");}
;
open_stmt:
IF'('booL')'stmt{printf("open_stmt-->if(bool)stmt\n");}
|IF'('booL')'matched_stmtELSEopen_stmt{printf("open_stmt-->if(bool)matched_stmtelseopen_stmt\n");}
;
matched_stmt:
IF'('booL')'matched_stmtELSEmatched_stmt{printf("matched_stmt-->if(bool)matched_stmtelsematched_stmt\n");}
|other{printf("matched_stmt-->other\n");}
;
other:
loc'='booL';'{printf("stmt-->loc=bool;\n");}
|WHILE'('booL')'stmt{printf("stmt-->while(bool)stmt\n");}
|DOstmtWHILE'('booL')'';'{printf("stmt-->dostmtwhile(bool);\n");}
|BREAK';'{printf("stmt-->break;\n");}
|block{printf("stmt-->block\n");}
;
loc:
loc'['booL']'{printf("loc-->loc[bool]\n");}
|ID{printf("loc-->id\n");}
;
booL:
booLORjoin{printf("bool-->bool||join\n");}
|join{printf("bool-->join\n");}
;
join:
joinANDequality{printf("join-->join&&equality\n");}
|equality{printf("join-->equality\n");}
;
equality:
equalityEQrel{printf("equality-->equality==rel\n");}
|equalityNErel{printf("equality-->equality!
=rel\n");}
|rel{printf("equality-->rel\n");}
;
rel:
expr'<'expr{printf("rel-->expr|exprLEexpr{printf("rel-->expr<=expr\n");}
|exprGEexpr{printf("rel-->expr>=expr\n");}
|expr'>'expr{printf("rel-->expr>expr\n");}
|expr{printf("rel-->expr\n");}
;
expr:
expr'+'term{printf("expr-->expr+term\n");}
|expr'-'term{printf("expr-->expr-term\n");}
|term{printf("expr-->term\n");}
;
term:
term'*'unary{printf("term-->term*unary\n");}
|term'/'unary{printf("term-->term/unary\n");}
|unary{printf("term-->unary\n");}
;
unary:
'!
'unary{printf("unary-->!
unary\n");}
|'-'unary{printf("unary-->-unary\n");}
|factor{printf("unary-->factor\n");}
;
factor:
'('booL')'{printf("factor-->(bool)\n");}
|loc{printf("factor-->loc\n");}
|NUM{printf("factor-->num\n");}
|REAL{printf("factor-->real\n");}
|TRUE{printf("factor-->true\n");}
|FALSE{printf("factor-->false\n");}
;
%%
#include"lex.yy.c"
main(intargc,char**argv)
{
yyparse();
}
yyerror(char*s)
{
fprintf(stderr,"error:
%s\n",s);
}
六、实验结果
Lex.l词法分析结果:
Yacc.y语法分析结果:
…..
…..
…..
七、实验总结
遇到的问题1):
刚开始在window环境下使用lex和yacc工具,编写lex.l文件的时候,在识别到if时,return(IF),提示IF没有定义,定义#defineIF265后,在yacc.y文件中,再定义%tokenIF,发生重定义错误。
解决办法:
在lex.l文件中,无须定义#defineIF265,只在yacc.y文件中定义%tokenIF即可,不过在yacc.y中要加入#include”lex.yy.c”,使两个文件关联起来。
遇到的问题2):
在使用yacc工具编译yacc.y文件时,提示缺少bison.simple。
解决办法:
上网下载一个bison.simple,放到yacc工具主目录下。
遇到的问题3):
在lex.l和yacc.y文件的第三部分同时写了main函数,导致错误。
解决办法:
Lex.l文件中第三部分为空,不需要任何函数。
因为关联lex.l和yacc.y后,yyparse()会自动调用yylex()。
遇到的问题4):
生成yacc.tab.c文件后,放入VC++编译器中编译,提示错误如下:
errorLNK2001:
unresolvedexternalsymbol_yyerror
Debug/main.exe:
fatalerrorLNK1120:
1unresolvedexternals
解决办法:
未找到解决办法,无奈只能放弃window环境,改用linux环境编写。
遇到的问题5):
IF'('bool')'stmt{printf("stmt--if(bool)stmt\n");}
IF'('bool')'stmtELSEstmt{printf("stmt-->if(bool)stmtelsestmt\n");}
存在冲突。
解决办法:
改为:
stmt:
matched_stmt{printf("stmt-->matched_stmt\n");}
|open_stmt{printf("stmt-->open_stmt\n");}
;
open_stmt:
IF'('booL')'stmt{printf("open_stmt-->if(bool)stmt\n");}
|IF'('booL')'matched_stmtELSEopen_stmt{printf("open_stmt-->if(bool)matched_stmtelseopen_stmt\n");}
;
matched_stmt:
IF'('booL')'matched_stmtELSEmatched_stmt{printf("matched_stmt-->if(bool)matched_stmtelsematched_stmt\n");}
|other{printf("matched_stmt-->other\n");}
遇到的问题6):
这是一个致命性的问题,由于使用的linux下的lex版本太低,导致照抄课本上的ID和NUM正则表达式无法识别,困扰了我很久很久。
解决办法:
多亏了朋友的帮助,终于发现错误,把{letter}({letter}|{digit})*改为[a-zA-Z_][a-zA-Z0-9_]*;把{digit}+(\.{digit}+)?
(E[+-]?
{digit}+)?
改为[+-]?
[0-9]+和[+-]?
[0-9]*[.][0-9]+,分别用于识别整数和浮点数。
遇到的问题7):
一些小错误,比如词法分析中,漏识别while等,还有把‘=’误当做了EQ。
解决办法:
仔细检查lex.l,对错漏的部分进行改补。
遇到的问题8):
对IF和IFELSE消除二义性后,依然存在冲突如下:
解决办法:
尚未找到解决办法。
本次实验主要是学习结合lex和yacc工具进行语法分析,通过工具文档,了解lex和yacc的编写规则,然后使用教程后的源语言定义规则,即语法分析的各个文法即可编写出正确的yacc.y。
在linux下使用lex和yacc比较容易,而在window下使用,就相对麻烦,会遇到的各种问题,所以该实验选用linux环境是不二选择。
其次,linux环境可能存在lex和yacc的版本比较低,导致一些教程上的一些正则表达式无法识别,这个错误比较难发现。
总之,通过本次实验,用了近一天的时间调试程序,对词法分析和语法分析有了进一步的认识,同时对程序纠错有了进一步的体会,再者更加熟悉了linux环境操作,更加体会到了linux功能的强大。
但本实验还有一些令人不太满意的地方,比如*.y文件中依然存在冲突没有解决彻底,而且*.l文件中对于浮点数的识别还是具有一定的局限性,不能识别所有可能出现的浮点数。