合肥工业大学编译原理 LL(1)自上而下文法分析

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） 初始状态您的程序通过读取一个文件中的“文本”格式开始。这个文件的结构可以随意构建，不做要求，但建议做成简单的<simp

4、le>。例如，程序描述以下语句：E = E + T |TT = T * F |FF =（E）| 0 |1在这种情况，我们可以很容易确定E，T和F是非终端，而符号“（”，“）”，“*”和“+”和数字“0”和“1”是在终端。第一个非终端（第一衍生物）被认为是语法的公理。文本结构（在内存中）过程显示在屏幕结果必须存储在内存中，是一个您所选择的数据结构。然后，使用一个函数再取出数据，存储在内存中并屏幕上显示（以你选择的格式）。在上面的图中，并在下文中，右列显示的程序的执行的过程，并左栏表示中使用的数据结构。这些都是明显的例子。你可以使用任何你想要的格式。3）消除传递没有发现传递关系发现传递关系判

5、断：是否包含左传递消除传递关系判断你的程序是否包含一个传递关系或没有。如果包含，递归应该被消除。没有传递关系的语句遍历语句指向自己的判断：您可以创建一个新的数据结构语句来表示其中传递关系已被删除，这有利于进一步加工。在这种情况下，如果语法不包含判定递归的语句，程序当然必须使用第二数据结构的副本。3）计算“first集”和“follow集”的集合为了产生一个分析器，你现在必须计算，每个分支，“第一个”和“其后”的集合·。 结果被存储在数据结构，再次“你的选择。”然后，这些集合被显示在屏幕上图注释：Calcul des ensembles « premiers

6、87; et « suivants » 计算“第一个”和“其后”的集合Affichage des ensembles 显示集合 premiers 第一个 suivants其后 4）分析表的结构具有非递归语法以及“第一个”和“其后”的集合，你的程序现在可以建立预测分析表。结果以表的形式显示在屏幕上。图注释：Construction de la table danalyse分析表的结构table danalyse 分析表 Affichage de la table danalyse 显示分析表输入字符串的分析最后一步：你的程序读取输入（键盘）的表达和分析。指出，结果是否符合语法

7、。你要尽可能准确的鉴定结果：定位错误在没有辨认出表达式的情况下。其次，你的程序必须能够完成对输入多个字符串作为输入，不要忘记重新启动你的程序。显示分析结果判断是否继续读取表达式5、 程序实现6、 程序代码/*不支持规则源文件中有空格注意 使用#表示空产生式 使用$表示结束符# */#include<iostream>#include<string>#include<fstream>#include<windows.h>using namespace std;const char* sourcefile="ma_grammaira.txt

8、" /定义源文件/const int max=100;#define max 100class signpublic:sign()sign(int check,char fu)if(check!=0&&check!=1) /符号属性只有0和1cout<<"error sign creat!"<<endl;elseidentity=check; /设置符号属性id=fu; /设置非终结符 符号funnumber=0;/设置符号规则数为0firstnumber=0;follownumber=0;void add(string s

9、l)/添加产生规则funfunnumber=sl;funnumber+;void pop(int q)/删除某一规则if(q>=funnumber|q<0)cout<<"error wrong delete fun in sign!"return;for(int x=q;x<funnumber-1;x+)funx=funx+1;funnumber-;void pop_first(char q)/从first集删除某一节点for(int x=0;x<firstnumber;x+)if(firstx=q)for(int y=x;y<fi

10、rstnumber-1;y+)firsty=firsty+1;firstnumber-;x-;/为了接着上次检查点void pop_follow(char q)/从first集删除某一节点for(int x=0;x<follownumber;x+)if(followx=q)for(int y=x;y<follownumber-1;y+)followy=followy+1;follownumber-;x-;/为了接着上次检查点void add_first(char q)/向first添加元素for(int x=0;x<firstnumber;x+)if(firstx=q)ret

11、urn; firstfirstnumber=q;firstnumber+;void add_follow(char q)/向follow添加元素for(int x=0;x<follownumber;x+)if(followx=q)return; followfollownumber=q;follownumber+;int identity; /符号属性0为非终结符 1为终结符char id; /符号string funmax;/符号产生规则int funnumber; /符号产生规则数量char firstmax;/first集 int firstnumber; char followm

