语法分析器的两个重要函数 FIRST和FOLLOW
一、FOLLOW的定义
在句型中紧跟在A右边的终结符号的集合
如果A是某些句型的最右符号，那么$在FOLLOW(A)中
A：非终结符
二、计算方法
循环应用下面的规则
1）将$放到FOLLOW(S)中，S是开始符号，$是输入右端的结束标记
2）如果存在一个产生式A->αBβ，那么FIRST(β)中除ε之外的所有符号都在FOLLOW(B)中
3）如果存在一个产生式A->αB，或A->αBβ且FIRST(β)包含ε，那么FOLLOW(A)中的所有符号都在FOLLOW(B)中
三、代码实现
/** * P141 FOLLOW(A)集合 * @param symbol * @return */ public Set<Terminal> follow(Nonterminal symbol) { Set<Terminal> result = new HashSet<>(); // 将$放到FOLLOW(S)中，S是开始符号，$是输入右端的结束标记 if (symbol.equals(start)) { result.add(Terminal.dollar); } // 遍历所有产生式 for (Production production : this.productions) { if (!production.getBody().contains(symbol)) { continue; } for (int i=0; i<production.getBody().size(); i++) { Symbol tmp = production.getBody().get(i); if (!tmp.equals(symbol)) { continue; } if (i + 1 == production.getBody().size()) { if (production.getHead().equals(symbol)) { continue; } //如果存在一个产生式A->αB，那么FOLLOW(A)中的所有符号都在FOLLOW(B)中 Set<Terminal> headFollow = follow(production.getHead()); result.addAll(headFollow); } else { List<Symbol> tokens = new ArrayList<>(); for (int j=i+1; j<production.getBody().size(); j++) { tokens.add(production.getBody().get(j)); } Set<Terminal> afterBFirst = first(tokens); //如果存在一个产生式\A->αBβ且FIRST(β)包含ε，那么FOLLOW(A)中的所有符号都在FOLLOW(B)中 if (afterBFirst.contains(Terminal.epsilon)) { if (!production.getHead().equals(symbol)) { Set<Terminal> headFollow = follow(production.getHead()); result.addAll(headFollow); } } //如果存在一个产生式A->αBβ，那么FIRST(β)中除ε之外的所有符号都在FOLLOW(B)中 afterBFirst.remove(Terminal.epsilon); result.addAll(afterBFirst); } } } return result; }