自底向上的语法分析，闭包、GOTO函数

自底向上的语法分析

一、一个串ω归约（reduction）为文法开始符号的过程

关键问题：

　　1.何时进行规约，2.用哪个产生式规约

句柄右边的串ω一定只包含终结符号。

如果文法是无二义性的，那么文法的每个右句型都有且只有一个句柄

二、LR(0) 自动机 Automaton

项

1.定义：产生式加上位于体中的点

2.项的分类

1）内核项：初始项S’ -> • S，点不在最左端的项

2）非内核项：除S’ -> • S之外的点在最左端的项

项集I的闭包

1）将I中各个项加入到CLOSURE(I)中

2）如果A ->α • Bβ在CLOSURE(I)中，B->γ 是一个产生式，并且B->• γ不在CLOSURE(I)中，就将这个项加入其中。

不断应用这个规则，直到没有新项加入。

GOTO函数

GOTO(I，X) 定义：I 中所有形如A ->α • Xβ的项所有对应的项A ->αX • β的集合的闭包

代码实现：

/**
     * P156 闭包
     * @param setOfItems
     * @return
     */
    public SetOfItems closure(SetOfItems setOfItems, Grammar grammar) {

        SetOfItems result = new SetOfItems();
        for (Item item : setOfItems.getItems()) {
            result.add(item);
        }

        boolean hasAdd;
        do {
            hasAdd = false;
            Set<Item> items = new HashSet<>(result.getItems());
            for (Item item : items) {

                Symbol symbolAfterDot = item.getSymbolAfterDot();
                if (symbolAfterDot == null) {
                    continue;
                }

                if (symbolAfterDot instanceof Nonterminal) {
                    List<Production> productionList = grammar.getProduction((Nonterminal) symbolAfterDot);
                    for (Production production : productionList) {
                        Item newItem = Item.of(production, 0);
                        if (result.contains(newItem)) {
                            continue;
                        }
                        result.add(newItem);
                        hasAdd = true;
                    }
                }
            }

        } while (hasAdd);

        return result;
    }

 GOTO函数

/**
     * P156 GOTO函数
     * @return
     */
    public SetOfItems gotoSet(Grammar grammar, SetOfItems setOfItems, Symbol symbol) {

        SetOfItems result = new SetOfItems();
        for (Item item : setOfItems.getItems()) {
            Symbol symbol1 = item.getSymbolAfterDot();
            if (symbol1 == null) {
                continue;
            }
            if (!symbol1.equals(symbol)) {
                continue;
            }
            result.add(Item.of(item, item.pos+1));
        }

        if (result.isEmpty()) {
            return null;
        }

        result = closure(result, grammar);

        return result;
    }