【编译原理】用Yacc做语法分析

getianao

2012-07-23

关注关注

08年9月入学，12年7月毕业，结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾，索引参见：http://blog.csdn.net/xiaowei_cqu/article/details/7747205

语法分析

Yacc 全称 Yet Another Compiler Compiler

Yacc是一个用来生成编译器的编译器（编译器代码生成器）。yacc生成的编译器主要是用C语言写成的语法解析器（Parser），需要与词法解析器Lex一起使用，再把两部份产生出来的C程序一并编译。

作为Yacc对说明文件中的%tokenNUMBER声明的对应。Yacc坚持定义所有的符号记号本身，而不是从别的地方引入一个定义。但是却有可能通过在记号声明中的记号名之后书写一个值来指定将赋给记号的数字值。

Yacc的输入是巴科斯范式（BNF）表达的语法规则以及语法规约的处理代码，Yacc输出的是基于表驱动的编译器，包含输入的语法规约的处理代码部分。

Yacc是开发编译器的一个有用的工具,采用LALR(1)语法分析方法。

【实验内容】

1、实验环境配置

安装ParserGenerator，并编译lex和yacc函数库

2、编写Lex程序

（1）练习9.4.1：编写一个Yacc程序。该程序以布尔表达式作为输入（如习题4.2.2所示）并输入次布尔表达式的值。

编写Yacc程序如下：

编写Lex程序如下：

布尔表达式对应的文法如下：

bexpr→bexpr or bterm | bterm
bterm→bterm and bfactor | bfactor
bfactor→not bfactor |(bexpr) | true |false

所以程序中通过相应的语法定义规则：

line : bexpr '\n'   {if($1==1){printf("true");}else{printf("false");}}
     | '\n'         {printf("\n");}
     ;
bexpr : bexpr '&' bterm   { if(($1==1)&&($3==1)){$$=1;}else{$$=0;} }
      | bterm
      ;
bterm : bterm '|' bfactor   {if(($1==0)&&($3==0)){$$=0;}else{$$=1;}}
      | bfactor           
      ;
bfactor :'~' bfactor     {if($2==1){$$=0;}else{$$=1;}}
        | '('bexpr')'   {$$=$2;}
        |  TRUE         
        |  FALSE

在读到1或0（通过Lex定义的语法返回的响应值）以及‘|’或‘&’‘~’布尔运算符号时，进行布尔预算，并返回值

根据布尔运算的结果打印“true”或“false”的消息

程序运行结果：

（2）练习9.4.2：编写一个yacc程序，把字符串（按4.2.2（5）语法定义，但使得可以输出任何一个字符元素，而不是仅仅字符a）作为输出，并输出相同顺序的字符串

4.2.2定义的规则（5）为：S→（L）|a L→L，S|S

在Yacc中只需定义相应的语法规则

line:  L '\n'		 	 
    | '\n' 
	;
L   : S					
    | L ',' S				
	    ;
S   :'(' L ')'	{$$=$2;}
    |  LETTER	{printf("%c",$1);}

并在遇到字符时，打印字符即可得到效果

编写Lex程序如下：

程序运行结果：

（3）练习9.4.3：编写一个Yacc程序。判断输入的字符串是否是回文（正读或逆读的结果相同）。

编写Lex程序如下：

程序通过Lex识别连续的字符串

之后通过C语言判断是否是回文：将第i个字符与第len-i-1个字符比较，如果有不相同的，则将标记tag标记为0（否则为1）

程序最后（读入换行符‘\n’时）通过tag标记输出是否为回文。

程序运行结果：

【结果分析】

通过实验熟悉了Yacc做语法分析。尝试了Yacc程序两种编写方式，只有Yacc以及与Lex结合。感觉还是与Lex结合更灵活一些，因为Lex定义正则表达式作词法分析。比如字符串true。Lex只需写true{yylval=1;return TRUE;}而在Yacc中尝试判断写出来的语句为char c=getchar();int i=0;while(c=getchar()){if(c=='t')i=1;else if(c=='r'&&i==1)i=2;else if(c=='u'&&i==2)i=3;else if(c=='e'&&i==3)yylval=1;i=0;return TRUE;}（当然也可能是自己的思路复杂了些。。。）
实验中几个题目并不复杂，前两个更侧重语法判断，但第三个回文测试时，感觉并没用到太多Yacc的语法分析。而是通过Lex识别字符串，之后用C的思想判断是为回文。虽然也达到了效果，但不知是否还有其他的方法？
实验程序的容错能力都比较差，输入一些没有定义的字符程序就会弹出终止，调了很久也没有解决。感觉自己语法分析还是掌握的不够扎实。