LL（1）文法 JAVA

灰太狼 2022-08-22 15:20 173阅读 0赞

E文法表达式类

G 定义文法类

LL 文法分析类 ， 包含对First,Follow,Select集合的求解以及对表达式的分析函数

Main测试分析程序，并输出结果

E.java

import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 文法表达式类
     * @author jiangliuhong 
     * @createTime 2016年5月30日 上午11:28:43 
     * @function
     */
    public class E {
    
    	//文法左部
    	private String left;
    	//文法右部
    	private String right;
    	
    	private List<String> rights = new ArrayList<>();
    	
    	public String getLeft() {
    		return left;
    	}
    	public void setLeft(String left) {
    		this.left = left;
    	}
    	public String getRight() {
    		return right;
    	}
    	public void setRight(String right) {
    		this.right = right;
    	}
    	public List<String> getRights() {
    		return rights;
    	}
    	public void setRights(List<String> rights) {
    		this.rights = rights;
    	}
    	public E() {
    	}
    	public E(String left, String right) {
    		this.left = left;
    		this.right = right;
    		createTaken();
    	}
    	 public void createTaken() {
    	     //   this.getLefts().add(this.getLeft());
    	        String right = this.getRight();
    	        /*if (right.equals("$")) {
    	            this.getRights().add(right);
    	        } else {*/
    	          /*  while (right.contains("$")) {
    	                right = right.replaceFirst("$", "#");
    	            }*/
    	            if (right.length() == 1) {
    	                this.getRights().add(right);
    	            } else {
    	                for (int i = 0; i < right.length(); i++) {
    	                    if ((i + 1 < right.length())
    	                            && String.valueOf(right.charAt(i + 1)).equals("'")) {
    	                        this.getRights().add(right.charAt(i) + "'");
    	                    } else {
    	                        if (!(String.valueOf(right.charAt(i)).equals("'"))) {
    	                            if (String.valueOf(right.charAt(i)).equals("#")) {
    	                                this.getRights().add("$");
    	                            } else {
    	                                this.getRights().add(
    	                                        String.valueOf(right.charAt(i)));
    	                            }
    	                        }
    	                    }
    	                }
    	            }
    	    }
    	/**
    	 * 格式化实处文法表达式
    	 * 重写toString方法
    	 * @return
    	 */
    	public String toString(){
    		return this.left+"->"+this.right;
    	}
    }

G.java 文法定义类

import java.util.Arrays;
    import java.util.List;
    /**
     * 文法定义类
     * 
     * @author jiangliuhong
     * @createTime 2016年5月30日 上午11:33:06
     * @function
     */
    public class G {
    	// 开始非终结符
    	private String start;
    	// 文法表达式
    	private List<E> es;
    	// 终结符
    	private List<String> terminator;
    	// 非终结符
    	private List<String> nonterminator;
    	public G() {
    	}
    	public G(String start, List<E> es) {
    		this.start = start;
    		this.es = es;
    	}
    	public G(String start) {
    		this.start = start;
    	}
    	public String getStart() {
    		return start;
    	}
    	public void setStart(String start) {
    		this.start = start;
    	}
    	public List<E> getEs() {
    		return es;
    	}
    	public void setEs(List<E> es) {
    		this.es = es;
    	}
    	public List<String> getTerminator() {
    		return terminator;
    	}
    	public void setTerminator(List<String> terminator) {
    		this.terminator = terminator;
    	}
    	public void setTerminator(String terminator) {
    		//this.terminator = new ArrayList<>();
    		/*for (int i = 0; i < terminator.length(); i++) {
    			this.terminator.add(terminator.charAt(i) + "");
    		}*/
    		String[] split = terminator.split(",");
    		this.terminator = Arrays.asList(split);
    	}
    	public List<String> getNonterminator() {
    		return nonterminator;
    	}
    	public void setNonterminator(List<String> nonterminator) {
    		this.nonterminator = nonterminator;
    	}
    	public void setNonterminator(String nonterminator) {
    		//this.nonterminator = new ArrayList<>();
    		/*for (int i = 0; i < nonterminator.length(); i++) {
    			this.nonterminator.add(nonterminator.charAt(i) + "");
    		}*/
    		String[] split = nonterminator.split(",");
    		this.nonterminator = Arrays.asList(split);
    	}
    	/**
    	 * 向文法中添加表达式
    	 * 
    	 * @param e
    	 */
    	public void andE(E e) {
    		this.es.add(e);
    	}
    }

