编译原理实验-递归下降语法分析

news/2024/10/30 11:21:23/

具体代码已放至Github(仅供参考):

qxpBlog/Compiler_UESTC: 电子科技大学编译原理实验 (github.com)

具体实验过程如下:

一、实验目的、原理、内容及步骤:

1目的:通过本实验加深对编译技术中重点算法和编译技术的理解,提高学生的编程能力培养好的程序设计风格。了解和掌握递归下降分析法的基本原理,根据给出的文法能够完成递归下降程序的实现。

2原理:递归下降分析器编译思想是简单的,从识别符号开始,在语法规则支配下进行语法分析,它逐个扫视源程序中的所有字符,根据文法和当前输入字符预测到下一个语法成份U时,便确定U为目标并调用分析和识别U的子程序,在分析U的过程中,又有可能确立其它(或自身)子目标并调用相应子程序,如此继续下去。

3内容:

1、学习所提供的“表达式文法”的递归下降处理

理解 lex.l、rdparser.c 的内容

在 vscode/Clion 中建立工程并调试运行

2、学习所提供的文法

与词法分析所提供的文法作比较

3、编写 rdgram 所提供文法的递归下降程序

(1) 编写不生成“语法树”的递归下降程序 rdcheck.c

(2) 将 rdcheck.c 改造为生成语法树的递归下降程序 rdparser.c

(3) 改进词法分析程序、showAst 函数、main 函数等,使递归下降程序 rdparser最终从命令行读取要分析的程序 test.c,分析后调用 showAst 打印该程序的结构。

4实验步骤:

1)编写不生成“语法树”的递归下降程序 rdcheck.c

主函数如图1-1所示,主要采取一个无限循环结构来实现多次对所输入的文法进行递归下降语法分析,并将分析结果打印出来。

图 1-1 rdcheck文件main函数

编写两个常用的函数:match匹配函数、advance移进函数,如图1-2所示。

图 1-2 match函数与advance函数定义

用这两个函数来实现将所输入的字符串与sysy文法进行逐一匹配。match函数主要用来检查sysy文法中的终结符是否与输入串中的当前字符匹配,如果匹配那么就是用调用advance,将下一个待分析的字符设置为当前字符,之后再调用文法中剩余字符对应的函数进行匹配;如果不匹配,则返回-1,表示文法匹配出错。

对于开始符号CompUnit的文法规则,如图1-3所示。

图 1-3 CompUnit的文法规则

由于其包含公共左因子,所以我们首先要消除公共左因子,改造后的语法规则如图1-4所示。

图 1-4 改造后的CompUnit的文法规则

其对应的语法分析函数CompUnit, CompUnit_,如图1-5所示。

图 1-5 CompUnit、CompUnit_函数定义

sysy文法程序开始可能包含两个部分变量或常量声明(定义)和函数定义。如果输入串是变量或常量声明,那么就进入其对应语法规则左侧非终结符函数Decl(),进行下一步的匹配;如果是函数定义,那么就进入对应的函数FuncDef,进行下一步的匹配。如果下一步也匹配成功,则说明输入串符合sysy文法,并返回1,否则,则表明输入串不符合sysy文法,返回0。

对于sysy文法中的语句Stmt的文法规则,如图1-6所示。

图 1-6 Stmt的语法规则

由于该文法规则中含有公共左因子,所以需要消除其公共左因子,改造后的文法规则如图1-7所示。

图 1-7 改造后的Stmt的语法规则

对应的Stmt函数如图1-8(a)、图1-8(b)、图1-8(c)、图1-8(d)所示。

图 1-8(a) Stmt函数定义

图 1-8(b) Stmt函数定义

图 1-8(c) Stmt函数定义

图 1-8(d) Stmt函数定义

假设输入串是一个while语句,那么在Stmt函数中,match函数会首先匹配while语句中前缀部分的终结符:‘while’、‘(’,之后需要匹配一个由非终结符LorExp产生的循环条件表达式单词序列,因此进入对应的函数LorExp,识别由该非终结符生成的单词序列。之后继续使用match函数匹配非终结符‘)’,最后进入函数Stmt,匹配由非终结符Stmt产生的单词序列。如图1-9所示

图 1-9 while语句处理

对于sysy文法中的表达式Exp的语法规则,如图1-10所示。

图 1-10 Exp表达式语法规则

对应的Exp函数如图1-11所示。

图 1-11 Exp函数定义

