start : <Goal>;  			<Goal> ::= <Expr>;  			<Expr> ::= <Term><Expr'>;  			<Expr'> ::= "+" <Term><Expr'>  					|	"-" <Term><Expr'>  					|	"ε";  			<Term> ::= <Factor><Term'>;  			<Term'> ::= "*" <Factor><Term'>  					|	"/" <Factor><Term'>  					|	"ε";  			<Factor> ::= "("<Expr>")"  					|	"num"  					|	"name";  			#

package cn.vizdl.LR1;    import java.util.ArrayList;  import java.util.HashMap;  import java.util.List;  import java.util.Scanner;    /*  項目名 :  LR(1) parser generator (LR(1)語法分析器生成器)  項目分析 :  	輸入 : 輸入某文件內存地址。且內部採用  <Expr> ::=  <Term> + <Factor>; 的結構輸入的LR(1)語法。  	這裡的僅支持 BNF範式內部的 終結符,非終結符,或運算,;(表示產生式結束),::=(表示為定義為)  	在這裡不支持閉包,也就是{},因為閉包可以轉換為非終結符的遞歸。  		輸入文本格式 :  			start : <aim_name>  //aim_name表示起始符號名稱  		例子 :  			start : <Goal>;  			<Goal> ::= <Expr>;  			<Expr> ::= <Expr> "+" <Term> | <Expr> "-" <Term>;  			<Term> ::= <Term> "*" <Factor> | <Term> "/" <Factor>;  			<Factor> ::= "number";  			#  		以#作為結尾  		輸入分析 : 因為上下文無關語法是一個四元組,而LR(1)語法又是上下文無關語法的子集。所以採用四元組的形式來表示LR(1)語法,是不會損失信息的。  			四元組 (T,NT,S,P)  			T ： 終結符集合  			NT : 非終結符集合  			S : 語法的起始符號(非終結符)  			P : 產生式集合  			T, NT都可以用一個hash_set來表示。  			P 可以分為兩個部分,左側一定是一個非終結符,右側是一個支持或運算的產生式。  			產生式左端可以使用Node節點來表示,產生式右端可以使用多個鏈表(具體有幾個取決於當前產生式有多少個或運算符)來表示。  			將當下語法分為三級,第一級是Expr,第二級別是Term,第三個級別是Factor  			<Expr> ::= <Term> { "|" <Term>}; //產生式(表達式)可以表達成多個小句子 或 起來  			<Term> ::= <Factor> { "+" <Factor>}; // + 表示連接  			<Factor> ::= <T> | <NT>  	輸出 ：Action 和 GoTo 表。  */  public class Demo {  	public static void main (String[] args) {  		//將輸入的產生式都放入ch中  		Scanner scanner = new Scanner(System.in);  		String s = new String();  		String c;  		//輸入處理...  		while (true) {  			c = scanner.nextLine();  			int i;  			for (i = 0; i < c.length(); i++) {  				if (c.charAt(i) != '#')  					s += c.charAt(i);  				else {  					scanner.close();  					break;  				}  			}  			if (i != c.length()) {  				break;  			}  		}  		//  		BnfContainer bc = new BnfContainer();  		CodeAnalyzer ca = new CodeAnalyzer(s, bc);  		ca.analyze();  		bc.printBNF();    	}  }    /**   * 用來裝載BNF範式的信息。   */  class BnfContainer {  	/**  	 * 內部類,NT的節點。  	 * @author HP  	 */  	class NTNode {  		private String name; //符號id  		private List<List<Integer>> expr;  		public NTNode(String name) {  			expr = new ArrayList<List<Integer>>();  			this.name = name;  		}  		/**  		 * 添加一條expr  		 * 返回這個expr的下標  		 * @return  		 */  		public int addExpr() {  			expr.add(new ArrayList<Integer>());  			return expr.size() - 1;  		}  		/**  		 * 向下標為idx的expr添加value  		 * @param idx  		 * @param value  		 */  		public void addExprElement (int idx, int value) {  			this.expr.get(idx).add(value);  		}  		/**  		 * 向最後一個表達式添加value  		 * @param value  		 */  		public void addExprElement (int value) {  			this.addExprElement(this.expr.size() - 1, value);  		}    		public void printNTNode () {  			System.out.println("NTNumber : " + this.name);  			for (List<Integer> list : this.expr) {  				for (Integer val : list) {  					System.out.print(val + " ");  				}System.out.println();  			}  		}  	}      	//常量定義  	/**  	 * 這兩個常量只出現在終結符  	 * 因為要將終結符和非終結符  	 * 放在同一個鏈表中  	 * 所以使用這個來辨別終結符和非終結符。  	 */  	private static final int MASK = 0X80000000; //掩碼,用來給終結符做掩飾的編碼。  	private static final int DECODE = 0X7fffffff; //解碼,破譯掩碼得到原本的編碼。  	/**  	 * 非終結符Map  	 * key : 非終結符名稱  	 * value : 非終結符在production鏈表中的下標  	 */  	private HashMap<String,Integer> NTMap;  	/**  	 * 終結符Map  	 * key : 終結符名稱  	 * value : 終結符在T鏈表中的下標  	 */  	private HashMap<String,Integer> TMap;  	// 終結符鏈表  	private ArrayList<String> T;  	// 產生式鏈表,因為一個非終結符一個產生式具有雙射關係。  	private ArrayList<NTNode> production;  	//如若未設置,默認為0  	public int startIndex = 0;  	public BnfContainer() {  		//內部數據結構初始化  		NTMap = new HashMap<String,Integer>();  		TMap = new HashMap<String,Integer>();  		T = new ArrayList<String>();  		production = new ArrayList<NTNode>();  	}    	/**  	 * 設置開始非終結符  	 * @param name  	 */  	public void setStart (String name) {  		this.addNT(name);  		this.startIndex = this.NTMap.get(name);  	}    	/**  	 * 將非終結符的名字傳入,即可添加一個非終結符節點。  	 * @param name  	 */  	public void addNT (String name) {  		if (name.isEmpty()) {  			System.out.println("終結符不可為空");  			System.exit(-1);  		}  		if (!NTMap.containsKey(name)) {  			NTNode node = new NTNode(name);  			NTMap.put(name, production.size());  			production.add(node);  		}  	}    	/**  	 * 將終結符傳入,增加非終結符。  	 * @param name  	 */  	public void addT(String name) {  		if (!this.TMap.containsKey(name)) {  			this.TMap.put(name, T.size());  //System.out.println(name);  			this.T.add(name);  		}  	}    	/**  	 * 輸入終結符名稱  	 * 獲取終結符編號  	 * 如若存在當前終結符,返回編號  	 * 否則返回-1,輸出錯誤警告並且退出。  	 * @param name  	 * @return  	 */  	private int getTSerialNumber (String name) {  		this.notFindTWarning(name);  		return this.TMap.get(name) | BnfContainer.MASK;  	}    	/**  	 * 輸入非終結符名稱  	 * 獲取非終結符編號  	 * 如若存在當前非終結符,返回編號  	 * 否則返回-1,輸出錯誤警告並且退出。  	 * @param name  	 * @return  	 */  	private int getNTSerialNumber (String name) {  		this.notFindNTWarning(name);  		return this.NTMap.get(name);  	}    	/**  	 * 創建新的表達式並添加到名稱為name的非終結符節點上  	 * 返回表達式編號  	 */  	public int creatNewExper(String name) {  		this.notFindNTWarning(name);  		NTNode ntn = this.production.get(this.NTMap.get(name));  		return ntn.addExpr();  	}  	/**  	 * 向左端非終結符名稱為name的產生式  	 * 第idx表達式添加元素  	 * @param name  	 * @param idx  	 * @param isNt  	 */  	public void addExpeElement(String name, int idx,boolean isNt, String addElement) {  		NTNode ntn = this.production.get(this.NTMap.get(name));  		if (isNt) {  			this.notFindNTWarning(name);  			this.notFindNTWarning(addElement);  			ntn.addExprElement(idx, this.getNTSerialNumber(addElement));  		}else {  			this.addT(addElement);  			ntn.addExprElement(idx, this.getTSerialNumber(addElement));  		}  	}    	/**  	 * 向左端非終結符名稱為name的產生式  	 * 最後一個表達式添加元素  	 * @param name  	 * @param list  	 */  	public void addExpeElement(String name,boolean isNt, String addElement) {  		NTNode ntn = this.production.get(this.NTMap.get(name));  		if (isNt) {  			this.notFindNTWarning(name);  			this.notFindNTWarning(addElement);  			ntn.addExprElement(this.getNTSerialNumber(addElement));  		}else {  			this.addT(addElement);  			ntn.addExprElement(this.getTSerialNumber(addElement));  		}  	}    	/**  	 * 如若找到了當前非終結符,什麼都不會發生。  	 * 否則會提示並且退出程序  	 * @param name  	 */  	private void notFindNTWarning(String name) {  		if (!this.NTMap.containsKey(name)) {  			System.out.println("錯誤的非終結符" + name + "!");  			System.exit(-1);  		}  	}  	/**  	 * 如若找到了當前終結符,什麼都不會發生。  	 * 否則會提示並且退出程序  	 * @param name  	 */  	private void notFindTWarning(String name) {  		if (!this.TMap.containsKey(name)) {  			System.out.println("錯誤的終結符" + name + "!");  			System.exit(-1);  		}  	}    	public void printBNF() {  		System.out.println("開始非終結符為 : " + this.production.get(startIndex).name);  		System.out.println("終結符對應表 : ");  		for (int i = 0; i < this.T.size(); i++) {  			System.out.println(this.T.get(i) + " : " + (i | MASK));  		}  		System.out.println("非終結符對應表 : ");  		for (int i = 0; i < this.production.size(); i++) {  			System.out.println(this.production.get(i).name + " : " + i);  		}  		for (NTNode ntn : this.production) {  			ntn.printNTNode();  		}  	}  }    /**   * 代碼分析器   * 可以將代碼轉換為信息等價的數據結構   */  class CodeAnalyzer {  	class Token{  		boolean isNt;  		String name;  		public Token (boolean isNt, String name) {  			this.isNt = isNt;  			this.name = name;  		}  	}  	private char[] text;  	private int textSize = 0; //字符串有效長度  	private int point = 0; //text解析進度的指針  	private BnfContainer bc;  	private Token token;  	String left; //左側非終結符  	private int count = 0; //記錄當前已經解析到哪個產生式了  	public CodeAnalyzer (String text, BnfContainer bc) {  		this.bc = bc;  		//初始化代碼分析器  		this.initText(text);  		this.initStartSymbol();  		this.initCodeAnalyzer();  	}  	/**  	 * 輸入字符串文本,返回處理完畢的字符數組。  	 * @param s  	 * @return  	 */  	private void initText(String s) {  		this.text = s.toCharArray();  		int idx = 0;  		//將字符串變為一個緊湊的字符數組(去除一些妨礙的字符)  		while (idx < text.length) {  			if (text[idx] == 'r' || text[idx] == 'n' || text[idx] == 't' || text[idx] == ' ') {  				idx++;  			}else {  				text[textSize++] = text[idx++];  			}  		}  	}    	private void initStartSymbol() {  		// 驗證是否存在start:<  		point = 0;  		char[] needle = { 's', 't', 'a', 'r', 't', ':', '<' };  		if (textSize <= needle.length) {  			this.notFindStartNT();  		}  		point = 0;  		while (point < needle.length) {  			if (needle[point] == text[point]) {  				point++;  			} else {  				this.notFindStartNT();  			}  		}  		point = needle.length;  		while (point < textSize && text[point] != '>') {  			point++;  		}  		this.bc.setStart(new String(text, needle.length, point - needle.length));  		this.skip(Type.RT);  		this.skip(Type.SEMICOLON);  	}  	/**  	 * 通過skip來跳過字符  	 */  	enum Type{  		LT, //左尖括號  		RT, //右尖括號  		SEMICOLON, //分號  		QUOTE, //雙引號  		OR, //或  		COLON, // :  		EQ, //等於號  	}  	private void skip (Type t) {  		switch(t) {  		case LT:  			this.skip('<');  			break;  		case RT:  			this.skip('>');  			break;  		case OR:  			this.skip('|');  			break;  		case SEMICOLON:  			this.skip(';');  			break;  		case QUOTE:  			this.skip('"');  			break;  		case COLON:  			this.skip(':');  			break;  		case EQ:  			this.skip('=');  			break;  		}  	}  	private void skip (char c) {  		if (point >= this.textSize || this.text[point] != c) {  			System.out.println("第" + this.count + "個產生式,缺少符號  " + c);  			System.exit(-1);  		}  		point++;  	}  	/**  	 * 報錯 : 沒有找到目標(開始)非終結符號! 並退出程序。  	 */  	private void notFindStartNT() {  		System.out.println("沒有找到目標非終結符號!");  		System.exit(-1);  	}    	/**  	 * 之所以一開始就要添加非終結符,而不在解析BNF時候添加  	 * 是因為,非終結符存在定義的問題,如若 沒有定義  	 * 但有使用(只在右側出現,未在左側定義),這個就是錯誤的。  	 */  	private void initCodeAnalyzer() {  		int idx = this.point;  		this.point = 0;  		this.count = 0;  		while (true) {  			while (this.point < textSize && text[this.point] != ';') {  				this.point++;  			}this.point++;  			this.count++;  			//如若分號後面沒有左括號  			if (this.point >= textSize) {  				break;  			}  			String name = this.getNT();  			bc.addNT(name);  		}this.count = 0;  		this.point = idx;  	}    	/**  	 * BNF  	 * 從point開始解析字符串。  	 * <Goal> ::= {<Production>}  	 * <Production> ::= <左側非終結符> "::=" <Expr>;  	 * <Expr> ::= <Term> { "|" <Term>}";";  	 * <Term> ::= {<Factor>}; 	//Term在這就是多個終結符或非終結符相連接  	 * <Factor> ::= <T> | <NT>  	 */  	public void analyze() {  		while (point < this.textSize) {  			this.count++;  			production();  		}  	}    	public void production(){  		//先跳過左側非終結符  		this.left = this.getNT();  		this.skipDefineSymol();  		this.expr();  	}  	/**  	 * 跳過 ::=  	 */  	public void skipDefineSymol() {  		skip(Type.COLON);  		skip(Type.COLON);  		skip(Type.EQ);  	}  	/**  	 * 獲取非終結符  	 * <xxx>  	 */  	public String getNT () {  		skip(Type.LT);  		StringBuilder res = new StringBuilder();  		while (this.point < this.textSize && text[this.point] != '>') {  			res.append(text[this.point++]);  		}  		skip(Type.RT);  		return res.toString();  	}    	/**  	 * 當前指針指向 "T" 中第一個"  	 * @return  	 */  	public String getT() {  		this.skip(Type.QUOTE);  		StringBuilder res = new StringBuilder();  		while (this.point < this.textSize && this.text[this.point] != '"') {  			res.append(text[this.point++]);  		}  		this.skip(Type.QUOTE);  		return res.toString();  	}    	/**  	 * 當前指針指向 ::= <T>... 中 = 後一個符號  	 */  	public void expr(){  		this.term();  		while (this.point < this.textSize && text[this.point] == '|') {  			this.skip(Type.OR);  			term();  		}this.skip(Type.SEMICOLON);  	}    	/**  	 * 如若還有符號,當前符號指向 終結符或非終結符的符號  < 或者 "  	 */  	public void term(){  		//創建一個屬於當前term的鏈表  		bc.creatNewExper(this.left);  		while (this.point < this.textSize && (text[this.point] == '"' || text[this.point] == '<')) {  			factor();  			bc.addExpeElement(this.left, token.isNt, token.name);  		}  	}    	/**  	 * 通過factor獲取token  	 */  	public void factor(){  		//非終結符  		if (text[this.point] == '"') {  			String name = this.getT();  			this.token = new Token(false, name);  		}else {  			String name = this.getNT();  			token = new Token (true, name);  		}  	}  }