实验四编译用Yacc工具构造语法分析器.doc

实验4 用Yacc工具构造语法分析器
一、实验目的
掌握移进-归约技术语法分析技术，利用语法分析器生成工具Yacc/Bison实现语法分析器的构造。
二、实验内容
利用语法分析器生成工具Yacc/Bison编写一个语法分析程序，与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。
源语言的文法定义见教材附录 A.1，p394，要求实现完整的语言。
三、实验要求
１．个人完成，提交实验报告。
２．实验报告中给出采用测试源代码片断，及其对应的最右推导过程（形式可以自行考虑，如依次给出推导使用的产生式）。
例如，程序片断

四、实验思路
本次实验是一次实现词法分析和语法分析的过程，词法分析的内容与第二次实验类似，对关键词，数字，标识符以及其他类型的字符进行识别，分别返回对应的数据类型，这个过程相对来说是比较简单的，由于有特定的词法分析过程的格式，很容易将代码编写出来。语法分析的过程则给出了文法以及相应的语义动作，代码的编写相对比较复杂。
首先，在D:\FlexBison的目录下建立一个文件夹，我命名为expmt3，将bison.exe和flex.exe放到expmt3目录下。然后编写mylex.l文件和myyacc.y文件，在dos下切换到expmt3目录下，先用命令flex mylex.l生成lex.yy.c文件，再用命令bison –d myyacc.y生成myyacc.tab.c文件和myyacc.tab.h文件，在这个目录中再新建一个example.c文件，用vc++打开这个文件，然后编译这个文件，再将前两步生成的lex.yy.c、myyacc.tab.c和myyacc.tab.h文件加入到工程中，再编译并连接生成可执行文件。最后测试程序的正确性要在expmt3的debug目录下创建一个测试文件test.txt，将测试片段放入其中，然后在dos界面运行程序，知道产生正确的结果，实验就完成了。

五、具体代码
Mylex.l
%option noyywrap
%{
#include<ctype.h>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include "myYacc.tab.h"
%}
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);}
%%
Myyacc.y
%{
#include<ctype.h>
#include<stdio.h>
extern int yylex();
extern int yyerror();
%}
%token NUM
%token ID
%token IF WHILE DO BREAK REAL TRUE FALSE BASIC ELSE INDEX GE LE NE EQ AND OR
%%
program : block { printf("program-->block\n"); }
;
block : '{' decls stmts '}' { printf("block-->{decls stmts}\n"); }
;
decls :
| decls decl { printf("decls-->decls decl\n"); }
;
decl : type ID ';' { printf("decl-->type id;\n"); }
;
type : type '[' NUM ']' { printf("type-->type[num]\n"); }
| BASIC { printf("type-->basic\n"); }
;
stmts :
| stmts stmt { printf("stmts-->stmts stmt\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_stmt ELSE open_stmt { printf("open_stmt-->if(bool) matched_stmt else open_stmt\n");}
;
matched_stmt: IF '(' booL ')' matched_stmt ELSE matched_stmt { printf("matched_stmt-->if(bool) matched_stmt else matched_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"); }
| DO stmt WHILE '(' booL ')' ';' { printf("stmt-->do stmt while(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 : booL OR join { printf("bool-->bool||join\n"); }
| join { printf("bool-->join\n"); }
;
join : join AND equality { printf("join-->join&&equality\n"); }
| equality { printf("join-->equality\n"); }
;
equality : equality EQ rel { printf("equality-->equality==rel\n"); }
| equality NE rel { printf("equality-->equality!=rel\n"); }
| rel { printf("equality-->rel\n"); }
;
rel : expr '<' expr { printf("rel-->expr<expr\n"); }
| expr LE expr { printf("rel-->expr<=expr\n"); }
| expr GE expr { 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"); }
;
%%
int yyerror(s)
char *s;
{
fprintf(stderr,"syntactic error:%s\n",s);
return 0;
}

六、 实验结果

七、 实验总结
实验中的注意事项：
（1）一个由 Yacc 生成的解析器调用 yylex() 函数来获得标记。对于由 Lex 生成的 lexer 来说，要和 Yacc 结合使用，每当 Lex 中匹配一个模式时都必须返回一个标记。 因此 Lex 中匹配模式时的动作一般格式为：
{pattern} { /* do smthg*/
return TOKEN_NAME; }
于是 Yacc 就会获得返回的标记。当 Yacc 编译一个带有 _d 标记的myyacc .y文件时，会生成一个头文件myyacc.tab.h，它对每个标记都有 #define 的定义。 如果 Lex 和 Yacc 一起使用的话，头文件必须在相应的 Lex 文件mylex.l中的 C 声明段中包括。
（2）在myyacc.y中要加入对函数int yylex()和函数int yyerror()的外部声明。
（3）对文件放置的位置也要很小心，不然很容易就造成错误
（4）这次的实验使我对语法分析的过程更加了解，更多的掌握了移进——规约技术语法分析，对理论知识起到了巩固的作用，加强了编译整个理论体系的认识，也对flex &bison的操作有了更深一步的了解。