编译原理-LR(0)文法算法实现(java)

作者: wo883721 | 来源:发表于2021-08-29 12:05 被阅读0次

本篇文章内的源码: 这里

我们知道 LL1 文法是自顶而下的语法分析，从文法开始符号起，采用最左推导的方式，一步一步推导出最终需要匹配的句子。
但是还有一种自底向上的语法分析，从输入的句子开始，采用最左归约的方式，一步一步归约成文法开始符号。

一. 移入-归约分析

自底向上语法分析采用的通用框架就是移入-归约分析，如下图:

移入归约.png

注意每次归约的都是句柄，也就是最左直接短语。

请参考这篇文章: 短语、直接短语、句柄

可能有的人说了， E -> E + E 不是输入符号串id + (id + id)的句柄，对的，它的确不是。但是这个时候它相对的句型就不是输入符号串，而是句型 E + (E + E), 的确是句柄。

因此移入-归约分析的过程就是:

从左到右扫描输入符号串，语法分析器将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串 β 进行归约为止。
然后将这个文法符号串 β 成某个产生式的左部。
语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空(当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析)为止。

所以分析过程有以下动作:

移入：将输入符号移到栈的顶端。
归约：将栈顶句柄的符号串进行归约，将归约后产生式左部非终结符替换这个符号串。
接收：宣布语法分析过程成功完成；
报错：发现一个语法错误，并调用错误恢复子例程。

仔细观察上面过程，你会发现判断何时归约才是最重要的，因为其他操作只是将输入符号移入栈中而已。
而判断归约就是要正确识别句柄，否则就会出现以下问题：

移入归约问题.png

图中 <IDS>, i 和 i 都是产生式的右部，但是i 并不是当前句型 var <IDS>, i 的句柄，所以不能用它进行归约。

其实我们可以换一个思路:

当识别到句型 var <IDS>, 时，其实已经算是识别到产生式1 <S> -> var <IDS> : <T> 的前面部分 <S> -> var <IDS> 和产生式3 <IDS> -> <IDS>, i 的前面部分<IDS>,。

此时遇到输入符号 i 时，肯定是归约产生式3了。

可以看出句柄是逐步形成的，用状态表示句柄识别的进展程度，而这个状态 在LR分析法中被称为项目。

二. LR分析法

2.1 LR(0)项目

2.1.1 项目定义

因此我们将右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）： A -> α • β

例如：产生式 S -> bBB

S-> •bBB (移进项目)

S-> b•BB (待约项目)
S-> bB•B (待约项目)

S-> bBB• (归约项目)
项目描述了句柄识别的状态；右侧有k个符号，则有k+1个项目。

2.1.2 后继项目

同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目。

例如: A→α•Xβ 的后继项目是 A→αX•β

2.1.3 等价项目

例如文法

文法G:
A -> aB
B -> b | c

你会发现项目 a•B 和 •b, •c 是等价的。
因为B 是非终结符，匹配 •B 就是要匹配 B 对应的产生式右部中的一个，所以•b, •c 与 •B 等价。

2.1.3 项目集

将等价项目组成一个集合，称为项目集(I)，也项目集闭包(Closure of Item Sets), 每个项目集对应着自动机的一个状态。

2.2 LR(0)分析表

2.2.1 CLOSURE() 函数

这个是求项目集闭包的方法，有如下定义:

CLOSURE() 函数定义.png

这个公式的含义就是，项目集I 的闭包等于

这个项目集I

与项目集闭包中任何 α•Bβ 项目对应 B -> •y 项目加入之后集合的合集。

对应的算法就是:

CLOSURE() 算法.png

这个算法理解起来很简单，就是找出 项目集I 所有的等价项目。

2.2.2 GOTO()函数

将方法就是返回 项目集I 对应文法符号X 的后继项目集。

GOTO()函数.png

先遍历当前项目集中所有项目，看有没有对应文法符号X 的后继项目。例如 A→α•Xβ 后继项目是 A→αX•β。
如果没有任何匹配，就返回 null，表示当前项目集没有对应文法符号X 的后继项目集。
如果有匹配，那么再通过 CLOSURE 方法，求这些匹配项目所有的等价项目，一起组成了当前项目集对应文法符号X 的后继项目集。

