编译原理实验二：消除文法的左递归

编辑原理实验报告实验名称消除了语法的左边递归实验时间2013年11月12日本科计算机科学电子技术与第11类计算机软件JV JV JP名郯庐汉强强许事故1.测试目的：输入：所有上下文无关语法。输出：删除左递归的等效语法。实验原理：1.直接删除左侧递归直接从生成中移除左侧递归更容易。例如，假设终止元p以外的规则如下：PP/其中是不以p开头的符号字符串。可以将p的规则以非直接左递归形式重写，例如p PP/这两个规则与原始规则相同。也就是说，在p中，两种形式的符号字符串是相同的。简单表达式语法GE:EE T/TTT*F/FF(E)/I直接去掉左边递归后，得到以下语法。ETE E TE/TFT T *FT/F(E)/I考虑到更常见的情况，对于不是终结器p的规则，假定PP1/P2 PP1/P2/Pn/1/2/mm其中 I (I=1，2，n)不是，而是每个 j (j=1，2，m)不以p开头，可以通过以下方式替换上述规则，直接删除p的左递归：P 1 P1 P/2 P /m P m p P 1p/ 2p/./ n p/间接左递归删除直接左侧递归在曲面上可见，因此使用这些方法可以很容易地将其移除。也就是说，可以直接用右边的递归代替左边的递归。但是语法表面没有左递归并不意味着语法没有左递归。有些语法表面上没有左递归，但隐藏着左递归。例如，语法GS:SQc/cQRb/bRSa/a没有左递归，但s，q，r被诱导多次，所以都是左递归SQcRbcSabcQbsabbcabRSaQcaRbca看到左边的递归性。间接左递归语法。可以直接用左递归语法重写间接左递归语法，然后通过删除直接左递归来重写语法，从而消除间接左递归。如果语法没有循环(像PP这样的导数，没有以为右部分的生成)，则可以使用以下算法消除语法中的所有左递归：移除左边的递回演算法：(1)所有非终结器(例如A1、A2、An)按语法g的顺序排列。(2)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规则中直接删除左侧递归。(3)简化结果语法(2)，就是消除不必要的规则。使用此算法，可以重写上述语法，消除左递归。首先，将非终结器与r、q、s对齐。对于r，没有直接左递归。将r赋予Q的相关规则会将Q的规则更改为QSab/ab/b。替代q在S中不直接包含左侧递归，S的规则更改为SSabc/abc/bc/c。此时，s有直接的左边递归。去掉s的直接左递归后，整个语法如下：s“abcS”/bcS/cSS abcS/QSab/ab/bRSa/a从语法开始符号S开始，可以知道永远达不到q和r，所以q和r的规则是不必要的，删除并简化，然后得到语法GS。SabcS/bcS/cSS abcS/当然，如果对终结器进行不同的排序，结果语法在形式上可能会有所不同，但都是对等的。例如，如果选取上述非终止元排序为s、q、R，则产生的语法GR为r bcar/car/arR bcaR/很容易证明上述两种语法是相同的。3 .实验内容：移除左边的递回演算法：(4)语法g中的所有非终结器，按任意顺序(例如，A1，A2，An)。(5)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规则中直接删除左侧递归。(6)简化结果语法(2)，就是消除不必要的规则。使用此算法，可以重写上述语法，消除左递归。注意事项：指示是否有左递归，以及左递归的类型。对于直接左递归，可以直接更改为右递归。对于间接左递归(也称为语法左递归)，必须根据算法删除非终结器数组的等价性，以消除左递归后的语法。(必须有n！物种)4.实验代码和结果：# include“stdafx . h”#include#include#define N 20char PNN；/规则集char QN；/间接左递归删除后保存某些规则的规则集char RNN；/用于存储规则的初始值int r；/实际输入的规则数int direct(char PNN)；/直接左递归函数int indirect(char PNN)；/间接左递归函数void direct remove(char PNN)；/直接删除左侧递归函数void indirect remove(char PNN)；/间接删除左侧递归函数Int direct(char PNN) /直接定义左侧递归函数int flag=0；for(int I=0)；I0)“Printf()”被认为语法直接包含左边递归！ n )；return 1；/直接属于左侧递归Elsereturn 0；/不直接属于左侧递归定义Int indirect(char PNN) /间接左递归函数int flag=0；for(int I=0)；I0)BreakIf(flag0)Printf()判断语法包含间接左递归！ n )；return 2；/属于间接左递归Elsereturn 0；/不属于间接左递归void direct remove(charpnn)/定义直接删除左侧递归的函数int j=4；for(int I=0)；I1)复制；/如果有相同的左部门，则规则总数会加上一个for(I=0)；I=4；S-)PI ks t-1=PI ks；for(int u=3)；u3 t；u)PI ku=PIu；Breakelse if(pI0=rg3)(flag 1=1)for(int y=0)；Rgy！=0；y)pcopy-1y=Rgy；int m=3；While(Pim)！=0) /统计替换字符数为m-1-2m；int t=m-3；int n=4；While(Pcopy-1n)！=0) /被统计取代的规则的非终止元数目为n-4n；for(int s=