《合肥工业大学编译原理 ll自上而下文法分析》由会员分享，可在线阅读，更多相关《合肥工业大学编译原理 ll自上而下文法分析（31页珍藏版）》请在金锄头文库上搜索。
1、 合肥工业大学计算机与信息学院计算机系2013级编译原理课程设计报告姓 名： 马骏 专业年级： 信息安全13-1 学 号： 2013211869 提交时间： 2016年07月 1、 实验题目自上而下的LL(1)文法分析2、 实验目的了解掌握自上而下的LL（1）文法分析过程。二、实验内容与要求 从语法分析树构造句型所有的推导的程序实现，接受用户任意输入的一个句型的语法分析树（其表示存于指定文件中），生成该语法分析树中包含的该句型的所有推导（显示输出）。 构造一程序，实现教材P.78的FIRST(X)集合的构造算法。对任一给定的文法G，程序输出所有非终结符P的FIRST(P)。构造一程序，实现教材
2、P.78的FIRST(X)集合的构造算法。对任一给定的文法G，程序输出所有非终结符P的FIRST(P)。在此基础上，构造一程序，实现教材P.79的FOLLOW(A)集合的构造算法。对任一给定的文法G，程序输出所有非终结符A的FOLLOW (A)。对于给定的一个LL(1)文法，假定所有非终结符号P的集合FIRST(P)和集合FOLLOW(P)都已知，构造其预测分析表（实现教材P.79给出的预测分析表构造算法）。对教材P.79给出的例4.7构造出预测分析表。程序显示输出预测分析表或输出到指定文件中。 首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法，再实现教材P.79给出的预测
3、分析表构造算法。程序显示输出预测分析表或输出到指定文件中。 对文法按教材P.76表4.1构造出G的预测分析程序，程序显示输出如P.78那样的匹配过程。三、实验环境与工具操作系统：Windows 7开发语言：C+4、 开发过程1） 字符要求：你的程序必须能够根据以下字符来处理语法：- 终端字符：字母，数字，符号例如“+”，“ ”，;- 非终端字母表中的大写字母。符号“=”，“|”和“”（替换“”，因为它更容易输入到文本文件）被保留用于语法的描述中，因此不能被用作终端。2） 初始状态您的程序通过读取一个文件中的“文本”格式开始。这个文件的结构可以随意构建，不做要求，但建议做成简单的。例如，程序描述
4、以下语句：E = E + T |TT = T * F |FF =（E）| 0 |1在这种情况，我们可以很容易确定E，T和F是非终端，而符号“（”，“）”，“*”和“+”和数字“0”和“1”是在终端。第一个非终端（第一衍生物）被认为是语法的公理。文本结构（在内存中）过程显示在屏幕结果必须存储在内存中，是一个您所选择的数据结构。然后，使用一个函数再取出数据，存储在内存中并屏幕上显示（以你选择的格式）。在上面的图中，并在下文中，右列显示的程序的执行的过程，并左栏表示中使用的数据结构。这些都是明显的例子。你可以使用任何你想要的格式。3）消除传递没有发现传递关系发现传递关系判断：是否包含左传递消除传递关
5、系判断你的程序是否包含一个传递关系或没有。如果包含，递归应该被消除。没有传递关系的语句遍历语句指向自己的判断：您可以创建一个新的数据结构语句来表示其中传递关系已被删除，这有利于进一步加工。在这种情况下，如果语法不包含判定递归的语句，程序当然必须使用第二数据结构的副本。3）计算“first集”和“follow集”的集合为了产生一个分析器，你现在必须计算，每个分支，“第一个”和“其后”的集合。结果被存储在数据结构，再次“你的选择。”然后，这些集合被显示在屏幕上图注释：Calcul des ensembles premiers et suivants 计算“第一个”和“其后”的集合Affichage
6、 des ensembles 显示集合 premiers 第一个 suivants其后 4）分析表的结构具有非递归语法以及“第一个”和“其后”的集合，你的程序现在可以建立预测分析表。结果以表的形式显示在屏幕上。图注释：Construction de la table danalyse分析表的结构table danalyse 分析表 Affichage de la table danalyse 显示分析表输入字符串的分析最后一步：你的程序读取输入（键盘）的表达和分析。指出，结果是否符合语法。你要尽可能准确的鉴定结果：定位错误在没有辨认出表达式的情况下。其次，你的程序必须能够完成对输入多个字符串作
7、为输入，不要忘记重新启动你的程序。显示分析结果判断是否继续读取表达式5、 程序实现6、 程序代码/*不支持规则源文件中有空格注意 使用#表示空产生式 使用$表示结束符# */#include#include#include#includeusing namespace std;const char* sourcefile=ma_grammaira.txt; /定义源文件/const int max=100;#define max 100class signpublic:sign()sign(int check,char fu)if(check!=0&check!=1) /符号属性只有0和1co
8、uterror sign creat!=funnumber|q0)couterror wrong delete fun in sign!;return;for(int x=q;xfunnumber-1;x+)funx=funx+1;funnumber-;void pop_first(char q)/从first集删除某一节点for(int x=0;xfirstnumber;x+)if(firstx=q)for(int y=x;yfirstnumber-1;y+)firsty=firsty+1;firstnumber-;x-;/为了接着上次检查点void pop_follow(char q)/从
9、first集删除某一节点for(int x=0;xfollownumber;x+)if(followx=q)for(int y=x;yfollownumber-1;y+)followy=followy+1;follownumber-;x-;/为了接着上次检查点void add_first(char q)/向first添加元素for(int x=0;xfirstnumber;x+)if(firstx=q)return; firstfirstnumber=q;firstnumber+;void add_follow(char q)/向follow添加元素for(int x=0;xfollownum
10、ber;x+)if(followx=q)return; followfollownumber=q;follownumber+;int identity; /符号属性0为非终结符 1为终结符char id; /符号string funmax;/符号产生规则int funnumber; /符号产生规则数量char firstmax;/first集 int firstnumber; char followmax;/follow集 int follownumber;class cell /分析表的单元格结构public: char cell_unendsign;/终结符char cell_endsig
11、n;/非终结符string cell_fun;/产生式;cell tablemaxmax; /分析表数据结构int table_unend_number;/非终结符数int table_end_number;/终结符数sign unendsignmax;/非终结点集合int unendsignnumber=0;sign endsignmax;/终结点集合int endsignnumber=0;void readsource(const char*sf) /读取源文件ma_grammaira.txt int x;unendsignnumber=0;endsignnumber=0;ifstream
12、 ifs;ifs.open(sourcefile);char bufmax;for(x=0;xmax;x+)bufx=0;while(ifs.getline(buf,sizeof(buf) /一行一行读取unendsignunendsignnumber=sign(0,buf0);unendsignnumber+;string rule;for(int x=2;xmax;x+)if(bufx=0) break;if(bufx=|)/coutruleendl;unendsignunendsignnumber-1.fununendsignunendsignnumber-1.funnumber=rule;/规则放在每个非终结符实例中unendsignunendsignnumber-1.funnumber+;rule=;conti
