实验四用语法分析器生成工具实现语法分析器.docx
- 文档编号:10399532
- 上传时间:2023-05-25
- 格式:DOCX
- 页数:13
- 大小:151.50KB
实验四用语法分析器生成工具实现语法分析器.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文件中对于浮点数的识别还是具有一定的局限性,不能识别所有可能出现的浮点数。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 用语 分析器 生成 工具 实现 语法