LR语法分析器
组成:一个输入,一个输出,状态栈,驱动程序,语法分析表
注意:规约后需要寻找新的符号在栈顶状态上的转换
例如:
状态栈 符号栈 输入
0 5 $id *id$ 此时需要按F -> id规约
0 3 $F *id$ 3是规约的新符号F在栈顶状态0上的转换
代码实现
/** * P159 算法4.44 LR语法分析算法 */ public boolean parse(Grammar grammar, List<Symbol> inputs, ParsingTable table) { LinkedList<Symbol> inputQueue = new LinkedList<>(inputs); inputQueue.addLast(Terminal.dollar); // 符号栈 (方便打印) Stack<Symbol> symbolStack = new Stack<>(); int state = 0;// 当前状态 // 状态栈 Stack<Integer> stateStack = new Stack<>(); stateStack.push(state); while (true) { state = stateStack.peek(); printStack(state, symbolStack, inputQueue); Symbol symbol = inputQueue.getFirst(); Action action = table.getAction(state, symbol); if (action instanceof ShiftAction) {// 移入 inputQueue.removeFirst(); ShiftAction shiftAction = (ShiftAction) action; stateStack.push(shiftAction.getToId()); symbolStack.push(symbol); LogUtil.print("移入:" + shiftAction.getToId()); LogUtil.newline(); } else if (action instanceof ReduceAction) {// 规约 ReduceAction reduceAction = (ReduceAction) action; Production production = reduceAction.getProduction(); for (Symbol bo : production.getBody()) { if (bo.equals(Terminal.epsilon)) { continue; } stateStack.pop(); symbolStack.pop(); } symbolStack.push(production.getHead()); state = stateStack.peek(); Integer gotoState = table.gotoSet(state, production.getHead()); stateStack.push(gotoState); LogUtil.print("规约:" + production + " GOTO:" + gotoState); LogUtil.newline(); } else if (action instanceof AcceptAction) { LogUtil.print("接受"); return true; } else { LogUtil.print("错误"); return false; } } }
标签:语法分析,inputQueue,state,算法,production,LR,LogUtil,action,stateStack From: https://www.cnblogs.com/kashin/p/17880781.html