資訊專欄INFORMATION COLUMN
摘要：基于這個結論，對某個非終結符展開形式的判定就變得明了起來。但嚴格的要求一個非終結符最多只能有一個產生式可以導出。這意味著我們必須明確知道每一個非終結符能不能導出。如果集包含這個終結符，則表明該非終結符需要導出。
tao 語言的 Parser 的語法分析是不帶回溯的，自頂向下的。文法選用 LL(1)，這種文法雖然略顯薄弱，但還尚可用。
回顧上一章提到的 LL(1) 的定義，可以得出如下結論。
在不考慮 ε 時，對于一個非終結符，它的每一個產生式都有一個FIRST 集與之對應。而這些 FIRST 集彼此不相交。
這個特征很有用，因為這個特征很容易得出以下結論。
對于某個非終結符的所有產生式而言，任取一個終結符，該終結符……
要么不屬于任何一個 FIRST 集；
要么僅屬于某一個FIRST集，從而找到唯一的一個產生式與之對應。
基于這個結論，Parser 對某個非終結符展開形式的判定就變得明了起來。將從 Tokenizer 處讀取到的 Token（即非終結符）遞歸的與非終結符產生式的 FIRST集做比較，一旦找到一個 FIRST 包含該 Token，即挑選該 FIRST 集對應的產生式。
整個過程可一氣呵成，不需要進行任何回溯。
但這么做之前，我們必須知道每一個非終結符的所有產生式的 FIRST 集。嗯，這是必要的，趕緊記在小本子上吧，在將來的章節中我們必須要寫求 FIRST 集的程序。
好，假設我們已經求出所有非終結符產生式的 FIRST 集了，是不是就可以開始寫 Parser 了呢？非也，之前的結論是建立在“不考慮 ε”的前提下。
所以，讓我們來討論允許 ε 的情況。
如果產生式中可能出現 ε，那么每一個產生式中的非終結符都有可能導出 ε 的嫌疑。但 LL(1) 嚴格的要求一個非終結符最多只能有一個產生式可以導出 ε。這意味著我們必須明確知道每一個非終結符能不能導出 ε。好在這并非難事，讓我們觀察，對于。
A → α | β | ε
而言，不用說 A 肯定能導出 ε，我都抓到現行了你還說沒有？！不解釋，它就可以導出 ε。
對于，
B → abide
可以肯定，不能導出 ε，因為產生式右邊全是終結符，終結符是不可能再展開的，因此我眼睛沒看到 ε，它就導不出 ε。
但是，這種情況就比較曖昧了，
C → αβγ
因為 α、β、γ 三個是式子，能不能導出 ε 真說不準。不過可以肯定的是，只要有一個式子不能導出 ε，那么 C 一定無法導出 ε。因為那個導不出 ε 的式子永遠不會“消失掉”，它霸占的位置最終會變成一組終結符串，故 C 絕不可能為空。反過來，只有當所有的式子都能導出 ε 的時候，C 才能導出 ε。
于是，判斷式子是否可以導出 ε 的條件呼之欲出。
終結符一定不能導出 ε。
如果存在產生式 A → ε，則非終結符 A 能導出 ε。
如果 A 的一個產生式 A → αβγ... 右側所有符號都可以導出 ε，則 A 可以導出 ε。
當某個非終結符可以導出 ε 時，Parser 在發現一個終結符的時候，在與其所有產生式的 FIRST 集比較過一次無果后，還可以與 FOLLOW 集比較。如果FOLLOW 集包含這個終結符，則表明該非終結符需要導出 ε。
至此，看來我們不但要事先求出每個非終結符的所有產生式的 FIRST 集，還要判斷每一個非終結符是否能導出 ε。這樣，我又要在筆記本上多記一條了。
嗯，到這里我已經連續講了3章理論了，雖然我原本打算盡量少講理論的，但是現在發現這些東西似乎避免不了。因為之后我要寫的東西全部來自這里頭。不過，下一章我還會繼續講理論，然后開始寫 Parser。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65505.html
摘要：一個非終結符可以被展開稱為一個串，如上定義便是將這個非終結符展開稱為一個又終結符和非終結符混合而成的串。特別注意我定義的方法僅僅用于修飾非終結符，而非展開式，雖然這個例子中我的方法更靠近方法，但并意味著用于修飾展開式。 各位久等了，本系列在新一年的連載中，形式會加入少許變化。首先，我會將 tao 語言編譯器（以及運行環境）的全部內容貼在 GitHub 上，在閱讀本系列的時候，需要對照 ...
摘要：對于而言，終結符與的是對應的。這些內容，我將其稱之為終結符的值。對于一個非終結符的產生式對于非終結符，其對象的字段則會表現成如下形式。對于里面的數組，其元素可能為終結符對象非終結符對象或表達式枚舉對象。 首先是 TerminalSymbol.java 即終結符。 package com.taozeyu.taolan.analysis; import java.util.HashSet...
摘要：希臘字母表示空，這個產生式表明非終結符可以產生一個空。此外，對于一個文法之中的非終結符，還有集集的概念。對于一個非終結符而言，它的集指可能展開的各種形式中，位于第一的所有終結符所組成的集合。 上一章中，我說 Parser 的工作就是依據文法定義，找到一個與源代碼匹配的展開方案就可以了。聽起來我們只要先給出一個 tao 語言的文法定義，然后寫一個找匹配方案的的程序就可以了。 然而事情情況...
摘要：考慮一個非終結符，如果對于另一個符號，存在如下產生式。則對于而言，它可以表示非終結符重復多次的各種形式。以上三個式子展現了將任意非終結符關于重復次數的多種形式。 式子中的符號，我還允許使用數量詞來修飾。考慮一個非終結符 A，如果對于另一個符號 α，存在如下產生式。 α → αA | ε 則對于 α 而言，它可以表示非終結符 A 重復 0 、1、多次的各種形式。 現在稍稍改變這個式子，使...
摘要：而，稱之為非終結符。而這個展開方案中對各個非終結符產生式的選擇過程，即是對源代碼中每一個部分的定性過程。這個過程讓能夠理解源代碼各個部分表示的含義，并以此生成對應的語法樹。 我需要定義出 tao 語言的細節，在此，需要引出文法這一概念。所謂文法，即是用于描述語言的一種工具。 例如，一個賦值語句可能寫成如下形式： variable = 1 + 3 如何充分定義這個賦值語句的形...
閱讀 3335·2021-11-22 12:04
閱讀 2719·2019-08-29 13:49
閱讀 492·2019-08-26 13:45
閱讀 2252·2019-08-26 11:56
閱讀 1011·2019-08-26 11:43
閱讀 604·2019-08-26 10:45
閱讀 1277·2019-08-23 16:48
閱讀 2166·2019-08-23 16:07
