【正文】 En，然后使用產(chǎn)生式⑥一次，使用產(chǎn)生式⑦ n1次，得到： S ? anbnen ? 因此該文法產(chǎn)生的語(yǔ)言是 L(G)={anbnen|n≥1}。 ?能夠被 5整除的整數(shù)其結(jié)構(gòu)特點(diǎn)是，末位數(shù)一定是 0或 5。據(jù)此，構(gòu)造描述能被 5整除的無(wú)符號(hào)整數(shù)集合的文法如下： ?G[S]： ?S?N0|N5 ?N?DN|? ?D?0|1|2|3|4|5|6|7|8|9 ? 例 寫出一個(gè)上下文無(wú)關(guān)文法 G，使得 L(G)={anbmcmdn|n≥0， m≥1} ? 分析該語(yǔ)言的特點(diǎn)，可以看出， a和 d的個(gè)數(shù)是一樣的， b和 c的個(gè)數(shù)是一樣的。寫出文法為： ? S?aAd|A ? A?bAc|bc ? 對(duì)于上下文無(wú)關(guān)文法，語(yǔ)法樹是句型推導(dǎo)過(guò)程的幾何表示；是進(jìn)行句型分析極好的工具。進(jìn)一步說(shuō)就是給定一個(gè)符號(hào)串時(shí)，按照某文法的規(guī)則為該符號(hào)串構(gòu)造推導(dǎo)或語(yǔ)法樹，以此來(lái)識(shí)別它是文法的一個(gè)句型。 自上向下的分析方法 ? 1．基本思想 ? 自上而下的分析方法就是從識(shí)別符號(hào)出發(fā)，看是否能推導(dǎo)出待檢查的符號(hào)串，如果能推導(dǎo)出這個(gè)符號(hào)串，則表明此符號(hào)串是該文法的句型或句子，否則就不是。如果能生成這樣的語(yǔ)法樹，則表明待檢查的符號(hào)串是該文法的一個(gè)句型或句子，否則就不是。 ? 方法：從文法的識(shí)別符號(hào) S開始出發(fā)，選擇它的一個(gè)產(chǎn)生式 S?aAbc 得到直接推導(dǎo) ? S? aAbc以識(shí)別符 S作為根結(jié)點(diǎn)，構(gòu)造語(yǔ)法樹，如下圖 27所示 S a A b c b a 圖 27自上而下的推導(dǎo)過(guò)程 S a A b c S a B S a B B e b S a B e b B d （ a） （ b） （ c） （ d） （ e） 2．分析過(guò)程 ? 符號(hào)串 aAbc與待檢查的符號(hào)串 abed的第一個(gè)符號(hào)相匹配。 A只有一個(gè)產(chǎn)生式A?ba。 ? 符號(hào)串 ababc與待查符號(hào)串 abed的第 2個(gè)符號(hào)相匹配，但與第 3個(gè)符號(hào)不相匹配，匹配失敗。這種選擇的過(guò)程稱之為 回溯 。 ?。但在推導(dǎo)過(guò)程中會(huì)出現(xiàn)回溯現(xiàn)象。這種方法花費(fèi)時(shí)間多，效率低，編程實(shí)現(xiàn)時(shí)復(fù)雜，如果對(duì)文法加以限制，就可以避免回溯，這就出現(xiàn)了我們后面要提到的 LL(1)分析方法 ?例 設(shè)文法 G[S] ?S?aBc|bCd ?B?eB|f ?C?dC|c ?試檢查符號(hào)串 aefc是不是該文法的句子。待檢查符號(hào)串 aefc的首符號(hào)是 a，所以從識(shí)別符 S出發(fā)，只能選擇其產(chǎn)生式 S?aBc得到直接推導(dǎo) S?aBc得到語(yǔ)法樹如圖 28（ a）所示。 ?由于待檢查的符號(hào)串 aefc的第 3個(gè)符號(hào)是終結(jié)符 f，因而對(duì)句型 aeBc中的非終結(jié)符 B選擇其產(chǎn)生式 B?f的推導(dǎo)S?aBc?aeBc?aefc得到語(yǔ)法樹如圖 28（ c）所示。 S a B c S a B c e B S a B c e B f 圖 28語(yǔ)法樹 ?例 若有文法 G[S] ?S?Ap|Bq ?A?a ?A?cA ?B?b ?B?dB ?當(dāng)輸入串 W=ccap，那么試圖推出輸入串的推導(dǎo)過(guò)程為： ?S?Ap?cAp?ccAp?ccap ?很容易構(gòu)造相應(yīng)語(yǔ)法樹，如圖 29所示。如果能歸約到文法的開始的識(shí)別符號(hào)，則表明此待檢查的符號(hào)串是該文法的一個(gè)句型或句子，否則便不是。 ? 首先從輸入串開始，掃描 cabd，從中尋找一個(gè)子串，該子串與某一產(chǎn)生式的右端相匹配。 ? 構(gòu)造一個(gè)直接推導(dǎo) cAd?cabd，即從 cabd葉子開始向上構(gòu)造語(yǔ)法樹，接下去在得到的串 cAd中又找到了子串 cAd與產(chǎn)生式①的右端相匹配，則用 S替代 cAd，或稱將 cAd歸約到 S，得到了又一直接推導(dǎo) S?cAd，形成了最終的語(yǔ)法樹。 圖 210自下而上構(gòu)造語(yǔ)法樹 c a b d c a b d A c a b d A S 2．存在問(wèn)題 ? 在自上向下的分析中，假定要被代換的最左非終結(jié)符的符號(hào)是 V，且有 n條規(guī)則： V??1|?2|?3|…| ?n，那么如何確定用哪個(gè)右部去替換 V？有一種解決方法是從各種可能的選擇中挑選一種，并希望它是正確的。 ? 在自下向上的分析方法中，在分析程序工作的每一步中，都從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號(hào)，我們暫且把這個(gè)子串稱為“可歸約串”。因此在歸約時(shí)， ab是“可歸約串”而不是 a。下面我們用“句柄”的概念來(lái)描述“可歸約 3．句柄的概念 ? （ 1）形式化定義 ? 定義 G是一文法， S是文法的開始符號(hào)， ??? 是文法的一個(gè)句型。特別地，如有 A??則稱 ?是句型 ???相對(duì)于規(guī)則 A??的直接短語(yǔ)。 ? （ 2）求一個(gè)句型的句柄 ? 給定某個(gè)句型，要求出該句型的句柄，比較直觀的方法就是畫出該句型的語(yǔ)法樹。 ? 語(yǔ)法樹的一棵簡(jiǎn)單子樹（只有單層子樹）的葉子結(jié)點(diǎn)組成的符號(hào)串是這個(gè)句型關(guān)于簡(jiǎn)單子樹根結(jié)點(diǎn)的一個(gè)直接短語(yǔ)。 ? 例 已知文法 G[S]： ? S?(R)|a|∧ ? R?T ? T?S,T|S ? 句型 ?=(a,(T),(S,T))的語(yǔ)法樹如圖 211所示。 ? 因此有短語(yǔ) ? 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語(yǔ)法樹 ? 一個(gè)文法的語(yǔ)法圖由該文法所有非終結(jié)符的定義圖組成。 ? 名字定義下一個(gè)候選式右部后繼 ? 寫成高級(jí)語(yǔ)言的結(jié)構(gòu)型數(shù)據(jù)形式，則為： ? type struc=↑boxes ? boxes=record ? name:array[1‥ 10] of char。 ? nextp:struc。 ? end?！岸x”是一個(gè)指針，對(duì)于非終結(jié)符號(hào)，它指向其第一個(gè)侯選式結(jié)構(gòu)圖的開始位置。若無(wú)侯選式，則它為 0；“右部后繼”是一個(gè)指針，指向同一個(gè)右部的下一個(gè)符號(hào)。 ? 也就是說(shuō)，這個(gè)數(shù)組的每個(gè)元素都是一個(gè)指針，分別指向相應(yīng)的非終結(jié)符號(hào)的第一個(gè)候選式的定義圖。文法可定義為一個(gè)四元組，文法 G=（ VN， VT，P， S），其中， VN是一個(gè)非終結(jié)符集， VT是一個(gè)終結(jié)符集， P是一個(gè)產(chǎn)生式集， S是文法的開始符號(hào)。程序設(shè)計(jì)語(yǔ)言的詞法規(guī)則屬于 3型文法（正規(guī)文法），程序設(shè)計(jì)語(yǔ)言的語(yǔ)法和語(yǔ)義部分一般是采用 2型文法來(lái)描述。要識(shí)別一個(gè)符號(hào)串是不是一個(gè)文法的句子，需要對(duì)它進(jìn)行語(yǔ)法分析。 ?為了進(jìn)行語(yǔ)法分析，需要事先將產(chǎn)生式存儲(chǔ)在計(jì)算機(jī)中。為了在分析過(guò)程中能迅速查找到相應(yīng)的產(chǎn)生式，還可以建立一個(gè)目錄表。 ? 2．令 ?={a,b,c}，又令 x=abc， y=b， z=aab，寫出下列符號(hào)串及它們的長(zhǎng)度： xy， xyz， (xy)3。 ? 4．已知文法 ? ① S?AB ? ② A??|aA ? ③ B?bc|bBc ? 寫出該文法描述的語(yǔ)言。 ? 6．對(duì)于文法 ? ① E?T|E+T|ET ? ② T?F|T*F|T/F ? ③ F?(E)|i ? 寫出句型 T+T*F+i的短語(yǔ)、簡(jiǎn)單短語(yǔ)以及句柄。 ? 8．文法 G=({A， B， S}， {a,b,c},P,S) ? 其中 P為： ? S→Ac|Ab ? A→ab ? B→bc ? 寫出 LG[S]）的全部元素。 ? 10．為句子 i+i*i構(gòu)造兩棵語(yǔ)法樹，從而證明下述文 法是二義性的。 ? （ 1） {anbnambm|n,m≥0} ? (2) {1n0m1m0n|n,m≥0} ? 12．句型、句子和語(yǔ)言之間有什么關(guān)系？