2.5.3 語法分析

　　語法分析的任務是識別由詞法分析給出的單詞符號序列是否為給定文法的正確句子(程序)。語法分析常用的方法有兩類：

　　◆自底向上分析方法(LR分析法和算符優先分析法)

　　也稱為移進-歸約分析法。對“可歸約串”刻畫的不同，形成兩種不同的分析方法，即規范歸約分析法和算符優先分析法。

　　◆自頂向下分析方法

　　也稱為面向目標的分析方法。存在兩種分析方法，遞歸子程序法和預測分析法，都使用LL(1)文法來進行語法分析。

　　例題：假設某程序語言的文法如下：

　　S→a | b | (T)

　　T→TdS | S

　　其中，VT={a,b,d,(，)}，VN={S,T}，S是開始符號。

　　考查該文法，稱句型(Sd(T)db)是S的一個A 。其中B是句柄;C是素短語;D是該句型的直接短語;E是短語。

　　A： ①最左推導 ②最右推導 ③規范推導 ④推導

　　B： ①S ②b ③(T) ④Sd(T)

　　C： ①S ②b ③(T) ④Sd(T)

　　D： ①S ②S,(T)，b ③S,(T)，TdS,b ④(Sd(T)db)

　　E： ①(Sd(T)db) ②d(T) ③Td ④Sd(T)d

　　此句型的語法樹如下所示：

　　S

　　(T)

　　(T d S)

　　(T d S b)

　　(S (T))

　　從語法樹我們可以看出，短語就是位于同一個非終端結點的所有葉子結點，比如S、Sd(T)、Sd(T)db就是是相對于T的短語，b、(T)、(Sd(T)db)是相對于S的短語。而直接短語則進一步要求這些葉子結點的非終端結點是它們的直接父結點。因此可以S、(T)、b都是該句型的直接短語。語法樹上最左的直接短語就是句柄，本題中是S。

　　所謂素短語是指這樣一個短語，它至少含有一個終結符，并且除它自身之外不再含任何更小的素短語。最左素短語則指處于句型最左邊的那個素短語。

　　最左推導是指任何一步推導過程σ→β，都是對σ中的最左非終結符進行替換。因此，在語法樹中也很容易看出，如果語法樹中的只有最左的非終結符結點(包括各級結點)具有其子樹，則它就是最左推導。最右推導與之類似，最右推導也稱規范推導。

　　相關推薦：

　　2012年軟考系統分析師考試60天完美復習計劃

　　2012年軟件水平考試網絡工程師章節筆記講義匯總

　　2012年上半年軟件水平考試成績查詢匯總