合肥工业大学编译原理-LL(1)自上而下文法分析(共52页).docx

《合肥工业大学编译原理-LL(1)自上而下文法分析(共52页).docx》由会员分享，可在线阅读，更多相关《合肥工业大学编译原理-LL(1)自上而下文法分析(共52页).docx（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 合肥工业大学计算机与信息学院计算机系2013级编译原理课程设计报告姓 名： 马骏 专业年级： 信息安全13-1 学 号： 提交时间： 2016年07月 一、 实验题目自上而下的LL(1)文法分析二、 实验目的了解掌握自上而下的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+四、 开发过程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 计算“第一个”和“其后”的集合Afficha

6、ge des ensembles 显示集合 premiers 第一个 suivants其后 4）分析表的结构具有非递归语法以及“第一个”和“其后”的集合，你的程序现在可以建立预测分析表。结果以表的形式显示在屏幕上。图注释：Construction de la table danalyse分析表的结构table danalyse 分析表 Affichage de la table danalyse 显示分析表输入字符串的分析最后一步：你的程序读取输入（键盘）的表达和分析。指出，结果是否符合语法。你要尽可能准确的鉴定结果：定位错误在没有辨认出表达式的情况下。其次，你的程序必须能够完成对输入多个字符

7、串作为输入，不要忘记重新启动你的程序。显示分析结果判断是否继续读取表达式五、 程序实现六、 程序代码/*不支持规则源文件中有空格注意 使用#表示空产生式 使用$表示结束符# */#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和1

8、couterror 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;xfollown

10、umber;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_ends

11、ign;/非终结符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;ifstre

12、am 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=r

13、ule;/规则放在每个非终结符实例中unendsignunendsignnumber-1.funnumber+;rule=;continue;rule+=bufx;char kk=bufx;unendsignunendsignnumber-1.fununendsignunendsignnumber-1.funnumber=rule;unendsignunendsignnumber-1.funnumber+;/coutruleendl;void addendsign(char sg) /添加终结符for(int x=0;xendsignnumber;x+)if(endsignx.id=sg)re

14、turn;endsignendsignnumber.id=sg;endsignendsignnumber.identity=1;endsignnumber+;void dealend()/由非终结符产生式得到终结符for(int x=0;xunendsignnumber;x+)for(int y=0;yunendsignx.funnumber;y+)for(int z=0;z=65&int(kk)=90)continue; /A到Z为非终结符else addendsign(kk);bool exit_endsign(char sg) /终结符表是否有sgint x;for(x=0;xendsi

15、gnnumber;x+)if(endsignx.id=sg) return true;return false;bool exit_unendsign(char sg) /非终结符表是否有sgfor(int x=0;xunendsignnumber;x+)if(unendsignx.id=sg)return true;return false;sign get_unendsign(char sg)/从非终结符表中得到非终结符为sg的实例for(int x=0;xunendsignnumber;x+)if(unendsignx.id=sg)return unendsignx;couterror

16、get no unend sign!endl;sign er;return er;int get_unendsign_number(char sg)/从非终结符表中得到非终结符为sg的下标for(int x=0;xunendsignnumber;x+)if(unendsignx.id=sg)return x;couterror get no unend sign!endl;return 0;int get_endsign_number(char sg)/从非终结符表中得到终结符为sg的下标for(int x=0;xendsignnumber;x+)if(endsignx.id=sg)retur

