布尔表达式的递归下降翻译程序设计

更新时间：2023-10-17 13:20:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

lambda表达式递归推荐度：
相关推荐

布尔表达式的递归下降翻译程序设计

1引言

“编译原理”是一门研究设计和构造编译程序原理和方法的课程，是计算机各

专业的一门重要的专业基础课。编译原理这门课程蕴含着计算机学科中解决问题的思路、形式化问题和解决问题的方法，对应用软件和系统软件的设计与开发有一定的启发和指导作用。“编译原理”是一门实践性较强的课程，要掌握这门课程中的思想，就必须要把所学到的知识付诸实践。而课程设计是将理论与实践相互联系的一种重要方式。

2概述

2.1设计题目

布尔表达式的递归下降翻译程序设计

2.2设计目的

课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。

2.3设计任务内容

布尔表达式的文法：

B ? TB′

B′? and T B′|ε T ? FT ′ T′? or FT′|ε

F ? not F |true｜false |（B）| i rop i

设计布尔表达式文法，给出该文法的属性文法，用递归下降分析法实现对布尔表达式的翻译，给出翻译的逆波兰式结果。

3设计环境与工具

Visual C++

4设计原则

4.1基本方法

在本程序中，输入一段布尔语句，使用递归下降的方法得到其推到过程，并

利用递归下降翻译的方法的到四元式序列，最终根据生成的四元式序列分析得到逆波兰式。

4.2属性文法

B ? TB′ B’.in=T.type

B′? and T B′ B’.in=T.type addtype(and,entry,B.in) B′?ε B’.val=ε T ? FT T.in=F.type.

T′? or FT′ T’.in=F.type addtype(or,entry,B.in) T′?ε T’val=ε

F ? not F F.val= not.F.val F ? true F.val=true F ? false F.val=false F ?（B） F.val=B.val F ? i rop i F.val=i.lexval rop i.lexval addtype(i，entry，l.in)

5简要的分析与概要设计

在该程序中，总共包括3个主要功能，第一个功能是对输入的布尔语句

进行递归下降的分析，从而得出从文法到该布尔语句的推导过程，第二个功能是使用递归下降的方法，该布尔语句的四元式序列，第三个功能对四元式序列进行扫描并分析每个四元式的结构特点，并据此将四元式转化为逆波兰式。 main 函数的流程图如下：

开始递归下降分析得到推导过程并输出递归下降分析得到四元式序列并输出读四元式并得到逆波兰式并输出结束

在开始进行本次实验中，本来计划在递归下降分析的过程中就得到逆波兰式，但是经过多次尝试之后总是存在错误，所以采用先得到四元式序列，再根据四元式序列生成逆波兰式这种效率比较低的方法。

6详细的算法描述，框图

6.1主要数据结构的设计

四元式类

在该类中，要包含四元式中的四个元素，运算结果，两个运算数以及一个运算符号 class quad {

public:

char result[8]; char arg1[8]; char op[8]; char arg2[8];

void print()//输出该四元式

{

cout<

}

}q[20]; Word结构体

这个结构体的对要用来存储单个单词，包括一个字符串成员。 struct word { char w[10]; void print() { cout<

}

}wr[200]; 逆波兰式结构体

这个结构体的对象用来存储逆波兰式，它的成员是一个word数组struct nipolan {

word nibolan[100];

} n; 翻译器类