2.2.3 文法所有项目集

状态集.png

这个方法是求文法对应的所有项目集，因此从文法开始符号对应的项目集起，求它对应每个文法符号(包括终结符和非终结符)得到后继项目集，再求这些后继项目集对应每个文法符号的后继项目集，直到没有新的后继项目集产生，那么就代表获取的所有项目集。

2.2.4 LR(0)分析表

得到文法对应的所有项目集，来开始构造LR(0)分析表了：

LR(0)分析表.png

还记得移入-归约分析的过程么，就是从左到右扫描输入符号串，将输入符号移入栈顶，直到能够对栈顶的文法符号串进行归约，将它归约成某个产生式的左部，重复上面过程，直到遍历完输入符号串，能够归约成文法开始符号，则匹配成功，否则都是匹配失败。

因此最需要解决的就是何时进行归约，其实很简单就是当前项目是不是归约项目(即 A -> α• ),如果是那么就可以进行归约啊。

当我们得到文法对应的所有项目集之后，移入-归约分析过程:

从左到右扫描输入符号串，得到当前输入符号 a，和文法开始项目集I0
项目集I0 遇到输入符号 a，得到后继项目集，我们假设是 I1 ；扫描下一个输入符号 b。

因为文法开始项目集，一般不可能进行归约，大部分都是进行移入操作，得到后继项目集。
当项目集 I1 遇到输入符号 b，这个时候就需要判断了:
- 如果项目集 I1 中有归约项目(肯定就是 a•)，那么就要进行归约了，得到对应产生式左部，假设是非终结符 A；这个时候需要得到项目集 I1 针对非终结符 A的后继项目集，假设是 I2。
- 如果项目集I1 中没有归约项目，那么就得到项目集 I1 相对于输入符号 b 的后继项目集，假设是 I2。
重复上述操作，直到遍历完输入符号串的同时，能够归约到文法开始符号。

所以LR(0)分析表就是文法所有项目集对应所有符号(还包括一个特殊符号，文法结束符号$) 的动作:

移入操作, 针对的都是终结符，将输入符号放入栈中，并进入它的后继项目集。

即 A -> α•aβ ∈ Ii , 且 GOTO(Ii, a) = Ij，那么ACTION[i, a] = sj
GOTO 操作，针对的非终结符，输入符号是没有非终结符的，这个非终结符都是归约操作后得到的，然后将这个非终结符放入栈中，并进入它的后继项目集。

即 A -> α•Bβ ∈ Ii , 且 GOTO(Ii, B) = Ij，那么ACTION[i, B] = j
归约操作，当前项目集中有归约项目(例如 A -> α•)分为两种情况
- 如果归约项目对应的产生式左部是文法开始符号，那么就代表归约操作已经到顶了，即为 ACTION[i, $] = acc。
  
  这个时候如果输入符号串还没有遍历完成，那么就代表匹配失败。
- 如果不是文法开始符号，那么就遇到任何终结符和结束符号$，都进行归约操作。

LR(0)分析表.png

2.2.5 分析过程

得到LR(0)分析表之后，我们进行语法分析工作，这里我们要使用两个栈，一个是符号栈，一个是状态栈(状态就是项目集)

LR 分析器_1.png

LR 分析器_2.png

LR 分析器_3.png

2.2.6 增广文法

有的文法开始符号对应产生式可能有多个，那么这个不符合LR分析的，我们需要开始符号对应产生式只有一个，从而使分析器只有一个接受状态。
这个时候我们就需要用到增广文法了，它也很简单就是新开始符号S’ 和产生式S’ → S ，而产生的新文法。

2.2.7 LR(0)分析表的问题

仔细看LR(0)分析表的构建过程，你会发现有一个问题，一个项目集中是有多个项目，所以针对项目集来说:

项目集中有两个项目(A -> α•aβ 和 A -> α• ), 那么遇到输入符号 a 的时候，这个项目集是进行移入操作还是进行归约操作。

这个就是移入-归约冲突
项目集中有两个项目(A -> α• 和 B -> α•)，那么遇到任一输入符号进行归约的时候，是归约成非终结符A 还是非终结符B 呢。