17、n x;couterror get no end sign!endl;return 0;bool rule_first_check(sign m_sign,char sg)/查看非终结符实例m_sign 产生式首是否为sg int y;for(y=0;ym_sign.funnumber;y+)if(m_sign.funy0=sg)return true;int check=0;for(y=0;ym_sign.funnumber;y+)if(exit_unendsign(m_sign.funy0)sign msg=get_unendsign(m_sign.funy0);if(rule_first

18、_check(msg,sg)check=1;break;if(check)return true;else return false;bool check_L_recursion()/检查是否含有直接左递归和传递左递归 true表示有 false表示没有 int x,y;for(x=0;xunendsignnumber;x+) /检查直接左递归for(y=0;yunendsignx.funnumber;y+)if(unendsignx.funy0=unendsignx.id)return true;for(x=0;x90|unendsignnumber26)couterror no more

19、size for unend sign!endl;break;int check=1; for(int x=0;xunendsignnumber;x+)if(unendsignx.id=a)a+;check=0;break;if(check)unendsignunendsignnumber.id=a;unendsignunendsignnumber.identity=0;unendsignnumber+;break;return unendsignunendsignnumber-1;void pop_unendsign(char sg) /删除某一非终结符for(int x=0;xunends

20、ignnumber;x+)if(unendsignx.id=sg)for(int y=x;yunendsignnumber-1;y+)unendsigny=unendsigny+1;unendsignnumber-;return;couterror no unend sign for popendl;return;void deal_direct_L_recursion(int thisnumber) /消除 unendsignthisnumber的直接左递归 在deal_L_total_recursion()中调用 int i;if(!check_L_recursion()return;in

21、t check=0;for(i=0;iunendsignthisnumber.funnumber;i+) /先检查 unendsignthisnumber是否存在 直接左递归 if(unendsignthisnumber.funi0=unendsignthisnumber.id)check=1;break;if(check)new_unendsign();int kp=unendsignnumber-1;for(i=0;ib0p|b1pif(unendsignthisnumber.funi0=unendsignthisnumber.id)string ss=;for(int x=1;xunen

22、dsignthisnumber.funi.length();x+)ss+=unendsignthisnumber.funix;if(ss=#)coutP# # 的规则for(i=0;ip. 的产生式if(unendsignthisnumber.funi0=unendsignthisnumber.id)unendsignthisnumber.pop(i);i=0;void deal_L_total_recursion()/消除所有左递归 int i,j,t,k,qq;for(i=0;iunendsignnumber;i+)for(j=0;ji;j+)for( t=0;tunendsigni.fu

23、nnumber;t+)if(unendsigni.funt0=unendsignj.id)string say=;for( k=1;kunendsigni.funt.length();k+)say+=unendsigni.funtk;unendsigni.pop(t);for( qq=0;qqunendsignj.funnumber;qq+)string sp=unendsignj.funqq;if(sp!=#)sp+=say;unendsigni.add(sp);deal_direct_L_recursion(i); /消除Pi 的直接左递归void deal_first_club()/求各

24、节点的first集 int x,t;for(x=0;xendsignnumber;x+)endsignx.add_first(endsignx.id);int check=1;while(check)check=0;for(x=0;xunendsignnumber;x+)int oldnumber=unendsignx.firstnumber; /用于记录first集是否再增大for(t=0;tunendsignx.funnumber;t+) unendsignx.add_first(unendsignx.funt0);for(t=0;tunendsignx.firstnumber;t+)if

25、(exit_unendsign(unendsignx.firstt)int kp=get_unendsign_number(unendsignx.firstt);for(int q=0;qunendsignkp.firstnumber;q+)if(unendsignkp.firstq!=#)unendsignx.add_first(unendsignkp.firstq);if(unendsignx.firstnumber!=oldnumber)check=1;check=1;while(check)check=0;for(x=0;xunendsignnumber;x+) /判断first是否应

26、包含# for(int y=0;yunendsignx.funnumber;y+) int overcheck=1; for(int t=0;tABCD. int thischeck=1;for(int t=0;tunendsignx.funy.length();t+)int oop=get_unendsign_number(unendsignx.funyt);int incheck=0;for(int z=0;zunendsignoop.firstnumber;z+)if(unendsignoop.firstz=#)incheck=1;break;if(incheck) continue;e

27、lse thischeck=0;break;if(thischeck)int sp=unendsignx.firstnumber;unendsignx.add_first(#);if(sp!=unendsignx.firstnumber) check=1; for(x=0;xunendsignnumber;x+)/消除first集中的非终结符for(int y=0;yunendsignx.firstnumber;y+)if(exit_unendsign(unendsignx.firsty)unendsignx.pop_first(unendsignx.firsty); y-;void deal

28、_follow_club() /求每个非终结符的follow集 int x,y,z,t;unendsign0.add_follow($);/在开始符号的follow集中添加结束符$ int check=1; while(check) /循环至follow集不在增大check=0;for(x=0;xunendsignnumber;x+)for( y=0;yunendsignx.funnumber;y+)for( z=0;zunendsignx.funy.length();z+)if(exit_unendsign(unendsignx.funyz)&z.Aa.int kp=get_unendsig

29、n_number(unendsignx.funyz);int ss=unendsignkp.follownumber;if(unendsignx.funyz+1!=#)unendsignkp.add_follow(unendsignx.funyz+1);if(unendsignkp.follownumber!=ss)check=1; if(z=unendsignx.funy.length()-1&exit_unendsign(unendsignx.funyz) /p-.Bint kp=get_unendsign_number(unendsignx.funyz);for(t=0;tunendsi

30、gnx.follownumber;t+)int ssp=unendsignkp.follownumber;unendsignkp.add_follow(unendsignx.followt);if(unendsignkp.follownumber!=ssp)check=1;if(exit_unendsign(unendsignx.funyz)&z.SABC 其中#在ABC的first集中for(int i=z+1;iunendsignx.funy.length();i+)if(exit_unendsign(unendsignx.funyi)int thisthischeck=0;int kp=

31、get_unendsign_number(unendsignx.funyi);for(int pp=0;ppunendsignkp.firstnumber;pp+)if(unendsignkp.firstpp=#)thisthischeck=1;break;if(thisthischeck)continue;elsethischeck=0;break;thischeck=0;break;if(thischeck)int kp=get_unendsign_number(unendsignx.funyz); for(t=0;tunendsignx.follownumber;t+)int ssp=u

32、nendsignkp.follownumber;unendsignkp.add_follow(unendsignx.followt);if(unendsignkp.follownumber!=ssp)check=1; for(x=0;xunendsignnumber;x+) /非终结点在follow集则要把 其first集除#放入follow集for(y=0;yunendsignx.follownumber;y+)if(exit_unendsign(unendsignx.followy)int kp=get_unendsign_number(unendsignx.followy);for(t=0;tunendsignkp.firstnumber;t+)if(unendsignkp.firstt=#)continue;elseint oop=un