分析一下此Java代码的parser函数:public boolean parse(String input) { Stack<String> inStack = new Stack<String>(); Stack<String> outStack = new Stack<String>(); outStack.push(startSymbolMap); for (int i = 0; i < input.length(); i++) { inStack.push(String.valueOf(input.charAt(input.length() - 1 - i))); } while (!outStack.isEmpty()) { if (isTerminal(outStack.peek())) { if (outStack.peek().equals(inStack.peek())) { outStack.pop(); inStack.pop(); } else { return false; } } else { Map<String, String> n = parseTable.get(outStack.peek()); String m = n.get(inStack.peek()); if(m!=null){ System.out.println(m); outStack.pop(); for (int k = m.length()-1; k>2; k--) { outStack.push(String.valueOf(m.charAt(k))); } }} } if (outStack.isEmpty() && inStack.isEmpty()) { return true; }else { return false; } }
时间: 2024-02-14 19:11:08 浏览: 25
这是一个简单的自顶向下的语法分析器。该函数接受一个字符串输入,然后按照给定的文法规则进行语法分析。主要分为以下几个步骤:
1. 创建两个栈,一个输入栈 inStack 和一个输出栈 outStack。
2. 将起始符号 startSymbolMap 压入输出栈中。
3. 将输入字符串中的每个字符压入输入栈 inStack 中。
4. 当输出栈不为空时,对栈顶进行判断:
- 如果是终结符号,则与输入栈顶进行比较,如果相等则将两个栈顶元素弹出,否则返回 false。
- 如果是非终结符号,则根据 LL(1) 文法分析表中对应的产生式进行推导,并将产生式右部逆序压入输出栈中。
5. 循环执行步骤 4 直到输出栈为空。
6. 最后判断输入栈和输出栈是否都为空,如果是则返回 true,否则返回 false。
需要注意的是,该函数依赖于一个 LL(1) 文法分析表,该表的结构是一个 Map,其中键为非终结符号,值为一个 Map,其键为终结符号,值为对应的产生式。此外,isTerminal 函数用于判断一个符号是否为终结符号。
相关问题
public class DFALexer { public static boolean dfaRecognize(Map<String, Object> dfa, String inputStr) { return true } public static Map<String, Object> json_file2map(String fileName) { JSONParser parser = new JSONParser(); Map<String, Object> dfa = new HashMap<>(); try { Object obj = parser.parse(new FileReader(fileName)); JSONObject dfaJson = (JSONObject) obj; List<Integer> endStates = new ArrayList<>(); JSONArray endStatesJson = (JSONArray) dfaJson.get("end"); for (Object stateObj : endStatesJson) { endStates.add(((Long) stateObj).intValue()); } List<String> symbols = new ArrayList<>(); JSONArray symbolsJson = (JSONArray) dfaJson.get("syms"); for (Object symbolObj : symbolsJson) { symbols.add((String) symbolObj); } List<List<Integer>> transitions = new ArrayList<>(); JSONArray transitionsJson = (JSONArray) dfaJson.get("transfer"); for (Object transitionObj : transitionsJson) { JSONArray transitionJson = (JSONArray) transitionObj; List<Integer> transition = new ArrayList<>(); for (Object valueObj : transitionJson) { if (valueObj instanceof String) { transition.add((int) ((String) valueObj).charAt(0)); } else { transition.add(((Long) valueObj).intValue()); } } transitions.add(transition); } dfa.put("end", endStates); dfa.put("start", ((Long) dfaJson.get("start")).intValue()); dfa.put("syms", symbols); dfa.put("transfer", transitions); } catch (Exception e) { e.printStackTrace(); } return dfa; }在这段代码实现DFA识别方法,要求:inpuStr被成功接收则返回true,不成功接收则返回false
public class DFALexer {
public static boolean dfaRecognize(Map<String, Object> dfa, String inputStr) {
int currentState = (int)dfa.get("start");
List<List<Integer>> transitions = (List<List<Integer>>)dfa.get("transfer");
List<Integer> endStates = (List<Integer>)dfa.get("end");
List<String> symbols = (List<String>)dfa.get("syms");
for (int i = 0; i < inputStr.length(); i++) {
char c = inputStr.charAt(i);
int symbolIndex = symbols.indexOf(String.valueOf(c));
if (symbolIndex == -1) {
return false;
}
currentState = transitions.get(currentState).get(symbolIndex);
}
return endStates.contains(currentState);
}
public static Map<String, Object> json_file2map(String fileName) {
JSONParser parser = new JSONParser();
Map<String, Object> dfa = new HashMap<>();
try {
Object obj = parser.parse(new FileReader(fileName));
JSONObject dfaJson = (JSONObject) obj;
List<Integer> endStates = new ArrayList<>();
JSONArray endStatesJson = (JSONArray) dfaJson.get("end");
for (Object stateObj : endStatesJson) {
endStates.add(((Long) stateObj).intValue());
}
List<String> symbols = new ArrayList<>();
JSONArray symbolsJson = (JSONArray) dfaJson.get("syms");
for (Object symbolObj : symbolsJson) {
symbols.add((String) symbolObj);
}
List<List<Integer>> transitions = new ArrayList<>();
JSONArray transitionsJson = (JSONArray) dfaJson.get("transfer");
for (Object transitionObj : transitionsJson) {
JSONArray transitionJson = (JSONArray) transitionObj;
List<Integer> transition = new ArrayList<>();
for (Object valueObj : transitionJson) {
if (valueObj instanceof String) {
transition.add((int) ((String) valueObj).charAt(0));
} else {
transition.add(((Long) valueObj).intValue());
}
}
transitions.add(transition);
}
dfa.put("end", endStates);
dfa.put("start", ((Long) dfaJson.get("start")).intValue());
dfa.put("syms", symbols);
dfa.put("transfer", transitions);
} catch (Exception e) {
e.printStackTrace();
}
return dfa;
}
}
需要注意的是,这里的DFA是由一个JSON文件转换而来的,JSON文件应该包含以下属性:
- start:DFA的起始状态
- end:DFA的终止状态
- syms:DFA的输入字符集
- transfer:DFA的转移函数,用二维数组表示
如果JSON文件格式有误,会抛出异常并返回空的DFA。
完善代码:public class LLParserExample { // 预测分析表 private Map<String, Map<String, String>> parseTable; private String startSymbolMap; private String []terminalSymbol; public LLParserExample(String startSymbolMap, String []terminalSymbol, Map<String, Map<String, String>> parseTable) { this.parseTable = parseTable; this.startSymbolMap = startSymbolMap; this.terminalSymbol = terminalSymbol; } public boolean parse(String input) { return false; } // 判断符号是否是终结符 private boolean isTerminal(String symbol) { for (int i=0; i<this.terminalSymbol.length ; i++) { if(this.terminalSymbol[i].equals(symbol)) return true; } return false; } public static void main(String[] args) { //文法终结符号集合 String []tSymbols = {"a","b"}; // 初始化预测分析表 Map<String, Map<String, String>> parseTable; parseTable = new HashMap<>(); Map<String, String> row1 = new HashMap<>(); row1.put("a", "A->aB"); row1.put("b", "A->b"); parseTable.put("A", row1); Map<String, String> row2 = new HashMap<>(); row2.put("a", "B->a"); row2.put("b", "B->bA"); parseTable.put("B", row2); //初始化LL(1)分析器 LLParserExample parser = new LLParserExample("A", tSymbols, parseTable); //分析input是否为文法的一个句子并输出产生式序列 String input = "abaa"; boolean success = parser.parse(input); if (success) { System.out.println("分析成功"); } else { System.out.println("分析失败"); } } }
public class LLParserExample {
// 预测分析表
private Map<String, Map<String, String>> parseTable;
private String startSymbolMap;
private String[] terminalSymbol;
public LLParserExample(String startSymbolMap, String[] terminalSymbol, Map<String, Map<String, String>> parseTable) {
this.parseTable = parseTable;
this.startSymbolMap = startSymbolMap;
this.terminalSymbol = terminalSymbol;
}
public boolean parse(String input) {
Stack<String> stack = new Stack<>();
stack.push("$"); // 将结束符号入栈
stack.push(this.startSymbolMap); // 将文法的开始符号入栈
int index = 0; // 输入串的指针
while (!stack.isEmpty()) {
String top = stack.pop(); // 栈顶元素出栈
if (this.isTerminal(top)) { // 如果栈顶为终结符
if (top.equals("$")) { // 如果栈顶为结束符号
return input.charAt(index) == '$'; // 如果输入串也为结束符号,则分析成功
}
if (top.equals(String.valueOf(input.charAt(index)))) { // 如果栈顶与输入串指针所指字符相同
index++; // 输入串指针后移
} else {
return false; // 分析失败
}
} else { // 如果栈顶为非终结符
Map<String, String> row = this.parseTable.get(top); // 获取预测分析表中该非终结符对应的一行
String production = row.get(String.valueOf(input.charAt(index))); // 获取该行中与输入串指针所指字符相对应的产生式
if (production == null) { // 如果找不到对应的产生式
return false; // 分析失败
}
String[] symbols = production.split("->")[1].split(""); // 获取产生式右部的符号序列
for (int i = symbols.length - 1; i >= 0; i--) { // 将产生式右部的符号序列逆序入栈
stack.push(symbols[i]);
}
}
}
return false; // 分析失败
}
// 判断符号是否是终结符
private boolean isTerminal(String symbol) {
for (int i = 0; i < this.terminalSymbol.length; i++) {
if (this.terminalSymbol[i].equals(symbol))
return true;
}
return false;
}
public static void main(String[] args) {
// 文法终结符号集合
String[] tSymbols = {"a", "b"};
// 初始化预测分析表
Map<String, Map<String, String>> parseTable;
parseTable = new HashMap<>();
Map<String, String> row1 = new HashMap<>();
row1.put("a", "A->aB");
row1.put("b", "A->b");
parseTable.put("A", row1);
Map<String, String> row2 = new HashMap<>();
row2.put("a", "B->a");
row2.put("b", "B->bA");
parseTable.put("B", row2);
// 初始化LL(1)分析器
LLParserExample parser = new LLParserExample("A", tSymbols, parseTable);
// 分析input是否为文法的一个句子并输出产生式序列
String input = "abaa";
boolean success = parser.parse(input);
if (success) {
System.out.println("分析成功");
} else {
System.out.println("分析失败");
}
}
}