資訊專欄INFORMATION COLUMN
摘要：希臘字母表示空，這個(gè)產(chǎn)生式表明非終結(jié)符可以產(chǎn)生一個(gè)空。此外，對(duì)于一個(gè)文法之中的非終結(jié)符，還有集集的概念。對(duì)于一個(gè)非終結(jié)符而言，它的集指可能展開(kāi)的各種形式中，位于第一的所有終結(jié)符所組成的集合。
上一章中，我說(shuō) Parser 的工作就是依據(jù)文法定義，找到一個(gè)與源代碼匹配的展開(kāi)方案就可以了。聽(tīng)起來(lái)我們只要先給出一個(gè) tao 語(yǔ)言的文法定義，然后寫一個(gè)找匹配方案的的程序就可以了。
然而事情情況并非如此簡(jiǎn)單。因?yàn)榧偃缥覀儾粚?duì)文法定義的形式加諸任何限制的話，讓 Parser 找到匹配方案并非很輕易的事情。
因此，我規(guī)定，tao 語(yǔ)言的將用 LL(1) 文法來(lái)定義。
在簡(jiǎn)單介紹 LL(1) 文法之前，我還要說(shuō)明一種比較特別的產(chǎn)生式。
A → ε
希臘字母 ε 表示“空”，這個(gè)產(chǎn)生式表明非終結(jié)符 A 可以產(chǎn)生一個(gè)空。具體來(lái)說(shuō)，如果有如下文法。
S → αAβ
A → ε
那么：
S → αβ
非終結(jié)符可以產(chǎn)生空這一特性，令文法的形式更加復(fù)雜，但是卻是必不可少的。少了這一特征，就很難描述 tao 語(yǔ)言的語(yǔ)法細(xì)節(jié)了。
此外，對(duì)于一個(gè)文法之中的非終結(jié)符，還有 FIRST 集、FOLLOW 集的概念。
對(duì)于一個(gè)非終結(jié)符 A 而言，它的 FIRST 集指 A 可能展開(kāi)的各種形式中，位于第一的所有終結(jié)符所組成的集合。記為 FIRST(A)。
而 FOLLOW 集，指在整個(gè)文法中，非終結(jié)符 A 后面可能接的所有終結(jié)符組成的集合。記為 FOLLOW(A)。
這么描述可能有點(diǎn)繞，細(xì)節(jié)先不管，但有一點(diǎn)很重要，即無(wú)論是 FIRST 集還是 FOLLOW 集，它們都只能包含終結(jié)符。
那么，LL(1) 又是怎樣一種文法呢？
對(duì)于一個(gè)文法而言，如果它的每一個(gè)非終結(jié)符的產(chǎn)生式
A → α | β | γ ……
都滿足如下三個(gè)條件，則將這個(gè)文法稱之為 LL(1) 文法。
對(duì)于所有不能導(dǎo)出 ε 的表達(dá)式 α、β、γ……，都有，F(xiàn)IRST(α)、FIRST(β)、FIRST(γ)……兩兩互不相交。
最多只有一個(gè)表達(dá)式可以導(dǎo)出 ε。
如果有一個(gè)表達(dá)式可以導(dǎo)出 ε，那么對(duì)于其他不可以導(dǎo)出 ε 的表達(dá)式 ξ，有，F(xiàn)IRST(ξ) ∩ FOLLOW(A) = Φ。
最后一條有加粗，當(dāng)然并非因?yàn)樗鼘?duì) LL(1) 本身很重要，而是因?yàn)槲以趯?shí)現(xiàn) Parser 的時(shí)候并沒(méi)有完全遵守這一條。某種意義上說(shuō)，tao 語(yǔ)言的 Parser 并非嚴(yán)格遵守 LL(1) 文法，因此在此加粗這條，以便與后面的章節(jié)呼應(yīng)。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64261.html
摘要：是的，這個(gè)系列將呈現(xiàn)一個(gè)完整的編譯器從無(wú)到有的過(guò)程。但在寫這個(gè)編譯器的過(guò)程中，我可不會(huì)偷工減料，該有的一定會(huì)寫上的。該語(yǔ)言的虛擬機(jī)將運(yùn)行于之上，同時(shí)編譯器將使用實(shí)現(xiàn)。我早有寫編譯器的想法之前沒(méi)寫過(guò)，故希望一邊寫編譯器一邊完成這個(gè)系列。 是的，這個(gè)系列將呈現(xiàn)一個(gè)完整的編譯器從無(wú)到有的過(guò)程。當(dāng)然，為了保證該系列內(nèi)容的簡(jiǎn)潔（也為了降低難度），僅僅保證編譯器的最低要求，即僅能用。但在寫這個(gè)編譯...
摘要：基于這個(gè)結(jié)論，對(duì)某個(gè)非終結(jié)符展開(kāi)形式的判定就變得明了起來(lái)。但嚴(yán)格的要求一個(gè)非終結(jié)符最多只能有一個(gè)產(chǎn)生式可以導(dǎo)出。這意味著我們必須明確知道每一個(gè)非終結(jié)符能不能導(dǎo)出。如果集包含這個(gè)終結(jié)符，則表明該非終結(jié)符需要導(dǎo)出。 tao 語(yǔ)言的 Parser 的語(yǔ)法分析是不帶回溯的，自頂向下的。文法選用 LL(1)，這種文法雖然略顯薄弱，但還尚可用。 回顧上一章提到的 LL(1) 的定義，可以得出如下結(jié)...
摘要：在之前的章節(jié)第章從零開(kāi)始寫個(gè)編譯器吧開(kāi)始寫詞法分析器中我有說(shuō)，我將函數(shù)設(shè)計(jì)成主動(dòng)調(diào)用的形式，而則是被動(dòng)調(diào)用的形式。接下來(lái)本系列將進(jìn)入編寫語(yǔ)法分析器的階段，不過(guò)在此之前，我將抽出一點(diǎn)時(shí)間介紹一下語(yǔ)言本身。 上周周末旅游去了，就沒(méi)更新了，雖然回到海拔0m的地區(qū)，不過(guò)目前似乎還在缺氧，所以本次就少更點(diǎn)吧。 這章將結(jié)束詞法分析的部分。 在之前的章節(jié)（第7章從零開(kāi)始寫個(gè)編譯器吧 - 開(kāi)始寫詞...
摘要：各位抱歉了，這個(gè)系列在多個(gè)平臺(tái)的專欄上連載。所以，我把從零開(kāi)始寫個(gè)編譯器吧弄到了上。以后更新也是先從上開(kāi)始。從零開(kāi)始寫歌編譯器吧更及時(shí)的信息可以從我的公眾號(hào)上獲得雖然不怎么寫公眾號(hào)，但是還是掛一下吧 各位抱歉了，這個(gè)系列在多個(gè)平臺(tái)的專欄上連載。每發(fā)一個(gè)新章節(jié)，都要同步到各個(gè)專欄上，于是可能漏掉 Segmentfault 的博客。汗，其實(shí) Segmentfault 這邊已經(jīng)落后很久了。 ...
摘要：自然，我們還是先從語(yǔ)言的編譯器下手吧。在動(dòng)手寫編譯器之前，得容我將編譯器的結(jié)構(gòu)進(jìn)行進(jìn)一步的劃分。這些將被語(yǔ)法分析器接收并進(jìn)行進(jìn)一步處理。由于本系列將著重于寫出編譯器，必要的理論和概念還是會(huì)交代的。從零開(kāi)始寫個(gè)編譯器吧編譯器的結(jié)構(gòu)的博客 自然，我們還是先從 tao 語(yǔ)言的編譯器下手吧。在動(dòng)手寫編譯器之前，得容我將編譯器的結(jié)構(gòu)進(jìn)行進(jìn)一步的劃分。編譯器可視為一個(gè)黑盒，從其一端輸入源代碼，另一...
閱讀 3068·2021-11-18 10:02
閱讀 3339·2021-11-02 14:48
閱讀 3398·2019-08-30 13:52
閱讀 563·2019-08-29 17:10
閱讀 2089·2019-08-29 12:53
閱讀 1414·2019-08-29 12:53
閱讀 1035·2019-08-29 12:25
閱讀 2170·2019-08-29 12:17
