第一次写博客。。。编译原理课的一个实验。
感觉自己花了挺长的时间，所以作为博客保留下来，挺有纪念意义的 （因为我是菜鸟）
package com.insist.entity;import java.util.ArrayList;import java.util.List;import java.util.Scanner;/** * * @author SNOOPY 消除一切左递归 */public class EliminateLeftRecursion { private static int n;// 实际输入产生式个数 public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("请输入产生式个数："); n = scan.nextInt(); // 创建产生式数组存放输入的产生式 List regulars = new ArrayList (); for (int i = 0; i < n; i++) { Regular reg = new Regular(); 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, int count) { 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 = new Regular(); 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 = new Regular(); 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); } } } } } return regulars; }} package com.insist.entity;import java.io.Serializable;/** * * @author SNOOPY * */public class Regular implements Serializable { private static final long serialVersionUID = 1L; private String right;// 定义产生式右部 private String left;// 定义产生式左部 public String getRight() { return right; } public void setRight(String right) { this.right = right; } public String getLeft() { return left; } public void setLeft(String left) { this.left = left; }}