`

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

 
阅读更多

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 对说明文件中的 %token NUMBER 声明的对应。Yacc 坚持定义所有的符号记号本身,而不是从别的地方引入一个定义。但是却有可能通过在记号声明中的记号名之后书写一个值来指定将赋给记号的数字值。
Yacc的输入是巴科斯范式(BNF)表达的语法规则以及语法规约的处理代码,Yacc输出的是基于表驱动的编译器,包含输入的语法规约的处理代码部分。
Yacc是开发编译器的一个有用的工具,采用LALR(1)语法分析方法。

【实验内容】

1、实验环境配置
安装Parser Generator,并编译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标记输出是否为回文。
程序运行结果:


【结果分析】

  1. 通过实验熟悉了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;}(当然也可能是自己的思路复杂了些。。。)
  2. 实验中几个题目并不复杂,前两个更侧重语法判断,但第三个回文测试时,感觉并没用到太多Yacc的语法分析。而是通过Lex识别字符串,之后用C的思想判断是为回文。虽然也达到了效果,但不知是否还有其他的方法?
  3. 实验程序的容错能力都比较差,输入一些没有定义的字符程序就会弹出终止,调了很久也没有解决。感觉自己语法分析还是掌握的不够扎实。

转载请注明出处:http://blog.csdn.net/xiaowei_cqu/article/details/7764913




分享到:
评论

相关推荐

    编译原理yacc实现语法分析器.rar_yacc_yacc原理_yacc语法分析_编译原理_编译原理yacc

    YACC语法分析: 在解析过程中,YACC遵循以下步骤: 1. **词法分析**:首先,词法分析器(如LEX/FLEX)读取源代码并产生词法单元。 2. **启动解析**:YACC的解析器开始工作,从输入流的第一个词法单元开始,按照语法...

    yacc语法分析和语义分析-编译原理

    在编译原理中,YACC(Yet Another Compiler-Compiler)是一种广泛应用的语法分析工具,它根据用户提供的文法定义生成解析器。这个压缩包文件包含了关于YACC在语法分析和语义分析方面的实践应用,是北邮编译原理课程...

    编译原理课程设计词法语法分析器

    提供的“编译原理课程设计VC实现源码”很可能是用Visual C++实现的一个编译器原型,包含了词法分析器和语法分析器的源代码。通过阅读和理解这些代码,你可以深入学习编译器的设计和实现过程,以及如何在实际项目中...

    编译原理 实验报告 此法分析语法分析

    编译原理实验报告—语法分析与词法分析实现研究 在现代编程语言的理论与实践中,编译原理是一个核心领域,它关乎计算机程序如何将高级语言转换为机器能够执行的指令。编译过程主要包含四个阶段:词法分析、语法分析...

    编译原理 语法分析 语法树生成

    压缩包中的“编译原理语法树”文件可能包含了使用yacc和lex构建的C++语法分析器的示例,以及它分析C++源代码后生成的语法树的可视化表示。通过查看这些示例,开发者可以更深入地理解编译器的工作原理,学习如何构建...

    编译原理实验四、用Flex&Bison;进行语法分析(实验4 用Yacc工具构造语法分析器)

    编译原理实验四、用Flex&Bison进行语法分析(实验4 用Yacc工具构造语法分析器) 知识点1: 编译原理实验四的主要目标是掌握移进-归约技术语法分析技术,利用语法分析器生成工具 Yacc/Bison 实现语法分析器的构造。 ...

    编译原理实验 词法分析 语法分析递归下降 预测分析 Python

    对于语法分析,我们定义非终结符和终结符,以及它们之间的关系,使用`ply.yacc`生成解析器。 实验可能包括编写词法分析器,解析简单的数学表达式,然后逐步扩展到更复杂的Python语法,如控制流、函数定义和类声明。...

    YUFAFENXI.rar_yufafenxi_编译原理_编译原理 语法分析_语法分析器_语法分析器实验报告

    在“语法分析器(040693邱婷)”这个文件中,可能包含了实现特定文法分析算法的代码,如递归下降解析、LR分析、LL分析或者使用解析器生成器如ANTLR、YACC或LEX生成的代码。这些代码可以被编译并生成EXE文件,用于...

    编译原理语法树,编译原理语法树怎么画,C/C++

    通过分析和修改这些例子,我们可以更好地掌握bison和flex的使用,加深对语法树和编译原理的理解。 总的来说,编译原理中的语法树是理解代码结构的核心,而bison和flex则是实现这一理解的实用工具。通过实际操作和...

    编译原理实验二,语法分析

    在编译原理中,语法分析是至关重要的一个环节,它主要负责将源代码按照语法规则分解成结构化的抽象语法树(Abstract Syntax Tree, AST)。本实验基于编译原理的第二版,旨在深入理解并实践语法分析的过程。下面将...

    北邮编译原理实验二:语法分析程序的设计与实现

    在编译原理中,语法分析是编译器设计的关键阶段之一,主要任务是根据语法规则解析源代码,构建抽象语法树(AST),为后续的语义分析和代码生成提供结构化信息。本实验——“北邮编译原理实验二:语法分析程序的设计...

    编译原理实验报告(语法分析和词法分析)

    4. **语法解析器**:可能包含自定义编写的解析器代码,或者使用Yacc、ANTLR等工具生成的解析器。 5. **错误处理**:如何处理词法和语法错误,例如未识别的标记、语法错误以及如何向用户友好地报告这些问题。 6. **...

    编译原理词法分析器、语法分析器python实现

    在编程领域,编译原理是理解计算机语言处理过程的关键部分,它涉及到词法分析、语法分析、语义分析以及代码生成等多个步骤。本项目聚焦于词法分析器和语法分析器的实现,采用Python作为开发语言,对于学习编译原理和...

    编译原理词法分析and语法分析

    相比之下,LR分析适用于处理更复杂的语法规则,尤其在处理上下文无关文法时更为强大,但实现起来相对复杂,通常需要使用如YACC或ANTLR这样的工具。 在实际的编译器设计中,词法分析和语法分析往往是结合进行的,...

    用YACC实现语法分析器

    本篇文章将深入探讨如何使用YACC(Yet Another Compiler-Compiler)工具来实现一个语法分析器。 YACC,由贝尔实验室的Douglas McIlroy开发,是一个基于LALR(1)解析算法的工具,用于生成解析器。它的主要任务是根据...

    基于yacc实现的语法分析和语义分析

    在编程领域,编译器是将高级语言转化为机器可执行代码的关键工具,而编译器设计的核心部分就...通过分析和理解这个资源中的代码,初学者可以更好地掌握语法分析和语义分析的概念,从而为深入研究编译技术打下坚实基础。

    YACC语法分析器词法分析器

    YACC Decaf 语法分析器 程序的执行方法是: (1)运行debug.bat; (2)用vc6.0打开pp2.dsw,编译链接生成pp2.exe; (3)运行pp2 [filename]。其中filename是可选部分,如果没有filename,就默认是打开test.frag,...

    编译原理语法分析实验

    编译原理语法分析实验,C语言编写的PL0代码编译程序

    编译原理lex和yacc

    4. **实验设计与报告**:在“编译原理课程设计实验报告”中,学生通常会被要求实现一个简单的编译器,可能涉及使用lex和yacc来处理特定的编程语言子集。实验报告会详细记录实验步骤、遇到的问题、解决方案以及实验...

    基于lex和yacc的词法分析器+语法分析器(C语言编译器)【100012624】

    总的来说,这个项目展示了如何使用 lex 和 yacc 这两个经典工具来实现编译器的关键部分,这对于理解编译原理和实践编译技术具有很高的价值。通过这样的练习,开发者不仅可以深入学习编译器的工作原理,还能提升在...

Global site tag (gtag.js) - Google Analytics