栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

消除左递归java实现

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

消除左递归java实现

仅消除左递归功能,消除一切左递归,嫖完给个赞家人们。

上图!!!

示例1.间接左递归文法:[S->aA|Ab, A->B|c, B->C, C->D, D->S]

示例2.直接左递归:E->T|E+T|E-T, T->F|T*F|T/F, F->(E)|i

 

示例3.不含左递归: [S->aA|Bd, A->Bc, B->a

 

消除左递归:


import java.util.ArrayList;


public class method {
	
	 public static final char SINGLE_ANGLE_QUOTE = ''';
	 public static final char EPSILON = 'ε';
	 public static final String RIGHT_INFER_QUOTE = " → ";
	 public static int q = -1;  //用于记录不能左递归的式子在数组中的位置
	 public static ArrayList ids = new ArrayList();

	 
	
	public void Eliminateleftrecursion(String[] arg1,String[] arg2) {
		System.out.println("----消除左递归过程----");
		
			//System.out.println(arg1.length);
			//System.out.println(arg1[i]);
			//System.out.println(arg2[i]);
		
		
		
		for(int i = 0;i

main 部分


import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class main {
	
	public static int num1 = -1;   //捕捉可能存在间接左递归的非终结符
	public static int num2 = -1;  //捕捉需要替换掉的前部
	public static Map map = new LinkedHashMap();

	public static void main(String[] args) throws IOException{
		ArrayList str = new ArrayList();
		File file = new File("C:\Users\Administrator\Desktop\2.txt");
		try(Scanner input = new Scanner(file)){
			while(input.hasNextLine()) {
				String s = input.nextLine();
				str.add(s);
			}
		}
		System.out.println("读入的产生式为:"+str);
		judgement(str);

		
    }
	
	
	public static void judgement(ArrayList str) {
		
		method me = new method();
		
		ArrayList r1 = new ArrayList();
		ArrayList r2 = new ArrayList();
		int count = 0; //预制,0默认无左递归
		
		//先进行预处理
		prepare(str);
		
		//对map进行遍历然后依次比较确定有无左递归,这里采用遍历key值然后得到map中value的方法
		Set> entry = map.entrySet();
		
		//先得到所有key值,value值
		for(Map.Entry entries :entry) {
	         r1.add((String) entries.getKey());
	         r2.add((String) entries.getValue());
	    }
	    
		//ArrayList转String[]方便后续操作
		String[] arg1 = (String[])r1.toArray(new String[r1.size()]);
		String[] arg2 = (String[])r2.toArray(new String[r2.size()]);
		
		//分割右部除去“|”
	    for(int i = 0;iA...的情况则有可能存在间接左递归
	 * */
	public static void Indirectjudgment(String[] arg1,String[] arg2) {
		System.out.println("----判断有无间接左递归-----");
		
		//分割所有产生式右部
		for(int i = 0;i"+pdd;    //拼接出完整的产生式,即带入后的产生式
		
	    map.put(arg1[num2], pdd);            //将新的到的产生式代入进去
	    
	    map.remove(arg1[num2], arg2[num2]);  //删除原来两个旧的产生式
		map.remove(arg1[num1], arg2[num1]);

        Set> entry = map.entrySet();  //展示一次代入后产生式
		for(Map.Entry entries :entry) {
	        System.out.println(entries);
	    }
		
		//再次调用方法判断有无直接左递归
		ArrayList str = new ArrayList();
	    str.add(fin);         //将代入后的产生式添加进去,方便传参
	    System.out.println("----重新判断有无直接左递归---");
		judgement(str);
	}
	
	
	
	private static void type2(String[] arg1, String[] arg2) {
		System.out.println("进行间接转直接:");
		//arg1[num1]=A  arg2[num1]=bS|Sc   arg1[num2]=S   arg2[num2]=Ab

		String[] t = arg2[num1].split("\|");
		String a = arg2[num2].substring(1);    //将被带入的式子的首字符即非终结符去掉  这里去A
		ArrayList arr = new ArrayList();   //中间过渡转数组,无实际用处
		for(int i = 0;i"+r.substring(0,r.length()-1);
		 String op = r.substring(0,r.length()-1);
		 System.out.println(fin);
		 
		 map.put(arg1[num2], op);
		 map.remove(arg1[num1], arg2[num1]);
		 map.remove(arg1[num2], arg2[num2]);
		 
		//再次调用方法判断有无直接左递归
		    ArrayList str = new ArrayList();
		  	str.add(fin);         //将代入后的产生式添加进去,方便传参
		  	System.out.println("----重新判断有无直接左递归---");
		    judgement(str);
	}
	
	
	
	
	private static void type3(String[] arg1, String[] arg2) {
		System.out.println("进行间接转直接:");
		
		//arg2[num1] = Sc    arg2[num2] = aA|Ab
		String[] t = arg2[num2].split("\|");
        ArrayList arr = new ArrayList();   //中间过渡转数组,无实际用处
		for(int i = 0;i"+r.substring(0, r.length()-1);
	    String op = r.substring(0, r.length()-1);
	    System.out.println(fin);
	    
	    map.put(arg1[num2], op);
	    map.remove(arg1[num2], arg2[num2]);
	    map.remove(arg1[num1], arg2[num1]);
	    
	    
	    //再次调用方法判断有无直接左递归
	    ArrayList str = new ArrayList();
	  	str.add(fin);         //将代入后的产生式添加进去,方便传参
	  	System.out.println("----重新判断有无直接左递归---");
	    judgement(str);
	}
	
	
	private static void type4(String[] arg1, String[] arg2) {
		System.out.println("进行间接转直接:");
 
		String p = new String();
		
		//arg1[num1]=A  arg2[num1]=S|b  arg1[num2]=S   arg2[num2]=a|Ab
	    String[] t1 = arg2[num1].split("\|");
	    String[] t2 = arg2[num2].split("\|");
	    

	    StringBuilder r = new StringBuilder();
	    ArrayList arr = new ArrayList();
	    for(String s1 : t1) { //S  b
	    	for(String s2 : t2) {  //aA  Ab
	    	p = s2.replace(arg1[num1], s1);   //p是已经替换后的结果 aS Sb ab bb
	    	System.out.println(p);
	    	r.append(p).append("|");
	 	    }
	 	}
	    String op = r.substring(0,r.length()-1);
	   String fin = arg1[num2]+"->"+op;
	   
	   map.put(arg1[num2], op);
	   map.remove(arg1[num1], arg2[num1]);
	   map.remove(arg1[num2], arg2[num2]);
	   
	 //再次调用方法判断有无直接左递归
	    ArrayList str = new ArrayList();
	  	str.add(fin);         //将代入后的产生式添加进去,方便传参
	  	System.out.println("----重新判断有无直接左递归---");
	    judgement(str);
	 }
	
	
	
	
	public static void prepare(ArrayList str) {

		//先将ArrayList转数组,否则不好分割
		String[] arr = (String[])str.toArray(new String[str.size()]);
		System.out.println("转为数组后:");
		for(int i=0;i"));  //遍历分割
			 for(int j = 0;j

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/956329.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号