1樓:慕容淵
挖乙個。。。
這個問題要明白為什麼需要定義 FOLLOW 集。
考慮如下文法 G[S].
如下文法中,大寫字母代表非終結符,小寫代表終結符,"#" 代表 epsilon(現在不好打那個字元)。
S -> aA
S -> d
A -> bAS
A -> #
首先求 FIRST 集,如下
FIRST(S) =
FIRST(A) =
輸入串 abd,我們有如下推導過程。
S => aA => abAS => abS => abd問題在於 abAS => abS 那一步,此時我們面臨的輸入是符號d,但是FIRST(A)裡面沒有d只有epsilon,我們選擇A的epsilon產生式,那麼此時就要求輸入d與FOLLOW(A)匹配。那麼自然,FOLLOW(A)必須不能與FIRST(A)相交。
2樓:楊健
抽象的表述 @mumu 已經說明白了。
非LL(1)意味著:1. 無法只用乙個向前看token來選擇產生式。2. 在乙個向前看中越陷越深最後爆棧(左遞迴文法)。
對於第1點,對應第一張截圖中的兩個條件,第乙個條件說的就是common prefixes.
第二個條件,舉個具體栗子,就是「dangling else」。給定以下文法:
stmt >ifcondition
then_clause
else_clause | other_stmt
then_clause -> thenstmt
else_clause -> elsestmt | ε
如果要parse下面的statement:
ifC1thenifC2thenS1elseS2
會有兩種parsing tree
ifC1then[ifC2thenS1elseS2] 或者ifC1then[ifC2thenS1]elseS2
簡單的說,就是最後那個else和該和哪個then配對?
當解析程式看到棧頂是else_clause時,有兩個產生式供選擇
else_clause -> elsestmt 和else_clause -> ε
選哪乙個,需要先求else_clause的 FIRST 集和 FOLLOW 集.
FIRST(else_clause) =
FOLLOW(else_clause) =
如果向前看token是else, 可以按else_clause -> elsestmt 解析,對應
ifC1then[ifC2thenS1elseS2] 這顆解析樹
不過,FIRST集中包含了ε,而FOLLOW集中也含有else,說明else_clause -> ε也行的通,對應
ifC1then[ifC2thenS1]elseS2 這顆解析樹
3樓:42nd Mu00
證明二義性很簡單,假設存在以下正規化:
A -> BC
B -> ε | b
C -> b
First(B) =
Follow(B) =
選擇A生成式的時候,顯然B的生成式無法確定。
4樓:
沒人回答,先自答一下,不知道對不對。。
規則二如果不成立,有交集a,那麼生成a有兩種方式。1是用first集合,直接生成a。2是用,生成空集的方式,生成a。這樣導致A的,不唯一性。。。
如何判斷乙個文法能否寫成ll 1 文法?
Joan Tsao 根據LL 1 文法的定義來判斷,分三步走 1 文法不含左遞迴 2 對文法中的任乙個非終結符A的各個產生式的侯選首終結符集兩兩不相交,即 若 A 1 2 n,則 First i First j i j 3 對文法中的每個非終結符A,若它的某個首終結符集含有 則 First A Fo...
為什麼2型文法比1型文法限制少了,但是卻是1型文法的子集?
一型文法形如 A 二型文法形如 A 二型文法可以看做特殊的一型文法 或一型文法的子集 形如 A X型文法,是文法的集合族,它的每個元素是乙個文法。對於某個集合全集的集合族,它可以做的描述越精細,它的元素就更多。對於2型文法是1型文法的子集,我想可以這樣理解 2型文法不是 去掉了 上下文有關 這一限制...
為什麼要定義C1 C2函式?
格式化 說愁客 這就是對函式光滑性的一種描述,題目裡給出這些條件條件有的時候是為了提示你要使用這個函式的導數來解題,有的時候是告訴你這個題目中不允許使用比他給你的更高階的導數了。 資冶通籤 C1 C2函式有什麼優良的性質,翻一翻數學分析的教材就知道了。函式單調性 凹凸性 極點等等與一階導數 二階導數...