用来存储翻译过程中的各个变量以及声明主要的函数： class interpreter {

private: ifstream SourceFile;

char buffercode[200];//存放源码的缓冲区 int syn;

int current;//buffercode中当前读到的字符下标

char token[8];//记录当前读到的单词

public:

void scaner(); void B(); void B1(); void T(); void F(); void T1(); void run(); void read(); void bolon(); void toword(); char *factor(); char *expression(); char *term(); void bolan(); void reset() { current=0;

};

void run1() { scaner(); expression();

};

6.2全局变量设计

int tear=51;//逆波兰式尾部 int head=50;//逆波兰是首部 int numberoftemp=0;//临时变量个数int numberofquad=0;//四元式个数

该函数首先调用了一个factor函数，如果下一个读到单词是“and”则分析and后面的一个factor并将or和两个factor写入到四元式序列中，如果读到的不是“and”则只把factor返回到四元式序列中。流程图为:

unit()函数

在该函数中，分析了优先级最高的运算或者是单个终结符，如果读入的是true或者false则直接返回token，如果读入的是 i则把i rop i写入到四元式序列中，如果读入的是not，则分析not后面的expression（），并将not 以及expression（）写入到四元式中，返回生成的newtemp 流程图：

该过程结束后，布尔语句对应的四元式存放在quad类生成的对象数组q中.

6.5分析四元式序列生成逆波兰式

本过程根据四元式序列以及每一个四元式的类型，将四元式中的信息按照一定

规则写入到逆波兰式中，主要函数为bolan（）函数，bolan函数将四元式序列从头到尾扫描一遍，对于每一个四元式序列根据其操作数是临时变量还是终结符将终结符以及操作符按照逆波兰式规则写入到逆波兰式类生成的对象n中。当当前四元式类型为临时变量=临时变量 OP 临时变量是，则直接将op插入到逆波兰式尾部。

当当前四元式类型为临时便令=arg1 op arg2时则按照arg1，arg2，op的顺序将他们插入逆波兰式的尾部。

当当前四元式类型为临时便令=临时变量 op arg1时则按照arg1，，op的顺序将他们插入逆波兰式的尾部。

当当前四元式类型为临时便令=arg1 op 临时变量时则将op的顺序将他们插入逆波兰式的尾部，将arg1插入到逆波兰式的首部。 bolan函数的流程图为：

本过程结束之后，逆波兰式存放在nibolan类定义的对象n中。

7软件的测试方法和测试结果

输入一个字符串，执行改程序，观察产生的四元式以及逆波兰式是否正确。测试数据1：

测试数据2

测试数据3

8设计的特点、不足收获与体会

8.1设计的特点

这次课程设计中，使用递归下降分析方法完成了布尔语句的翻译，程序不仅按照题目要求的到了翻译的逆波兰式，而且还求出了布尔语句的推导过程和四元式，实现的功能比较多，对翻译的过程和结果有一个比较全面的描述。程序的逻辑明确，易于理解。

8.2设计的不足

由于程序设计水平有限，在本次课程设计的程序中存在着两个主要问题：（1）：没有在递归下降的过程中直接求出逆波兰式，而是根据生成的四元式序列产生的逆波兰式，虽然可以达到题目的要求，但是程序的效率比较低。（2）：在递归下降生成逆波兰式的过程中，由于最小单元函数中读入”not”以及”(”的分支中出现了问题，导致了在调试过程中not语句以及括号中语句必须放在最后，否则在分析完该单元之后程序不再继续向后扫描。导致了布尔语句

分析不全。

8.3收获与体会

在何老师的指导下，经过三天的编码与调试，我终于完成了这次课程设计，通

过本次课程设计，我更加认识到了编译原理这门课的重要性，对于这门课在实践中是如何应用的有了一个更深的理解。虽然程序中有很多错误与漏洞，但是我仍然获得了很多，我不仅熟练地掌握了递归下降分析的方法，更加强了自己程序设计的能了，认识到了实践的重要性。

9参考文献

《编译原理》，主编：胡伦俊、徐兰芳、骆婷，出版社：电子工业出版社，出版时间：2005年12月

《程序设计语言编译原理》（第3版）,主编：陈火旺、刘春林等,出版社：国防工业出版社,出版时间：2003年2月

《编译原理》（第二版）,主编：吕映芝、张素琴、蒋维杜,出版社：清华大学出版社,出版时间：2004年11月

《编译原理》,主编：张幸儿,出版社：科学出版社,出版时间：1999年4月《Compilers:Principles,Techniques,and Tools》,主编：Alfred V A,Ravi S, Ullman J D, 出版社：人民邮电出版社,出版时间：2002年2月

《编译原理与技术》（第二版）,主编：陈意云,出版社：中国科学技术大学出版社, 出版时间：2002年1月

《编译原理实践教程》,主编：胡元义、邓亚玲、胡英,出版社：西安电子科技大学出版社, 出版时间：2002年1月

《编译原理课程设计》,主编：王雷、刘志成、周晶,出版社：机械工业出版社, 出版时间：2005年3月