【正文】 推導(dǎo)和語法樹 前例 對(duì)文法 G[S]=({S,A,B},{a,b},P,S) 其中 P為： 可用語法樹非常直觀地求出句型 baSb的全部短語，直接短語和句柄。 S?AB A?Aa | bB B?a | Sb 推導(dǎo)和語法樹 分析 首先根據(jù)句型 baSb的推導(dǎo)過程畫出對(duì) 應(yīng)的語法樹如下： Sb 為句型的相對(duì)于 B的短語、 直接短語 baSb 為句型的相對(duì)于 S的短語 ba 為句型的相對(duì)于 A的短語 a 句型的相對(duì)于 B的短語、 直接短語 和 句柄 S?AB?bBB?baB?baSb S?AB?ASb?bBSb?baSb S A B b B S b a 由語法樹可知 文法的二義性 從前面的討論可以看出，對(duì)于文法 G中 任一句型的推導(dǎo)序列 , 我們總能為它構(gòu)造 一棵語法樹，現(xiàn)在我們提出一個(gè)問題： 文法的某個(gè)句型是否只對(duì)應(yīng)唯一的一棵 語法樹呢？ 也就是，它是否只有唯一的一 個(gè)最左 (最右 )推導(dǎo)呢？ 文法的二義性 例如 設(shè)有文法 G[E]： 句子 i*i+i 有兩個(gè)不同的最左推導(dǎo)，對(duì)應(yīng)兩棵不同的語法樹。 E ? E+E | E*E | (E) | i 文法的二義性 最左推導(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 E E * E E + E i i i E E + E E * E i i i 文法的二義性 如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng) 兩棵不同的語法樹， 則說這個(gè)文法是 二義性 的。 或者說，若一個(gè)文法中存在某個(gè)句子，它有 兩個(gè)不同的最左 (最右 ) 推導(dǎo)，則這個(gè)文法是 二義性的。 E ? E+E | E*E | (E) | i 文法二義性的消除 1. 不改變文法中原有的語法規(guī)則 , 僅加 進(jìn)一些 非形式 的語法規(guī)定。 E E + E E * E i i i 文法二義性的消除 2. 構(gòu)造一個(gè) 等價(jià)的無二義性文法 。即 把排除二義性的規(guī)則 合并 到原有文法中 , 改寫原有的文法。 例如，對(duì)于上例文法 G[E]， 將運(yùn)算符的 優(yōu)先順序和結(jié)合規(guī)則： *優(yōu)先于＋ 。 ＋、 * 左結(jié)合加到原有文法中 , 可構(gòu)造出無二義 性文法如下 ： 文法二義性的消除 則句子 i*i+i只有唯一一棵語法樹： E?E+T | T T?T*F | F F?(E) | i E E + T T T * F F i i F i 文法二義性的消除 例 2 定義某程序語言條件語句的文法 G為 : 試證明該文法是二義性的并消除之。 分析 該文法的句子 if b if b A else A 對(duì)應(yīng)下面兩棵不同的語法樹： S?if b S | if b S else S | A (其它語句） 文法二義性的消除 所以該文法是二義的。 S if b S b S S if A else A S b S S if A else A if b S S?if b S | if b S else S | A 句子 if b if b A else A 文法二義性的消除 消除文法的二義性可采用下面兩種方法： 1. 不改變已有規(guī)則 ，僅 加進(jìn)一非形式的語法規(guī) 定： else與前面最接近 的不帶 else的 if 相對(duì)。 S if b S b S S if A else A 文法 G的句子 if b if b A else A 只對(duì)應(yīng)唯一的一棵語法樹 ， 消除了二義性。 文法二義性的消除 2. 改寫文法 G為 G39。 S? S1 | S2 S1? if b S1 else S1 | A S2? if b S | if b S1 else S2 G39。: S?if b S | if b S else S | A (其它語句） G: 文法二義性的消除 這是因?yàn)橥ㄟ^ 分析 ，得知引起二義性的原因是 : if—else 語句的 if 后可以是 if型， 因此改寫文法時(shí)規(guī)定 : if — else之間只能是 if—else語句或其他語句 。 文法二義性的消除 S? S1 | S2 S1? if b S1 else S1 | A S2? if b S | if b S1 else S2 if b S b if A else A S S2 S1 S1 S1 對(duì)改寫后的文法，句子 if b if b A else A 只對(duì)應(yīng)唯一的一棵語法樹。 通常我們 只說文法的二義性 , 而不說語言的二義性 , 這是因?yàn)榭赡苡袃蓚€(gè)不同的文法 G和 G39。 ， 而且其中一個(gè)是 二義性的， 另一個(gè)是 無二義性的 , 但卻有L(G)=L(G39。), 即這兩個(gè)文法所產(chǎn)生的 語言是相同的。 文法二義性的消除 應(yīng)該指出的是文法的二義性和語言的二義性是 兩個(gè)不同的概念 。 文法二義性的消除 將一個(gè)語言說成是二義性的， 是指對(duì)它 不存在無二義性的文法， 這樣的語言稱為先天二義性的語言。 例如 L={ ai bj