第一次寫博客。。。編譯原理課的一個(gè)實(shí)驗(yàn)。

　　感覺自己花了挺長的時(shí)間，所以作為博客保留下來，挺有紀(jì)念意義的??（因?yàn)槲沂遣锁B）

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;// 實(shí)際輸入產(chǎn)生式個(gè)數(shù)public static void main(String[] args) {Scanner scan = new Scanner(System.in);System.out.println("請輸入產(chǎn)生式個(gè)數(shù)：");n = scan.nextInt();// 創(chuàng)建產(chǎn)生式數(shù)組存放輸入的產(chǎn)生式List<Regular> regulars = new ArrayList<Regular>();for (int i = 0; i < n; i++) {Regular reg = new Regular();System.out.println("請輸入產(chǎn)生式左部:");String left = scan.next();reg.setLeft(left);System.out.println("請輸入產(chǎn)生式的右部:");String right = scan.next();reg.setRight(right);regulars.add(reg);}/** 測試輸出------->成功 for (Regular reg: regulars) { System.out.println(reg.getLeft()+"---->"+reg.getRight()); }*/// 構(gòu)造一個(gè)字符型的數(shù)組用來存放排序好的非終結(jié)符String[] Vn = new String[50];// 對所有的產(chǎn)生式按照一定的順序存放Vn[0] = regulars.get(0).getLeft();// 把產(chǎn)生式第一個(gè)非終結(jié)符放到集合中int flag = 0;int count = 0;for (int i = 1; i < n; i++) {// 對非終結(jié)符排序并存取 1、遍歷產(chǎn)生式數(shù)組for (int j = 0; j < i; j++) {// 如果產(chǎn)生式左部等于在它前面的產(chǎn)生式的左部if (regulars.get(i).getLeft().equals(regulars.get(j).getLeft())) {// 說明有重復(fù)的flag++;}}if (flag == 0) {// 說明沒有重復(fù)，則加入非終結(jié)符數(shù)組中count++;Vn[count] = regulars.get(i).getLeft();}flag = 0;}/** 測試非終結(jié)符數(shù)組------------>成功 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<Regular> subFunction(List<Regular> regulars, String[] Vn, int count) {int flag = 0;// 判斷是否存在間接左遞歸并轉(zhuǎn)化為直接左遞歸for (int i = 0; i <= count; i++) {// 對每一個(gè)非終結(jié)符 迭代for (int j = 0; j < i; j++) {// 對每一個(gè)小于i的非終結(jié)符遍歷for (int k = 0; k < regulars.size(); k++) // 對每一個(gè)產(chǎn)生式if (Vn[i].equals(regulars.get(k).getLeft())) {// i非終結(jié)符與第k產(chǎn)生式左邊第一個(gè)字母相等-->鎖定非終結(jié)符集合中的一個(gè)非終結(jié)符的產(chǎn)生式if (regulars.get(k).getRight().substring(0, 1).equals(Vn[j])) { // g產(chǎn)生式右邊產(chǎn)生式第一個(gè)符號與第j個(gè)非終結(jié)符相等-->說明存在間接左遞歸for (int h = 0; h < regulars.size(); h++) {if (regulars.get(h).getLeft().equals(Vn[j])) {// 進(jìn)行替換 String str;str = regulars.get(k).getRight().substring(1);// 截取右邊第一個(gè)以后的字符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])) {// 尋找與存在直接左遞歸的非終結(jié)符左部相同的的產(chǎn)生式if (regulars.get(j).getLeft().equals(regulars.get(j).getRight().substring(0, 1))) {// 直接左遞歸的產(chǎn)生式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;// 定義產(chǎn)生式右部private String left;// 定義產(chǎn)生式左部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;} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/snoopylovefiona/p/4593726.html

總結(jié)

以上是生活随笔為你收集整理的消除文法中一切左递归算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。