1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// epsilon 不属于非终结符，也不属于终结符！！！
// 看起来要用好多次，就先定义好了
var epsilonSymbol = GrammarSymbol{
    Name: "epsilon",
    Type: Null,
}

var endSymbol = TerminalSymbol{
    GrammarSymbol: GrammarSymbol{
        Name: "#",
        Type: Terminal,
    },
}

1
2
3
4
5
6
7
8

type NonTerminalSymbol struct {
    GrammarSymbol
    ProductionTable      []*Production               // 非终结符的产生式表
    NumOfProduction      int                         // 产生式数量
    FirstSet             map[interface{}]bool        // 该非终结符的 First 函数值
    FollowSet            map[interface{}]bool        // 该非终结符的 Follow 函数值
    DependentSetInFollow map[*NonTerminalSymbol]bool // 该非终结符的 Follow 函数中依赖的非终结符
}

1
2
3
4

var LL1AnalysisTable = map[struct {
    *NonTerminalSymbol
    string
}]*Production{}

1
2
3
4
5
6

type ItemSet struct {
    // 状态序号
    ID int
    // LR(0) 项目表（其实是个集合）
    ItemTable map[LR0Item]struct{}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// LR Action 表
// 由状态 ID 和终结符名称，到动作类型和编号的映射
var ActionTable map[struct {
    // 当前栈顶状态序号
    StateID int
    // 待读入的终结符名称
    TerminalSymbolName string
}]struct {
    // 动作类型
    Type ActionCategory
    // 动作编号，如归约的产生式编号和移进的下个状态
    ActionID int
}

1
2
3
4
5
6
7
8

// LR(0) 自动机
var DFA struct {
    // 开始项集
    StartItemSet *ItemSet
    // map 优化的变迁边表
    // 通常查询更快，极端情况下也不会更慢
    EdgeSet map[TransitionKey]*ItemSet
}

1
2
3
4

    // 只有 epsilon，就直接返回
    if p.BodySize == 1 && cmp.Equal(p.BodySymbol[0], &epsilonSymbol) {
        return map[interface{}]bool{&epsilonSymbol: true}
    }

1
2
3
4
5
6
7
8

    // 初始化 FOLLOW 集合
    for _, A := range GrammarSymbolTable {
        // 如果不是非终结符，跳过
        if reflect.TypeOf(A) != reflect.TypeOf(RootSymbol) {
            continue
        }
        A.(*NonTerminalSymbol).FollowSet = make(map[interface{}]bool)
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

    // 寻找 epsilon 的产生式（仅含 epsilon）
    for _, p := range nt.ProductionTable {
        if p.BodySize == 1 {
            symbol, ok := p.BodySymbol[0].(*GrammarSymbol)
            if ok && symbol.Type == Null { // 为什么不能放到一个 if 里啊！！！
                // 如果存在将 epsilon 加入该非终结符的 First 函数值
                nt.FirstSet[&epsilonSymbol] = true
            }
        }
    }

1
2
3
4
5
6
7

                    // 先看成 A \Rightarrow \alpha B \beta，求 FIRST(\beta)
                    // 将 \beta 部分组合成一个产生式
                    tempProduction := Production{
                        BodySymbol: production.BodySymbol[index+1:],
                        BodySize:   len(production.BodySymbol[index+1:]),
                    }
                    betaFirst := tempProduction.First()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// 对所有非终结符检测左递归
func CheckLeftRecursion() (ret bool) {
    return checkLeftRecursion(make(map[string]bool), RootSymbol)
}

// 使用 DFS 检测左递归，rec 用于记录已经检测过的非终结符
func checkLeftRecursion(rec map[string]bool, curr *NonTerminalSymbol) bool {
    // 如果已经检测过，返回
    if rec[curr.Name] {
        return true
    }
    // 否则加入 map
    rec[curr.Name] = true

    for _, production := range curr.ProductionTable {
        // 长度为 0，返回
        if len(production.BodySymbol) == 0 {
            continue
        }
        // 是非终结符
        if symbol, ok := production.BodySymbol[0].(*NonTerminalSymbol); ok {
            if checkLeftRecursion(rec, symbol) {
                return true
            }
        }
    }
    return false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

    // 遍历项目集中的每个项目
    // 此处并不需要驱动符一层项目再一层，省点时间
    for item := range itemSet.ItemTable {
        // 如果已经是归约 / 接受项目（A \to \cdot \alpha），则不需要变迁
        if item.DotPosition == len(item.Production.BodySymbol) {
            continue
        }
        // 取出该驱动符对应的项目集
        itemSet := newItemSets[item.Production.BodySymbol[item.DotPosition]].ItemTable
        // 将项目 item 的点后移一位
        // 新的项目！
        item1 := LR0Item{
            NonTerminalSymbol: item.NonTerminalSymbol,
            Production:        item.Production,
            DotPosition:       item.DotPosition + 1,
            Type:              CoreItem, // 一定是核心项啦
        }
        // 将新项目加入项目集
        itemSet[item1] = struct{}{}
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

        for item := range itemSet.ItemTable {
            // 判断项目类型
            // 为什么不用一个 switch？因为特么的 go 不支持 switch 里做声明
            if item.NonTerminalSymbol == RootSymbol && item.DotPosition == len(item.Production.BodySymbol) {
                // 接受项目 S' \to S \cdot
                // ACTION[i,#] = accept
                // code...
            } else if item.DotPosition == len(item.Production.BodySymbol) {
                // 归约项目 A \to \alpha \cdot
                // 对所有非终结符 a 或 #，ACTION[i,a] = reduce j
                // code...
            } else if symbol, ok := item.Production.BodySymbol[item.DotPosition].(*TerminalSymbol); ok {
                // 移进项目 A \to \alpha \cdot a \beta
                // action[i,a] = shift j
                // code...
            } else if symbol, ok := item.Production.BodySymbol[item.DotPosition].(*NonTerminalSymbol); ok {
                // 待约项目 A \to \alpha \cdot B
                // goto[i,B] = j
                // code...
            }
        }