在sysy文法中,表达式就是加减表达式,因此在对表达式进行递归下降语法分析时,会进入AddExp函数,识别由非终结符AddExp产生的单词序列。

该递归下降分析程序对输入串“int main(){while(1==2){return 0;}}”的识别结果如图1-12所示。

图 1-12 识别结果

2)将 rdcheck.c 改造为生成语法树的递归下降程序 rdparser.c

将rdcheck.c改造后,生成Stmt语句结点的函数astStmt如图2-1(a)、图2-1(b)、图2-1(c)、图2-1(d)、图2-1(e)所示。

图 2-1(a) 生成Stmt结点函数astStmt定义

图 2-1(b) 生成Stmt结点函数astStmt定义

图 2-1(c) 生成Stmt结点函数astStmt定义

图 2-1(d) 生成Stmt结点函数astStmt定义

图 2-1(e) 生成Stmt结点函数astStmt定义

在语句结点中,关于if语句结点生成的代码部分如图2-2所示。

图 2-2 生成if语句结点代码

在构建抽象语法树(AST)的过程中,我们将舍弃一些无用的界符,例如‘;’、‘(’、‘)’等,方便编译后续阶段的进行。因此在构建if语句结点时,用match匹配终结符‘if’、‘(’并将其舍弃,如果匹配成功则之后进入函数astLorExp,生成条件判断表达式结点l;反之匹配失败,返回NULL。之后匹配终结符‘)’并将其舍弃,如果匹配成功,那么就进入函数astStmt,生成复合语句结点CompoundStmt,反之则匹配失败,返回NULL。之后,如果能够匹配字符‘else’,那么就继续进入astStmt函数,生成复合语句结点CompoundStmt,最后返回生成的if语句结点;反之,则输入串中无else语句,那么直接返回不含else语句的if语句。

对于生成加减表达式结点的函数astAddExp定义如图2-3所示。

图 2-3 生成加减表达式结点函数astStmAddExp定义

在生成加减表达式结点的时候,根据AddExp文法可知,加减表达式包含右递归,其每个操作数都可能是由若干个其他表达式构成,因此采用while循环结构来生成加减表达式结点。

3)该进词法分析程序、showAst 函数、main 函数等,使递归下降程序 rdparser最终从命令行读取要分析的程序 test.c,分析后调用 showAst 打印该程序的结构。

改进后的main函数如图3-1所示。

图 3-1 改进后的main函数

从文法开始符号CompUnit对应的函数astCompUnit开始构建输入串的抽象语法树(AST),并将抽象语法树(AST)的根节点返回给node,之后调用函数showAst打印生成的抽象语法树(AST)。

改进后的showAst函数如图3-2(a)、图3-2(b)所示。

图 3-2(a) 改进后的showAst函数

图 3-2(b) 改进后的showAst函数

在showAst函数中,对与不同的结点类型,我们将打印不同的信息。

对于函数形参结点,我们调用showParaDecl函数对其所包含的结点进行打印,如图3-3所示。由于构建函数形参结点的时候我们是逆序构建,因此需采用非递归中序遍历的算法对其结点进行打印,以便保证函数形参顺序的正确。

图 3-3 showParaDecl函数定义

对于复合语句,我们调用showCompoundStmt函数对其所包含的结点进行打印,如图3-4所示。由于构建函数形参结点的时候我们是顺序序构建,并且假定只有left结点才是真正的语句结点,因此我们只需逐一访问每一层复合语句结点的左子结点并打印其所包含的信息即可。

   

图 3-4 showCompoundStmt函数定义               

对于函数调用结点,我们调用showCallExp函数对其所包含的结点进行打印,如图3-5所示。由于构建函数形参结点的时候我们是顺序序构建,并且假定只有left结点才是真正的语句结点,因此我们只需逐一访问每一层复合语句结点的左子结点并打印其所包含的信息即可。

   

图 3-5 showCallExp函数定义    

           

对于编译单元,我们调用showTranstion函数对其所包含的结点进行打印,如图3-6所示。由于构建函数形参结点的时候我们是顺序序构建,并且只有left结点才是变量结点或常量结点或者函数定义节点,因此我们只需逐一访问每一层编译单元结点的左子结点并打印其所包含的信息即可。

 图 3-6 showTrasntion函数定义

二、实验运行结果:

(1)测试用例1:在终端输入字符串“int main(int m, int n){l = 1 + 2; while(1 == 2){ l = l + 1;} }” ,程序运行结果如图4-1所示。

