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