原理
数据结构
// GO
private static Map<Map<Integer,String>,Integer> GO
= new HashMap<Map<Integer,String>,Integer>(); // 规范族集 C
private static Map<Integer,Map<String,List<String>>> C
= new HashMap<Integer, Map<String, List<String>>>(); // 文法 G
private static Map<String,List<String>> G = new HashMap<String, List<String>>(); // 文法 G’
private static List<String> Gc = new ArrayList<String>(); // 文法的项目
private static Map<String,List<String>> GItems = new HashMap<String, List<String>>(); // ACTION 表
private static Map<Map<Integer,String>,String> ACTION
= new HashMap<Map<Integer,String>,String>(); // GOTO 表
private static Map<Map<Integer,String>,Integer> GOTO
= new HashMap<Map<Integer,String>,Integer>();
这个结构很清晰，不解释
算法步骤
在每个文法适当位置插入特殊字符圈，构成新的文法的项目GItems,这一步可以在输入的时候完成
例如有文法产生式为
E=[aA, bB]
则得到的文法的项目应该是，这里用*号代表圈
E=[*aA, a*A, aA*, *bB, b*B, bB*]
根据文法的项目构造识别活前缀的有限自动机DFA，如图
构造文法的规范族集
按图以对其中的每一项编号即可得到规范族集C={I0,I1,I2,....,In}
输入
S'->E
E->aA|bB
A->cA|d
B->cB|d
完整算法
package org.lyh.app; import java.io.*;
import java.util.*; public class Main { private static Integer I = 0;
// GO
private static Map<Map<Integer,String>,Integer> GO
= new HashMap<Map<Integer,String>,Integer>(); // 规范族集 C
private static Map<Integer,Map<String,List<String>>> C
= new HashMap<Integer, Map<String, List<String>>>(); // 文法 G
private static Map<String,List<String>> G = new HashMap<String, List<String>>(); // 文法 G’
private static List<String> Gc = new ArrayList<String>(); // 文法的项目
private static Map<String,List<String>> GItems = new HashMap<String, List<String>>(); // ACTION 表
private static Map<Map<Integer,String>,String> ACTION
= new HashMap<Map<Integer,String>,String>(); // GOTO 表
private static Map<Map<Integer,String>,Integer> GOTO
= new HashMap<Map<Integer,String>,Integer>(); public static void main(String[] args) throws Exception { FileReader fr = new FileReader("main.in");
BufferedReader br = new BufferedReader(fr); String line = null;
while((line = br.readLine()) != null){ // 构造文法 String [] pLine = line.split("->");
List<String> pLineValues = G.get(pLine[0]);
if(null == pLineValues) pLineValues = new ArrayList<String>();
pLineValues.addAll(Arrays.asList(pLine[1].split("\\|")));
G.put(pLine[0], pLineValues); for (String val : pLineValues){
String pStr = pLine[0]+"->"+val;
if(!Gc.contains(pStr)) Gc.add(pStr);
}
// 构造文法的项目，这里以*代替书上的圆点 List<String> pItemValues = GItems.get(pLine[0]);
if(null == pItemValues) pItemValues = new ArrayList<String>();
for(Iterator<String> iterator = pLineValues.iterator();iterator.hasNext();){
String pValueItem = iterator.next();
for (int i=0;i<pValueItem.length();i++){
String newItem = new StringBuilder(pValueItem).insert(i, "*").toString();
pItemValues.add(newItem);
}
pItemValues.add(pValueItem+"*");
}
GItems.put(pLine[0], pItemValues);
}
fr.close();
br.close(); System.out.println("文法G：" + G);
System.out.println("文法G'："+Gc);
System.out.println("文法G的项目："+GItems); // 构造项目集规范族
// 这里将问题稍稍简化，假设S'对应的第一个项目为初态
initC("S'", "*E");
System.out.println("C："+C);
System.out.println("GO："+GO); // 构造ACTION表和GOTO表
// 首先考虑最开始的情况
Map<Integer,String> acKey = new HashMap<Integer,String>();
acKey.put(0,"#");
ACTION.put(acKey,"acc");
// 遍历 项目集规范族 C
for(Iterator<Map.Entry<Integer,Map<String,List<String>>>> iterator
= C.entrySet().iterator();
iterator.hasNext();){
Map.Entry<Integer,Map<String,List<String>>> CI
= iterator.next();
//System.out.println(iterator.next());
// 扫描 CI ,switch判断每条文法
int k = CI.getKey();
Map<String,List<String>> values = CI.getValue();
for (Iterator<Map.Entry<String,List<String>>> mapIterator
= values.entrySet().iterator();mapIterator.hasNext();){
Map.Entry<String,List<String>> value = mapIterator.next();
String pLeft = value.getKey();
List<String> pRightValues = value.getValue();
for(int x = 0;x<pRightValues.size();x++){
String pRightVal = pRightValues.get(x);
System.out.println("K:"+k+" "+pLeft+"->"+pRightVal);
String a = null;
Integer GOka = 0;
Map<Integer,String> ka = new HashMap<Integer,String>(); if(pRightVal.matches("\\w*\\*[a-z]{1}\\w*")){
// 形如 A-> 。。。。 书上第一种情况
a = pRightVal.charAt(pRightVal.indexOf("*")+1)+"";
// System.out.println(a);
ka.put(k, a);
int j = GO.get(ka);
// System.out.println(j);
Map<Integer,String> key = new HashMap<Integer,String>();
key.put(k,a);
ACTION.put(key,"S"+j);
}
else if(pRightVal.matches("\\w*\\*$")){
// 形如书上第二种情况
// 扫描这个文法串
int j = 0;
j = Gc.indexOf(pLeft+"->"
+pRightVal.substring(0,pRightVal.length()-1));
for(int r = 0;r<pRightVal.length();r++){
char vti = pRightVal.charAt(r);
if(vti >= 'a' && vti <= 'z'){
// 是非终结符
// 置ACTION[k,a] 为 rj
Map<Integer,String> key = new HashMap<Integer,String>();
key.put(k,vti+"");
// 在G‘中查找A->r 得到j if(j>=0) ACTION.put(key,"r"+j);
}
}
Map<Integer,String> key = new HashMap<Integer,String>();
key.put(k,"#");
ACTION.put(key,"r"+j);
}
}
} } // GOTO表
// 判断 GO（Ik,A） == Ij
// 扫描 GO 表
for (Iterator<Map.Entry<Map<Integer,String>,Integer>> goit = GO.entrySet().iterator();
goit.hasNext();){
Map.Entry<Map<Integer,String>,Integer> goi = goit.next();
Map<Integer,String> gKey = goi.getKey();
//System.out.println("gKey:"+gKey);
int k =((Integer) gKey.keySet().toArray()[0]);
char A = ((String)gKey.values().toArray()[0]).charAt(0);
// System.out.println(A);
if(A >= 'A' && A <= 'Z'){
Map<Integer,String> gotoKey = new HashMap<Integer,String>();
gotoKey.put(k,A+"");
GOTO.put(gotoKey,goi.getValue());
}
} System.out.println("ACTION 表："+ACTION);
System.out.println("GOTO 表："+GOTO);
} private static void initC(String start, String pValue) { Map<String,List<String>> CI = new HashMap<String,List<String>>();
//List<String> pValues = GItems.get(start);
List<String> startCIValues = new ArrayList<String>();
startCIValues.add(pValue);
CI.put(start, startCIValues); System.out.println(start + "->" + pValue); int new_index = pValue.indexOf("*") + 1;
if(new_index != pValue.length()){
// 找到key为E（newStart）的右部以*a(这里a是终结符)的产生式，一并加到CI中
String newStart = pValue.substring(new_index,new_index+1);
List<String> seValues = GItems.get(newStart); List<String> newStartCIValues = newStart.equals(start)
? startCIValues : new ArrayList<String>(); //System.out.println(seValues);
for (String value : seValues){
if(value.matches("^\\*[a-z]{1}\\w*")){
newStartCIValues.add(value);
System.out.println(newStart+"->"+value);
}
} CI.put(newStart, newStartCIValues); C.put(I,CI);
int curI = I;
I++; String VC = ""+pValue.charAt(new_index);
Map<Integer,String> GOI = new HashMap<Integer,String>();
GOI.put(curI,VC);
GO.put(GOI,I); System.out.println("------------");
// 将第一条程式的圆点移动到下一位
StringBuilder sb = new StringBuilder(pValue);
sb.deleteCharAt(new_index-1).insert(new_index, "*");
String newPValue = sb.toString();
// 对第一条程式进行递归查找
initC(start, sb.toString()); // 将下面程式的原点移动到下一位
for(String value : newStartCIValues){ sb.delete(0, sb.length());
sb.append(value);
int x_index = sb.indexOf("*"); VC = ""+value.charAt(x_index+1);
GOI = new HashMap<Integer,String>();
GOI.put(curI,VC);
// 下移一位
sb.deleteCharAt(x_index).insert(x_index + 1, "*");
if(!pValue.equals(sb.toString())){
// 判断C当中是否已经存在这个程式
Map<String,List<String>> _this = new HashMap<String,List<String>>();
List<String> v = new ArrayList<String>();
v.add(sb.toString());
_this.put(newStart,v);
// 查找是否已经存在这个CI了
boolean has = false;
int exist_key = 0;
Set<Integer> keys = C.keySet();
for (Integer key : keys){
// 找到这个ID
if(C.get(key).equals(_this)){
//System.out.println("存在重复");
has = true;
exist_key = key;
break;
}
}
if(has){
//System.out.println("存在重复");
// 将 GO 的值 指向这个已经存在的
GO.put(GOI,exist_key);
}
else{
// 正常新建一个CI
GO.put(GOI,I);
initC(newStart, sb.toString());
}
}else{
// 指向自身
//System.out.println("指向自身");
GO.put(GOI,curI);
}
}
}
else{
System.out.println("------------");
C.put(I,CI);
I++;
} } }
运行结果
文法G：{E=[aA, bB], S'=[E], A=[cA, d], B=[cB, d]}
文法G'：[S'->E, E->aA, E->bB, A->cA, A->d, B->cB, B->d]
文法G的项目：{E=[*aA, a*A, aA*, *bB, b*B, bB*], S'=[*E, E*], A=[*cA, c*A, cA*, *d, d*], B=[*cB, c*B, cB*, *d, d*]}
S'->*E
E->*aA
E->*bB
------------
S'->E*
------------
E->a*A
A->*cA
A->*d
------------
E->aA*
------------
A->c*A
A->*cA
A->*d
------------
A->cA*
------------
A->d*
------------
E->b*B
B->*cB
B->*d
------------
E->bB*
------------
B->c*B
B->*cB
B->*d
------------
B->cB*
------------
B->d*
------------
C：{0={E=[*aA, *bB], S'=[*E]}, 1={S'=[E*]}, 2={E=[a*A], A=[*cA, *d]}, 3={E=[aA*]}, 4={A=[c*A, *cA, *d]}, 5={A=[cA*]}, 6={A=[d*]}, 7={E=[b*B], B=[*cB, *d]}, 8={E=[bB*]}, 9={B=[c*B, *cB, *d]}, 10={B=[cB*]}, 11={B=[d*]}}
GO：{{2=d}=6, {7=B}=8, {4=c}=4, {4=A}=5, {0=E}=1, {7=c}=9, {0=b}=7, {7=d}=11, {4=d}=6, {2=c}=4, {2=A}=3, {0=a}=2, {9=d}=11, {9=c}=9, {9=B}=10}
K:0 E->*aA
K:0 E->*bB
K:0 S'->*E
K:1 S'->E*
K:2 E->a*A
K:2 A->*cA
K:2 A->*d
K:3 E->aA*
K:4 A->c*A
K:4 A->*cA
K:4 A->*d
K:5 A->cA*
K:6 A->d*
K:7 E->b*B
K:7 B->*cB
K:7 B->*d
K:8 E->bB*
K:9 B->c*B
K:9 B->*cB
K:9 B->*d
K:10 B->cB*
K:11 B->d*
ACTION 表：{{1=#}=r0, {2=d}=S6, {5=c}=r3, {0=#}=acc, {4=c}=S4, {7=c}=S9, {3=#}=r1, {6=d}=r4, {0=b}=S7, {3=a}=r1, {5=#}=r3, {7=d}=S11, {4=d}=S6, {6=#}=r4, {0=a}=S2, {2=c}=S4, {11=d}=r6, {8=#}=r2, {11=#}=r6, {10=#}=r5, {9=d}=S11, {9=c}=S9, {8=b}=r2, {10=c}=r5}
GOTO 表：{{0=E}=1, {4=A}=5, {7=B}=8, {2=A}=3, {9=B}=10}
Process finished with exit code 0
求LR(0)文法的规范族集和ACTION表、GOTO表的构造算法的更多相关文章
-
编译原理LR(0)项目集规范族的构造详解
转载于https://blog.csdn.net/johan_joe_king/article/details/79051993#comments 学编译原理的时候,感觉什么LL(1).LR(0).S ...
-
LR(0)文法项目集规范族、DFA和分析表的构建实例
最近在复习编译原理,考试之前以为自己懂了,眼高手低就没去实践.结果一考试出问题了.... 学习就要脚踏实地,容不得半点模糊.凭着侥幸心理很危险的.以后要引以为戒啊. 特别写出这篇文章 :一来总结一下这 ...
-
编译原理根据项目集规范族构造LR(0)分析表
转载于https://blog.csdn.net/Johan_Joe_King/article/details/79058597?utm_medium=distribute.pc_relevant.n ...
-
LL(1),LR(0),SLR(1),LR(1),LALR(1)的 联系与区别
一:LR(0),SLR(1),规范LR(1),LALR(1)的关系 首先LL(1)分析法是自上而下的分析法.LR(0),LR(1),SLR(1),LALR(1)是自下而上的分析法. ...
-
LL(1),LR(0),SLR(1),LALR(1),LR(1)对比与分析
前言:考虑到这几种文法如果把具体内容讲下来肯定篇幅太长,而且繁多的符号对初学者肯定是极不友好的,而且我相信看这篇博客的人已经对这几个文法已经有所了解了,本篇博客的内容只是对 这几个文法做一下对比,加深 ...
-
LR(1)语法分析器生成器(生成Action表和Goto表)java实现(二)
本来这次想好好写一下博客的...结果耐心有限,又想着烂尾总比断更好些.于是还是把后续代码贴上.不过后续代码是继续贴在BNF容器里面的...可能会显得有些臃肿.但目前管不了那么多了.先贴上来吧hhh.说 ...
-
LR(1)语法分析器生成器(生成Action表和Goto表)java实现(一)
序言 : 在看过<自己实现编译器链接器>源码之后,最近在看<编译器设计>,但感觉伪代码还是有点太浮空.没有掌握的感觉,也因为内网几乎没有LR(1)语法分析器生成器的内容,于是我 ...
-
LR(1)文法分析器 //c++ 实现
1.先读入终结符,非终结符,和所有产生式. 2.预处理:初始化:getpp()获得每个非终结符在产生式左边时的产生式编号, 记录在 string getp[]中(可以多个). 3.获得所有的符号的fi ...
-
北航 编译实践 PL/0文法
编译实践-PL\0编译系统实现 姓名: 专业: 计算机科学与技术 学院: 软件学院 提交时间: 2013年12月25日 北京航空航天大学·软件学院 编译实践-PL\0编译系统实现 实验要求 以个人 ...
随机推荐
-
在 Java EE 组件中使用 Camel Routes
摘要:你可以通过集成 Camel 和 WildFly 应用服务器(使用 WildFly-Camel 子系统)在 Java EE 组件中开始使用 Apache Camel Routes. [编者按]作者 ...
-
ztree使用font-awesome字体的问题，
ztree要使用自定义图标字体的时候 需要自己做皮肤cssstyle,官方有文档,但是有些时候我们值需要简单的设置图标字体class样式 是没办法使用的,我们需要对两个函数进行修改. 下面是两个函数请 ...
-
CSS-图片占位的技巧
图片占位技巧,防止动态获取图片 网络慢,页面一跳一跳的情况发生 .food .image-header { position: relative; width: 1 ...
-
洛谷P3369 【模板】普通平衡树
题目描述 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 插入x数 删除x数(若有多个相同的数,因只删除一个) 查询x数的排名(排名定义为比当前数小的数的个数+1.若有多 ...
-
BugPhobia进阶篇章：系统架构技术规格
0x01 :开发级需求分析 在开发过程中,团队本身在开发的起始阶段确定了基本的开发级需求分析: 在开发过程中,除了需要满足用户级需求以为,我们还需要针对开发团队的特点,满足一些开发级的需求和约束.作为 ...
-
IE8.0如何关闭启用内存保护帮助减少联机攻击?
默认情况下,该选项卡是灰色的(表示用户不能直接修改),win7电脑可以通过“以管理员身份”运行 IE 来放开该功能,但个别电脑即便用这种方法仍无法解决,此时,您可以试试如下方法: 1.在“运行”框中输 ...
-
StringUtils一些常用方法
StringUtils是org.apache.commons.lang jar包里面的类方法,当输入参数String为null则不会抛出NullPointerException,而是做了相应处理,nu ...
-
Linux的软硬链接
Linux链接分为两种,一种是硬链接一种是符号链接. 硬链接: 硬链接是指通过索引节点来进行.再Linux文件系统中,保存在磁盘分区中的文件不管是什么类型都给它分配一个编号,称为索引节点(Inode ...
-
leetcode记录-组合两个表
表1: Person +-------------+---------+ | 列名 | 类型 | +-------------+---------+ | PersonId | int | | Firs ...
-
Codeforces 464E. The Classic Problem
题目大意 给定一张$n$个点, $m$条边的无向图,求$S$ 到$T$的最短路,其中边权都是$2^k$的形式$n,m,k<=10^5$,结果对$10^9+7$取模 题解 大佬好厉害 跑一边dij ...