从零开始写个编译器吧 - LL

admin 5年前

原文  http://segmentfault.com/blog/moskize/1190000002561366


上一章中,我说 Parser 的工作就是依据文法定义,找到一个与源代码匹配的展开方案就可以了。听起来我们只要先给出一个 tao 语言的文法定义,然后写一个找匹配方案的的程序就可以了。然而事情情况并非如此简单。因为假如我们不对文法定义的形式加诸任何限制的话,让 Parser 找到匹配方案并非很轻易的事情。

因此,我规定, tao 语言的将用 LL(1) 文法来定义

在简单介绍 LL(1) 文法之前,我还要说明一种比较特别的产生式。


A → ε

希腊字母 ε 表示“空”,这个产生式表明非终结符 A 可以产生一个空。具体来说,如果有如下文法。


S → αAβ

A → ε

那么:


S → αβ

非终结符可以产生空这一特性,令文法的形式更加复杂,但是却是必不可少的。少了这一特征,就很难描述 tao 语言的语法细节了。

此外,对于一个文法之中的非终结符,还有 FIRST 集、FOLLOW 集的概念。

  • 对于一个非终结符 A 而言,它的 FIRST 集指 A 可能展开的各种形式中,位于第一的所有终结符所组成的集合。记为 FIRST(A)。

  • 而 FOLLOW 集,指在整个文法中,非终结符 A 后面可能接的所有终结符组成的集合。记为 FOLLOW(A)。

这么描述可能有点绕,细节先不管,但有一点很重要,即无论是 FIRST 集还是 FOLLOW 集, 它们都只能包含终结符

那么,LL(1) 又是怎样一种文法呢?

对于一个文法而言,如果它的每一个非终结符的产生式


A → α | β | γ ……

都满足如下三个条件,则将这个文法称之为 LL(1) 文法。

  1. 对于所有不能导出 ε 的表达式 α、β、γ……,都有,FIRST(α)、FIRST(β)、FIRST(γ)……两两互不相交。

  2. 最多只有一个表达式可以导出 ε。

  3. 如果有一个表达式可以导出 ε,那么对于其他不可以导出 ε 的表达式 ξ,有,FIRST(ξ) ∩ FOLLOW(A) = Φ。

最后一条有加粗,当然并非因为它对 LL(1) 本身很重要,而是因为我在实现 Parser 的时候并没有完全遵守这一条。某种意义上说,tao 语言的 Parser 并非严格遵守 LL(1) 文法,因此在此加粗这条,以便与后面的章节呼应。

</div>