图 4-1 测试用例1运行结果

(2)测试用例2:在终端输入字符串“int main(int m, int n){l = 1 + 2; if(1 > 2){return 1;} } ” ,程序运行结果如图4-2所示。

图 4-2 测试用例2运行结果

(3)测试用例3:在终端输入字符串“int main(int m, int n){l = 1; if(6 < 2){return 1;}else {return 5;} }” ,程序运行结果如图4-3所示。

图 4-3 测试用例3运行结果

(4)测试用例4:在终端输入字符串“int func(){return 1;} int main(){int l = func();}”,程序运行结果如图4-4所示。

图 4-4 测试用例4运行结果

三、实验结论与总结:

        本次实验所实现的递归下降分析程序,能够完成对sysy文法中函数定义、函数形参、语句块、语句、表达式等部分的语法分析,并能够生成相应的抽象语法树(AST)。较好的完成了本次实验的要求。

        通过本次实验,了解和掌握了递归下降分析法的基本原理,并且能够根据给出的文法完成递归下降程序的实现。同时也对编译过程中词法分析这一环节有了一个更加深刻的认知。同时,在实验的过程中也逐渐地的意识到递归下降分析法的缺陷所在:对含有公共左因子和左递归的文法词法分析效果较差。


http://www.ppmy.cn/news/92282.html

相关文章

android 12.0Settings去掉二级三级菜单搜索功能

1.概述 在12.0由于客户定制开发需求,需要去掉Settings里面的搜索功能,主页面的搜索功能,在前面的章节已经讲了 这里需要去掉二级三级菜单的搜索功能,需要从搜索功能流程分析去掉搜索功能 2.Settings去掉二级三级菜单搜索功能核心代码 packages/apps/Settings/src/com/and…

tektronix泰克TDS3054数字荧光示波器

tektronix TDS3054是泰克TDS3000系列示波器&#xff0c;它是一种新的图形界面操作模式&#xff0c;称为QuickMenu。这种快速访问的用户界面使得主要的示波器控制访问一个单一的按键。每一个示波器都包含一个在示波器中运行的在线巡览盘。此磁盘提供了产品的操作和功能的概述。 …

今麦郎跻身“我最喜欢中国品牌”榜,致力领航中国品牌发展新范式

在中国经济探寻高质量发展的当下&#xff0c;中国民营企业肩负着推动经济发展的重任。在当前中国经济向上向前的大背景下&#xff0c;展示中国特色、传播中国文化、践行社会责任多位一体的高质量品牌越来越受到重视。但冰冻三尺非一日之功&#xff0c;唯有经历时间考验&#xf…

【Leetcode -605.种花问题 -628.三个数的最大乘积】

Leetcode Leetcode -605.种花问题Leetcode -628.三个数的最大乘积 Leetcode -605.种花问题 题目&#xff1a;假设有一个很长的花坛&#xff0c;一部分地块种植了花&#xff0c;另一部分却没有。可是&#xff0c;花不能种植在相邻的地块上&#xff0c;它们会争夺水源&#xff0…

apache虚拟主机头的实现方式

目录 一&#xff1a;基于不同的IP地址 二&#xff1a;基于不同的端口 三&#xff1a;基于不同的域名 一&#xff1a;基于不同的IP地址 步骤一&#xff1a;修改主配置文件 vim /usr/local/apache/conf/httpd.conf 声明监听不同的IP地址的80端口 Listen 192.168.2.20:80 Listen…

JUnit 使用详解,让你的项目健壮起来

JUnit 是 Java 中最为流行的测试框架之一&#xff0c;用于对单元测试进行自动化测试。本文将全面介绍 JUnit 的相关概念和使用方式&#xff0c;并提供多种类型的代码示例。 一、JUnit 简介 1.1 JUnit 概述 JUnit 是一个基于 Java 语言的测试框架&#xff0c;最初是由 Kent B…

全国第六届研究生数学建模竞赛-多传感器数据融合与航迹预测

目录 摘 要: 一、问题重述 1.1 背景分析 1.2 有关情况 1.3 问题提出 二、模型假设

【JavaSE】Java基础语法(十七)

文章目录 1. final2. 代码块2.1 代码块概述2.2 代码块分类 1. final fianl关键字的作用 final代表最终的意思&#xff0c;可以修饰成员方法&#xff0c;成员变量&#xff0c;类 final修饰类、方法、变量的效果 fianl修饰类&#xff1a;该类不能被继承&#xff08;不能有子类&a…