这个就是归约-归约冲突

那么可能有人问了，有没有移入-移入冲突呢?

不会有这种冲突的，因为进行移入操作，是有一个特定的终结符的，这个是确定的。

没有上诉冲突的文法，我们成为LR(0)文法，但是大部分文法都不符合，我们就要通过 SLR 和 LR(1) 算法来解决上诉操作。

三. 代码实现

注意这里 Symbol, Production,Grammar 这些类就不重复介绍了。

3.1 Action 类

package xinhao.lr.lr0;

import xinhao.Production;

/**
 * @author by xinhao  2021/8/23
 * LR0 对应的动作
 */
public class Action {

    // 移入
    public static final String TYPE_S = "s";
    // 归约
    public static final String TYPE_R = "r";
    // 终结
    public static final String TYPE_ACC = "acc";

    private final String type;

    // 如果action是移入的时候，stateItemSet代表移入状态，通过stateItemSet的state表示
    private final ProductionItemSet stateItemSet;

    // 当action是归约的时候，production就是归约的产生式
    private final Production production;

    private Action(String type, ProductionItemSet stateItemSet, Production production) {
        this.type = type;
        this.stateItemSet = stateItemSet;
        this.production = production;
    }

    public static Action createAcc() {
        return new Action(TYPE_ACC, null, null);
    }

    public static Action createS(ProductionItemSet stateItemSet) {
        return new Action(TYPE_S, stateItemSet, null);
    }

    public static Action createR(Production production) {
        return new Action(TYPE_R, null, production);
    }

    public boolean isAcc() {
        return TYPE_ACC.equals(type);
    }

    public boolean isS() {
        return TYPE_S.equals(type);
    }

    public boolean isR() {
        return TYPE_R.equals(type);
    }

    public String getType() {
        return type;
    }

    public ProductionItemSet getStateItemSet() {
        return stateItemSet;
    }

    public Production getProduction() {
        return production;
    }

    @Override
    public String toString() {
        if (isAcc()) {
            return "acc";
        }
        if (isR()) {
            return "r->" + production;
        }
        if (isS()) {
            return "s"+stateItemSet.getState();
        }
        return "";
    }
}

对应LR(0)分析表中的 ACTION 操作，所以有三个类型:

移入操作，这个时候 stateItemSet 有值表示后继项目集，即下一个状态。
归约操作，这个时候 production 有值，表示归约用到的产生式。
终结操作，表示匹配到开始符号。

3.2 ProductionItem 类

package xinhao.lr.lr0;

import xinhao.Production;
import xinhao.Symbol;

import java.util.Objects;

/**
 * @author by xinhao  2021/8/19
 * 右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）
 * 例:产生式 S -> bBB
 * 对应的项目就是 •bBB b•BB bB•B bBB•
 * 其中 •bBB 叫做移进项目； b•BB bB•B 叫做待约项目；bBB• 叫做归约项目
 */
public class ProductionItem implements Comparable<ProductionItem> {
    public static final String ITEM_SYMBOL = "•";

    /**
     * 项目对应的产生式
     */
    private final Production production;

    /**
     * 表示当前项目对应的位置，即圆点的位置。
     */
    private final int pos;

    /**
     * 表示当前pos位置对应的字符。
     * 例:产生式 S -> bBB
     * 它有四个项目         •bBB b•BB  bB•B  bBB•
     * pos 位置分别是        0    1     2    3
     * 对应的posSymbol就是   b    B     B    Symbol.END
     */
    private final Symbol posSymbol;

    /**
     * 这个产生式项目的标签
     * 例如 •bBB b•BB bB•B bBB•
     * 也是这个产生式项目是否相等判断的依据
     */
    private final String label;

    private ProductionItem(Production production, int pos, Symbol posSymbol, String label) {
        this.production = production;
        this.pos = pos;
        this.posSymbol = posSymbol;
        this.label = label;
    }

    /**
     * 创建产生式对应的移进项目
     * @param production
     * @return
     */
    public static ProductionItem createProduction(Production production) {
        return create(production, 0);
    }

    /**
     * 创建当前项目 item 的后继项目
     * @param item
     * @return
     */
    public static ProductionItem nextByItem(ProductionItem item) {
        return create(item.production, item.pos + 1);
    }

