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
于是就增加两个新的转换,如下图:
具体的转换步骤如下:
|
|