2012年軟考系統(tǒng)分析師經(jīng)典教程：重點(diǎn)與難點(diǎn)

　　2.5.3 語法分析

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

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

　　也稱為移進(jìn)-歸約分析法。對(duì)“可歸約串”刻畫的不同，形成兩種不同的分析方法，即規(guī)范歸約分析法和算符優(yōu)先分析法。

　　◆自頂向下分析方法

　　也稱為面向目標(biāo)的分析方法。存在兩種分析方法，遞歸子程序法和預(yù)測(cè)分析法，都使用LL(1)文法來進(jìn)行語法分析。

　　例題：假設(shè)某程序語言的文法如下：

　　S→a | b | (T)

　　T→TdS | S

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

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

　　A： ①最左推導(dǎo) ②最右推導(dǎo) ③規(guī)范推導(dǎo) ④推導(dǎo)

　　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))

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

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

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

　　相關(guān)推薦：

　　2012年軟考系統(tǒng)分析師考試60天完美復(fù)習(xí)計(jì)劃

　　2012年軟件水平考試網(wǎng)絡(luò)工程師章節(jié)筆記講義匯總

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