動機
上下文無關文法描述了字串可以如何構造,但分析器必須在讀入輸入的同時決定使用哪條產生式。預測分析器只借助一個前瞻符號作出這項選擇,既不先猜測、也不回退重來。核心困難來自空產生式:若某個非終結符可以消失,下一個輸入符號就可能來自它後面的內容,而不是來自該非終結符本身。
FIRST 集與 FOLLOW 集把這兩種前瞻來源區分開來。我們將構造 LL(1) 分析表,證明分析成功的確切含義,並說明為甚麼衝突只是針對某個具體文法的警告,而不是證明該語言不可能用其他方式分析。
定義
設 G = ( N , Σ , P , S ) G=(N,\Sigma,P,S) G = ( N , Σ , P , S ) 為有限上下文無關文法。假設 N N N 與 Σ \Sigma Σ 不相交,S ∈ N S\in N S ∈ N ,且 # \# # 是文法字母表以外的新結束標記。假設每個非終結符都從 S S S 可達,並且至少推導出一個終結符串;這項約化文法假設使下文的語義集合與標準的局部不動點規則一致。語言為空的文法不滿足該假設,因為其開始符號不是可產生的(productive);本章不對這種情況斷言不動點結論。當開始符號仍可產生時,一般的有用符號預處理可以刪去不可產生和不可達的符號,但我們明確以所得的假設為前提。
文法符號串 α ∈ ( N ∪ Σ ) ∗ \alpha\in(N\cup\Sigma)^* α ∈ ( N ∪ Σ ) ∗ 稱為可空的 (nullable),若 α ⇒ ∗ ε \alpha\Rightarrow^*\varepsilon α ⇒ ∗ ε 。定義 FIRST ( α ) \operatorname{FIRST}(\alpha) FIRST ( α ) 為:包含每個能作為 α \alpha α 所推導的終結符串之首的終結符,並且當 α \alpha α 可空時還包含 ε \varepsilon ε 。
對非終結符 A A A ,若對某些文法符號串 μ , ν \mu,\nu μ , ν 有 S ⇒ ∗ μ A a ν S\Rightarrow^*\mu A a\nu S ⇒ ∗ μ A a ν ,則終結符 a a a 屬於 FOLLOW ( A ) \operatorname{FOLLOW}(A) FOLLOW ( A ) 。若 S ⇒ ∗ μ A ν S\Rightarrow^*\mu A\nu S ⇒ ∗ μ A ν 且 ν \nu ν 可空,則 # \# # 屬於 FOLLOW ( A ) \operatorname{FOLLOW}(A) FOLLOW ( A ) 。等價地說,在某個句型中,若 A A A 的某次出現之後可以接以 a a a 開頭的終結符延續,則該 a a a 在 FOLLOW 中;結束標記則記錄了該次出現可能是輸入的最後來源。
分析表的每個非終結符對應一行,每個終結符及 # \# # 各對應一列。對每條產生式 A → α A\to\alpha A → α ,對每個終結符 a ∈ FIRST ( α ) a\in\operatorname{FIRST}(\alpha) a ∈ FIRST ( α ) ,把該產生式放入 M [ A , a ] M[A,a] M [ A , a ] 。若 ε ∈ FIRST ( α ) \varepsilon\in\operatorname{FIRST}(\alpha) ε ∈ FIRST ( α ) ,還要對每個 b ∈ FOLLOW ( A ) b\in\operatorname{FOLLOW}(A) b ∈ FOLLOW ( A ) ,把它放入 M [ A , b ] M[A,b] M [ A , b ] 。單元格可以留空。衝突是指某個單元格含有兩條不同的產生式;同一條產生式被放入兩次不構成衝突。
概念視角 結構
無衝突即兩項互斥檢驗 對化簡後的文法,分析表無衝突,當且僅當對每個有產生式 A → α 1 ∣ ⋯ ∣ α m A\to\alpha_1\mid\cdots\mid\alpha_m A → α 1 ∣ ⋯ ∣ α m 的 A A A ,下列兩個條件成立。第一,當 i ≠ j i\ne j i = j 時 FIRST ( α i ) ∩ FIRST ( α j ) = ∅ \operatorname{FIRST}(\alpha_i)\cap\operatorname{FIRST}(\alpha_j)=\varnothing FIRST ( α i ) ∩ FIRST ( α j ) = ∅ ,其中 ε \varepsilon ε 也算作成員。第二,若 α i \alpha_i α i 可空,則對每個 j ≠ i j\ne i j = i 都有 FIRST ( α j ) ∩ FOLLOW ( A ) = ∅ \operatorname{FIRST}(\alpha_j)\cap\operatorname{FOLLOW}(A)=\varnothing FIRST ( α j ) ∩ FOLLOW ( A ) = ∅ 。這分別是 FIRST/FIRST 與 FIRST/FOLLOW 檢驗,每次失敗都指出相互碰撞的那一對產生式。
定理
對每條產生式 A → α B β A\to\alpha B\beta A → α B β ,FIRST ( β ) \operatorname{FIRST}(\beta) FIRST ( β ) 中的每個終結符都屬於 FOLLOW ( B ) \operatorname{FOLLOW}(B) FOLLOW ( B ) 。若 β \beta β 可空,則 FOLLOW ( A ) \operatorname{FOLLOW}(A) FOLLOW ( A ) 的每個成員也屬於 FOLLOW ( B ) \operatorname{FOLLOW}(B) FOLLOW ( B ) 。結束標記屬於 FOLLOW ( S ) \operatorname{FOLLOW}(S) FOLLOW ( S ) 。
因為 A A A 可達,對某些符號串 μ , ν \mu,\nu μ , ν 有 S ⇒ ∗ μ A ν S\Rightarrow^*\mu A\nu S ⇒ ∗ μ A ν ,再用產生式 A → α B β A\to\alpha B\beta A → α B β 得到 S ⇒ ∗ μ α B β ν S\Rightarrow^*\mu\alpha B\beta\nu S ⇒ ∗ μα B β ν 。若終結符 a ∈ FIRST ( β ) a\in\operatorname{FIRST}(\beta) a ∈ FIRST ( β ) ,則對某個符號串 γ \gamma γ 有 β ⇒ ∗ a γ \beta\Rightarrow^*a\gamma β ⇒ ∗ aγ ,所以 S ⇒ ∗ μ α B a γ ν S\Rightarrow^*\mu\alpha B a\gamma\nu S ⇒ ∗ μα B aγ ν ,即 a ∈ FOLLOW ( B ) a\in\operatorname{FOLLOW}(B) a ∈ FOLLOW ( B ) 。
現設 β \beta β 可空。若 a ∈ FOLLOW ( A ) a\in\operatorname{FOLLOW}(A) a ∈ FOLLOW ( A ) ,例如 S ⇒ ∗ μ ′ A a ν ′ S\Rightarrow^*\mu' A a\nu' S ⇒ ∗ μ ′ A a ν ′ ,則 S ⇒ ∗ μ ′ α B β a ν ′ ⇒ ∗ μ ′ α B a ν ′ S\Rightarrow^*\mu'\alpha B\beta a\nu'\Rightarrow^*\mu'\alpha B a\nu' S ⇒ ∗ μ ′ α B β a ν ′ ⇒ ∗ μ ′ α B a ν ′ ,因為 β \beta β 消失;所以 a ∈ FOLLOW ( B ) a\in\operatorname{FOLLOW}(B) a ∈ FOLLOW ( B ) 。若 # ∈ FOLLOW ( A ) \#\in\operatorname{FOLLOW}(A) # ∈ FOLLOW ( A ) ,即 S ⇒ ∗ μ ′ A ν ′ S\Rightarrow^*\mu' A\nu' S ⇒ ∗ μ ′ A ν ′ 且 ν ′ \nu' ν ′ 可空,則 β ν ′ \beta\nu' β ν ′ 可空,並且 S ⇒ ∗ μ ′ α B β ν ′ S\Rightarrow^*\mu'\alpha B\beta\nu' S ⇒ ∗ μ ′ α B β ν ′ ,所以 # ∈ FOLLOW ( B ) \#\in\operatorname{FOLLOW}(B) # ∈ FOLLOW ( B ) 。最後,S ⇒ ∗ S S\Rightarrow^*S S ⇒ ∗ S (μ \mu μ 與 ν \nu ν 皆為空),這使 # \# # 屬於 FOLLOW ( S ) \operatorname{FOLLOW}(S) FOLLOW ( S ) 。
該規則對各次出現分別處理:一個非終結符可以有多種不同的上下文,其 FOLLOW 集是這些上下文所給集合的並集。
集合的計算
可空非終結符透過最小不動點獲得。起初沒有任何標記。反覆進行如下操作:若某條產生式 A → X 1 ⋯ X k A\to X_1\cdots X_k A → X 1 ⋯ X k 的每個 X i X_i X i 都已被標記為可空,則標記 A A A ;空的右部立即滿足條件。含有終結符的右部不可能是可空的。由於非終結符只有有限多個,這個過程必然停止。
計算 FIRST 時,若某終結符能作為 A A A 的某條產生式右部之首,就把它加入 FIRST ( A ) \operatorname{FIRST}(A) FIRST ( A ) 。由左至右掃描右部:加入每個符號 FIRST 中的非空終結符,僅當該符號可空時才繼續越過它。當右部每個符號都可空時,加入 ε \varepsilon ε 。重複直至沒有集合再增大,就得到最小不動點。對終結符 a a a ,FIRST ( a ) = { a } \operatorname{FIRST}(a)=\{a\} FIRST ( a ) = { a } ;空字串的 FIRST 集為 { ε } \{\varepsilon\} { ε } 。
計算 FOLLOW 時,從 # ∈ FOLLOW ( S ) \#\in\operatorname{FOLLOW}(S) # ∈ FOLLOW ( S ) 出發,對每個右部中每個非終結符的出現反覆應用傳播定理。永遠不要把 ε \varepsilon ε 放入 FOLLOW 集。每個集合都是有限集 Σ ∪ { # } \Sigma\cup\{\#\} Σ ∪ { # } 的子集,所以不動點計算會終止。最小不動點恰好包含由有限推導所證成的符號:每次插入都有推導見證,而對有限推導作歸納可知,每個應當出現的符號最終都會被插入。
解讀不動點計算
把各輪計算與最終結果區分開來會有幫助。考慮 A → B C A\to BC A → B C ,B → ε ∣ b B\to\varepsilon\mid b B → ε ∣ b ,C → ε ∣ c C\to\varepsilon\mid c C → ε ∣ c 。第一輪可空性計算因 B B B 、C C C 各有一條空產生式而標記二者;下一輪即可標記 A A A 。於是 A A A 的 FIRST 同時含有 b b b 與 c c c (因為 B B B 可以消失),並含有 ε \varepsilon ε (因為兩個組成部分都可以消失)。若 A A A 是開始符號,則其 FOLLOW 含有結束標記。對 B B B 的這次出現,規則把 c c c 與結束標記加入 FOLLOW ( B ) \operatorname{FOLLOW}(B) FOLLOW ( B ) ;而 C C C 得到結束標記。
應當持續計算直至不可能再有變化,而不是在固定遍數後停止。一條產生式鏈可能涉及許多非終結符,一端的資訊可能需要經過若干輪才能傳到另一端。終止性來自有限且只增不減的集合,而不是來自「兩遍」之類預先規定的數字。反過來,若僅因某終結符出現在產生式後面某處就把它加入 FIRST,則當前面的某個不可空符號將其擋住時,會高估 FIRST。傳播的方向以及對可空前綴的條件都很重要。
預測分析器
初始化堆疊:S S S 在 # \# # 之上;輸入為該符號串後接 # \# # 。反覆檢查堆疊頂部符號與當前輸入符號。若二者是相同的終結符,則同時移除並推進輸入。若堆疊頂部是非終結符 A A A ,則對當前輸入符號 a a a 查表 M [ A , a ] M[A,a] M [ A , a ] 。若其中有產生式 A → X 1 ⋯ X k A\to X_1\cdots X_k A → X 1 ⋯ X k ,就移除 A A A ,並把右部按逆序壓入堆疊,使 X 1 X_1 X 1 位於頂部;若右部為空,則不壓入任何符號。空單元格或終結符不匹配則報告失敗。當堆疊與輸入都只剩 # \# # 時接受。
在我們的追蹤記錄中,堆疊的書寫方式是頂部在左。例如,把頂部的 A A A 替換為 B C BC B C ,會使堆疊 A γ # A\gamma\# A γ # 變為 B C γ # BC\gamma\# B C γ # 。只有在前面所有終結符都已匹配之後,才展開最左的待處理非終結符。因此,分析器所作的產生式選擇描述的是一個最左推導。
證明
可靠性與完備性
若分析表沒有衝突,則上文所述的堆疊式分析器恰好接受 G G G 所生成的終結符串。對每個被生成的符號串,分析器在有限步內到達接受狀態。對於不在語言中的輸入,接受永不會發生;這裏並不斷言分析器對每個這樣的輸入都會終止。
關於可靠性,維持如下不變式:已消耗的輸入後接堆疊中的文法符號部分,是一個由 S S S 推導出的句型。產生式步驟對最左的待處理非終結符應用所指示的文法規則;匹配步驟把堆疊頂部的終結符轉移到已消耗的前綴中,而二者的連接結果不變。當兩個結束標記都到達時,堆疊中已沒有文法符號。因此已消耗的輸入是由 S S S 推導出的終結符串。
關於完備性,固定一個被生成的符號串及其一個有限的最左推導。假設分析器到目前為止一直沿著該推導進行。若堆疊頂部符號是終結符,則它等於下一個輸入終結符。若頂部是非終結符 A A A ,並且在所選推導中由 A → α A\to\alpha A → α 展開,則有兩種情況:要麼剩餘輸入以 α \alpha α 所生成的某個終結符開頭,要麼 α \alpha α 推導出 ε \varepsilon ε ,而前瞻符號來自 A A A 這次出現之後的延續部分(也可能是 # \# # )。在第一種情況中,該產生式是依據 FIRST 插入表中的;在第二種情況中,是依據 FOLLOW 插入的。分析表沒有衝突,所以分析器選中的正是這條產生式。沿著該有限推導作歸納,即可一直到達接受。
這個論證並不要求斷言任意表驅動計算在每個被拒絕的輸入上都會終止。它證明的是:每個成員都有一個有限的成功計算,並且由於分析表是確定性的,分析器恰好沿著它進行。因此在所述假設下,任何報告的失敗都是正確的拒絕。若要另外證明對所有非成員的最壞運行時間或終止保證,則需要對文法和實現作額外分析。
證明透視
前瞻符號從何而來? 完備性論證是對堆疊頂部符號的分情況討論。頂部是終結符時不需要查表:推導已決定了它,而輸入與之吻合。頂部是非終結符 A A A ,並由 A → α A\to\alpha A → α 展開時,再依當前前瞻符號 a a a 分情況。若 a a a 是 α \alpha α 所推導符號串之首,則 a ∈ FIRST ( α ) a\in\operatorname{FIRST}(\alpha) a ∈ FIRST ( α ) ,單元格 M [ A , a ] M[A,a] M [ A , a ] 由 FIRST 規則填入。若在所選推導中 α ⇒ ∗ ε \alpha\Rightarrow^*\varepsilon α ⇒ ∗ ε ,則 a a a 來自 A A A 這次出現之後的內容,所以 a ∈ FOLLOW ( A ) a\in\operatorname{FOLLOW}(A) a ∈ FOLLOW ( A ) ,單元格由 FOLLOW 規則填入;這時 a a a 也可以是 # \# # 。兩種情況涵蓋所有可能,這就是兩個集合都不可缺少的原因。
假設在三處被使用。約化文法假設使這裏用到的語義 FOLLOW 與不動點所算出的集合一致。無衝突這一假設只在最後使用一次:它把「正確的產生式在單元格內」變成「正確的產生式是單元格內唯一的一條」。沒有它,表中仍可含有每個正確的選擇,但分析器無從知道該選哪一個。對 S → A a S\to Aa S → A a 、A → a ∣ ε A\to a\mid\varepsilon A → a ∣ ε 與輸入 a a a ,單元格 M [ A , a ] M[A,a] M [ A , a ] 含有兩條產生式,若分析器選擇 A → a A\to a A → a ,便會在 # \# # 處失敗,儘管 a a a 是被生成的。最後,歸納沿著一條固定的有限推導進行,所以成功的運行自然是有限的。
例題詳解
設 S → A b S\to Ab S → A b 且 A → a ∣ ε A\to a\mid\varepsilon A → a ∣ ε 。則 A A A 可空,FIRST ( A ) = { a , ε } \operatorname{FIRST}(A)=\{a,\varepsilon\} FIRST ( A ) = { a , ε } ,FOLLOW ( A ) = { b } \operatorname{FOLLOW}(A)=\{b\} FOLLOW ( A ) = { b } 。分析表為 M [ S , a ] = M [ S , b ] = S → A b M[S,a]=M[S,b]=S\to Ab M [ S , a ] = M [ S , b ] = S → A b ,M [ A , a ] = A → a M[A,a]=A\to a M [ A , a ] = A → a ,M [ A , b ] = A → ε M[A,b]=A\to\varepsilon M [ A , b ] = A → ε 。沒有單元格衝突。該語言為 { b , a b } \{b,ab\} { b , ab } 。
對輸入 a b # ab\# ab # ,堆疊/輸入對依次開始於 S # / a b # S\#/ab\# S #/ ab # ,然後是 A b # / a b # Ab\#/ab\# A b #/ ab # ,再然後是 a b # / a b # ab\#/ab\# ab #/ ab # 。匹配 a a a 與 b b b 後到達 # / # \#/\# #/# 。對輸入 b # b\# b # ,表項 M [ A , b ] M[A,b] M [ A , b ] 選擇空產生式,並容許同樣的最終匹配。
對 S → a b ∣ a c S\to ab\mid ac S → ab ∣ a c ,兩個右部的 FIRST 集都是 { a } \{a\} { a } ,所以 M [ S , a ] M[S,a] M [ S , a ] 含有兩條產生式。僅憑當前前瞻符號,分析表無法在二者之間作出選擇。提取左公因子得到 S → a T S\to aT S → a T 與 T → b ∣ c T\to b\mid c T → b ∣ c ,就為同一語言給出了無衝突的分析表。可見原來的表衝突涉及的是所給的文法,而不是正則語言 { a b , a c } \{ab,ac\} { ab , a c } 本身。
例題 3.2.8
(FIRST/FOLLOW 衝突)
設 S → A a S\to Aa S → A a 且 A → a ∣ ε A\to a\mid\varepsilon A → a ∣ ε 。因為 a ∈ FOLLOW ( A ) a\in\operatorname{FOLLOW}(A) a ∈ FOLLOW ( A ) ,單元格 M [ A , a ] M[A,a] M [ A , a ] 既從 FIRST 得到 A → a A\to a A → a ,又從 FOLLOW 得到 A → ε A\to\varepsilon A → ε 。看到第一個 a a a 時,一個前瞻符號無法區分它屬於 A A A 還是屬於後面的終結符。該語言是 { a , a a } \{a,aa\} { a , aa } ,這再次說明文法衝突並不意味著語言本身難以分析。
對 S → A B C S\to ABC S → A B C ,A → a A\to a A → a ,B → b ∣ ε B\to b\mid\varepsilon B → b ∣ ε ,C → c ∣ ε C\to c\mid\varepsilon C → c ∣ ε ,B B B 與 C C C 都可空。因此 B C BC B C 的 FIRST 含有 b , c , ε b,c,\varepsilon b , c , ε 。FOLLOW 規則把 b b b 與 c c c 放入 FOLLOW ( A ) \operatorname{FOLLOW}(A) FOLLOW ( A ) ;因為整個後綴 B C BC B C 可空,它還把 # \# # 放入其中。若只看緊鄰的非終結符 B B B ,就會漏掉終結符 c c c 和結束標記。
反例模式
分析表衝突並不證明語言不可能被分析 斷言:若某文法的分析表有衝突,則該語言不可能用一個前瞻符號作確定性分析。對 S → a b ∣ a c S\to ab\mid ac S → ab ∣ a c ,單元格 M [ S , a ] M[S,a] M [ S , a ] 含有兩條產生式,所以分析表有衝突。然而語言 { a b , a c } \{ab,ac\} { ab , a c } 是有限的,而提取公因子後的文法 S → a T S\to aT S → a T 、T → b ∣ c T\to b\mid c T → b ∣ c 有 M [ S , a ] = S → a T M[S,a]=S\to aT M [ S , a ] = S → a T 、M [ T , b ] = T → b M[T,b]=T\to b M [ T , b ] = T → b 、M [ T , c ] = T → c M[T,c]=T\to c M [ T , c ] = T → c ,沒有任何單元格含有兩條產生式。衝突表明的是:這個文法以及這種單符號前瞻的表構造無法作出所需的確定性選擇;它並不表明該語言的每個文法都會衝突。
常見錯誤
一個符號串的 FIRST 並不簡單等於該串中各符號的 FIRST 集之並。只有當前面所有符號都消失時,後面的符號才可能成為所推導符號串之首。在 A b Ab A b 中,若 A A A 可空且 FIRST ( A ) = { a , ε } \operatorname{FIRST}(A)=\{a,\varepsilon\} FIRST ( A ) = { a , ε } ,則 FIRST ( A b ) = { a , b } \operatorname{FIRST}(Ab)=\{a,b\} FIRST ( A b ) = { a , b } ;空字串不在該集合中,因為終結符 b b b 仍然保留。
常見錯誤
(FOLLOW 不是 FIRST,# 也不是空字串)
FOLLOW 描述的是某次出現之後可能出現的符號,而不是該非終結符自身所生成的符號。應當把可空產生式放入 FOLLOW 對應的列,但不要把 ε \varepsilon ε 加為分析表的一列。結束標記與空字串不同:它是一個記帳用的符號,表示已無剩餘輸入。
無衝突的分析表可以含有空單元格。它們是有用的:若分析器到達空單元格,則依據正確性定理,該前瞻符號不可能開啟任何成功的延續。把任意規則填入空單元格,可能使分析器出錯。
總結
可空性資訊控制 FIRST 在右部中向後掃描的範圍。FOLLOW 則在可空展開之後提供前瞻符號。無衝突的分析表能確定性地選擇產生式;堆疊不變式證明可靠性,有限的最左推導則證明對每個成員的完備性。表衝突屬於所選的文法和前瞻構造,所以等價的文法變換可以消除某些衝突。
練習
快速檢查
(對 S → a S ∣ ε S\to aS\mid\varepsilon S → a S ∣ ε ,計算 FIRST ( S ) \operatorname{FIRST}(S) FIRST ( S ) 與 FOLLOW ( S ) \operatorname{FOLLOW}(S) FOLLOW ( S ) ,並給出兩個非空的表單元格。)
解答 · 答案 FIRST ( S ) = { a , ε } \operatorname{FIRST}(S)=\{a,\varepsilon\} FIRST ( S ) = { a , ε } ,FOLLOW ( S ) = { # } \operatorname{FOLLOW}(S)=\{\#\} FOLLOW ( S ) = { # } 。單元格 M [ S , a ] M[S,a] M [ S , a ] 含有 S → a S S\to aS S → a S ,M [ S , # ] M[S,\#] M [ S , # ] 含有 S → ε S\to\varepsilon S → ε 。
快速檢查
(對 S → A B S\to AB S → A B ,A → a ∣ ε A\to a\mid\varepsilon A → a ∣ ε ,B → b ∣ ε B\to b\mid\varepsilon B → b ∣ ε ,計算 FIRST ( S ) \operatorname{FIRST}(S) FIRST ( S ) 與 FOLLOW ( A ) \operatorname{FOLLOW}(A) FOLLOW ( A ) 。)
解答 · 答案 A A A 與 B B B 都可空,所以 FIRST ( S ) = { a , b , ε } \operatorname{FIRST}(S)=\{a,b,\varepsilon\} FIRST ( S ) = { a , b , ε } 。A A A 之後的後綴是 B B B ,其非空 FIRST 含有 b b b 且 B B B 可空;因此 FOLLOW ( A ) = { b , # } \operatorname{FOLLOW}(A)=\{b,\#\} FOLLOW ( A ) = { b , # } 。
快速檢查
(解釋 S → a ∣ a S S\to a\mid aS S → a ∣ a S 中的衝突,並給出一個等價的無衝突文法。)
解答 · 答案 兩個選擇都以 a a a 開頭,所以 M [ S , a ] M[S,a] M [ S , a ] 含有兩條產生式。文法 S → a T S\to aT S → a T ,T → a T ∣ ε T\to aT\mid\varepsilon T → a T ∣ ε 生成同一語言 a + a^+ a + ,並且表中的選擇互不相交:遇 a a a 用 T → a T T\to aT T → a T ,遇 # \# # 用 T → ε T\to\varepsilon T → ε 。
快速檢查
(對文法 S → a S ∣ ε S\to aS\mid\varepsilon S → a S ∣ ε ,在輸入 a a aa aa 上追蹤分析器,列出各次產生式選擇以及最終的標記條件。)
解答 · 答案 對第一個和第二個 a a a ,分析器都選擇 S → a S S\to aS S → a S 並匹配該終結符。到達輸入末端時選擇 S → ε S\to\varepsilon S → ε ,堆疊與輸入中都只剩 # \# # 。於是接受。推導為 S ⇒ a S ⇒ a a S ⇒ a a S\Rightarrow aS\Rightarrow aaS\Rightarrow aa S ⇒ a S ⇒ aa S ⇒ aa 。