LL.java ll文法分析类

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.Stack;
    /**
     * ll文法分析类
     * 
     * @author jiangliuhong
     * @createTime 2016年5月30日 上午11:38:52
     * @function
     */
    public class LL {
    	private G g;
    	// 三个集合
    	private Map<String, List<String>> first = new HashMap<>();
    	private Map<String, List<String>> follow = new HashMap<>();
    	private Map<String, List<String>> select = new HashMap<>();
    	//分析栈
    	private Stack<String> stack = new Stack<String>();
    	private Stack<String> str = new Stack<String>();
    	public LL(G g) {
    		this.g = g;
    	}
    	public G getG() {
    		return g;
    	}
    	public void setG(G g) {
    		this.g = g;
    	}	
    	/**
    	 * 分析输入串
    	 */
    	public void chkString(String string){
    		//判断是否为标准文法
    		//判断终结符
    		for(int i = string.length()-1 ;i>=0;i--){
    			String s = string.charAt(i) + "";
    			str.push(s);
    			if(!g.getTerminator().contains(s)){
    				System.out.println("输入串不符合规则");
    				return ;
    			}
    		}
    		//分析串
    		boolean flag = true;
    		int ii = 1;
    		stack.push("#");
    		stack.push(g.getStart());
    		System.out.println("步骤\t分析栈\t剩余输入串\t推导所用匹配");
    		ff:while(flag){
    			if(str.isEmpty()){
    				return ;
    			}
    			if(ii == 100){
    				return ;
    			}
    			System.out.print(ii+"\t");
    			String peek = stack.peek();
    			String speek = str.peek();
    			for (Map.Entry<String, List<String>> entry : select.entrySet()) {
    				String key = entry.getKey();
    				List<String> list = entry.getValue();
    				if(list.contains(speek)){
    					String first = getSelectFirtsOrFollow(true,key);
    					if(!first.equals(peek)){
    						continue;
    					}
    					String kright = getSelectFirtsOrFollow(false, key);
    					if(peek.equals(speek)){
    						if(speek.equals("#")&&peek.equals("#")){
    							System.out.print(stack.toString()+"\t"+str.toString()+"\t"+"接受\n");
    							return;
    						}
    						System.out.print(stack.toString()+"\t"+str.toString()+"\t"+speek+"匹配\n");
    						str.pop();
    						stack.pop();
    					}else{
    						System.out.print(stack.toString()+"\t"+str.toString()+"\t"+key+"\n");
    						stack.pop();
    					}
    					for(int j = kright.length()-1;j>=0;j--){
    						String ss = kright.charAt(j)+"";
    						if(ss.equals("'")){
    							ss = kright.charAt(j-1)+ss;
    							j--;
    						}
    						stack.push(ss);
    					}
    					ii++;
    					continue ff;
    				}
    			}
    			ii++;
    			//select中无匹配项 ， 输入串错误
    			//System.out.println("\n输入串错误");
    			//return;
    		}
    	}
    	
    	/**
    	 * 打印分析表
    	 */
    	public void printfAnalyzeTable(){
    		//打印表头
    		System.out.print("\t\t");
    		for(String term : g.getTerminator()){
    			System.out.print("\t"+term+"\t");
    		}
    		System.out.println();
    		/*for (Map.Entry<String, List<String>> entry : select.entrySet()) {
    			String key = entry.getKey();
    			int indexOf = key.indexOf("->");
    			String nonter = key.substring(0, indexOf);
    		}*/
    		for(E e : g.getEs()){
    			System.out.print("\t"+e.getLeft()+"\t");
    			for(String term : g.getTerminator()){
    				Map<String, List<String>> selectLikeKey = findSelectLikeKey(e.getLeft());
    				for(String term_ : g.getTerminator()){
    					for (Map.Entry<String, List<String>> entry : selectLikeKey.entrySet()) {
    						List<String> value = entry.getValue();
    						if(value.contains(term_)){
    							String key = entry.getKey();
    							int indexOf = key.indexOf(">");
    							String string = key.substring(indexOf+1 );
    							System.out.print("\t->"+string+"\t");
    						}else{
    							System.out.print("\t");
    						}
    					}
    				}
    			}
    			System.out.println();
    		}
    	}
    	/**
    	 * 得到 select key中含指定非终结符的映射
    	 */
    	private Map<String, List<String>> findSelectLikeKey(String likeKey){
    		Map<String, List<String>> result = new HashMap<>();
    		for (Map.Entry<String, List<String>> entry : select.entrySet()) {
    			String key = entry.getKey();
    			String skey = getSelectFirtsOrFollow(true,key);
    			if(skey.equals(likeKey)){
    				result.put(key, entry.getValue());
    			}
    		}
    		return result;
    	}
    	/**
    	 * 取select ->前部分
    	 */
    	private String getSelectFirtsOrFollow(boolean isFirst,String key){
    		if(isFirst){
    			int indexOf = key.indexOf("-");
    			String skey = key.substring(0, indexOf);
    			return skey;
    		}else{
    			int indexOf = key.indexOf(">");
    			String skey = key.substring(indexOf+1);
    			return skey;
    		}
    	}
    	/**
    	 * 打印Select集合
    	 */
    	public void printfSelect(){
    		System.out.println("Select集合为：");
    		for (Map.Entry<String, List<String>> entry : select.entrySet()) {
    			List<String> list = entry.getValue();
    			System.out.print("Select(" + entry.getKey() + ")={");
    			System.out.print(list.toString());
    			System.out.println("}");
    		}
    	}
    	/**
    	 * 分析Select 集合
    	 */
    	public void chkSelect(){
    		//遍历文法
    		for(E e : g.getEs()){
    			String right = e.getRight();
    			String left = e.getLeft();
    			//  |  判断
    			String[] split = right.split("\\|");
    			for(String sp : split){
    				// $ 判断
    				if(!right.contains("$")){
    					String begin = right.charAt(0) + "";
    					if(g.getNonterminator().contains(begin)){
    						//非终结符，存入first
    						select.put(left+"->"+sp,first.get(begin) );
    					}else{
    						//终结符
    						List<String> sel = new ArrayList<>();
    						sel.add(begin);
    						select.put(left+"->"+sp,sel);
    					}
    				}else{
    					select.put(left+"->"+sp,follow.get(left));
    				}
    			}
    		}
    	}
    	/**
    	 * 打印follow集合
    	 */
    	public void printfFollow() {
    		System.out.println("Follow集合为：");
    		for (Map.Entry<String, List<String>> entry : follow.entrySet()) {
    			List<String> list = entry.getValue();
    			System.out.print("Follow(" + entry.getKey() + ")={");
    			System.out.print(list.toString());
    			System.out.println("}");
    		}
    	}
    	/**
    	 * 分析follow集合
    	 */
    	public void chkFollow() {
    		//给每个非终结符创建一个map集合
    		for (String symbol : g.getNonterminator()) {
    			List<String> list = new ArrayList<String>();
    			list.add("#");
    			follow.put(symbol, list);
    		}
    		//定义一个循环上线
    		int count = 100;
    		//遍历非终结符
    		for (int i = 0, j = 0; i < g.getNonterminator().size()
    				&& j < count; i = (i + 1) % (g.getNonterminator().size()), j++) {
    			String symbol = g.getNonterminator().get(i);
    			//遍历文法表达式
    			for (E e : g.getEs()) {
    				if (e.getRight().contains(symbol)) {
    					for (int k = 0; k < e.getRights().size(); k++) {
    						//该文法表达式右部包含该非终结符
    						if (e.getRights().get(k).equals(symbol)) {
    							// 开始文法分析
    							//定义循环变量
    							boolean canDo = false, meDo = false;
    							for (int n = k; n < e.getRights().size() && !(e.getRights().get(n).equals("|"))
    									&& !canDo; n++) {
    								//判断后补是否为非终结符
    								if (n + 1 < e.getRights().size()) {
    									String rightString = e.getRights().get(n + 1);
    									if (g.getNonterminator().contains(rightString)) {
    										if (!canDo && !meDo) {
    											meDo = true;
    											List<String> leftFirst = first.get(rightString);
    											List<String> symbolFollow = follow.get(symbol);
    											for (int m = 0; m < leftFirst.size(); m++) {
    												if (!(symbolFollow.contains(leftFirst.get(m)))
    												) {
    													if (!(leftFirst.get(m).equals("$")))
    														if (!(leftFirst.get(m).equals("|")))
    															symbolFollow.add(leftFirst.get(m));
    												}
    											}
    											follow.put(symbol, symbolFollow);
    										}
    									} else {
    										List<String> symbolFollow = follow.get(symbol);
    										if (!(symbolFollow.contains(rightString)) && !(rightString.equals("|"))) {
    											symbolFollow.add(rightString);
    											follow.put(symbol, symbolFollow);
    											canDo = true;
    										}
    									}
    								}
    							}
    							// | 的文法判断 
    							if (k == e.getRights().size() - 1
    									|| e.getRights().get(k + 1).equals("|") && !canDo) {
    								String leftSymbol = e.getLeft();
    								List<String> leftFollow = follow.get(leftSymbol);
    								List<String> symbolFollow = follow.get(symbol);
    								for (int m = 0; m < leftFollow.size(); m++) {
    									if (!(symbolFollow.contains(leftFollow.get(m)))) {
    										if (!(leftFollow.get(m).equals("$")))
    											if (!(leftFollow.get(m).equals("|")))
    												symbolFollow.add(leftFollow.get(m));
    									}
    								}
    								follow.put(symbol, symbolFollow);
    								canDo = true;
    							} else {
    								int nonTerminatingSymbol = 0;
    								int isepsilon = 0;
    								boolean isMe = false;
    								for (int n = k; n < e.getRights().size()
    										&& !(e.getRights().get(n).equals("|")); n++) {
    									if (n + 1 < e.getRights().size()) {
    										String rightString = e.getRights().get(n + 1);
    										if (g.getTerminator().contains(rightString)) {
    											isMe = true;
    										}
    										if (g.getNonterminator().contains(rightString)) {
    											nonTerminatingSymbol++;
    											if (hasepsilon(rightString)) {
    												isepsilon++;
    											}
    										}
    									}
    								}
    								if (nonTerminatingSymbol == isepsilon && !canDo && !isMe) {
    									String leftSymbol = e.getLeft();
    									List<String> leftFollow = follow.get(leftSymbol);
    									List<String> symbolFollow = follow.get(symbol);
    									for (int m = 0; m < leftFollow.size(); m++) {
    										if (!(symbolFollow.contains(leftFollow.get(m)))) {
    											if (!(leftFollow.get(m).equals("$")))
    												if (!(leftFollow.get(m).equals("|")))
    													symbolFollow.add(leftFollow.get(m));
    										}
    									}
    									follow.put(symbol, symbolFollow);
    								}
    							}
    						}
    					}
    				}
    			}
    		}
    	}
    	/**
    	 * 判断是否含有 $ $ 即 epsilon
    	 * @param symbol
    	 * @return
    	 */
    	private boolean hasepsilon(String symbol) {
    		for (E e : g.getEs()) {
    			if (e.getLeft().equals(symbol)) {
    				int index = e.getRights().indexOf("$");
    				if (index < 0) {
    					return false;
    				} else {
    					if (e.getRights().size() == 1 && e.getRights().contains("$")) {
    						return true;
    					} else {
    						if (index == e.getRights().size() - 1 && e.getRights().get(index - 1).equals("|")) {
    							return true;
    						} else {
    							if (index + 1 < e.getRights().size() && e.getRights().get(index + 1).equals("|")
    									&& index == 0) {
    								return true;
    							} else {
    								if (index + 1 < e.getRights().size()
    										&& e.getRights().get(index + 1).equals("|") && index - 1 > 0
    										&& e.getRights().get(index - 1).equals("|")) {
    									return true;
    								}
    							}
    						}
    					}
    				}
    			}
    		}
    		return false;
    	}
    	/**
    	 * 输出first集合
    	 */
    	public void printfFirst() {
    		System.out.println("First集合为：");
    		for (Map.Entry<String, List<String>> entry : first.entrySet()) {
    			List<String> list = entry.getValue();
    			System.out.print("First(" + entry.getKey() + ")={");
    			System.out.print(list.toString());
    			System.out.println("}");
    
    		}
    	}
    	/**
    	 * 分析first集合
    	 */
    	public void chkFirst() {
    		// 遍历非终结符
    		for (String nonter : g.getNonterminator()) {
    			List<String> listFirst = new ArrayList<String>();
    			iterativeToFirst(nonter, listFirst);
    		}
    	}
    	/**
    	 * 文法分析
    	 * 
    	 * @param symbol
    	 * @param listFirst
    	 */
    	private void iterativeToFirst(String symbol, List<String> listFirst) {
    		for (E e : g.getEs()) {
    			if (e.getLeft().equals(symbol)) {
    				// 根据| 划分文法表达式
    				String[] rights = e.getRight().split("\\|");
    				for (String right : rights) {
    					if (!isStartWithSymbol(right)) {
    						// 不是非终结符，加入list
    						listFirst.add(getStartWithSymbol(right));
    					} else {
    						iterativeToFirst(getStartWithSymbol(right), listFirst);
    					}
    				}
    			}
    		}
    		first.put(symbol, listFirst);
    	}
    	/**
    	 * 判断开始是否为非终结符
    	 * 
    	 * @param symbol
    	 * @return
    	 */
    	private boolean isStartWithSymbol(String symbol) {
    		for (String nonTerminatingSymbol : g.getNonterminator()) {
    			if (symbol.startsWith(nonTerminatingSymbol)) {
    				return true;
    			}
    		}
    		return false;
    	}
    	/**
    	 * 得到文法的第一个字符
    	 * 
    	 * @param symbol
    	 * @return
    	 */
    	private String getStartWithSymbol(String symbol) {
    		for (String nonTerminatingSymbol : g.getNonterminator()) {
    			if (symbol.startsWith(nonTerminatingSymbol)) {
    				return nonTerminatingSymbol;
    			}
    		}
    		// $ 代替epsilon
    		if (symbol.equals("$")) {
    			return "$";
    		} else {
    			return String.valueOf(symbol.charAt(0));
    		}
    	}
    }