    private static ProductionItem create(Production production, int pos) {
        StringBuilder sb = new StringBuilder();
        Symbol posSymbol = null;
        for (int index = 0; index < production.getRight().size(); index++) {
            Symbol symbol = production.getRight().get(index);
            if (index == pos) {
                posSymbol = symbol;
                sb.append(ITEM_SYMBOL);
            }
            sb.append(symbol.getLabel());
        }
        if (pos == production.getRight().size()) {
            posSymbol = Symbol.END;
            sb.append(ITEM_SYMBOL);
        }
        return new ProductionItem(production, pos, posSymbol, sb.toString());
    }

    public Production getProduction() {
        return production;
    }

    public int getPos() {
        return pos;
    }

    public Symbol getPosSymbol() {
        return posSymbol;
    }

    public String getLabel() {
        return label;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        ProductionItem that = (ProductionItem) o;
        return label.equals(that.label);
    }

    @Override
    public int hashCode() {
        return Objects.hash(label);
    }

    @Override
    public String toString() {
        return label;
    }

    @Override
    public int compareTo(ProductionItem o) {
        return label.compareTo(o.label);
    }
}

3.3 ProductionItemSet 类

package xinhao.lr.lr0;

import java.util.*;

/**
 * @author by xinhao  2021/8/19
 * 项目集( I )，称为项目集闭包(Closure of Item Sets)，每个项目集闭包对应着自动机的一个状态。
 */
public class ProductionItemSet {
    /**
     * 记录所有创建过的项目集
     */
    public static final Map<String, ProductionItemSet> allItemSetMap = new HashMap<>();

    private static int stateGenerate = 0;

    /**
     * 当前项目集对应的状态
     */
    private final int state;

    /**
     * 项目的集合
     */
    private final Set<ProductionItem> itemSet;

    /**
     * 项目集的label，用来它来判断两个项目集是否相等
     */
    private final String label;

    private ProductionItemSet(int state, Set<ProductionItem> itemSet, String label) {
        this.state = state;
        this.itemSet = itemSet;
        this.label = label;
    }

    public static ProductionItemSet create(Set<ProductionItem> items) {
        StringBuilder sb = new StringBuilder();
        // 这里必须进行排序，才能比较两个
        items.stream().sorted().forEach(item -> sb.append(item.getLabel()).append(","));
        if (sb.length() != 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
        String label = sb.toString();
        /**
         * 如果 label 相同，说明是同一个项目集，那么返回之前创建的；
         * 保证相同 items 的是返回的是同一个 ProductionItemSet
         */
        ProductionItemSet itemSet = allItemSetMap.get(label);
        if (itemSet == null) {
            itemSet = new ProductionItemSet(stateGenerate++, items, sb.toString());
            allItemSetMap.put(label, itemSet);
        }
        return itemSet;
    }

    public Set<ProductionItem> getItemSet() {
        return itemSet;
    }

    public String getLabel() {
        return label;
    }

    public int getState() {
        return state;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        ProductionItemSet that = (ProductionItemSet) o;
        return label.equals(that.label);
    }

    @Override
    public int hashCode() {
        return Objects.hash(label);
    }

    @Override
    public String toString() {
        return state+"=="+label;
    }
}

3.4 closure 方法

对应 CLOSURE() 函数:

