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

Tony 發(fā)布于2019-08-14 12:03 / 638人閱讀

摘要：希臘字母表示空，這個產(chǎn)生式表明非終結(jié)符可以產(chǎn)生一個空。此外，對于一個文法之中的非終結(jié)符，還有集集的概念。對于一個非終結(jié)符而言，它的集指可能展開的各種形式中，位于第一的所有終結(jié)符所組成的集合。

上一章中，我說 Parser 的工作就是依據(jù)文法定義，找到一個與源代碼匹配的展開方案就可以了。聽起來我們只要先給出一個 tao 語言的文法定義，然后寫一個找匹配方案的的程序就可以了。
然而事情情況并非如此簡單。因?yàn)榧偃缥覀儾粚ξ姆ǘx的形式加諸任何限制的話，讓 Parser 找到匹配方案并非很輕易的事情。

因此，我規(guī)定，tao 語言的將用 LL(1) 文法來定義。

在簡單介紹 LL(1) 文法之前，我還要說明一種比較特別的產(chǎn)生式。

A → ε

希臘字母 ε 表示“空”，這個產(chǎn)生式表明非終結(jié)符 A 可以產(chǎn)生一個空。具體來說，如果有如下文法。

S → αAβ

A → ε

那么：

S → αβ

非終結(jié)符可以產(chǎn)生空這一特性，令文法的形式更加復(fù)雜，但是卻是必不可少的。少了這一特征，就很難描述 tao 語言的語法細(xì)節(jié)了。

此外，對于一個文法之中的非終結(jié)符，還有 FIRST 集、FOLLOW 集的概念。

對于一個非終結(jié)符 A 而言，它的 FIRST 集指 A 可能展開的各種形式中，位于第一的所有終結(jié)符所組成的集合。記為 FIRST(A)。

而 FOLLOW 集，指在整個文法中，非終結(jié)符 A 后面可能接的所有終結(jié)符組成的集合。記為 FOLLOW(A)。

這么描述可能有點(diǎn)繞，細(xì)節(jié)先不管，但有一點(diǎn)很重要，即無論是 FIRST 集還是 FOLLOW 集，它們都只能包含終結(jié)符。

那么，LL(1) 又是怎樣一種文法呢？

對于一個文法而言，如果它的每一個非終結(jié)符的產(chǎn)生式

  A → α | β | γ ……

都滿足如下三個條件，則將這個文法稱之為 LL(1) 文法。

對于所有不能導(dǎo)出 ε 的表達(dá)式 α、β、γ……，都有，F(xiàn)IRST(α)、FIRST(β)、FIRST(γ)……兩兩互不相交。

最多只有一個表達(dá)式可以導(dǎo)出 ε。

如果有一個表達(dá)式可以導(dǎo)出 ε，那么對于其他不可以導(dǎo)出 ε 的表達(dá)式 ξ，有，F(xiàn)IRST(ξ) ∩ FOLLOW(A) = Φ。

最后一條有加粗，當(dāng)然并非因?yàn)樗鼘?LL(1) 本身很重要，而是因?yàn)槲以趯?shí)現(xiàn) Parser 的時候并沒有完全遵守這一條。某種意義上說，tao 語言的 Parser 并非嚴(yán)格遵守 LL(1) 文法，因此在此加粗這條，以便與后面的章節(jié)呼應(yīng)。