packagecom.insist.entity;importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;/***
*@authorSNOOPY 消除一切左递归*/
public classEliminateLeftRecursion {private static int n;//实际输入产生式个数
public static voidmain(String[] args) {
Scanner scan= newScanner(System.in);
System.out.println("请输入产生式个数：");
n=scan.nextInt();//创建产生式数组存放输入的产生式
List regulars = new ArrayList();for (int i = 0; i < n; i++) {
Regular reg= newRegular();
System.out.println("请输入产生式左部:");
String left=scan.next();
reg.setLeft(left);
System.out.println("请输入产生式的右部:");
String right=scan.next();
reg.setRight(right);
regulars.add(reg);
}/** 测试输出------->成功 for (Regular reg: regulars) { System.out.println(reg.getLeft()+"---->"+reg.getRight()); }*/
//构造一个字符型的数组用来存放排序好的非终结符
String[] Vn = new String[50];//对所有的产生式按照一定的顺序存放
Vn[0] = regulars.get(0).getLeft();//把产生式第一个非终结符放到集合中
int flag = 0;int count = 0;for (int i = 1; i < n; i++) {//对非终结符排序并存取 1、遍历产生式数组
for (int j = 0; j < i; j++) {//如果产生式左部等于在它前面的产生式的左部
if (regulars.get(i).getLeft().equals(regulars.get(j).getLeft())) {//说明有重复的
flag++;
}
}if (flag == 0) {//说明没有重复，则加入非终结符数组中
count++;
Vn[count]=regulars.get(i).getLeft();
}
flag= 0;
}/** 测试非终结符数组------------>成功 for (int i = 0; i < Vn.length; i++) { if(Vn[i]!=null){ System.out.println(Vn[i]); } }*/
for(Regular reg : regulars) {if (reg != null) {
System.out.println(reg.getLeft()+ "---->" +reg.getRight());
}
}
regulars=subFunction(regulars, Vn, count);for(Regular reg : regulars) {if (reg != null) {
System.out.println(reg.getLeft()+ "---->" +reg.getRight());
}
}
}public static List subFunction(List regulars, String[] Vn, intcount) {int flag = 0;//判断是否存在间接左递归并转化为直接左递归
for (int i = 0; i <= count; i++) {//对每一个非终结符 迭代
for (int j = 0; j < i; j++) {//对每一个小于i的非终结符遍历
for (int k = 0; k < regulars.size(); k++) //对每一个产生式
if (Vn[i].equals(regulars.get(k).getLeft())) {//i非终结符与第k产生式左边第一个字母相等-->锁定非终结符集合中的一个非终结符的产生式
if (regulars.get(k).getRight().substring(0, 1).equals(Vn[j])) { //g产生式右边产生式第一个符号与第j个非终结符相等-->说明存在间接左递归
for (int h = 0; h < regulars.size(); h++) {if (regulars.get(h).getLeft().equals(Vn[j])) {//进行替换
String str;
str= regulars.get(k).getRight().substring(1);//截取右边第一个以后的字符
Regular reg = newRegular();
reg.setLeft(regulars.get(k).getLeft());
reg.setRight(regulars.get(h).getRight()+str);
regulars.add(reg);
}
}
regulars.remove(k);
}
}
}
}//消除所有直接左递归
for (int i = 0; i <= count; i++) {
flag= 0;for (int j = 0; j < regulars.size(); j++) {//判断是否存在直接左递归
if(regulars.get(j).getLeft().equals(Vn[i])) {
System.out.println(regulars.get(j).getLeft()+ " ======= " +Vn[i]);if (regulars.get(j).getLeft().equals(regulars.get(j).getRight().substring(0, 1))) {
System.out.println("消除间接左递归后存在直接左递归");
flag++;
}
}
}if (flag != 0) {//存在直接左递归
for (int j = 0; j < regulars.size(); j++) {if (regulars.get(j).getLeft().equals(Vn[i])) {//寻找与存在直接左递归的非终结符左部相同的的产生式
if (regulars.get(j).getLeft().equals(regulars.get(j).getRight().substring(0, 1))) {//直接左递归的产生式
String str = regulars.get(j).getRight().substring(1);
String temp=regulars.get(j).getLeft();
String temp1= "'";
regulars.get(j).setLeft(temp+temp1);
regulars.get(j).setRight(str+regulars.get(j).getLeft());
Regular reg= newRegular();
reg.setLeft(regulars.get(j).getLeft());
reg.setRight("ε");
regulars.add(reg);
}else{
String temp=regulars.get(j).getLeft();
String temp1= "'";
temp= temp +temp1;
regulars.get(j).setRight(regulars.get(j).getRight()+temp);
}
}
}
}
}returnregulars;
}
}
转播