    /**
     * 求解相同项目的集合
     * 对于任何 S -> a•Bb 的项目，因为圆点后面的是非终结符，
     * 那么这个非终结符 B 的产生式 B -> b B ->c
     * 对应的移入项目组  B -> •b B -> •c  都是相同项目，加入同一个项目集。
     * closure 方法就是计算项目集
     * @param items
     * @param grammar
     * @return
     */
    private static Set<ProductionItem> closure(Set<ProductionItem> items, Grammar grammar) {
        // 结果的项目集合
        Set<ProductionItem> resultItems = new HashSet<>(items);
        Stack<ProductionItem> stack = new Stack<>();
        // 先将传入的items添加到栈里面
        stack.addAll(items);
        // 栈不为空，说明还有项目没有遍历到
        while (!stack.isEmpty()) {
            ProductionItem item = stack.pop();
            /**
             * 当前项目圆点位置是非终结符，那么这个非终结符的产生式组对应的移进项目和当前项目属于一个闭包
             */
            if (!item.getPosSymbol().isTerminator()) {
                // 非终结符对应的产生式组
                List<Production> productionList = grammar.getProductionsMap()
                        .get(item.getPosSymbol());
                for (Production production : productionList) {
                    // 创建产生式对应的项目
                    ProductionItem newItem = ProductionItem.createProduction(production);
                    /**
                     * 如果这个项目在 resultItems 中不包含，那么就添加
                     */
                    if (!resultItems.contains(newItem)) {
                        resultItems.add(newItem);
                        // 添加到栈中，新项目需要查找它的相同项目
                        stack.push(newItem);
                    }
                }
            }
        }
        return resultItems;
    }

3.5 Goto 方法

对应 GOTO()函数:

    // 为 Goto 创建一个缓存 table，这样就只需要求解一次
    private static final Map<ProductionItemSet, Map<Symbol, ProductionItemSet>> GOTO_TABLE = new HashMap<>();
    static ProductionItemSet Goto(ProductionItemSet itemSet, Symbol symbol, Grammar grammar) {
        // 如果缓存里有，那么直接返回，不用在求解了
        if (GOTO_TABLE.containsKey(itemSet)) {
            Map<Symbol, ProductionItemSet> map = GOTO_TABLE.get(itemSet);
            if (map.containsKey(symbol)) {
                return map.get(symbol);
            }
        }
        // 当前项目集 itemSet 遇到符号 symbol 的后继项目集合
        Set<ProductionItem> nextItems = new HashSet<>();
        for (ProductionItem item : itemSet.getItemSet()) {
            /**
             * 项目pos点的符号与 symbol 是否相同
             * 即项目 a•Bb 匹配 符号B
             * 后继项目就是 aB•b
             */
            if (item.getPosSymbol().equals(symbol)) {
                // 将后继项目添加到nextItems
                nextItems.add(ProductionItem.nextByItem(item));
            }
        }
        // 如果nextItems为空，说明当前项目集没有 符号symbol的后继项目
        if (nextItems.isEmpty()) {
            return null;
        }
        // 创建后继项目集
        ProductionItemSet gotoItemSet = ProductionItemSet.create(closure(nextItems, grammar));
        // 存放到缓存中
        Utils.addToDoubleMap(GOTO_TABLE, itemSet, symbol, gotoItemSet);
        return gotoItemSet;
    }

3.6 getAllItemSet 方法

    /**
     * 得到当前文法所有的项目集
     * @param grammar
     * @return
     */
    private static List<ProductionItemSet> getAllItemSet(Grammar grammar) {
        // 文法中所有符号，包括终结符和非终结符，但是不包括结束符号 END
        Set<Symbol> allSymbol = grammar.getAllSet();
        Symbol start = grammar.getStart();
        // 开始符号只有一个产生式，这里用到增广文法
        Production startProduction = grammar.getProductionsMap().get(start).get(0);
        // 开始符号产生式对应的移进项目
        ProductionItem startItem = ProductionItem.createProduction(startProduction);
        // 开始符号对应的项目集，也是第一个项目集
        ProductionItemSet startItemSet = ProductionItemSet.create(closure(Utils.asSet(startItem), grammar));

        // 当前文法所有的项目集
        List<ProductionItemSet> allItemSetList = new ArrayList<>();
        allItemSetList.add(startItemSet);
        // 通过栈来遍历所有的项目集，得到项目集对所有符号产生的新的项目集
        Stack<ProductionItemSet> stack = new Stack<>();
        stack.push(startItemSet);
        while (!stack.isEmpty()) {
            ProductionItemSet itemSet = stack.pop();
            // 遍历所有符号
            for (Symbol eachSymbol : allSymbol) {
                // 当前项目集遇到字符eachSymbol得到后继项目集
                ProductionItemSet gotoItemSet = Goto(itemSet, eachSymbol, grammar);
                /**
                 * 如果得到的后继项目集gotoItemSet 在allItemSetList中没有，
                 * 那么代表它是全新的，那么添加进行。
                 */
                if (gotoItemSet != null && !allItemSetList.contains(gotoItemSet)) {
                    allItemSetList.add(gotoItemSet);
                    // 新的项目集要添加到栈中，进行遍历
                    stack.push(gotoItemSet);
                }
            }
        }
        return allItemSetList;
    }

3.7 createLR0Table 方法