12、ax;/follow集 int follownumber;class cell /分析表的单元格结构public: char cell_unendsign;/终结符char cell_endsign;/非终结符string cell_fun;/产生式;cell tablemaxmax; /分析表数据结构int table_unend_number;/非终结符数int table_end_number;/终结符数sign unendsignmax;/非终结点集合int unendsignnumber=0;sign endsignmax;/终结点集合int endsignnumber=0;void

13、 readsource(const char*sf) /读取源文件ma_grammaira.txt int x;unendsignnumber=0;endsignnumber=0;ifstream ifs;ifs.open(sourcefile);char bufmax;for(x=0;x<max;x+)bufx='0'while(ifs.getline(buf,sizeof(buf) /一行一行读取unendsignunendsignnumber=sign(0,buf0);unendsignnumber+;string rule;for(int x=2;x<max

14、;x+)if(bufx='0') break;if(bufx='|')/cout<<rule<<endl;unendsignunendsignnumber-1.fununendsignunendsignnumber-1.funnumber=rule;/规则放在每个非终结符实例中unendsignunendsignnumber-1.funnumber+;rule=""continue;rule+=bufx;char kk=bufx;unendsignunendsignnumber-1.fununendsignunends

15、ignnumber-1.funnumber=rule;unendsignunendsignnumber-1.funnumber+;/cout<<rule<<endl;void addendsign(char sg) /添加终结符for(int x=0;x<endsignnumber;x+)if(endsignx.id=sg)return;endsignendsignnumber.id=sg;endsignendsignnumber.identity=1;endsignnumber+;void dealend()/由非终结符产生式得到终结符for(int x=0;x

16、<unendsignnumber;x+)for(int y=0;y<unendsignx.funnumber;y+)for(int z=0;z<unendsignx.funy.length();z+)char kk=unendsignx.funyz;if(int(kk)>=65&&int(kk)<=90)continue; /A到Z为非终结符else addendsign(kk);bool exit_endsign(char sg) /终结符表是否有sgint x;for(x=0;x<endsignnumber;x+)if(endsignx.

17、id=sg) return true;return false;bool exit_unendsign(char sg) /非终结符表是否有sgfor(int x=0;x<unendsignnumber;x+)if(unendsignx.id=sg)return true;return false;sign get_unendsign(char sg)/从非终结符表中得到非终结符为sg的实例for(int x=0;x<unendsignnumber;x+)if(unendsignx.id=sg)return unendsignx;cout<<"error ge

18、t no unend sign!"<<endl;sign er;return er;int get_unendsign_number(char sg)/从非终结符表中得到非终结符为sg的下标for(int x=0;x<unendsignnumber;x+)if(unendsignx.id=sg)return x;cout<<"error get no unend sign!"<<endl;return 0;int get_endsign_number(char sg)/从非终结符表中得到终结符为sg的下标for(int x

19、=0;x<endsignnumber;x+)if(endsignx.id=sg)return x;cout<<"error get no end sign!"<<endl;return 0;bool rule_first_check(sign m_sign,char sg)/查看非终结符实例m_sign 产生式首是否为sg int y;for(y=0;y<m_sign.funnumber;y+)if(m_sign.funy0=sg)return true;int check=0;for(y=0;y<m_sign.funnumber;

20、y+)if(exit_unendsign(m_sign.funy0)sign msg=get_unendsign(m_sign.funy0);if(rule_first_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;x<unendsignnumber;x+) /检查直接左递归for(y=0;y<unendsignx.funnumber;y+)if

21、(unendsignx.funy0=unendsignx.id)return true;for(x=0;x<unendsignnumber;x+) /检查传递左递归 if(rule_first_check(unendsignx,unendsignx.id) return true;return false;sign new_unendsign() /创建一个新非终结符 即用于规则p=p. 需要p'char a=65;while(1)if(a>90|unendsignnumber>26)cout<<"error no more size for u

22、nend sign!"<<endl;break;int check=1; for(int x=0;x<unendsignnumber;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

23、;x<unendsignnumber;x+)if(unendsignx.id=sg)for(int y=x;y<unendsignnumber-1;y+)unendsigny=unendsigny+1;unendsignnumber-;return;cout<<"error no unend sign for pop"<<endl;return;void deal_direct_L_recursion(int thisnumber) /消除 unendsignthisnumber的直接左递归 在deal_L_total_recursion

24、()中调用 int i;if(!check_L_recursion()return;int check=0;for(i=0;i<unendsignthisnumber.funnumber;i+) /先检查 unendsignthisnumber是否存在 直接左递归 if(unendsignthisnumber.funi0=unendsignthisnumber.id)check=1;break;if(check)new_unendsign();int kp=unendsignnumber-1;for(i=0;i<unendsignthisnumber.funnumber;i+) /

25、增加p'的规则a0p'|a1p'|# 增加p->b0p'|b1p'if(unendsignthisnumber.funi0=unendsignthisnumber.id)string ss=""for(int x=1;x<unendsignthisnumber.funi.length();x+)ss+=unendsignthisnumber.funix;if(ss="#")cout<<"error can't deal whith P->P# "<&l

26、t;endl;return;ss=ss+unendsignkp.id;unendsignkp.add(ss);elseif(unendsignthisnumber.funi!="#")unendsignthisnumber.funi=unendsignthisnumber.funi+unendsignkp.id;if(unendsignthisnumber.funi="#")string ss=""ss+=unendsignkp.id;unendsignthisnumber.add(ss);unendsignkp.add("

27、#");/为p'增加 p-># 的规则for(i=0;i<unendsignthisnumber.funnumber;i+) /删除p->p. 的产生式if(unendsignthisnumber.funi0=unendsignthisnumber.id)unendsignthisnumber.pop(i);i=0;void deal_L_total_recursion()/消除所有左递归 int i,j,t,k,qq;for(i=0;i<unendsignnumber;i+)for(j=0;j<i;j+)for( t=0;t<unends

28、igni.funnumber;t+)if(unendsigni.funt0=unendsignj.id)string say=""for( k=1;k<unendsigni.funt.length();k+)say+=unendsigni.funtk;unendsigni.pop(t);for( qq=0;qq<unendsignj.funnumber;qq+)string sp=unendsignj.funqq;if(sp!="#")sp+=say;unendsigni.add(sp);deal_direct_L_recursion(i);

29、 /消除Pi 的直接左递归void deal_first_club()/求各节点的first集 int x,t;for(x=0;x<endsignnumber;x+)endsignx.add_first(endsignx.id);int check=1;while(check)check=0;for(x=0;x<unendsignnumber;x+)int oldnumber=unendsignx.firstnumber; /用于记录first集是否再增大for(t=0;t<unendsignx.funnumber;t+) unendsignx.add_first(unend

30、signx.funt0);for(t=0;t<unendsignx.firstnumber;t+)if(exit_unendsign(unendsignx.firstt)int kp=get_unendsign_number(unendsignx.firstt);for(int q=0;q<unendsignkp.firstnumber;q+)if(unendsignkp.firstq!='#')unendsignx.add_first(unendsignkp.firstq);if(unendsignx.firstnumber!=oldnumber)check=1;

31、check=1;while(check)check=0;for(x=0;x<unendsignnumber;x+) /判断first是否应包含# for(int y=0;y<unendsignx.funnumber;y+) int overcheck=1; for(int t=0;t<unendsignx.funy.length();t+) if(exit_unendsign(unendsignx.funyt)continue;elseovercheck=0;break; if(overcheck)/如果存在P->ABCD. int thischeck=1;for(in

32、t t=0;t<unendsignx.funy.length();t+)int oop=get_unendsign_number(unendsignx.funyt);int incheck=0;for(int z=0;z<unendsignoop.firstnumber;z+)if(unendsignoop.firstz='#')incheck=1;break;if(incheck) continue;else thischeck=0;break;if(thischeck)int sp=unendsignx.firstnumber;unendsignx.add_fi

33、rst('#');if(sp!=unendsignx.firstnumber) check=1; for(x=0;x<unendsignnumber;x+)/消除first集中的非终结符for(int y=0;y<unendsignx.firstnumber;y+)if(exit_unendsign(unendsignx.firsty)unendsignx.pop_first(unendsignx.firsty); y-;void deal_follow_club() /求每个非终结符的follow集 int x,y,z,t;unendsign0.add_follo

34、w('$');/在开始符号的follow集中添加结束符$ int check=1; while(check) /循环至follow集不在增大check=0;for(x=0;x<unendsignnumber;x+)for( y=0;y<unendsignx.funnumber;y+)for( z=0;z<unendsignx.funy.length();z+)if(exit_unendsign(unendsignx.funyz)&&z<unendsignx.funy.length()-1)/p->.A kp=get_une

35、ndsign_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(unends

36、ignx.funyz);for(t=0;t<unendsignx.follownumber;t+)int ssp=unendsignkp.follownumber;unendsignkp.add_follow(unendsignx.followt);if(unendsignkp.follownumber!=ssp)check=1;if(exit_unendsign(unendsignx.funyz)&&z<unendsignx.funy.length()-1)int thischeck=1; / 判断p->.SABC 其中#在ABC的first集中for(in

37、t i=z+1;i<unendsignx.funy.length();i+)if(exit_unendsign(unendsignx.funyi)int thisthischeck=0;int kp=get_unendsign_number(unendsignx.funyi);for(int pp=0;pp<unendsignkp.firstnumber;pp+)if(unendsignkp.firstpp='#')thisthischeck=1;break;if(thisthischeck)continue;elsethischeck=0;break;thisch

38、eck=0;break;if(thischeck)int kp=get_unendsign_number(unendsignx.funyz); for(t=0;t<unendsignx.follownumber;t+)int ssp=unendsignkp.follownumber;unendsignkp.add_follow(unendsignx.followt);if(unendsignkp.follownumber!=ssp)check=1; for(x=0;x<unendsignnumber;x+) /非终结点在follow集则要把 其first集除#放入follow集fo

39、r(y=0;y<unendsignx.follownumber;y+)if(exit_unendsign(unendsignx.followy)int kp=get_unendsign_number(unendsignx.followy);for(t=0;t<unendsignkp.firstnumber;t+)if(unendsignkp.firstt='#')continue;elseint oop=unendsignx.follownumber;unendsignx.add_follow(unendsignkp.firstt);if(unendsignx.fo

40、llownumber!=oop)check=1;for(x=0;x<unendsignnumber;x+) /删除follow集中的非终结点for(int y=0;y<unendsignx.follownumber;y+)if(exit_unendsign(unendsignx.followy)unendsignx.pop_follow(unendsignx.followy);y-; void init_LL_table() /分析表初始化 int x,y;addendsign('$');table_unend_number=0;table_end_number=0

41、;for(x=0;x<unendsignnumber;x+)for(y=0;y<endsignnumber;y+)tablexy.cell_endsign=endsigny.id;tablexy.cell_unendsign=unendsignx.id;cout<<"init table begin:"<<endl;for(x=0;x<unendsignnumber;x+)for(y=0;y<endsignnumber;y+)cout<<tablexy.cell_unendsign<<":&q

42、uot;<<tablexy.cell_endsign<<" "cout<<endl;void deal_LL_table()/ 产生LL(1)文法分析表 int x,j,y,t;init_LL_table(); for(x=0;x<unendsignnumber;x+)for(y=0;y<unendsignx.funnumber;y+)int check=1;int i=0;while(check) /P->A #一直属于Aif(i=unendsignx.funy.length()break;check=0;if(exi

43、t_unendsign(unendsignx.funyi) /P->A 将A的first集的终结符 单元格 赋值P->Aint kp=get_unendsign_number(unendsignx.funyi);for(t=0;t<unendsignkp.firstnumber;t+)if(unendsignkp.firstt='#')check=1;i+;elseif(unendsignkp.firstt!='#') j=get_endsign_number(unendsignkp.firstt); tablexj.cell_fun=unen

44、dsignx.funy;else /p->a a是非终结符if(unendsignx.funyi!='#')j=get_endsign_number(unendsignx.funyi);tablexj.cell_fun=unendsignx.funy;if(unendsignx.funyi='#'&&i=0)check=1;break;if(check) /P->A如果#属于Afor(t=0;t<unendsignx.follownumber;t+)if(unendsignx.followt!='#') j=ge

45、t_endsign_number(unendsignx.followt); tablexj.cell_fun=unendsignx.funy;for(x=0;x<unendsignnumber;x+) /没有产生式的单元格标记为错误for(y=0;y<endsignnumber;y+) if(tablexy.cell_fun.length()>0)continue;else tablexy.cell_fun="error"void analizeLL_1() /预测分析程序string putin;char stackmax;int stacknumber

46、=0;stackstacknumber='$'stacknumber+;stackstacknumber=unendsign0.id;stacknumber+;cout<<"please enter:"cin>>putin;int x;for(x=0;x<putin.length();x+)cout<<putinx;if(!exit_endsign(putinx)|putinx='$'|putinx='#')cout<<" <- error no match sign"<<endl;return