Posts Tagged ‘LALR’

简明Lemon核心代码分析二–向前看符号集的生成

所谓的向前看符号,就是当某一个项目的点号已经在最右边时,当下一个符号是什么符号时,可以使用该产生式进行归约操作。

比如,有一个项目是T→T*F·,它的向前看符号为=号,那么就意味着,如果当前栈的栈顶的符号为T*F,而下一个输入符号为=号时,可以使用产生式T→T*F进行归约操作,也就是将栈顶的T*F符号弹出,压入符号T=。

如果说,前面的buildshifts函数确定了不同的状态之间,经过哪些符号可以到达,那么向前看符号就决定了何时可以进行归约。要计算向前看符号,过程还是比较复杂,需要好几个辅助变量的计算。

首先要计算的是所有符号的first集合。它的算法,简单描述如下:

简明Lemon核心代码分析之一–LR(0)项目的生成

上一篇提到了Lemon这个项目,对于一个只有4000多行代码量的项目,用了一本400页的书来分析它的实现。我觉得应该把书读薄一点,所以我尝试着把这里我认为最核心的部分做一个我自己的诠释。

Lemon是一个LALR的语法分析器,有它自己自定义的语法规则,分析语法文件之后再根据模板文件输出C代码。这里涉及到几个步骤:词法分析,LALR语法分析,生成C代码文件。词法分析没有太多可说,就是根据语法规则定义状态机,提取词法的token,逐个进行分析。这个过程完毕之后,将产生相应的产生式,符号,产生式的左边符号,右边符号,开始符号等等这些都是在这一步完毕之后可以知道的。这一步不做太多的分析,因为相对而言还是比较简单的。而最后一步,也不做分析。重点在第二步,如何根据LALR算法得到动作表。

在我看来,核心包括两步:LR(0)项目的生成,以及每个LR(0)项目的向前看符号的计算。

首先看如何生成LR(0)项目。简单的说,是从开始符号出发,逐个遍历以它为产生式左边符号的产生式,逐个生成LR(0)项目。