国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

Tony / 634人閱讀

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

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

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

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

  
A → ε

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

  
S → αAβ

  
  
A → ε

那么：

  
S → αβ

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

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

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

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

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

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

對于一個文法而言，如果它的每一個非終結符的產生式

  
A → α | β | γ ……

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

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

最多只有一個表達式可以導出 ε。

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

最后一條有加粗，當然并非因為它對 LL(1) 本身很重要，而是因為我在實現(xiàn) Parser 的時候并沒有完全遵守這一條。某種意義上說，tao 語言的 Parser 并非嚴格遵守 LL(1) 文法，因此在此加粗這條，以便與后面的章節(jié)呼應。

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64261.html

相關文章

  • 從零開始寫個編譯器吧系列

    摘要：是的，這個系列將呈現(xiàn)一個完整的編譯器從無到有的過程。但在寫這個編譯器的過程中，我可不會偷工減料，該有的一定會寫上的。該語言的虛擬機將運行于之上，同時編譯器將使用實現(xiàn)。我早有寫編譯器的想法之前沒寫過，故希望一邊寫編譯器一邊完成這個系列。 是的，這個系列將呈現(xiàn)一個完整的編譯器從無到有的過程。當然，為了保證該系列內容的簡潔（也為了降低難度），僅僅保證編譯器的最低要求，即僅能用。但在寫這個編譯...

    genedna 評論0 收藏0

  • 從零開始寫個編譯器吧 - 分析非終結符

    摘要：基于這個結論，對某個非終結符展開形式的判定就變得明了起來。但嚴格的要求一個非終結符最多只能有一個產生式可以導出。這意味著我們必須明確知道每一個非終結符能不能導出。如果集包含這個終結符，則表明該非終結符需要導出。 tao 語言的 Parser 的語法分析是不帶回溯的，自頂向下的。文法選用 LL(1)，這種文法雖然略顯薄弱，但還尚可用。 回顧上一章提到的 LL(1) 的定義，可以得出如下結...

    snifes 評論0 收藏0

  • 從零開始寫個編譯器吧 - 開始寫詞法分析器（3）

    摘要：在之前的章節(jié)第章從零開始寫個編譯器吧開始寫詞法分析器中我有說，我將函數(shù)設計成主動調用的形式，而則是被動調用的形式。接下來本系列將進入編寫語法分析器的階段，不過在此之前，我將抽出一點時間介紹一下語言本身。 上周周末旅游去了，就沒更新了，雖然回到海拔0m的地區(qū)，不過目前似乎還在缺氧，所以本次就少更點吧。 這章將結束詞法分析的部分。 在之前的章節(jié)（第7章從零開始寫個編譯器吧 - 開始寫詞...

    Barrior 評論0 收藏0

  • 從零開始寫個編譯器吧系列——將在 GitBook 上以在線電子書的形式繼續(xù)連載

    摘要：各位抱歉了，這個系列在多個平臺的專欄上連載。所以，我把從零開始寫個編譯器吧弄到了上。以后更新也是先從上開始。從零開始寫歌編譯器吧更及時的信息可以從我的公眾號上獲得雖然不怎么寫公眾號，但是還是掛一下吧 各位抱歉了，這個系列在多個平臺的專欄上連載。每發(fā)一個新章節(jié)，都要同步到各個專欄上，于是可能漏掉 Segmentfault 的博客。汗，其實 Segmentfault 這邊已經落后很久了。 ...

    justCoding 評論0 收藏0

  • 從零開始寫個編譯器吧 - 編譯器的結構

    摘要：自然，我們還是先從語言的編譯器下手吧。在動手寫編譯器之前，得容我將編譯器的結構進行進一步的劃分。這些將被語法分析器接收并進行進一步處理。由于本系列將著重于寫出編譯器，必要的理論和概念還是會交代的。從零開始寫個編譯器吧編譯器的結構的博客 自然，我們還是先從 tao 語言的編譯器下手吧。在動手寫編譯器之前，得容我將編譯器的結構進行進一步的劃分。編譯器可視為一個黑盒，從其一端輸入源代碼，另一...

    wudengzan 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<