前面已经实现了SLR语法分析表,但是可能会出现即使语法不是二义性文法,也存在移入/规约冲突
状态 i 包含项[A ->α ],当状态 i 出现在栈顶时,栈中的可行前缀时βα且在任何最后句型中a都不可能跟在βA之后,
那么当输入a时不应该A->α进行规约
为了解决这个问题, 引入更强大的构造语法分析表方法:
1.规范LR(1)语法分析表
2.LALR语法分析表
一、规范LR(1)项
形式:[A -> α · β, a],a为一个终结符
作用:[A -> α · , a]只有在一下输入符号等于a时才要求按照A -> α进行规约
/** * LR(1)项 P166 */ public class LR1Item extends Item { /** 向前看符号 */ private List<Terminal> lookaheads; @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; if (!super.equals(o)) return false; LR1Item lr1Item = (LR1Item) o; return Objects.equals(lookaheads, lr1Item.lookaheads); } @Override public int hashCode() { return Objects.hash(super.hashCode(), lookaheads); } }
闭包函数
/** * LR(1)项集族的构造方法 P167 * @param setOfItems * @param grammar * @return */ public SetOfItems closure(SetOfItems setOfItems, Grammar grammar) { SetOfItems result = new SetOfItems(); Set<LR1Item> oldItems = setOfItems.getItems(); for (LR1Item item : oldItems) { result.add(item); } boolean hasAdd; do { hasAdd = false; Set<LR1Item> items = new HashSet<>(result.getItems()); for (LR1Item item : items) {// I中的每个项[A → α·Bβ,a] Symbol symbolAfterDot = item.getSymbolAfterDot();// B if (symbolAfterDot == null) { continue; } if (!(symbolAfterDot instanceof Nonterminal)) { continue; } List<Symbol> symbolAfter = item.getSymbolAfterDot1();//β Set<Terminal> first = grammar.first(symbolAfter);// first(β) if (first.contains(Terminal.epsilon)) { first.addAll(item.getLookaheads()); } first.remove(Terminal.epsilon);// lookahead不包含ε List<Production> productionList = grammar.getProduction((Nonterminal) symbolAfterDot); for (Production production : productionList) { LR1Item newItem = LR1Item.of(production, 0, new ArrayList<>(first)); if (!result.contains(newItem)) { result.add(newItem); hasAdd = true; } } } } while (hasAdd); return result; }
构造SLR语法分析表
/** * P161 算法4.46 构造一个SLR语法分析表 * @param grammar * @param setList * @return */ public ParsingTable buildParsingTable(Grammar grammar, List<SetOfItems> setList) { ParsingTable result = new ParsingTable(); for (SetOfItems from : setList) { Set<LR1Item> items = from.getItems(); for (LR1Item item : items) { if (item.pos != item.getProduction().getBody().size()) { continue; } Nonterminal head = item.getProduction().getHead(); if (head.equals(grammar.start)) { // 如果[S' -> S· $]在I中,那么将ACTION[i $]设置为接受 for (Terminal lookahead : item.getLookaheads()) { result.addAction(from.getId(), lookahead, AcceptAction.of()); } } else { // 如果[A -> α· a]在I中,那么将ACTION[i a]设置为规约 for (Terminal symbol : item.getLookaheads()) { result.addAction(from.getId(), symbol, ReduceAction.of(item.getProduction())); } } } for (Map.Entry<Symbol, SetOfItems> entry : from.getGotoMap().entrySet()) { Symbol symbol = entry.getKey(); SetOfItems to = entry.getValue(); // 如果[A -> α·aβ, b]在from中并且GOTO(from, a) = to,那么将Action[from,a]设置为移入to,a必须为一个终结符 if (symbol instanceof Terminal) { result.addAction(from.getId(), symbol, ShiftAction.of(to.getId())); } else { result.addGoto(from.getId(), symbol, to.getId()); } } } return result; }
标签:return,grammar,LR1Item,规范,item,LR,result,语法分析 From: https://www.cnblogs.com/kashin/p/17814053.html