【C++实现】编译原理 免考小队 消除一切左递归
P → βP′ P′ → αP′ | ϵ S → Qc | c Q → Rb | b R → Sa | a
发布日期:2021-06-29 14:32:29
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月17日 16时21分29秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Java Callable、Future、FutureTask
2019-04-29
Java 父线程与子线程相互通信的方法
2019-04-29
Java 逃逸分析
2019-04-29
Java 装饰模式
2019-04-29
Java 观察者模式
2019-04-29
Java ReentrantLock源码解读
2019-04-29
Java CompletableFuture
2019-04-29
缓存行、伪共享
2019-04-29
Redis 六种淘汰策略和三种删除策略
2019-04-29
Java LinkedHashMap
2019-04-29
PostgreSQL 关闭session链接
2019-04-29
JPA 多线程同时对一条数据进行Update的问题
2019-04-29
JPA 多线程对数据进行更新,Update和Insert同时存在的问题
2019-04-29
Java 高性能队列Disruptor
2019-04-29
SpringBoot 使用https
2019-04-29
Java 读写锁
2019-04-29
JVM Minor GC、Full GC和Major GC
2019-04-29
SpringBoot @Scheduled 执行两次的问题
2019-04-29
idea maven工程打jar包,运行出现xxx.jar中没有主清单属性的问题解决方法
2019-04-29