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