LR算法

背景

构造自动机

语法描述如下：

add : mul | add '+' mul ;
mul : pri | mul '*' pri ;
pri : INT | '(' add ')' ;

首先把所有产生式右侧的or节点都展开，再增加一个开始节点，此时的所有产生式如下：

start : add
add   : mul
add   : add + mul
mul   : pri
mul   : mul * pri
pri   : INT
pri   : ( add )

对上述每个产生式增加item
比如 add : add + mul可以生成4个item：

add : .add + mul
add : add. + mul
add : add +. mul
add : add + mul.

.后面的就表示可以接受某个状态，比如：
add : add. + mul就表示接受到+后可以迁移到
add : add +. mul
有了这些item，就可以生成 NFA 了
首先建立子图的关系，一共是7个子图，20个状态节点

之后，将这些子图连起来
比如add->add+.mul，接受mul后可以转到add->add+mul.
也可以接受ε，转到mul->.mul*pri、mul->pri
于是就增加两个新的转换，如下图：

具体的转换步骤如下：

1
2
3
4
5
6

for 20个状态:
    for 7个子图:
        # add->add+.mul后面跟着mul状态，由ε可以转到
        # mul->.mul*pri、mul->.pri 三个状态
        if 当前状态(.后面跟着的状态)是否匹配某个子图:
            建立当前状态 -> 子图的ε转换

NFA的转换图如下：

LR执行过程