龙华网站开发公司电话,网络公司名字怎么取,网站备案幕布大小,蝙蝠侠seoHNU编译原理lab2实验–在 Lab1 已完成的 flex 词法分析器的基础上#xff0c;进一步使用 bison 完成语法分析器。也就是补全两个文件。#xff08;其实我也是抄的#xff0c;什么也不会 .#xff09;
本文没有添加任何图片#xff0c;但是以复制输出的形式展现出…HNU编译原理lab2实验–在 Lab1 已完成的 flex 词法分析器的基础上进一步使用 bison 完成语法分析器。也就是补全两个文件。其实我也是抄的什么也不会 .
本文没有添加任何图片但是以复制输出的形式展现出来了实验结果。
实验要求
本次实验需要各位同学首先将自己的 lab1 的词法部分复制到 /src/parser 目录的 lexical_analyzer.l并合理修改相应部分然后根据 cminus-f 的语法补全 syntax_analyer.y 文件完成语法分析器要求最终能够输出解析树。如 输入
int bar;
float foo(void) { return 1.0; }则 parser 将输出如下解析树
-- program
| -- declaration-list
| | -- declaration-list
| | | -- declaration
| | | | -- var-declaration
| | | | | -- type-specifier
| | | | | | --* int
| | | | | --* bar
| | | | | --* ;
| | -- declaration
| | | -- fun-declaration
| | | | -- type-specifier
| | | | | --* float
| | | | --* foo
| | | | --* (
| | | | -- params
| | | | | --* void
| | | | --* )
| | | | -- compound-stmt
| | | | | --* {
| | | | | -- local-declarations
| | | | | | --* epsilon
| | | | | -- statement-list
| | | | | | -- statement-list
| | | | | | | --* epsilon
| | | | | | -- statement
| | | | | | | -- return-stmt
| | | | | | | | --* return
| | | | | | | | -- expression
| | | | | | | | | -- simple-expression
| | | | | | | | | | -- additive-expression
| | | | | | | | | | | -- term
| | | | | | | | | | | | -- factor
| | | | | | | | | | | | | -- float
| | | | | | | | | | | | | | --* 1.0
| | | | | | | | --* ;
| | | | | --* }
请注意上述解析树含有每个解析规则的所有子成分包括诸如 ; { } 这样的符号请在编写规则时务必不要忘了它们。
实验难点
掌握flex和bison的基本原理和使用方法怎么将文法产生式转换为bison语句如何联合flex和bison了解bison源程序的写法熟悉语法分析器的工作流程看懂yylval.node的含义
实验设计
bisonn源程序的写法
bison 是一个语法分析器的生成器网址为http://www.delorie.com/gnu/docs/bison/bison_toc.html。 bison 和 flex 配合使用它可以将用户提供的语法规则转化成一个语法分析器。简单来说从语法的产生式开始通过一系列的复杂的构造流程最终得到了一个动作表然后又利用这个动作表去解析句子。 bison 就是干这个事情的它读取用户提供的语法的产生式生成一个 C 语言格式的 LALR(1) 动作表并将其包含进一个名为 yyparse 的 C 函数这个函数的作用就是利用这个动作表来解析 token stream 而这个 token stream 是由 flex 生成的词法分析器扫描源程序得到。 bison 的自定义语法文件的格式和 flex 分词模式文件的格式非常相似共分为 4 段如下
%{ Declarations %}
Definitions
%%
Productions
%%
User subroutines其中的 Declarations 段和 User subroutines 和 flex 文件中是一样的 bison 会将这些代码原样的拷贝到 y.tab.c 文件中 Definitions 段和 flex 中的功能也差不多也是在这个段定义一些 bison 专有的变量稍后再解释这个文件中的这个段里的代码最重要的是 Productions 段这里面是用户编写的语法产生式比如以下定义的产生式用常规的方式书写的格式如下
S : S E \n { printf(ans %d\n, $2); } | /* empty */ { /* empty */ } ;
E : E E { $$ $1 $3; } | E - E { $$ $1 - $3; } | E * E { $$ $1 * $3; } | E / E { $$ $1 / $3; } | T_NUM { $$ $1; } | ( E ) { $$ $2; }
S - S E \n | ε
E - E E | E - E | E * E | E / E | T_NUM | ( E )bison 里面 ”:” 代表一个 “-” 同一个非终结符的不同产生式用 “|” 隔开用 ”;” 结束表示一个非终结符产生式的结束每条产生式的后面花括号内是一段 C 代码、这些代码将在该产生式被应用时执行这些代码被称为 action 产生式的中间以及 C 代码内部可以插入注释产生式右边是 ε 时不需要写任何符号一般用一个注释 /* empty */ 代替。
补齐lexical_analyzer.l文件
根据样例的修改参考
/* Example for you :-) */
\ { pos_start pos_end; pos_end 1; pass_node(yytext); return ADD; }post_start和post_end等部分不变然后添加pass_node函数观察到pass_node函数这个函数用于flex和bison之间的协作。 yytest是匹配到正则表达式的那转字符串 这里对yylval进行了复制yylval的类型是接下来要补充的union用来记录token的内容。 所以在词法分析中每个token匹配时都需要在原基础上添加一句 pass_node(yytext) 相当于在语法 分析树中创建了一个新的语法单元节点。 但是因为语法分析树不考虑制表符TAB注释COMMENT换行EOL以及空格BLANK所以不用建立节点但仍需要读取识别故保持原有的正则表达式以及 pos_start、pos_end 等的代码但删去return 代码即不返回仅读取识别也不添加 pass_node因为无需建立节点也无需传到 bison 中。 对于语法错误的直接return ERROR即可。
void pass_node(char *text){yylval.node new_syntax_tree_node(text);
}因此词法分析部分修改增加为
/***************TO STUDENTS: Copy your Lab1 here. Make adjustments if necessary.*/
%%
\ { pos_start pos_end; pos_end 1; pass_node(yytext); return ADD; }
\- { pos_start pos_end;pos_end; pass_node(yytext); return SUB;}
\* { pos_start pos_end;pos_end; pass_node(yytext); return MUL;}
\/ { pos_start pos_end;pos_end; pass_node(yytext); return DIV;}
\ { pos_start pos_end;pos_end; pass_node(yytext); return LT;}
\\ { pos_start pos_end;pos_end 2; pass_node(yytext); return LTE;}
\ { pos_start pos_end;pos_end; pass_node(yytext); return GT;}
\\ { pos_start pos_end;pos_end 2; pass_node(yytext); return GTE;}
\\ { pos_start pos_end;pos_end 2; pass_node(yytext); return EQ;}
\!\ { pos_start pos_end;pos_end 2; pass_node(yytext); return NEQ;}
\ { pos_start pos_end;pos_end; pass_node(yytext); return ASSIN;}
\; { pos_start pos_end;pos_end; pass_node(yytext); return SEMICOLON;}
\, { pos_start pos_end;pos_end; pass_node(yytext); return COMMA;}
\( { pos_start pos_end;pos_end; pass_node(yytext); return LPARENTHESE;}
\) { pos_start pos_end;pos_end; pass_node(yytext); return RPARENTHESE;}
\[ { pos_start pos_end;pos_end; pass_node(yytext); return LBRACKET;}
\] { pos_start pos_end;pos_end; pass_node(yytext); return RBRACKET;}
\{ { pos_start pos_end;pos_end; pass_node(yytext); return LBRACE;}
\} { pos_start pos_end;pos_end; pass_node(yytext); return RBRACE;}
else { pos_start pos_end;pos_end 4; pass_node(yytext); return ELSE;}
if { pos_start pos_end;pos_end 2; pass_node(yytext); return IF;}
int { pos_start pos_end;pos_end 3; pass_node(yytext); return INT;}
float { pos_start pos_end;pos_end 5; pass_node(yytext); return FLOAT;}
return { pos_start pos_end;pos_end 6; pass_node(yytext); return RETURN;}
void { pos_start pos_end;pos_end 4; pass_node(yytext); return VOID;}
while { pos_start pos_end;pos_end 5; pass_node(yytext); return WHILE;}[a-zA-Z] { pos_start pos_end;pos_end strlen(yytext); pass_node(yytext); return IDENTIFIER;}
[0-9] { pos_start pos_end;pos_end strlen(yytext); pass_node(yytext); return INTEGER;}
[0-9]\.|[0-9]*\.[0-9] { pos_start pos_end;pos_end strlen(yytext); pass_node(yytext); return FLOATPOINT;}
\[\] { pos_start pos_end;pos_end 2; pass_node(yytext); return ARRAY;}
[a-zA-Z] { pos_start pos_end;pos_end; pass_node(yytext); return LETTER;}
[\n] { pos_start 1;pos_end 1;lines;}
\/\*([*]*(([^*/])([/])*)*)*\*\/ {}
[ \f\n\r\t\v] { pos_end;pos_start pos_end;}%%
/*Note: dont modify the prologue unless you know what you are doing.
***************/补全syntax_analyer.y文件
先考虑%union因为在语法树上每个节点都对应一个语义值这个值的类型是 YYSTYPE。YYSTYPE 的具体内容是由 %union 构造指出的。如图所示不管是%token还是%type都应该是syntax_tree_node * node类型这样才能构建解析树。
/* TODO: Complete this definition. */
%union {syntax_tree_node * node;}根据lexical_analyzer.l中的token定义%tokennode ,以及lab2的要求定义%typenode。
/* TODO: Your tokens here. */
%token node ADD SUB MUL DIV LT LTE GT GTE EQ NEQ ASSINSEMICOLON COMMA LPARENTHESE RPARENTHESE LBRACKET RBRACKETLBRACE RBRACE ELSE IF INT FLOAT RETURN VOID WHILEIDENTIFIER INTEGER FLOATPOINT ARRAY LETTER%type node program declaration-list declaration var-declarationtype-specifier fun-declaration params param-list paramcompound-stmt local-declarations statement-liststatement expression-stmt selection-stmt iteration-stmtreturn-stmt expression var simple-expression relopadditive-expression addop term mulop factor integer float callargs arg-list%start program
%%根据实验中所给的Cminus-f语法补充每个%typenode的文法解析。 注意的是每个条文法解析后面都要有分号除了本身给出的第一条{}里写与该解析对应的处理代码。例如declaration-list ,其第一条解析所得到的是两个解析符号declaration-list declaration所以对于该解析要执行的操作是
program : declaration-list
{ $$ node(program, 1, $1); gt-root $$; }再查看 node 函数的函数原型syntax_tree_node *node(const char node_name, int children_num, …)结合实验资料 README.md 中对于 bison 语法的介绍可以看出 program 为语法分析的起始该结点类型为 syntax_tree_node。 KaTeX parse error: Cant use function $ in math mode at position 23: …(program, 1, $̲1)表示为当前识别到的 pro…将 program 结点作为根节点使其作为语法分析树的起始。 因此可以看出对于语法的分析结构应该为如下的形式
parent : son { $$ node(parent, 1, $1);}| daughter { $$ node(parent, 1, $1);}| son AND daughter { $$ node(parent, 3, $1, $2, $3);}其中 parent、son、daughter 都是 syntax_tree_node* 类型都为非终结符AND 也是 syntax_tree_node* 类型为终结符。
再结合token和Cminus-f语法补全剩下的代码
/* TODO: Your rules here. */
program : declaration-list { $$ node(program, 1, $1); gt-root $$; }declaration-list : declaration-list declaration { $$ node(declaration-list, 2, $1, $2);}| declaration { $$ node(declaration-list, 1, $1); }declaration : var-declaration { $$ node(declaration, 1, $1); }| fun-declaration { $$ node(declaration, 1, $1); }var-declaration : type-specifier IDENTIFIER SEMICOLON { $$ node(var-declaration, 3, $1, $2, $3); }| type-specifier IDENTIFIER LBRACKET INTEGER RBRACKET SEMICOLON { $$ node(var-declaration, 6, $1, $2, $3, $4, $5, $6); }type-specifier : INT { $$ node(type-specifier, 1, $1); }| FLOAT { $$ node(type-specifier, 1, $1); }| VOID { $$ node(type-specifier, 1, $1); }fun-declaration : type-specifier IDENTIFIER LPARENTHESE params RPARENTHESE compound-stmt { $$ node(fun-declaration, 6, $1, $2, $3, $4, $5, $6); }params : param-list { $$ node(params, 1, $1); }| VOID { $$ node(params, 1, $1); }param-list : param-list COMMA param { $$ node(param-list, 3, $1, $2, $3); }| param { $$ node(param-list, 1, $1); }param : type-specifier IDENTIFIER { $$ node(param, 2, $1, $2); }| type-specifier IDENTIFIER ARRAY { $$ node(param, 3, $1, $2, $3); }compound-stmt : LBRACE local-declarations statement-list RBRACE { $$ node(compound-stmt, 4, $1, $2, $3, $4); }local-declarations : { $$ node(local-declarations, 0); }| local-declarations var-declaration { $$ node(local-declarations, 2, $1, $2); }statement-list : { $$ node(statement-list, 0); }| statement-list statement { $$ node(statement-list, 2, $1, $2); }statement : expression-stmt { $$ node(statement, 1, $1); }| compound-stmt { $$ node(statement, 1, $1); }| selection-stmt { $$ node(statement, 1, $1); }| iteration-stmt { $$ node(statement, 1, $1); }| return-stmt { $$ node(statement, 1, $1); }expression-stmt : expression SEMICOLON { $$ node(expression-stmt, 2, $1, $2); }| SEMICOLON { $$ node(expression-stmt, 1, $1); }selection-stmt : IF LPARENTHESE expression RPARENTHESE statement { $$ node(selection-stmt, 5, $1, $2, $3, $4, $5); }| IF LPARENTHESE expression RPARENTHESE statement ELSE statement { $$ node(selection-stmt, 7, $1, $2, $3, $4, $5, $6, $7); }iteration-stmt : WHILE LPARENTHESE expression RPARENTHESE statement { $$ node(iteration-stmt, 5, $1, $2, $3, $4, $5); }return-stmt : RETURN SEMICOLON { $$ node(return-stmt, 2, $1, $2); }| RETURN expression SEMICOLON { $$ node(return-stmt, 3, $1, $2, $3); }expression : var ASSIN expression { $$ node(expression, 3, $1, $2, $3); }| simple-expression { $$ node(expression, 1, $1); }var : IDENTIFIER { $$ node(var, 1, $1); }| IDENTIFIER LBRACKET expression RBRACKET { $$ node(var, 4, $1, $2, $3, $4); }simple-expression : additive-expression relop additive-expression { $$ node(simple-expression, 3, $1, $2, $3); }| additive-expression { $$ node(simple-expression, 1, $1); }relop : LTE { $$ node(relop, 1, $1); }| LT { $$ node(relop, 1, $1); }| GT { $$ node(relop, 1, $1); }| GTE { $$ node(relop, 1, $1); }| EQ { $$ node(relop, 1, $1); }| NEQ { $$ node(relop, 1, $1); }additive-expression : additive-expression addop term { $$ node(additive-expression, 3, $1, $2, $3); }| term { $$ node(additive-expression, 1, $1); }addop : ADD { $$ node(addop, 1, $1); }| SUB { $$ node(addop, 1, $1); }term : term mulop factor { $$ node(term, 3, $1, $2, $3); }| factor { $$ node(term, 1, $1); }mulop : MUL { $$ node(mulop, 1, $1); }| DIV { $$ node(mulop, 1, $1); }factor : LPARENTHESE expression RPARENTHESE { $$ node(factor, 3, $1, $2, $3); }| var { $$ node(factor, 1, $1); }| call { $$ node(factor, 1, $1); }| integer { $$ node(factor, 1, $1); }| float { $$ node(factor, 1, $1); }integer : INTEGER { $$ node(integer, 1, $1); }float : FLOATPOINT { $$ node(float, 1, $1); }call : IDENTIFIER LPARENTHESE args RPARENTHESE { $$ node(call, 4, $1, $2, $3, $4); }args : { $$ node(args, 0); }| arg-list { $$ node(args, 1, $1); }arg-list : arg-list COMMA expression { $$ node(arg-list, 3, $1, $2, $3); }| expression { $$ node(arg-list, 1, $1); }%%在编译的过程中发现yyin变量未声明。经过查找对应资料后对 yyin 添加声明extern FILE *yyin;。再次编译成功编译。
实验结果及验证
编译过程与lab1的编译过程相同
make build
cd build
cmake ../
make parser输入指令 make parser
sunny2004sunny2004-VirtualBox:~/lab1/cminus_compiler-2023-fall$ cd build
sunny2004sunny2004-VirtualBox:~/lab1/cminus_compiler-2023-fall/build$ make parser
[ 36%] Built target common
[ 81%] Built target syntax
[100%] Built target parser
sunny2004sunny2004-VirtualBox:~/lab1/cminus_compiler-2023-fall/build$
![[Snipaste_2023-11-23_13-59-55.png]] 运行灵活使用重定向输入
cd cminus_compiler-2023-fall
./build/parser # 交互式使用不进行输入重定向
在这里输入 Cminus-f 代码如果遇到了错误将程序将报错并退出。
输入完成后按 ^D 结束输入此时程序将输出解析树。
./build/parser test.cminus # 重定向标准输入
此时程序从 test.cminus 文件中读取输入因此不需要输入任何内容。
如果遇到了错误将程序将报错并退出否则将输出解析树。
./build/parser test.cminus # 不使用重定向直接从 test.cminus 中读入
./build/parser test.cminus out
此时程序从 test.cminus 文件中读取输入因此不需要输入任何内容。
如果遇到了错误将程序将报错并退出否则将输出解析树到 out 文件中。不使用重定向输入运行验证输入./build/parser后直接输入Cminus-f代码输入完成以后按^d结束输入此时程序将输出解析树如果遇到了报错程序将报错。
sunny2004sunny2004-VirtualBox:~/lab2/cminus_compiler-2023-fall$ ./build/parser
int a;
-- program
| -- declaration-list
| | -- declaration
| | | -- var-declaration
| | | | -- type-specifier
| | | | | --* int
| | | | --* a
| | | | --* ;
sunny2004sunny2004-VirtualBox:~/lab2/cminus_compiler-2023-fall$ 重定向运行
cd cminus_compiler-2023-fall
./build/parser test.cminus # 重定向标准输入
此时程序从 test.cminus 文件中读取输入因此不需要输入任何内容。
如果遇到了错误将程序将报错并退出否则将输出解析树。
./build/parser test.cminus # 不使用重定向直接从 test.cminus 中读入
./build/parser test.cminus out
此时程序从 test.cminus 文件中读取输入因此不需要输入任何内容。
如果遇到了错误将程序将报错并退出否则将输出解析树到 out 文件中。验证过程 本次试验测试案例较多为此我们将这些测试分为两类
easy: 这部分测试均比较简单且单纯适合开发时调试。normal: 较为综合适合完成实验后系统测试。 我们使用 diff 命令进行验证。将自己的生成结果和助教提供的 xxx_std 进行比较
验证输入指令./tests/lab2/test_syntax.sh easy yes ![[Snipaste_2023-11-23_20-25-10.png]] 验证输入指令./tests/lab2/test_syntax.sh normal yes 输出
sunny2004sunny2004-VirtualBox:~/lab2/cminus_compiler-2023-fall$ ./tests/lab2/test_syntax.sh normal yes
[info] Analyzing array1.cminus
[info] Analyzing array2.cminus
[info] Analyzing func.cminus
[info] Analyzing gcd.cminus
[info] Analyzing if.cminus
[info] Analyzing selectionsort.cminus
[info] Analyzing tap.cminus
[info] Analyzing You_Should_Pass.cminus
[info] Comparing...
[info] No difference! Congratulations!
sunny2004sunny2004-VirtualBox:~/lab2/cminus_compiler-2023-fall$ 使用diff命令验证 没有任何输出结果表示正确
sunny2004sunny2004-VirtualBox:~/lab1/cminus_compiler-2023-fall$ diff ./tests/lab2/syntree_easy ./tests/lab2/syntree_easy_std
sunny2004sunny2004-VirtualBox:~/lab1/cminus_compiler-2023-fall$ diff ./tests/lab2/syntree_normal ./tests/lab2/syntree_normal_std
sunny2004sunny2004-VirtualBox:~/lab1/cminus_compiler-2023-fall$ 设计自己的testcase编写cminus程序如下
/****/
/*absys***/
void hahah(int a){}
float temp[10];
int main(void) {int j;j 10;while (j 3) {temp[j] j * (j 2);j j - 1;}
}
void ohuuhu(int a) {
a a 3;
}执行指令./build/parser tests/lab2/easy/mytest.cminus tests/lab2/syntree_easy_std/mytest.syntax_tree 在没有语法错误的情况下将解析树定向输出到mytest.syntax_tree中。 在相应的文件夹中能够正确地生成语法树。
实验反馈
对于本次实验我的总结如下
注意bison的语法规则和如何与flex联合进行语法分析产生式中的词法单元是与.l文件中定义的词 法单元对应的对于空串也要正确地进行处理将子节点数量设置为0对于EOL、COMMENT、BLANK在语法分析中需要识别但不需要分析所以删去return和 pass_node部分且因为是需要被识别到的所以不能直接将.l文件中的相关语句全部删去
