【正文】 析方法的基本思想是從待檢查的符號串出發(fā)，看最終是否能歸約到文法的識別符號。如果能歸約到文法的開始的識別符號，則表明此待檢查的符號串是該文法的一個句型或句子，否則便不是。 ? 例 若有文法 G[S] ? ① S?cAd ? ② A?ab ? ③ A?a ? 識別輸入串 w=cabd是否是該文法的句子。 ? 首先從輸入串開始，掃描 cabd，從中尋找一個子串，該子串與某一產(chǎn)生式的右端相匹配。子串 a和子串 ab都是合格的，假若我們選用了 ab，用產(chǎn)生式②的左端 A去替代它，即把 ab歸約到 A，得到串 cAd。 ? 構(gòu)造一個直接推導 cAd?cabd，即從 cabd葉子開始向上構(gòu)造語法樹，接下去在得到的串 cAd中又找到了子串 cAd與產(chǎn)生式①的右端相匹配，則用 S替代 cAd，或稱將 cAd歸約到 S，得到了又一直接推導 S?cAd，形成了最終的語法樹。分析過程如圖 210所示。 圖 210自下而上構(gòu)造語法樹 c a b d c a b d A c a b d A S 2．存在問題 ? 在自上向下的分析中，假定要被代換的最左非終結(jié)符的符號是 V，且有 n條規(guī)則： V??1|?2|?3|…| ?n，那么如何確定用哪個右部去替換 V？有一種解決方法是從各種可能的選擇中挑選一種，并希望它是正確的。如果發(fā)現(xiàn)它是錯誤的，我們必須退回，再試著進行另外的選擇，這種方式稱為回溯。 ? 在自下向上的分析方法中，在分析程序工作的每一步中，都從當前串中選擇一個子串，將它歸約到某個非終結(jié)符號，我們暫且把這個子串稱為“可歸約串”。出現(xiàn)的問題是如何確定這個“可歸約串”？比如在上例中，我們在對輸入串 cabd 的分析中，如果不是選擇 ab，用產(chǎn)生式②，而是選擇 a，用產(chǎn)生式③將 a歸約到 A，那么最終就達不到 S的結(jié)果，也就不知道 cabd是一個句子。因此在歸約時， ab是“可歸約串”而不是 a。如何求“可歸約串”成為自下而上進行分析的關(guān)鍵。下面我們用“句柄”的概念來描述“可歸約 3．句柄的概念 ? （ 1）形式化定義 ? 定義 G是一文法， S是文法的開始符號， ??? 是文法的一個句型。如果有： S ?A?且 A ?則稱 ?是句型 ???相對于非終結(jié)符 A的短語。特別地，如有 A??則稱 ?是句型 ???相對于規(guī)則 A??的直接短語。一個句型的最左直接短語稱為該句型的句柄。 ? （ 2）求一個句型的句柄 ? 給定某個句型，要求出該句型的句柄，比較直觀的方法就是畫出該句型的語法樹。該語法樹的一棵子樹的葉子結(jié)點（從左到右）組成的符號串便是這個句型關(guān)于子樹根結(jié)點的一個短語。 ? 語法樹的一棵簡單子樹（只有單層子樹）的葉子結(jié)點組成的符號串是這個句型關(guān)于簡單子樹根結(jié)點的一個直接短語。語法樹的最左的簡單子樹葉子結(jié)點組成的符號串就是這個句型的句柄。 ? 例 已知文法 G[S]： ? S?(R)|a|∧ ? R?T ? T?S,T|S ? 句型 ?=(a,(T),(S,T))的語法樹如圖 211所示。 ? 【 解答 】 觀察該語法樹，共有 10個非葉子結(jié)點， 10棵子樹。 ? 因此有短語 ? a ? T ? (T) ? S,T ? (S,T) ? (T), (S,T) ? a, (T), (S,T) ? (a, (T), (S,T)) S ( R ) S ， T a T ， S T ( R ) T S ( R ) S ， T 圖 211語法樹 ? 一個文法的語法圖由該文法所有非終結(jié)符的定義圖組成。每個非終結(jié)符號的定義圖是一個結(jié)構(gòu)型數(shù)據(jù)。 ? 名字定義下一個候選式右部后繼 ? 寫成高級語言的結(jié)構(gòu)型數(shù)據(jù)形式，則為： ? type struc=↑boxes ? boxes=record ? name:array[1‥ 10] of char。 ? def:struc。 ? nextp:struc。 ? rights:struc。 ? end。 ? 其中，“名字”是用某種內(nèi)部形式表示的終結(jié)符號或非終結(jié)符號的名字?！岸x”是一個指針，對于非終結(jié)符號，它指向其第一個侯選式結(jié)構(gòu)圖的開始位置。對于終結(jié)符號，它為 0；“下一個侯選式”是一個指針，指向相同左部的下一個侯選式的開始位置。若無侯選式，則它為 0；“右部后繼”是一個指針，指向同一個右部的下一個符號。另用一個一維數(shù)組記錄所有的非終結(jié)符號定義圖的開始地址。 ? 也就是說，這個數(shù)組的每個元素都是一個指針，分別指向相應(yīng)的非終結(jié)符號的第一個候選式的定義圖。 ? 例 ? E?EAT|T ? T?TMF|F ? F?（ E） |i ? A?+|－ ? M?*|/ ? 按照上面的存儲結(jié)構(gòu)，畫出文法的存儲結(jié)構(gòu)如圖 212所示： E E + T ∧ E T 文法 圖 215文法的鏈表結(jié)構(gòu)圖 T ∧ T * F ∧ T F ∧ F ( E ) ∧ F i ∧ 小 結(jié) ?文法是形式語言的一個十分重要的基本概念。文法可定義為一個四元組，文法 G=（ VN， VT，P， S），其中， VN是一個非終結(jié)符集， VT是一個終結(jié)符集， P是一個產(chǎn)生式集， S是文法的開始符號。 ?Chomsky 將文法分為 0 型， 1型， 2型和 3型文法。程序設(shè)計語言的詞法規(guī)則屬于 3型文法（正規(guī)文法），程序設(shè)計語言的語法和語義部分一般是采用 2型文法來描述。 ?對于一個文法，我們需要研究它的句型，句子和語言。要識別一個符號串是不是一個文法的句子，需要對它進行語法分析。分析方法有兩類，一類是自上而下分析法，另一類是自下而上的分析方法。 ?為了進行語法分析，需要事先將產(chǎn)生式存儲在計算機中?？梢詾槲姆ń⒁粋€產(chǎn)生式表，把文法的所有的產(chǎn)生式都放在這個產(chǎn)生式表中。為了在分析過程中能迅速查找到相應(yīng)的產(chǎn)生式，還可以建立一個目錄表。 習 題 ? 1．設(shè)字母表 A={a}，符號串 x=aaa，寫出下列符號串及其長度： x0， xx， x5以及 A+和 A*。 ? 2．令 ?={a,b,c}，又令 x=abc， y=b， z=aab，寫出下列符號串及它們的長度： xy， xyz， (xy)3。 ? 3．設(shè)文法 G[S]： S→SS*|SS+|a，寫出符號串 aa+a*規(guī)范推導，并構(gòu)造語法樹。 ? 4．已知文法 ? ① S?AB ? ② A??|aA ? ③ B?bc|bBc ? 寫出該文法描述的語言。 ?5．已知文法 ?① E?T|E+T|ET ?② T?F|T*F|T/F ?③ F?(E)|i ?寫出該文法的開始符號、終結(jié)符集合 VT、非終結(jié)符集合 VN。 ? 6．對于文法 ? ① E?T|E+T|ET ? ② T?F|T*F|T/F ? ③ F?(E)|i ? 寫出句型 T+T*F+i的短語、簡單短語以及句柄。 ? 7．設(shè)計出語言 {anbm|n,m≥1}的文法。 ? 8．文法 G=({A， B， S}， {a,b,c},P,S) ? 其中 P為： ? S→Ac|Ab ? A→ab ? B→bc ? 寫出 LG[S]）的全部元素。 ? 9．已知文法 Z→aZb ? Z→ab ? 寫出 L（ G[Z]）的全部元素。 ? 10．為句子 i+i*i構(gòu)造兩棵語法樹，從而證明下述文 法是二義性的。 ? 表達式 →i|(表達式 )|表達式 運算符 表達式 ? 運算符 →+|－ |*|/ ? 11．寫出生成下述語言的上下文無關(guān)文法。 ? （ 1） {anbnambm|n,m≥0} ? (2) {1n0m1m0n|n,m≥0} ? 12．句型、句子和語言之間有什么關(guān)系？