  /**
     * 得到文法对应的 LR0 分析表 actionMap 和 gotoMap
     * @param grammar
     * @param allItemSetList
     * @param actionMap
     * @param gotoMap
     */
    private static void createLR0Table(Grammar grammar, List<ProductionItemSet> allItemSetList,
                                       Map<ProductionItemSet, Map<Symbol, Action>> actionMap,
                                       Map<ProductionItemSet, Map<Symbol, ProductionItemSet>> gotoMap) {
        // 开始符号
        Symbol start = grammar.getStart();
        // 所有的非终结符
        Set<Symbol> vtSymbols = grammar.getVtSet();
        // 将结束符号添加进去
        vtSymbols.add(Symbol.END);
        // 遍历文法所有的项目集
        for (ProductionItemSet itemSet : allItemSetList) {
            // 遍历项目集中的项目
            for (ProductionItem item : itemSet.getItemSet()) {
                // 得到当前项目 pos 位置的符号
                Symbol posSymbol = item.getPosSymbol();
                // 如果是非终结符，那么就要添加到 gotoMap 中
                if (!posSymbol.isTerminator()) {
                    Utils.addToDoubleMapPrintConflict(gotoMap, itemSet, posSymbol, LR0Utils.Goto(itemSet, posSymbol, grammar),
                            "gotoMap 有冲突: old: %s, new: %s");
                } else {
                    // 是终结符但不是结束符号 END
                    if (!Symbol.END.equals(posSymbol)) {
                        // 获取后继项目集
                        ProductionItemSet nextItemSet = LR0Utils.Goto(itemSet, posSymbol, grammar);
                        // 想 action 中添加移入操作action
                        Utils.addToDoubleMapPrintConflict(actionMap, itemSet, posSymbol, Action.createS(nextItemSet),
                                "actionMap 有冲突: old: %s,  new: %s");
                    } else {
                        // 当前项目是 aBb• 格式，说明需要归约，这个就是归约需要的产生式
                        Production production = item.getProduction();
                        // 如果产生式左部和开始符号相同，说明是总结了，添加 acc 的action
                        if (start.equals(production.getLeft())) {
                            Utils.addToDoubleMapPrintConflict(actionMap, itemSet, posSymbol, Action.createAcc(),
                                    "actionMap 有冲突: old: %s,  new: %s");
                        } else {
                            /**
                             * 在LR0 算法中，对于  aBb• 这类项目，只要它对应的产生式不是开始符号的产生式
                             * 那么遇到任意终结符包括终止符号$ 都进行归约。
                             * 但是这种方式是会有冲突的，例如:
                             * 1. 对于同一个项目集 itemSet 中有两个项目 S-> a• 和 S-> a•b,
                             *    遇到终结符b，那么既可以归约，又可以移入，这就是移入-归约冲突
                             * 2. 对于同一个项目集 itemSet 中有两个项目 S-> a• 和 A-> b•
                             *    两个项目都可以归约，但是归约的产生式不同，这个时候就是归约-归约冲突
                             */
                            for (Symbol symbol : vtSymbols) {
                                Utils.addToDoubleMapPrintConflict(actionMap, itemSet, symbol, Action.createR(production),
                                        "actionMap 有冲突: old: %s,  new: %s");
                            }
                        }
                    }
                }
            }
        }
    }

3.8 match 方法

