前端编译原理 移进规约自动机

前面了解了jison的使用,了解了jison生成的parser代码的结构,那么现在我们是不是应该开始了解parser generator的代码逻辑了呢?

抱着这样的心态,我发现我错了,这个代码的难度有点大,需要先了解编译原理的文法转换表才能知道是怎么生成的parser中的table

由于时间的原因,不大可能从头看编译原理了,搜了些博客看看移进规约自动机到底是怎样生成的,这篇比较详尽的,https://blog.csdn.net/qq_40147863/article/details/93253171,感觉也让我回想起了大学的时候的一点知识。也可以直接看上面的博客,忽略这篇。

     这边会以上次的例子,生成个简单的转换表。文法很简单再贴下

 

  1.文法的拓广并编号:

拓广就是只默认加入S' -> E的文法,以这个文法为基础文法进行推到

E:叫做非终结符号,它在文法的左边出现,还可以继续推导

NAT:叫做终结符,只在文法的右边出现,最终的标示

2.推导自动机

.标示当前输入的状态 , 标示向前搜索符

状态0,I0,

  以S' -> E开始,S' -> .E,$       当前输入.后面的E为非终结符,还可以进行公式2进行推导

                            E -> .NAT, $   当前输入.后面的NAT终结符, 向前搜索符根据S' -> .E,$的E后面的标识符,所以是$

                                                 即如果 S' -> .E+,$,则 E -> .NAT, +

根据I0的规则,当前输入,遇到符号的不同情况推导

状态1,I1,

  遇到符号E,S' -> E.,$

状态2,I2,

  遇到符号NAT,E -> NAT.,$

 3)分析表

action里面是终结符 + $end

goto里面是非终结符

状态0,遇到终结符NAT,S标示移进,遇到非终结符E,直接跳转状态1

如果一个状态里面,有文法当前输入.在最后一位,(忽略,向前推导的内容)

对于S' -> E,开始的规则则填入 acc

对于其他的规则,在向前搜索符对应的位置,根据相应的规则进行规约,rn, n填写文法的编号

状态 action goto
NAT $ E
I0 S2   1
I1   acc  
I2   r1  

可以和parser generator 生成的 table 对比下

至于jison库的文法生成代码就不去啃了,一时间也没那么多的精力,差不多上面的过程,当然还有些优化逻辑在里面。

原文地址:https://www.cnblogs.com/legu/p/11321062.html