一、 实验目的

根据算符优先分析法，对表达式进行语法分析，使其能够判断一个表达式是否正确。通过算符优先分析方法的实现，加深对自下而上语法分析方法的理解。

二、 实验内容

1、输入文法。可以是如下算术表达式的文法（你可以根据需要适当改变）：
E→E+T|E-T|T
T→T*F|T/F|F
F→（E）|i

2、对给定表达式进行分析，输出表达式正确与否的判断。
程序输入/输出示例：
输入：1+2;
输出：正确
输入：(1+2)/3+4-(5+6/7);
输出：正确
输入：((1-2)/3+4
输出：错误
输入：1+2-3+(*4/5)
输出：错误

3、参考数据结构
char *VN=0,*VT=0;//非终结符和终结符数组
char firstvt[N][N],lastvt[N][N],table[N][N];
typedef struct //符号对(P,a)
{
char Vn;
char Vt;
} VN_VT;
typedef struct //栈
{
VN_VT *top;
VN_VT *bollow;
int size;
}stack;

4、根据文法求FIRSTVT集和LASTVT集

5、构造算符优先分析表

6、构造总控程序

7、对给定的表达式，给出准确与否的分析过程
8、给出表达式的计算结果。（本步骤可选作）

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.*;/*** @author [25'h]* @datetime 2022.11.02*/
public class Reducing {public static String startLabel;//开始符public static ArrayList terSymbol = new ArrayList<>();// 终结符public static ArrayList non_ter = new ArrayList<>();// 非终结符public static HashMap> formula = new HashMap<>();//产生式public static HashMap[]> firstvtAndLastvt = new HashMap<>();//FIRST  和  FOLLOW/*firstvtAndLastvt的数据含义：- key : 非终结符- value : 非终结符对应的FIRSTVT  和  FOLLOWVT 集- 1     非终结符对应的FIRSTVT- 2     非终结符对应的FOLLOWVT*/public static boolean[] booleansFirst;// 辅助变量public static boolean[] booleansLast;public static String[][] table;//优先表public static String objString;// 目标匹配字符串public static LinkedList deque;public static void main(String[] args) {File file = new File("src/StringToJAVA/test3.txt");BufferedReader bufferedReader;try {// 读取文法和目标式子bufferedReader = new BufferedReader(new FileReader(file));startLabel = bufferedReader.readLine();// 读取非终结符non_ter.addAll(Arrays.asList(bufferedReader.readLine().split(" ")));booleansFirst = new boolean[non_ter.size()];// 初始化辅助变量booleansLast = new boolean[non_ter.size()];// 初始化firstAndFollow中的Map对象for (String s : non_ter) {firstvtAndLastvt.put(s, new HashSet[]{new HashSet(), new HashSet()});}// 读取终结符terSymbol.addAll(Arrays.asList(bufferedReader.readLine().split(" ")));table = new String[terSymbol.size() + 1][terSymbol.size() + 1];//将产生式右部或表达式分离String s;while ((s = bufferedReader.readLine()).contains("->")) {String[] split = s.split("->");formula.put(split[0], Arrays.asList(split[1].split("\\|")));}// 赋值目标串objString = s;} catch (Exception e) {e.printStackTrace();}// 生成firstvt和lastvtgenerateFirstVTAndLastVT();// 生成优先分析表generateTable();// 归约reducing();show();}private static void reducing() {// 终结符中添加结尾符号terSymbol.add("#");deque = new LinkedList<>();deque.push("#");for (int i = 0; i < objString.length(); i++) {// 取出下一个字符String sub = objString.substring(i, i + 1);if (terSymbol.contains(sub)) {// 是终结符// 栈最上面的终结符是tempString temp = terSymbol.contains(deque.peek()) ? deque.peek() : deque.get(1);// 看看跟上一个终结符和sub大优先级关系String bol = table[terSymbol.indexOf(temp)][terSymbol.indexOf(sub)];// 是> 就归约if (bol.equals(">")) {func(sub);}// 归约后终结符入栈}deque.push(sub);// 直接压入showCurStack(i);}}//输出当前的栈状态private static void showCurStack(int i) {StringBuffer b = new StringBuffer();for (int j = deque.size() - 1; j >= 0; j--) {b = b.append(deque.get(j));}if (i != objString.length() - 1)b = b.append("\t\t\t").append(objString.substring(i + 1));System.out.println(b.toString());}private static void func(String curTer) {String te;// 栈顶非终结符读出if (!terSymbol.contains(deque.peek())) {deque.pop();}do {te = deque.pop();// 当前规约串的终结符te
// te左的非终结符if (!terSymbol.contains(deque.peek())) {deque.pop();}} while (!table[terSymbol.indexOf(deque.peek())][terSymbol.indexOf(te)].equals("<"));// 栈顶终结符te = deque.peek();deque.push("N");// 标记// 若还是>,则递归调用if (table[terSymbol.indexOf(te)][terSymbol.indexOf(curTer)].equals(">")) {func(curTer);}}private static void generateTable() {// 对于每个公式都要取出终结符for (String non : formula.keySet()) {List list = formula.get(non);//non这个非终结符对应的生成式for (String f : list) {// 对于每个式子fArrayList li = new ArrayList<>();// 每个式子的终结符记下来，因为他们之间的关系是=// 对式子f要查找终结符位置for (int i = 0; i < f.length(); i++) {// 对于f中每个元素subString sub = f.substring(i, i + 1);// 若是终结符if (terSymbol.contains(sub)) {li.add(sub);//几下终结符// 左边有非终结符if (i != 0 && non_ter.contains(f.substring(i - 1, i))) {//赋值“>”pre(f.substring(i - 1, i), sub);}//右边有非终结符if (i != f.length() - 1 && non_ter.contains(f.substring(i + 1, i + 2))) {//赋值“<”post(f.substring(i + 1, i + 2), sub);}}}// 想等情况赋值，注意是 j = i + 1for (int i = 0; i < li.size(); i++) {for (int j = i + 1; j < li.size(); j++) {table[terSymbol.indexOf(li.get(i))][terSymbol.indexOf(li.get(j))] = "=";}}}}// 关于#的赋值Set[] sets = firstvtAndLastvt.get(startLabel);for (String s : sets[0]) {table[terSymbol.size()][terSymbol.indexOf(s)] = "<";}for (String s : sets[1]) {table[terSymbol.indexOf(s)][terSymbol.size()] = ">";}table[terSymbol.size()][terSymbol.size()] = "=";}private static void post(String non, String ter) {int index = terSymbol.indexOf(ter);Set set = firstvtAndLastvt.get(non)[0];for (String s : set) {table[index][terSymbol.indexOf(s)] = "<";}}private static void pre(String non, String ter) {int index = terSymbol.indexOf(ter);Set set = firstvtAndLastvt.get(non)[1];for (String s : set) {table[terSymbol.indexOf(s)][index] = ">";}}//生成firstvt和lastvtprivate static void generateFirstVTAndLastVT() {for (String s : non_ter) {if (!booleansFirst[non_ter.indexOf(s)])generateEachFirstVT(s);if (!booleansLast[non_ter.indexOf(s)]) {generateEachLastVT(s);}}}/*生成每个非终结符non的Lastvt集*/private static void generateEachLastVT(String non) {Set curList = firstvtAndLastvt.get(non)[1];for (String s : formula.get(non)) {// lastvt本质就是firstvt反过来的求法modify(non, curList, new StringBuffer(s).reverse().toString(), 1);}booleansLast[non_ter.indexOf(non)] = true;}/*生成每个非终结符non的Firstvt集*/private static void generateEachFirstVT(String terNon) {Set curList = firstvtAndLastvt.get(terNon)[0];for (String s : formula.get(terNon)) {modify(terNon, curList, s, 0);}booleansFirst[non_ter.indexOf(terNon)] = true;}private static void modify(String non, Set curList, String s, int i) {String firstSub = s.substring(0, 1);if (terSymbol.contains(firstSub)) {// 终结符开头curList.add(firstSub);} else {// 非终结符开头// 终结符是第二个位置if (s.length() >= 2 && terSymbol.contains(s.substring(1, 2))) {curList.add(s.substring(1, 2));}// firstSub和non相同，避免栈溢出返回if (firstSub.equals(non)) return;if (i == 0) {// 求firstvt，用booleansFirstif (!booleansFirst[non_ter.indexOf(firstSub)]) {generateEachFirstVT(firstSub);}} else {// 求lastvt，booleansLastif (!booleansLast[non_ter.indexOf(firstSub)]) {generateEachLastVT(firstSub);}}curList.addAll(firstvtAndLastvt.get(firstSub)[i]);}}private static void show() {System.out.println(startLabel);System.out.println(Arrays.toString(non_ter.toArray()));System.out.println(Arrays.toString(terSymbol.toArray()));for (String s : formula.keySet()) {System.out.println(s + "\t" + Arrays.toString(formula.get(s).toArray()));}System.out.println();for (String s : firstvtAndLastvt.keySet()) {System.out.println(s + "\t" + Arrays.toString(firstvtAndLastvt.get(s)[0].toArray()) + "\t" + Arrays.toString(firstvtAndLastvt.get(s)[1].toArray()));}System.out.println();for (String[] strings : table) {System.out.println(Arrays.toString(strings));}}}

test3.txt文件：

E
E T F
i * / + - ( )
E->E+T|E-T|T
T->T*F|T/F|F
F->(E)|i
(1+2)/3+4-(5+6/7)#

输出结果：

"D:\Program Files\Java\jdk1.8.0_291\bin\java.exe" "-javaagent:D:\IntelliJ IDEA 2020.1\lib\idea_rt.jar=54769:D:\IntelliJ IDEA 2020.1\bin" -Dfile.encoding=UTF-8 -classpath "D:\Program Files\Java\jdk1.8.0_291\jre\lib\charsets.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\deploy.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\access-bridge-64.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\cldrdata.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\dnsns.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\jaccess.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\jfxrt.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\localedata.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\nashorn.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\sunec.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\sunjce_provider.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\sunmscapi.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\sunpkcs11.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\ext\zipfs.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\javaws.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\jce.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\jfr.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\jfxswt.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\jsse.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\management-agent.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\plugin.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\resources.jar;D:\Program Files\Java\jdk1.8.0_291\jre\lib\rt.jar;D:\code_management\algorithm\out\production\algorithm" StringToJAVA.Reducing
#(			1+2)/3+4-(5+6/7)#
#(1			+2)/3+4-(5+6/7)#
#(1+			2)/3+4-(5+6/7)#
#(1+2			)/3+4-(5+6/7)#
#(N)			/3+4-(5+6/7)#
#N/			3+4-(5+6/7)#
#N/3			+4-(5+6/7)#
#N+			4-(5+6/7)#
#N+4			-(5+6/7)#
#N-			(5+6/7)#
#N-(			5+6/7)#
#N-(5			+6/7)#
#N-(5+			6/7)#
#N-(5+6			/7)#
#N-(5+6/			7)#
#N-(5+6/7			)#
#N-(N)			#
#N#
E
[E, T, F]
[i, *, /, +, -, (, ), #]
T	[T*F, T/F, F]
E	[E+T, E-T, T]
F	[(E), i]T	[(, i, *, /]	[), i, *, /]
E	[(, i, *, +, -, /]	[), i, *, +, -, /]
F	[(, i]	[), i][null, >, >, >, >, null, >, >]
[<, >, >, >, >, <, >, >]
[<, >, >, >, >, <, >, >]
[<, <, <, >, >, <, >, >]
[<, <, <, >, >, <, >, >]
[<, <, <, <, <, <, =, null]
[null, >, >, >, >, null, >, >]
[<, <, <, <, <, <, null, =]Process finished with exit code 0