构造SLR语法分析表
方法:
1)构造G‘的规范LR(0)项集族
2)根据规则生成动作
3)生成转换
4)设置报错
/** * P157 规范LR(0)项集族 * @param grammar */ public List<SetOfItems> items(Grammar grammar) { int setId = 0; List<SetOfItems> result = new ArrayList<>(); Map<Symbol, SetOfItems> gotoMap = new HashMap<>(); List<Production> production = grammar.getProduction(grammar.start); // 开始状态 SetOfItems startSet = new SetOfItems(); startSet.add(Item.of(production.get(0), 0)); startSet = closure(startSet, grammar); startSet.setId(setId++); result.add(startSet); boolean hasNew;// 是否产生新的项集 do { hasNew = false; List<SetOfItems> allSet = new ArrayList<>(result); for (SetOfItems setOfItems : allSet) { for (Symbol symbol : grammar.allSymbols) { SetOfItems gotoTarget = gotoSet(grammar, setOfItems, symbol); // 在符号symbol上没有GOTO集合 if (gotoTarget == null) { continue; } // 判断项集是否已经存在 SetOfItems pre = CollectionUtil.find(result, gotoTarget); if (pre != null) {// 已经存在只记录GOTO setOfItems.addGoto(symbol, pre); continue; } gotoTarget.setId(setId++); setOfItems.addGoto(symbol, gotoTarget); result.add(gotoTarget); hasNew = true; } } } while (hasNew); return result; }
语法分析表的结构
1.动作函数ACTION,移入,规约,接受,报错
2.转换函数GOTO
/** * 语法分析表 */ public class ParsingTable { private Map<Integer, Map<Symbol, Action>> set_symbol_action = new HashMap<>(); private Map<Integer, Map<Symbol, Integer>> set_symbol_set = new HashMap<>(); public void addAction(int fromId, Symbol symbol, Action action) { Map<Symbol, Action> actionMap = set_symbol_action.computeIfAbsent(fromId, k -> new HashMap<>()); actionMap.put(symbol, action); } public void addGoto(int fromId, Symbol symbol, int toId) { Map<Symbol, Integer> actionMap = set_symbol_set.computeIfAbsent(fromId, k -> new HashMap<>()); actionMap.put(symbol, toId); } public Action getAction(int setId, Symbol symbol) { Map<Symbol, Action> actionMap = set_symbol_action.get(setId); if (actionMap == null) { return null; } return actionMap.get(symbol); } public Integer gotoSet(int setId, Symbol symbol) { Map<Symbol, Integer> setMap = set_symbol_set.get(setId); if (setMap == null) { return null; } return setMap.get(symbol); } }
构建语法分析表
/** * 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) { for (Item item : from.getItems()) { if (item.pos != item.getProduction().getBody().size()) { continue; } Nonterminal head = item.getProduction().getHead(); if (head.equals(grammar.start)) { // 如果[S' -> S·]在I中,那么将ACTION[i $]设置为接受 Set<Terminal> follows = grammar.follow(head); for (Terminal symbol : follows) { result.addAction(from.getId(), symbol, AcceptAction.of()); } } else { // 如果[A -> α·]在I中,那么对于所有FOLLOW(A)中的所有a,将ACTION[i a]设置为规约 Set<Terminal> follows = grammar.follow(head); for (Terminal symbol : follows) { 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β]在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; }
标签:set,grammar,symbol,构造,SLR,new,语法分析,setId,result From: https://www.cnblogs.com/kashin/p/17795622.html