一个完整的语法分析、词法分析例子——Universal Pasrser

需求：用户用formal notation指定语法、词法，然后可以匹配相应的文本。用法类似正则表达式，只需给出formal notation，不需要为每一种格式的文本单独写匹配器。

formal notation主要是3个部分：

1）BNF 列表 table：给出上下文无关文法的产生式规则，以及所有的符号（终端和非终端）

2）起始符号 start

3）终端符号Regular Expression Table：用RE给出每个终端符号的匹配规则

其中BNF目前只接受left factor过的，去左递归的上下文无关文法。

关于空格的处理有3种方式，本案采用第2种：

1）作为文法的一部分：

<SPACE> --> S*

<E> --> <SPACE> <E> <SPACE> + <SPACE>  <E> <SPACE>

2）作为terminal symbol的一部分

对每个terminal symbol的regular expression做处理，两头加上匹配空白的规则 re = "\\s+" + re + "\\s+"

3）如果不是用正则表达式匹配终端符号，而是自己写term(TOKEN type)函数

对于空格，skip掉就可以了

文法匹配就是 top down的 recursive descend 算法，

1）对于当前符号，如果是终结符号，到终结符号RE表找到对应的RE做匹配，匹配成功要把指针移动到后一个位置。

2）如果是非终结符号，尝试每个production, 直到某个production成功。（left factor 保证只有一个production是可行的），注意epsilon production放到最后。

下一步工作：

1）支持没有进行left factor的文法。现在是一个production失败了才回溯尝试下一个production。一般的情况是，一个符号V即使走某条production成功匹配了，但有可能导致V后面的符号无法匹配成功，这时候也要回溯，尝试V的别的production。

2）自动消除左递归，这样用户只需要自然的写BNF就行了

package excercise;
import java.util.*;
import java.util.regex.*;
class CFG {
	private Map<String, List<String[]>> BNF;
	private Map<String, String> termRegex;
	private String start, text;
	private int i = 0;
	public CFG(Map<String, List<String[]>> productions, String start, Map<String, String> termRegex) {
		this.BNF = productions;
		this.termRegex = termRegex;
		this.start = start;
	}
	public boolean recognize(String text) {
		this.text = text;
		return match(start) && i == text.length();
	}
	private boolean match(String V) {
		if (V.isEmpty()) return true; //epsilon
		List<String[]> production = BNF.get(V);
		if (production == null) { //no production for this symbol, should be terminal symbol
			String re = termRegex.get(V); //get the regex for this terminal symbol
			if (re == null) throw new RuntimeException("invalid CFG.");
			re = "\\s*" + re + "\\s*";
			Pattern pattern = Pattern.compile(re);
			Matcher matcher = pattern.matcher(text);
			if (matcher.find(i) && matcher.start() == i) {
				i = matcher.end();
				return true;
			}
			return false;
		}
		//try each production. if one matches, succeed, or recover the pointer and try next.
		int save = i;
		for (String[] p : production) {
			boolean flag = true;
			i = save;
			for (String T : p) {
				if (!match(T)) {
					flag = false;
					break; 
				}
			}
			if (flag) {
				System.out.println(V + "->" + String.join(" ", p));
				return true;
			}
		}
		return false;
	}
	public static void main(String[] args) {
	//1) E -> TE'
	//2) E'-> +TE' | -TE' | e
	//3) T -> FT'
	//3) T'-> *FT' | /FT' | e
	//4) F -> int | (E)
		//specify the BNF table, should be left factored, left recursion removed
		Map<String, List<String[]>> BNF = new HashMap<String, List<String[]>>();
		List<String[]> pE = new ArrayList<String[]>();
		pE.add(new String[]{"T", "EA"});
		BNF.put("E", pE);
		List<String[]> pEA = new ArrayList<String[]>();
		pEA.add(new String[]{"+", "T", "EA"});
		pEA.add(new String[]{"-", "T", "EA"});
		pEA.add(new String[]{""});
		BNF.put("EA", pEA);
		List<String[]> pT = new ArrayList<String[]>();
		pT.add(new String[]{"F", "TA"});
		BNF.put("T", pT);
		List<String[]> pTA = new ArrayList<String[]>();
		pTA.add(new String[]{"*", "F", "TA"});
		pTA.add(new String[]{"/", "F", "TA"});
		pTA.add(new String[]{""});
		BNF.put("TA", pTA);
		List<String[]> pF = new ArrayList<String[]>();
		pF.add(new String[]{"INT"});
		pF.add(new String[]{"(", "E", ")"});
		BNF.put("F", pF);
		
		//specify terminal symbol regular expression table
		Map<String, String> termRegex = new HashMap<String, String>();
		termRegex.put("+", "\\+");
		termRegex.put("-", "\\-");
		termRegex.put("*", "\\*");
		termRegex.put("/", "/");
		termRegex.put("(", "\\(");
		termRegex.put(")", "\\)");
		termRegex.put("INT", "[0-9]");
		
		CFG cfg = new CFG(BNF, "E", termRegex);
		boolean b = cfg.recognize("(1 + 1)*2");
		System.out.println(b);
	}
}