手把手教你用Java实现算符优先分析器：从FIRSTVT/LASTVT到完整语法分析

用Java实现算符优先分析器的实战指南编译原理课程中的语法分析环节常常让学生感到头疼尤其是算符优先分析法这种需要同时处理理论推导和代码实现的课题。本文将从零开始带你用Java完整实现一个算符优先分析器重点解决学生在实验环节常见的三大痛点FIRSTVT/LASTVT集合的构造、优先关系表的生成以及移进-归约过程的实现。1. 理解算符优先分析的核心概念算符优先分析法本质上是一种特殊的自底向上语法分析方法它通过比较相邻运算符的优先级来决定分析动作。与LR分析相比它的实现更简单特别适合处理表达式语法。关键术语解析FIRSTVT(P)非终结符P能推导出的最左终结符集合LASTVT(P)非终结符P能推导出的最右终结符集合优先关系三种关系(,,)决定了分析栈的操作我们以以下文法为例贯穿全文实现E → ET | T T → T*F | F F → P^F | P P → (E) | i2. 数据结构设计与初始化任何语法分析器的实现都始于合理的数据结构设计。我们创建Experiment4类声明核心数据结构// 终结符和非终结符定义 public static final char[] T {, *, ^, i, (, ), #}; public static final char[] N {E, T, F, P}; // 核心数据结构 public static boolean[][] firstvt new boolean[N.length][T.length]; public static boolean[][] lastvt new boolean[N.length][T.length]; public static Character[][] priorityTables new Character[T.length][T.length]; public static Character[] stack new Character[100]; // 分析栈这里使用二维布尔数组存储FIRSTVT和LASTVT集合字符二维数组存储优先关系表。这种设计既节省空间又便于快速查询。3. 构造FIRSTVT和LASTVT集合3.1 FIRSTVT集合构造算法实现根据定义FIRSTVT的构造分为两个阶段public static void getFirstVT() { // 初始化 for(int i0; iN.length; i) Arrays.fill(firstvt[i], false); // 第一阶段处理直接出现在产生式首位的终结符 for(String production : normativeGrammar) { char nonTerminal production.charAt(0); for(int j2; jproduction.length(); j) { if(isTerminal(production.charAt(j))) { setFirstVT(nonTerminal, production.charAt(j)); break; } } } // 第二阶段处理传递关系 boolean changed; do { changed false; for(String production : normativeGrammar) { if(production.length()2 isNonTerminal(production.charAt(2))) { changed | mergeFirstVT( production.charAt(0), production.charAt(2) ); } } } while(changed); }辅助方法mergeFirstVT负责合并两个非终结符的FIRSTVT集合private static boolean mergeFirstVT(char target, char source) { boolean changed false; int rowTarget getNonTerminalIndex(target); int rowSource getNonTerminalIndex(source); for(int j0; jT.length; j) { if(!firstvt[rowTarget][j] firstvt[rowSource][j]) { firstvt[rowTarget][j] true; changed true; } } return changed; }3.2 LASTVT集合的对称实现LASTVT的构造与FIRSTVT类似只是改为从产生式末尾向前扫描public static void getLastVT() { // 初始化代码与getFirstVT类似... // 扫描方向改为从右向左 for(String production : normativeGrammar) { char nonTerminal production.charAt(0); for(int jproduction.length()-1; j2; j--) { if(isTerminal(production.charAt(j))) { setLastVT(nonTerminal, production.charAt(j)); break; } } } // 传递关系处理也相应调整... }4. 构建算符优先关系表有了FIRSTVT和LASTVT集合我们就可以构建优先关系表了。这是整个分析器的核心决策依据。public static void buildPriorityTable() { // 初始化所有关系为null for(int i0; iT.length; i) Arrays.fill(priorityTables[i], null); // 处理四种优先关系情形 for(String production : normativeGrammar) { for(int i2; iproduction.length()-1; i) { char current production.charAt(i); char next production.charAt(i1); // 情形1相邻终结符 a b if(isTerminal(current) isTerminal(next)) { setPriority(current, next, ); } // 情形2a C b 形式(a,b为终结符C为非终结符) if(iproduction.length()-2 isTerminal(current) isTerminal(production.charAt(i2)) isNonTerminal(next)) { setPriority(current, production.charAt(i2), ); } // 情形3a是非终结符b是终结符 if(isTerminal(current) isNonTerminal(next)) { int ntIndex getNonTerminalIndex(next); for(int j0; jT.length; j) { if(firstvt[ntIndex][j]) { setPriority(current, T[j], ); } } } // 情形4a是非终结符b是终结符 if(isNonTerminal(current) isTerminal(next)) { int ntIndex getNonTerminalIndex(current); for(int j0; jT.length; j) { if(lastvt[ntIndex][j]) { setPriority(T[j], next, ); } } } } } // 处理边界情况#的优先级 int sharpIndex T.length-1; for(int i0; isharpIndex; i) { priorityTables[i][sharpIndex] ; priorityTables[sharpIndex][i] ; } priorityTables[sharpIndex][sharpIndex] ; }5. 移进-归约分析过程实现有了优先关系表我们就可以实现核心的分析算法了。这个过程需要维护一个分析栈和输入缓冲区。public static void parse() { stack[0] #; // 初始化栈 int top 0; // 栈顶指针 int inputPos 0; printStep(top, inputPos, 初始化); while(true) { // 找到栈中最顶层的终结符 int j (isTerminal(stack[top])) ? top : top-1; // 获取当前输入符号 char a inputString.charAt(inputPos); // 根据优先关系决定动作 switch(getPriority(stack[j], a)) { case : case : // 移进动作 stack[top] a; inputPos; printStep(top, inputPos, 移进); break; case : // 归约动作 do { char Q stack[j]; if(isTerminal(stack[j-1])) { j--; } else { j - 2; } } while(getPriority(stack[j], stack[j1]) ! ); // 执行归约 char left reduce(j1, top); top j1; stack[top] left; printStep(top, inputPos, 归约到 left); break; default: throw new RuntimeException(语法错误); } // 接受判断 if(stack[top] E a #) { printStep(top, inputPos, 接受); break; } } }归约函数reduce需要根据栈内容找到最左素短语private static char reduce(int start, int end) { // 构建栈顶符号串 StringBuilder sb new StringBuilder(); for(int istart; iend; i) sb.append(stack[i]); String handle sb.toString(); // 匹配产生式右部 for(String production : normativeGrammar) { String right production.substring(2); if(right.equals(handle)) { return production.charAt(0); } } // 处理部分匹配情况(如ET) if(handle.length()1 handle.charAt(1)) return E; if(handle.length()1 handle.charAt(1)*) return T; if(handle.length()1 handle.charAt(1)^) return F; if(handle.startsWith((E))) return P; throw new RuntimeException(无法归约: handle); }6. 调试技巧与常见问题解决在实际实现过程中以下几个调试技巧非常有用优先关系表可视化 打印出优先关系表确保所有关系正确建立public static void printPriorityTable() { System.out.print( ); for(char t : T) System.out.printf(%3c, t); System.out.println(); for(int i0; iT.length; i) { System.out.printf(%3c, T[i]); for(int j0; jT.length; j) { System.out.printf(%3s, priorityTables[i][j]null ? : priorityTables[i][j]); } System.out.println(); } }FIRSTVT/LASTVT集合验证 编写单元测试验证集合计算结果是否符合预期。分析过程跟踪 像示例代码中的printStep方法一样在关键步骤打印栈状态和输入剩余部分。常见问题解决方案优先级关系冲突检查文法是否满足算符优先文法的条件归约失败确认所有可能的右部都在reduce方法中处理无限循环检查优先关系表的对称性和边界条件7. 完整流程测试示例让我们以输入字符串ii*i#为例观察分析过程步骤 栈 输入串 动作 0 # ii*i# 初始化 1 #i i*i# 移进 2 #E i*i# 归约到 E 3 #E i*i# 移进 4 #Ei *i# 移进 5 #EE *i# 归约到 E 6 #EE* i# 移进 7 #EE*i # 移进 8 #EE*E # 归约到 E 9 #EE # 归约到 E 10 #E # 归约到 E 11 #E# 接受这个输出清晰地展示了移进和归约的交替过程最终成功接受输入字符串。