logo资料库

消除左递归.docx

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.11M 资料格式：docx 举报 版权申诉
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页，全文预览结束
    1．直接左递归的消除
    2．间接左递归的消除
    编译原理课程设计 消除左递归 040930421 李沛斌
    1.试验目的 输入：任意的上下文无关文法。 输出：消除了左递归的等价文法。 2.实验原理 1．直接左递归的消除 消除产生式中的直接左递归是比较容易的。例如假设非终结符 P 的规则为 P→Pα / β 其中，β是不以 P 开头的符号串。那么，我们可以把 P 的规则改写为如下的非直 接左递归形式： P→βP’ P’→αP’ / ε 这两条规则和原来的规则是等价的，即两种形式从 P 推出的符号串是相同的。 设有简单表达式文法 G[E]： E→E+T/ T T→T*F/ F F→（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→β1 P’ / β2 P’ /…/βm P’ P’ →α1P’ / α2 P’ /…/ αn P’ /ε 2．间接左递归的消除 直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左 递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存 在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设 有文法 G[S]： S→Qc/ c Q→Rb/ b R→Sa/ a 虽不具有左递归，但 S、Q、R 都是左递归的，因为经过若干次推导有 S Qc Rbc Sabc
    Q Rb Sab Qcab R Sa Qca Rbca 就显现出其左递归性了，这就是间接左递归文法。 消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后 用消除直接左递归的方法改写文法。  如果一个文法不含有回路，即形如 P P 的推导，也不含有以ε为右部的产 生式，那么就可以采用下述算法消除文法的所有左递归。 消除左递归算法： （1） 把文法 G 的所有非终结符按任一顺序排列，例如，A1，A2，…，An。 （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 的规则变为 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'/ ε 容易证明上述两个文法是等价的。 3..实验内容 消除左递归算法： (1)把文法 G 的所有非终结符按任一顺序排列，例如，A1，A2，…，An。 (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）所得到的文法，即去掉多余的规则。 利用此算法可以将上述文法进行改写，来消除左递归。 4.实验代码 #include #include #include using std::cin; using std::cout; using std::endl; using std::string; using std::fstream; const int size=10; string gene[size],temp[size]; int main() { int i=0,count=0; cout<<"\t\t 输入 1 表示直接输入文法\n\t\t 输入表示其他退出!"<>i; if(i==1) { cout<<"请输入文法的行数："<>count; cout<<"请输入文法："<>gene[i]; } else return 0; cout<<"原文法为："<
    start=2; char qj=gene[j][0]; //修改每一条满足条件的产生式 bool rgt=false; int count1=0; string tt[size]; size_t s=0; size_t e=0; do { start++; if(gene[i][start]==qj)//如果满足 pi->qj*; { size_t es=gene[i].find_first_of("|",start+1); if(es==string::npos) es=gene[i].length(); string te=gene[i].substr(start+1,es-start-1); if(!rgt) { s=gene[j].find_first_not_of("|",3); while(s!=string::npos) { e=gene[j].find_first_of("|",s+1); if(e==string::npos) e=gene[j].length(); tt[count1]=gene[j].substr(s,e-s); count1++; s=gene[j].find_first_not_of("|",e+1); } rgt=true; } int k=0; string ttl="\0"; for(;k
    char ch=gene[i][0]; bool rg=false; while(sss!=string::npos) { eee=gene[i].find_first_of("|",sss+1); if(eee==string::npos)eee=gene[i].length(); if(gene[i][sss]==ch) { rg=true; p1+=gene[i].substr(sss+1,eee-sss-1)+ch+"\'|"; } else { p2+=gene[i].substr(sss,eee-sss)+ch+"\'|"; } sss=gene[i].find_first_not_of("|",eee+1); } p2[p2.length()-1]='\0'; if(rg) { temp[count2]=ch+("\'->"+p1+"ε"); count2++; gene[i].replace(3,gene[i].length()-3,p2); } } cout<<"消除递归后的文法为："<
    消除间接左递归： 6.实验心得  一个文法是含有左递归的，如果存在非终结符 P ，P  Pα 含有左递归的文法将使上述的自上而下的分析过程陷入无限循环，即当试图 用 P 去匹配输入串时，就会出现在没有吃进任何输入符号的情况下，又得重新要
    求 P 去进行新的匹配。因此，使用自上而下分析法必须消除文法的左递归性。  对文法中一切左递归的消除要求文法中不含回路即无 A A 的推导。满足这个要 求的充分条件是：文法中不包含形如 A→A 和 A→ε的空产生式。 根据消除左递归的算法步骤我们可以得出整个程序思路。对于产生式的存储问题， 采用定义产生式的结构体，再用表的形式来存储所有的产生式。再输入存储时就 将产生式的左部和右部分开存储于产生式结构体中，方便后面的操作。在消除左 递归的过程中，对于直接左递归，可将其改为直接右递归；对于间接左递归（也 称文法左递归），则应按照算法给出非终结符不同排列的等价的消除左递归后的 文法。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料