【正文】 ? 表達(dá)式 →i|(表達(dá)式 )|表達(dá)式 運(yùn)算符 表達(dá)式 ? 運(yùn)算符 →+|－ |*|/ ? 11．寫(xiě)出生成下述語(yǔ)言的上下文無(wú)關(guān)文法。 ? 9．已知文法 Z→aZb ? Z→ab ? 寫(xiě)出 L（ G[Z]）的全部元素。 ? 7．設(shè)計(jì)出語(yǔ)言 {anbm|n,m≥1}的文法。 ?5．已知文法 ?① E?T|E+T|ET ?② T?F|T*F|T/F ?③ F?(E)|i ?寫(xiě)出該文法的開(kāi)始符號(hào)、終結(jié)符集合 VT、非終結(jié)符集合 VN。 ? 3．設(shè)文法 G[S]： S→SS*|SS+|a，寫(xiě)出符號(hào)串 aa+a*規(guī)范推導(dǎo)，并構(gòu)造語(yǔ)法樹(shù)。 習(xí) 題 ? 1．設(shè)字母表 A={a}，符號(hào)串 x=aaa，寫(xiě)出下列符號(hào)串及其長(zhǎng)度： x0， xx， x5以及 A+和 A*?？梢詾槲姆ń⒁粋€(gè)產(chǎn)生式表，把文法的所有的產(chǎn)生式都放在這個(gè)產(chǎn)生式表中。分析方法有兩類，一類是自上而下分析法，另一類是自下而上的分析方法。 ?對(duì)于一個(gè)文法，我們需要研究它的句型，句子和語(yǔ)言。 ?Chomsky 將文法分為 0 型， 1型， 2型和 3型文法。 ? 例 ? E?EAT|T ? T?TMF|F ? F?（ E） |i ? A?+|－ ? M?*|/ ? 按照上面的存儲(chǔ)結(jié)構(gòu)，畫(huà)出文法的存儲(chǔ)結(jié)構(gòu)如圖 212所示： E E + T ∧ E T 文法 圖 215文法的鏈表結(jié)構(gòu)圖 T ∧ T * F ∧ T F ∧ F ( E ) ∧ F i ∧ 小 結(jié) ?文法是形式語(yǔ)言的一個(gè)十分重要的基本概念。另用一個(gè)一維數(shù)組記錄所有的非終結(jié)符號(hào)定義圖的開(kāi)始地址。對(duì)于終結(jié)符號(hào)，它為 0；“下一個(gè)侯選式”是一個(gè)指針，指向相同左部的下一個(gè)侯選式的開(kāi)始位置。 ? 其中，“名字”是用某種內(nèi)部形式表示的終結(jié)符號(hào)或非終結(jié)符號(hào)的名字。 ? rights:struc。 ? def:struc。每個(gè)非終結(jié)符號(hào)的定義圖是一個(gè)結(jié)構(gòu)型數(shù)據(jù)。 ? 【 解答 】 觀察該語(yǔ)法樹(shù)，共有 10個(gè)非葉子結(jié)點(diǎn)， 10棵子樹(shù)。語(yǔ)法樹(shù)的最左的簡(jiǎn)單子樹(shù)葉子結(jié)點(diǎn)組成的符號(hào)串就是這個(gè)句型的句柄。該語(yǔ)法樹(shù)的一棵子樹(shù)的葉子結(jié)點(diǎn)（從左到右）組成的符號(hào)串便是這個(gè)句型關(guān)于子樹(shù)根結(jié)點(diǎn)的一個(gè)短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。如果有： S ?A?且 A ?則稱 ?是句型 ???相對(duì)于非終結(jié)符 A的短語(yǔ)。如何求“可歸約串”成為自下而上進(jìn)行分析的關(guān)鍵。出現(xiàn)的問(wèn)題是如何確定這個(gè)“可歸約串”？比如在上例中，我們?cè)趯?duì)輸入串 cabd 的分析中，如果不是選擇 ab，用產(chǎn)生式②，而是選擇 a，用產(chǎn)生式③將 a歸約到 A，那么最終就達(dá)不到 S的結(jié)果，也就不知道 cabd是一個(gè)句子。如果發(fā)現(xiàn)它是錯(cuò)誤的，我們必須退回，再試著進(jìn)行另外的選擇，這種方式稱為回溯。分析過(guò)程如圖 210所示。子串 a和子串 ab都是合格的，假若我們選用了 ab，用產(chǎn)生式②的左端 A去替代它，即把 ab歸約到 A，得到串 cAd。 ? 例 若有文法 G[S] ? ① S?cAd ? ② A?ab ? ③ A?a ? 識(shí)別輸入串 w=cabd是否是該文法的句子。 S A p S A p c A S A p c A c A S A p c A c A a 圖 29語(yǔ)法樹(shù) （ a） （ b） （ c） （ d） ?1．基本思想 ?自下而上的分析方法的基本思想是從待檢查的符號(hào)串出發(fā)，看最終是否能歸約到文法的識(shí)別符號(hào)。 ?如此推導(dǎo)出的符號(hào)串 aefc，語(yǔ)法樹(shù)的葉子結(jié)點(diǎn)序列是 aefc，與待檢查的符號(hào)串 aefc相匹配。其中，非終結(jié)符 B有兩條產(chǎn)生式，它們右部首符號(hào)分別是終結(jié)符 e與 f，而待檢查的符號(hào)串 aefc的第2個(gè)符號(hào)是終結(jié)符 e，所以選擇 B的產(chǎn)生式B?eB ?得到推導(dǎo) S?aBc?aeBc，得到語(yǔ)法樹(shù)如圖28（ b）所示。 ?識(shí)別符 S有兩條產(chǎn)生式，它們的右部首符號(hào)分別是終結(jié)符 a和 b。我們把出現(xiàn)回溯的分析稱為不確定的自頂上下分析方法。 3．存在問(wèn)題 ? 自上而下分析方法是從文法的識(shí)別符號(hào)開(kāi)始，選擇相應(yīng)的產(chǎn)生式規(guī)則進(jìn)行推導(dǎo)。 ?選擇 S的另外一條產(chǎn)生式的規(guī)則 S?aB，得到直接推導(dǎo) S?aB，得到語(yǔ)法樹(shù) 27（ c），再選取其中的一條產(chǎn)生式 B?beB，得到推導(dǎo)S?aB?abeB，得到語(yǔ)法樹(shù)如圖（ d），將B?d代入即可得到該字符串 abed。此時(shí)，需要退回到非終結(jié)符 A，重新選擇 S另外的產(chǎn)生式，再做試探。以其右部替換 A，得推導(dǎo)S?aAbc?ababc得到語(yǔ)法樹(shù)，如圖 27（ b）所示。由于符號(hào)串 aAbc的第 2個(gè)符號(hào)是非終結(jié)符，因此需要對(duì)它進(jìn)行替換。 ? 例 設(shè)文法 G[S]： ? S?aAbc| aB ? A?ba ? B?beB|d ? 輸入串： abed，識(shí)別該串是否是該文法的一個(gè)句子?；蛘哒f(shuō)，以文法的識(shí)別符號(hào)作為根結(jié)點(diǎn)，看是否能構(gòu)造出一個(gè)語(yǔ)法樹(shù)，而且此語(yǔ)法樹(shù)所有葉子結(jié)點(diǎn)從左到右所構(gòu)成的符號(hào)串恰好是待檢查的符號(hào)串。對(duì)于上下文無(wú)關(guān)文法，其句型分析方法有兩大類，一類是自上而下的分析方法（又稱自頂向下），另一類是自下而上（自底向上）的分析方法。所謂句型分析就是識(shí)別一個(gè)符號(hào)串是否是某一個(gè)文法的句型。 m的取值范圍從 1開(kāi)始，所以至少有一個(gè) bc， n的最小值為 0。所以，只要保證生成的整數(shù)末位數(shù)字是 0或 5即可。 ? 例 設(shè)有上下文無(wú)關(guān)文法如下： ? G[S]： ? S?AB ? A?UT ? U?a|aU ? T?b|bT ? B?c|cC ? 將文法的產(chǎn)生式代入產(chǎn)生如下文法： ? G[S]： ? S?UTB ? U?a| aU ? T?b|bT ? B?c|cC ?考察文法，用 L(S)， L(U)， L(T)和 L(B)分別表示從終結(jié)符 S， U， T和 B出發(fā)推導(dǎo)出的符號(hào)串的集合，不難發(fā)現(xiàn)： ?L（ U） ={ai|i≥1}={a}+ ?L（ T） ={bj|j≥1}={a}+ ?L（ B） ={ck|k≥1}={a}+ ?由于有 S?UTB，則有： ?L（ S） =L(U)L(T)L(B) ?=(aibjck|i≥1,j≥1, k≥1) ?={a}++{c}+ ?例 構(gòu)造一個(gè)上下文無(wú)關(guān)文法 G，使其描述的語(yǔ)言 L（ G）是能夠被 5整除的無(wú)符號(hào)整數(shù)集合。設(shè) n=3，aaBEBEBE?aaaBBEEBE?aaaBBEBEE?aaaBBBEEE。該文法產(chǎn)生式左部串的長(zhǎng)度均小于等于右部串的長(zhǎng)度，符合 1型文法的定義，所以該文法是上下文有關(guān)文法。 ? 推導(dǎo) 1： E?E+E?E*E+E?i*E+E?i*i+E?i*i+i ? 推導(dǎo) 2： E?E*E?i*E?i*E+E?i*i+E?i*i+i ? 推導(dǎo)的兩棵語(yǔ)法樹(shù)如圖 26所示。 ? 【 證明 】 取句型 i*i+i，寫(xiě)出該句型的兩個(gè)不同的推導(dǎo)。 ? 我們要證明一個(gè)文法是否是一個(gè)二義性文法，就是找到該文法的一個(gè)句型特例，能夠畫(huà)出這個(gè)句型的兩棵語(yǔ)法樹(shù)，該文法就是二義性文法。 S if B then S if B then else S S S if B then else S S if B then S 2．二義性文法的證明 ? 要判定一個(gè)文法是否是二義性文法，或它是否產(chǎn)生一個(gè)先天二義性的上下文無(wú)關(guān)語(yǔ)言，是個(gè)遞歸不可解的。 ?在語(yǔ)言中，為了避免二義性的文法，往往對(duì)文法加以一定的限制，如限制條件語(yǔ)句then之后不允許再是條件語(yǔ)句，或者從語(yǔ)義解釋方面限制條件語(yǔ)句中的 else只能與其前面的、還沒(méi)有和其他 else配對(duì)的 then配對(duì)。 ? 語(yǔ)法樹(shù)的結(jié)構(gòu)如圖 25所示。如果一個(gè)文法含有二義性的句子，則稱該文法具有二義性。 ?