從零開始寫個編譯器吧 - LL

上一章中，我說 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) 文法，因此在此加粗這條，以便與后面的章節呼應。