勵志

勵志人生知識庫

ll文法

LL(1)文法是一種上下文無關文法,它的特點包括:

從左到右掃描輸入符號串:第一個"L"代表從左向右掃描輸入符號串。

使用最左推導:第二個"L"代表在分析過程中,每一步推導都要向前查看一個輸入符號,即當前正在處理的輸入符號。

單符號預測:"1"代表在分析過程中,對每次直接推導只需向前看一個輸入符號。

LL(1)文法滿足以下判定條件:

無二義性:文法中每一個產生式的左部都是一個非終結符,且沒有多重定義的條目。

無左遞歸:文法中不存在左遞歸的產生式。

無左公因子:文法中不存在左公因子的產生式。

LL(1)文法可以進行確定的自頂向下語法分析,這意味著對於所有LL(1)文法的句子,都可以進行自頂向下的分析,而不會出現回溯現象。

為了判斷一個文法是否是LL(1)文法,需要按照以下步驟進行計算:

計算First集合:對於文法中的每個產生式,計算其左部的First集合,即所有可能的最左推導的輸入符號。

計算Follow集合:對於文法中的每個非終結符,計算其所有可能的最左推導的輸出符號的集合,即Follow集合。

計算SELECT集合:對於每個產生式,計算其SELECT集合,即所有可能的最左推導的輸出符號的集合。如果SELECT集合中的交集為空,則該文法是LL(1)文法。

需要注意的是,並不是所有的語言都可以用LL(1)文法來描述,而且不存在判定某語言是否是LL(1)文法的算法。