消除左递归实验报告.doc

编译原理实验报告实验名称消除文法左递归_____实验时间12月12日___院系软件工程____________班级软件工程(2)班_____学号E01214215___________姓名刘翼______________实验目的:输入:任意的上下文无关文法。输出:消除了左递归的等价文法。实验原理:。例如假设非终结符P的规则为P→Pα/β其中,β是不以P开头的符号串。那么,我们能够把P的规则改写为如下的非直接左递归形式: P→βP’ P’→αP’/ε这两条规则和原来的规则是等价的,即两种形式从P推出的符号串是相同的。设有简单表达式文法G[E]:E→E+T/TT→T*F/FF→(E)/I经消除直接左递归后得到如下文法:E→TE’E’→+TE’/εT→FT’T’→*FT’/εF→(E)/I考虑更一般的情况,假定关于非终结符P的规则为P→Pα1/Pα2/…/Pαn/β1/β2/…/βm其中,αi(I=1,2,…,n)都不为ε,而每个βj(j=1,2,…,m)都不以P开头,将上述规则改写为如下形式即可消除P的直接左递归:P→β1P’/β2P’/…/βmP’P’→α1P’/α2P’/…/αnP’/,利用以上的方法能够很容易将其消除,即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归,但却隐藏着左递归。例如,设有文法G[S]:S→Qc/cQ→Rb/bR→Sa/a虽不具有左递归,但S、Q、R都是左递归的,因为经过若干次推导有SQcRbcSabcQRbSabQcabRSaQcaRbca就显现出其左递归性了,这就是间接左递归文法。消除间接左递归的方法是,把间接左递归文法改写为直接左递归文法,然后用消除直接左递归的方法改写文法。如果一个文法不含有回路,即形如PP的推导,也不含有以ε为右部的产生式,那么就能够采用下述算法消除文法的所有左递归。消除左递归算法:把文法G的所有非终结符按任一顺序排列,例如,A1,A2,…,An。for(i=1;i<=n;i++)for(j=1;j<=i-1;j++) { 把形如Ai→Ajγ的产生式改写成Ai→δ1γ/δ2γ/…/δkγ 其中Aj→δ1/δ2/…/δk是关于的Aj全部规则; 消除Ai规则中的直接左递归;}化简由(2)所得到的文法,即去掉多余的规则。利用此算法能够将上述文法进行改写,来消除左递归。首先,令非终结符的排序为R、Q、S。对于R,不存在直接左递归。把R代入到Q中的相关规则中,则Q的规则变为Q→Sab/ab/b。代换后的Q不含有直接左递归,将其代入S,S的规则变为S→Sabc/abc/bc/c。此时,S存在直接左递归。在消除了S的直接左递归后,得到整个文法为: S→abcS’/bcS'/cS' S’→abcS'/ε Q→Sab/ab/b R→Sa/a能够看到从文法开始符号S出发,永远无法达到Q和R,所以关于Q和R的规则是多余的,将其删除并化简,最后得到文法G[S]为: S→abcS'/bcS’/cS' S'→abcS'/ε当然如果对文法非终结符排序的不同,最后得到的文法在形式上可能不一样,但它们都是等价的。例如,如果对上述非终结符排序选为S、Q、R,那么最后得到的文法G[R]为:R→bcaR'/caR'/aR’ R'→bcaR'/ε容易证明上述两个文法是等价的。实验内容:指明是否存在左递归,以及左递归的类型。对于直接左递归,可将其改为直接右递归;对于间接左递归(也称文法左递归),则应按照算法给出非终结符不同排列的等价的消除左递归后的文法。(应该有n!种)实验代码与结果:#include<>#include<>#include<>#defineN20charP[N][N];//存放文法charQ[N];//存放非终结符charR[N][N];//存放含有间接左递归的产生式charstr[N][N],str1[N][N];intsp[N];//标记无用的产生式intr,count=0,count1=0;intdirect(charP[N][N]);//判断直接左递归intindirect(charP[N][N]);//判断间接左递归voiddirectRemove(charP[N][N]);//消除直接左递归voidindirectRemove(charP[N][N]);//消除间接左递归voidperm(charstr[N][N],inti,intn);//实现全排列intmain(){printf("请输入文法P产生式的个数:");scanf("%d/n",&r);printf("请输入各条产生式,产生式的左部跟右部用->连接:\n")