本文共 3335 字，大约阅读时间需要 11 分钟。

背景

期末考试免考，冲！

实验名称

消除一切左递归

实验时间

2020年5月27日 到 2020年5月31日

院系

信息科学与工程学院

组员姓名

Chocolate、kry2025、钟先生、leo、小光

实验环境介绍

• windows 10 操作系统
• Eclipse 进行 java 编程
• CodeBlocks 进行 C++ 编程

实验目的与要求

目的

• 深刻理解左递归的算法
• 掌握消除左递归的过程
• 加强团队合作能力
• 提高自身的编程能力和解决问题的能力

要求

• 编程实现消除一切左递归
• 算法简洁，不冗余

解决问题

产生式直接消除左递归

形如 P → Pα | β 可以通过直接消除转化为：

产生式间接消除左递归

有时候虽然形式上产生式没有递归，但是因为形成了环，所以导致进行闭包运算后出现左递归，如下：

虽不具有左递归，但S、Q、R都是左递归的，因为经过若干次推导有

• SQcRbcSabc
• QRbSabQcab
• RSaQcaRbca

就显现出其左递归性了，这就是间接左递归文法。

消除间接左递归的方法是:

把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。

如果一个文法不含有回路，即形如PP的推导，也不含有以ε为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。

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规则中的直接左递归；   }

实验结果

源代码

#include
   
    #define endl '\n'using namespace std;const int maxn=100+5;char buf[maxn];   //输入产生式int n;   //产生式的数量class node{
   public:    string left;  //产生式左部    set
    
      right; //产生式右部    node(const string& str){
           left=str;        right.clear();    }    void push(const string& str){
           right.insert(str);    }    void print(){
           printf("%s->",left.c_str());        set
     
      ::iterator it = right.begin();        printf("%s",it->c_str());        it++;        for (;it!= right.end();it++ )            printf("|%s",it->c_str());        cout<
      
        mp;  //记录每个node的下标vector
       
         vnode;  //每一个产生式string start;   //文法G[s]bool used[maxn];  //用于去掉无用产生式//初始化工作void init(){
       mp.clear();    vnode.clear();    start="S";}//消除间接左递归void eliminateIndirectLeftRecursion(){
       for(int i=0;i
        
          ans; set
         
          & righti=vnode[i].right; set
          
           & rightj=vnode[j].right; char ch=vnode[j].left[0]; //取所有Aj产生式的左部的非终结符 set
           
            ::iterator iti,itj; for(iti=righti.begin();iti!=righti.end();iti++){ if(iti->at(0)==ch) //如果当前产生式右部的非终结符和Aj相同 for(itj=rightj.begin();itj!=rightj.end();itj++) ans.push_back(*itj+iti->substr(1)); //进行替换操作,先存储起来 } while(!righti.empty()){ if(righti.begin()->at(0)!=ch) //存储当前没有替换的产生式右部 ans.push_back(*righti.begin()); righti.erase(righti.begin()); //被替换过的产生式右部也删除掉 } for(int k=0;k
            
             & right=vnode[i].right; //拿到当前右部 set
             
              ::iterator it; string tmp=vnode[i].left.substr(0,1)+"\'"; //对非终结符更改 bool flag=true; for(it=right.begin();it!=right.end();it++){ if(it->at(0)==ch){ vnode.push_back(node(tmp)); mp[tmp]=vnode.size(); flag=false; break; } } int idx=mp[tmp]-1; if(flag) continue; //对于非终结符不相同的产生式我们需要跳过 vector
              
                ans; set
               
                & tmpSet=vnode[idx].right; tmpSet.insert("~"); //添加空字符 while(!right.empty()){ if(right.begin()->at(0)==ch) tmpSet.insert(right.begin()->substr(1)+tmp); else ans.push_back(right.begin()->substr(0)+tmp); right.erase(right.begin()); //删除掉原本产生式右部 } for(int k=0;k
                
                 ::iterator it=vnode[x].right.begin(); for(;it!=vnode[x].right.end();it++){ for(int i=0;i
                 
                  length();i++){ if(isupper(it->at(i))){ //判断是否是大写字母 if(i+1
                  
                   length() && it->at(i+1)=='\'') //如果当前是替换的那个字符 dfs(mp[it->substr(i,2)]-1); else dfs(mp[it->substr(i,1)]-1); } } }}//去掉无用产生式void removeUselessProduction(){ memset(used,0,sizeof(used)); int idx=mp[start]-1; dfs(idx); //搜索 cout<<"最终文法："<
                   
                     res; for(int i=0;i
                    
                     >n){ init(); //初始化 getchar(); cout<<"依次输入文法G[S]的产生式："<
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

输出结果

测试样例

6S->QcS->cQ->RbQ->bR->SaR->a6R->SaR->aQ->RbQ->bS->QcS->c6Q->RbQ->bR->SaR->aS->QcS->c6Q->RbR->SaQ->bS->QcR->aS->c

参考文献

感谢以下博主的文章，本文参考了部分代码和知识。

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/106395934 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！