语法制导的实现可以有很多中,如后缀翻译方案,L属性定义的SDT,遍历语法分析树
这里选择使用语法分析树来实现,即
1.建立一棵语法分析树
2.按照从左到右的深度优先顺序执行动作
3.产生式体中的动作在它左边的所有文法符号都被匹配之后立刻执行
这样选择的理由是,非常通用任何SDT都可以实现
一、首先改造之前的语法分析,在分析过程中构造一个语法分析树,在分析完成后返回根节点
语法分析树是推导的图形表示形式,每个内部结点表示一个产生式的应用。
因此,只要在使用产生式进行规约时生成相应树结构就可以完成构造
public Node parseWithNode(Grammar grammar, List<Symbol> inputs, ParsingTable table) { LinkedList<Symbol> inputQueue = new LinkedList<>(inputs); inputQueue.addLast(Terminal.dollar); // 符号栈 (方便打印) Stack<Symbol> symbolStack = new Stack<>(); final int initStateCode = 0;// 初始状态 // 状态栈 Stack<StateStackItem> stateStack = new Stack<>(); stateStack.push(StateStackItem.of(initStateCode)); while (true) { StateStackItem state = stateStack.peek();// 当前状态 printStack(state, symbolStack, inputQueue); Symbol symbol = inputQueue.getFirst(); Action action = table.getAction(state.getState(), symbol); if (action instanceof ShiftAction) {// 移入 inputQueue.removeFirst(); ShiftAction shiftAction = (ShiftAction) action; stateStack.push(StateStackItem.of(shiftAction.getToId())); symbolStack.push(symbol); LogUtil.print("移入:" + shiftAction.getToId()); LogUtil.newline(); } else if (action instanceof ReduceAction) {// 规约 ReduceAction reduceAction = (ReduceAction) action; Production production = reduceAction.getProduction(); Node node = Node.of(production.getHead()); node.setProduction(production); for (Symbol bo : production.getBody()) { if (bo.equals(Terminal.epsilon)) {// 形如 E -> ·ε,不需要弹出产生式的体,直接进行规约 continue; } StateStackItem item = stateStack.pop(); Symbol childSymbol = symbolStack.pop(); Node child; if (item.getValue() == null) {// 终结符 child = Node.of(childSymbol); } else { child = (Node) item.getValue(); } // 由于符号栈的顶端时产生式体的右边,将后面的节点添加到子节点列表的前面,即左边 node.addChildFirst(child); } symbolStack.push(production.getHead()); state = stateStack.peek(); Integer gotoState = table.gotoSet(state.getState(), production.getHead()); StateStackItem item = StateStackItem.of(gotoState); item.setValue(node); stateStack.push(item); LogUtil.print("规约:" + production + " GOTO:" + gotoState); LogUtil.newline(); } else if (action instanceof AcceptAction) { LogUtil.print("接受"); LogUtil.newline(); return (Node) stateStack.peek().getValue(); } else { LogUtil.print("错误"); LogUtil.newline(); return null; } } }
标签:Node,StateStackItem,语法,item,production,LogUtil,应用,制导,stateStack From: https://www.cnblogs.com/kashin/p/17931697.html