Main.java测试类

import java.util.ArrayList;
    import java.util.List;
    /**
     * @author jiangliuhong 
     * @createTime 2016年5月30日 上午11:31:15 
     * @function
     */
    public class Main {
    	public static void main(String[] args) {
    		List<E> es = new ArrayList<>();
    		es.add(new E("E", "TE'"));
    		es.add(new E("E'", "+TE'|$"));
    		es.add(new E("T", "FT'"));
    		es.add(new E("T'", "*FT'|$"));
    		es.add(new E("F", "i|(E)"));
    		G g = new G("E", es );
    		List<String> non = new ArrayList<>();
    		g.setNonterminator("E,E',T,T',F");
    		g.setTerminator("i,+,*,(,),#");
    		LL ll = new LL(g);
    		ll.chkFirst();
    		ll.printfFirst();
    		ll.chkFollow();
    		ll.printfFollow();
    		ll.chkSelect();
    		ll.printfSelect();
    		ll.printfAnalyzeTable();
    		ll.chkString("i+i*i#");
    	}
    }

控制台输出结果

First集合为：
    First(E)={[i, (]}
    First(T)={[i, (]}
    First(T')={[*, $]}
    First(F)={[i, (]}
    First(E')={[+, $]}
    Follow集合为：
    Follow(T)={[#, +, )]}
    Follow(E)={[#, )]}
    Follow(F)={[#, *, +, )]}
    Follow(T')={[#, +, )]}
    Follow(E')={[#, )]}
    Select集合为：
    Select(F->(E))={[i]}
    Select(F->i)={[i]}
    Select(E'->+TE')={[#, )]}
    Select(T->FT')={[i, (]}
    Select(E'->$)={[#, )]}
    Select(E->TE')={[i, (]}
    Select(T'->$)={[#, +, )]}
    Select(T'->*FT')={[#, +, )]}
    			i		+		*		(		)		#	
    	E		->TE'				->TE'				
    	E'				->TE'					->$ 	->$
    	T 		->FT'					->FT'
    	T'				->$		->*FT'			->$		->$
    	F 		->i						->(E)
    
    步骤	分析栈	剩余输入串	推导所用匹配
    1	[#, E]	[#, i, *, i, +, i]	E->TE'
    2	[#, E', T]	[#, i, *, i, +, i]	T->FT'
    3	[#, E', T', F]	[#, i, *, i, +, i]	F->i
    4	[#, E', T', i]	[#, i, *, i, +, i]	i匹配
    5	[#, E', T']	   [#, i, *, i, +]		T'->$
    6	[#, E']		 [#, i, *, i, +]		E'->+TE'
    7	[#, E',T,+]		[#, i, *, i, +]		+匹配
    8	[#, E',T]	 [#, i, *, i]	  T->FT'
    9	[#, E',T',F]   [#, i, *, i]	  F->i
    10    [#, E',T',i]	  [#, i, *, i]		i匹配
    11	  [#, E',T']	[#, i, *]		T'->*FT'
    12	  [#, E',T',F,*]	[#, i, *]		*匹配
    13	  [#, E',T',F]	  [#, i]		F->i
    14	  [#, E',T',i]	  [#, i]		i匹配
    15	  [#, E',T']  	 [#]		T'->$
    16	  [#, E'] 		[#]		  E'->$
    17	  [#] 		[#]			接受