  /**
     * 判断文法能否匹配这个输入符号串inputSymbols
     * @param inputSymbols
     * @param startState
     * @param actionMap
     * @param gotoMap
     * @return
     */
    private static boolean match(List<Symbol> inputSymbols, ProductionItemSet startState,
                              Map<ProductionItemSet, Map<Symbol, Action>> actionMap,
                              Map<ProductionItemSet, Map<Symbol, ProductionItemSet>> gotoMap) {
        // 匹配的产生式列表
        List<Production> matchProductions = new ArrayList<>();
        // 状态栈
        Stack<ProductionItemSet> stateStack = new Stack<>();
        // 放入开始状态，即开始项目集
        stateStack.push(startState);
        // 符号栈
        Stack<Symbol> symbolStack = new Stack<>();
        // 先放入结束符号$
        symbolStack.push(Symbol.END);

        // 表示读取输入符号的位置
        int inputPos = 0;
        while (true) {
            // 当前状态栈栈顶状态
            ProductionItemSet currentItemSet = stateStack.peek();
            // 当然输入字符
            Symbol inputSymbol = inputSymbols.get(inputPos);
            // 获取当前栈顶状态遇到输入符号得到的 action
            Action action = actionMap.get(currentItemSet).get(inputSymbol);
            // 如果是 acc
            if (action.isAcc()) {
                // 当输入字符是最后一个字符，表示匹配成功。否则输入字符还没有匹配完成，匹配失败
                if (inputPos == inputSymbols.size() -1) {
                    System.out.println("匹配成功");
                    System.out.println(matchProductions);
                    return true;
                }
                System.out.println("匹配失败");
                System.out.println(matchProductions);
                return false;
            } else if (action.isS()) {
                // 移入操作
                stateStack.push(action.getStateItemSet());
                symbolStack.push(inputSymbol);
                // 下一个输入字符
                inputPos ++;
            } else if (action.isR()){
                // 归约操作的产生式
                Production production = action.getProduction();
                int size = production.getRight().size();
                // 记录一下状态栈弹出的状态
                List<Integer> popStateList = new ArrayList<>();
                // 记录一下弹出的字符
                List<Symbol> popSymbol = new ArrayList<>();
                // 根据产生式右部的字符数量，从状态栈和字符栈中弹出对应数量的元素
                for (int index = 0; index < size; index++) {
                    popStateList.add(stateStack.pop().getState());
                    popSymbol.add(symbolStack.pop());
                }
                System.out.println("popStateList: " + popStateList + "  popSymbol:"+popSymbol+"  production:"+production);
                // 添加归约的产生式
                matchProductions.add(production);

                // 将产生式左部添加到字符栈
                symbolStack.push(production.getLeft());
                // 获取这个字符在 gotoMap 中对应的状态，添加到状态栈
                ProductionItemSet itemSet = gotoMap.get(stateStack.peek()).get(production.getLeft());
                stateStack.push(itemSet);
            } else {
                throw new RuntimeException("匹配错误");
            }
        }
    }

3.9 实例

    public static void main(String[] agrs) {
        Symbol start = Alphabet.addSymbol("S'");
        Grammar grammar = Grammar.create(start,
                Production.create(start, "S"),
                Production.create(Alphabet.getSymbol("S"), "BB"),
                Production.create(Alphabet.getSymbol("B"), "aB"),
                Production.create(Alphabet.getSymbol("B"), "b")
                );

        List<ProductionItemSet> allItemSetList = getAllItemSet(grammar);
        System.out.println(allItemSetList);

        Map<ProductionItemSet, Map<Symbol, Action>> actionMap = new HashMap<>();
        Map<ProductionItemSet, Map<Symbol, ProductionItemSet>> gotoMap = new HashMap<>();
        createLR0Table(grammar, allItemSetList, actionMap, gotoMap);

        List<Symbol> inputSymbols = Utils.createSymbolsByString("bab");
        inputSymbols.add(Symbol.END);
        match(inputSymbols, allItemSetList.get(0), actionMap, gotoMap);
    }

输出结果:

[0==•BB,•S,•aB,•b, 1==a•B,•aB,•b, 2==B•B,•aB,•b, 3==b•, 4==S•, 5==BB•, 6==aB•]
popStateList: [3]  popSymbol:[b]  production:B->b
popStateList: [3]  popSymbol:[b]  production:B->b
popStateList: [6, 1]  popSymbol:[B, a]  production:B->aB
popStateList: [5, 2]  popSymbol:[B, B]  production:S->BB
匹配成功
[B->b, B->b, B->aB, S->BB]

文章中大部分图来自 https://piperliu.blog.csdn.net/article/details/107575430