编译原理实验八：非LL(1)文法到LL(1)文法的转换.doc

实验八：非LL(1)文法到LL(1)文法的转换一：要求输入：非LL(1)文法输出：LL(1)文法二：实验目的1掌握LL(1)文法2熟悉运用C+语言对消除左递归的使用三：实验原理直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为PP / 其中，是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式： PP PP / 这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。 设有简单表达式文法GE： EE+T/ T TT*F/ F F（E）/ I经消除直接左递归后得到如下文法： ETE E +TE/ TFTT *FT/ F（E）/ I考虑更一般的情况，假定关于非终结符P的规则为PP1 / P2 / Pn / 1 / 2 /m其中，i（I1，2，n）都不为，而每个j（j1，2，m）都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归：P1 P / 2 P /m PP 1P / 2 P / n P /间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设有文法GS：SQc/ cQRb/ bRSa/ a虽不具有左递归，但S、Q、R都是左递归的，因为经过若干次推导有SQcRbcSabcQRbSabQcabRSaQcaRbca就显现出其左递归性了，这就是间接左递归文法。消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。如果一个文法不含有回路，即形如PP的推导，也不含有以为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。消除左递归算法：（1） 把文法G的所有非终结符按任一顺序排列，例如，A1，A2，An。（2） for （i1；i=n；i+）for （j1；j=i1；j+）把形如AiAj的产生式改写成Ai1 /2 /k 其中Aj1 /2 /k是关于的Aj全部规则； 消除Ai规则中的直接左递归； （3） 化简由（2）所得到的文法，即去掉多余的规则。利用此算法可以将上述文法进行改写，来消除左递归。首先，令非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q中的相关规则中，则Q的规则变为QSab/ ab/ b。代换后的Q不含有直接左递归，将其代入S，S的规则变为SSabc/ abc/ bc/ c。此时，S存在直接左递归。在消除了S的直接左递归后，得到整个文法为：SabcS/ bcS/ cSS abcS/ QSab/ ab/ bRSa/ a可以看到从文法开始符号S出发，永远无法达到Q和R，所以关于Q和R的规则是多余的，将其删除并化简，最后得到文法GS为：SabcS/ bcS/ cSS abcS/ 当然如果对文法非终结符排序的不同，最后得到的文法在形式上可能不一样，但它们都是等价的。例如，如果对上述非终结符排序选为S、Q、R，那么最后得到的文法GR为： RbcaR/ caR/ aRR bcaR/ 容易证明上述两个文法是等价的。四：数据结构与算法typedef struct Chomsky /定义一个产生式结构体 string left; /定义产生式的左部 string right; /定义产生式的右部Chomsky;void apart(Chomsky *p,int i) /分开产生式左右部，i代表产生式的编号int zero(Chomsky *p)/0型文法int one(Chomsky *p)/1型文法int two(Chomsky *p)/2型文法int remove(Chomsky *p,int n)/消除左递归五：出错分析1：空符号表示错误，前后不一致2：文法判断参数传递错误六：实验结果与分析不是二型文法的：是二型文法的：七：源代码#include#includeusing namespace std;typedef struct Chomsky /定义一个产生式结构体 string left; /定义产生式的左部 string right; /定义产生式的右部Chomsky;int n;/产生式总数string strings;/存储产生式char q20;void apart(Chomsky *p,int i) /分开产生式左右部，i代表产生式的编号int j; for(j=0;jstrings.length();j+)if(stringsj=-)pi.left=strings.substr(0,j);/从0开始的j长度的子串，即0j-1pi.right=strings.substr(j+1,strings.length()-j);/从j+1开始的后面子串int zero(Chomsky *p)/0型文法int flag(0),count(0); int i,j; for(i=0;in;i+) for(j=0;j=A&pi.leftj0)/说明某一个产生式左部有非终结符flag=0;/下个产生式判断前清零count+;/左部存在非终结符的产生式 个数加1else break; /左部没有非终结符，结束if(count=n) return 1; /属于0型文法elsecoutendl所输产生式不属于任何文法。endl;return 0;int one(Chomsky *p)/1型文法int flag(0); int i; if(zero(p)for(i=0;in;i+) if(pi.right.length()0)coutendl此文法属于0型文法，即短语文法。endl; return 0; /不属于1型文法else if(flag=0)return 1; /属于1型文法elsereturn 0;int two(Chomsky *p)/2型文法int flag(0); int i; if(one(p)for(i=0;i=A&pi.left00)coutendl此文法属于1型文法，即上下文有关文法。endl; return 0; /不属于2型文法else if(flag=0)return 1; /属于2型文法elsereturn 0;int remove(Chomsky *p,int n)/消除左递归/把文法的所有非终结符按某一顺序排序 int i,j,count=1,count1=n,flag=0,m,x; q0=p0.left0; for(i=1;in;i+) for(j=0;ji;j+)if(pi.left=pj.left)break;if(j=i)qcount+=pi.left0; count-; for(i=0;in;i+)/判断第一个非终结符是否存在直接左递归 if(pi.left0=q0&pi.left0=pi.right0) flag+;if(flag!=0)/消除第一个非终结符的直接左递归 for(i=0;in;i+) if(pi.left0=q0) if(pi.left0=pi.right0) pi.left=pi.left+; pi.right=pi.right.substr(1,pi.right.length()+pi.left; elsepi.right=pi.right+pi.left+; pcount1.left=p0.left; pcount1+.right=#;/用#代替空产生式 /消一切左递归 for(m=0;m=count;m+) for(i=0;in;i+) if(pi.left0=qm) for(j=0;jcount1;j+) for(x=m+1;x=count;x+) if(pj.left0=qx&pj.right0=qm) pcount1.left=pj.left; pcount1.right=pi.right+pj.right.substr(1,pj.right.length(); count1=count1+1; for(j=0;jcount1;j+) for(x=m+1;x=count;x+) if(pj.right0=qm&pj.left0=qx) pj.right=;pj.left=; for(x=0,flag=0;xcount1;x+)/判断第m个非终结符是否存在直接左递归 if(px.left0=qm&px.left0=px.right0) flag+; /消直接左递归if(flag!=0) for(i=0;icount1;i+)if(pi.left0=qm) if(pi.left0=pi.right0) pi.left=pi.left+; pi.right=pi.right.substr(1,pi.right.length()+pi.left; pcount1.left=pi.left; pcount1.right=#;/用#代替空产生式 else pi.right=pi.right+pi.left+; count1=count1+1; count1-; return count1;void main( )int i,j,count1;cout.编译原理实验八：非LL(1)文法到LL(1)文法的转换.endl; cout请输入产生式总数及各产生式：endl其中左右部之间用-表示，空用#表示n;Chomsky *p=new Chomsky50; / 初始化产生式数组for(i=0;istrin