【文章內(nèi)容簡(jiǎn)介】 一組 非終結(jié)符 ，一個(gè) 開始符號(hào) ，以及一組 產(chǎn)生式 。 ? 形式上定義一個(gè)上下文無關(guān)文法Ｇ 是一個(gè)四元式（Ｖ Ｔ ，Ｖ Ｎ ，Ｓ， P） 第二章 高級(jí)語言及其語法描述 上下文無關(guān)文法的形式定義 形式上定義一個(gè)上下文無關(guān)文法Ｇ 是一個(gè)四元式 （Ｖ Ｔ ，Ｖ Ｎ ，Ｓ， P）其中 Ｖ Ｔ 是一個(gè)非空有限集，它的每一個(gè)元素稱為終結(jié)符號(hào)； Ｖ Ｎ 是一個(gè)非空有限集，它的每一個(gè)元素稱為非終結(jié)符號(hào)，Ｖ Ｔ ∩ Ｖ Ｎ ＝ ?； Ｓ 是一個(gè)非終結(jié)符號(hào)，稱為開始符號(hào)； P是一個(gè)產(chǎn)生式（有限）集合，每個(gè)產(chǎn)生式形式是 A→ ? ，其中， A∈ Ｖ Ｎ， ? ∈ （ Ｖ Ｔ ∪ Ｖ Ｎ ） ＊ 開始符號(hào) S至少必須在某一產(chǎn)生式的左部出現(xiàn)一次。 第二章 高級(jí)語言及其語法描述 上下文無關(guān)文法的舉例 一個(gè)上下文無關(guān)文法 G(Z)是一個(gè)四元式（Ｖ Ｔ ，Ｖ Ｎ ，Ｓ， P） 其中 Ｖ Ｔ ={a， b， c} Ｖ Ｎ ={Z， A， B}， Ｓ =Z P={Z?AB， A ?aAb| ?， B ?cB|c} 第二章 高級(jí)語言及其語法描述 上下文無關(guān)文法的定義 1. 所謂 終結(jié)符號(hào) 乃是組成語言的基本符號(hào)，“ 終結(jié)” 含義在于是具有獨(dú)立意義的最小語法單位，即不能再分解了的語法單位，如， He， book，如程序語言中的基本字，標(biāo)識(shí)符，常數(shù)，算符和界符等 .如： { *,+,a,b,c,(,),+,} ? 終結(jié)符號(hào)一般用小寫字母表示 第二章 高級(jí)語言及其語法描述 上下文無關(guān)文法 2. 所謂 非終結(jié)符號(hào) （也稱語法變量）用來代表語法范疇。如“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“過程”等。一個(gè)非終結(jié)符代表一個(gè)一定的語法概念。因此非終結(jié)符是一個(gè)類（或集合）記號(hào)，而不是個(gè)體記號(hào)。 ? 非終結(jié)符號(hào)一般用大寫字母表示 ? 如： {E， T， F} 第二章 高級(jí)語言及其語法描述 3. 開始符號(hào) 是一個(gè)特殊的 非終結(jié)符號(hào) ，它代表所定義的語言中我們最感興趣的語法范疇。 上下文無關(guān)文法 第二章 高級(jí)語言及其語法描述 4. 產(chǎn)生式 （也稱為產(chǎn)生規(guī)則或簡(jiǎn)稱規(guī)則）是定義語法范疇的一種書寫規(guī)則。 一個(gè)產(chǎn)生式的形式是 A→ α ? 其中箭頭左邊的 A是一個(gè) 非終結(jié)符 ，稱為產(chǎn)生式的左部符號(hào)； ? 箭頭右邊的 α是終結(jié)符號(hào)或與非終結(jié)符號(hào)組成的一符號(hào)串，稱為產(chǎn)生式的右部，或稱 候選式 。 上下文無關(guān)文法 第二章 高級(jí)語言及其語法描述 文法簡(jiǎn)寫約定 ? 只寫出產(chǎn)生式集合； ? 第一個(gè)產(chǎn)生式的左部符號(hào)約定為文法的開始符號(hào) ? 所有產(chǎn)生式中的大寫字母組成文法的非終結(jié)符號(hào)集；小寫字母組成文法的終結(jié)符號(hào)集； 一個(gè)上下文無關(guān)文法 G(Z)是一個(gè)四元式（Ｖ Ｔ ，Ｖ Ｎ ，Ｓ， P）其中 Ｖ Ｔ ={a， b， c}，Ｖ Ｎ ={Z,A,B}， Ｓ =Z P={Z?AB， A ?aAb| ?， B ?cB|c} G(Z)： Z?AB A ?aAb| ? B ?cB|c 簡(jiǎn)寫 第二章 高級(jí)語言及其語法描述 產(chǎn)生式實(shí)例 變量是一個(gè)算術(shù)表達(dá)式 ； 若 E1和 E2是算術(shù)表達(dá)式， E1+E2是算術(shù)表達(dá)式 E1*E2是算術(shù)表達(dá)式 (E1)是算術(shù)表達(dá)式 E→i Ｅ → Ｅ＋Ｅ Ｅ → Ｅ＊Ｅ Ｅ → （Ｅ） 第二章 高級(jí)語言及其語法描述 關(guān)于產(chǎn)生式 ? 可能用多個(gè)產(chǎn)生式對(duì)一個(gè)非終結(jié)符進(jìn)行定義 E→i Ｅ → Ｅ＋Ｅ Ｅ → Ｅ＊Ｅ Ｅ → （Ｅ） ? 定義產(chǎn)生式，可以采用遞歸的形式 ? 直接遞歸 ? 間接遞歸 第二章 高級(jí)語言及其語法描述 利用語法規(guī)則進(jìn)行分析的方法 ? 推導(dǎo) ——對(duì)于當(dāng)前符號(hào)串中的非終結(jié)符，用對(duì)應(yīng)的產(chǎn)生式的右部去替換之。 ? 構(gòu)造語法樹 ——文法的開始符號(hào)作為根結(jié)點(diǎn)，每推導(dǎo)一步，將非終結(jié)符作為父結(jié)點(diǎn)，對(duì)應(yīng)的產(chǎn)生式的右部作為其孩子結(jié)點(diǎn)。 第二章 高級(jí)語言及其語法描述 推導(dǎo)與直接推導(dǎo) ? 直接推導(dǎo)：僅當(dāng) A — γ 是一個(gè)產(chǎn)生式，有 α Aβ ? αγ β 該推導(dǎo)稱為直接推導(dǎo)（直接導(dǎo)出） ? 推導(dǎo)的描述形式： ? ?：任意次推導(dǎo) ? ?：至少一次推導(dǎo) * + 第二章 高級(jí)語言及其語法描述 句型與句子 假定 G是一個(gè) 文法 ， S是它的開始符號(hào)。如果S??(表示從 S出發(fā)，經(jīng) 0步或若干步可推出 ?），則稱 ?是一個(gè) 句型 。僅含終結(jié)符號(hào)的句型是一個(gè) 句子 。文法 G所產(chǎn)生的句子的全體是一個(gè)語言，將它記為 L(G). L(G)={?|S ? ? amp。 ?∈V T* } * + 第二章 高級(jí)語言及其語法描述 句型與句子 例如：終結(jié)符號(hào)串 （ i*i+i)是文法 E→E+E|E*E|(E)| ｉ 的一個(gè)句子。 因?yàn)榇嬖谝粋€(gè)從開始符號(hào) E至 (i*i+i)的推導(dǎo)： E?(E)?(E+E) ? (E*E+E) ? (i*E+E) ? (i*i+E) ? (i*i+i) 而 E,(E),(E*E+E)等是文法的句型。 第二章 高級(jí)語言及其語法描述 用文法定義語言的方法 ? 采用推導(dǎo)的方法： 從文法的開始符號(hào)，利用產(chǎn)生式，對(duì)非終結(jié)符進(jìn)行替換、展開，推導(dǎo)出全部句子的集合。 第二章 高級(jí)語言及其語法描述 例 考慮一個(gè)文法 G1: S→bA A→aA|a 它定義了一個(gè)什么語言呢？ 解：從開始符號(hào) S出發(fā)，我們可以推出如下句子： S?bA ?ba S?bA ?baA ?baa S?bA ?baA ? … ? baa… a 可以寫為： L(G1)={ban|n≥1} 第二章 高級(jí)語言及其語法描述 例 設(shè)有文法 G2 S→P|aPb P→ba|bQa Q→ab 求語言 L(G2)。 解： L(G2)={ba,baba,abab,ababab} 第二章 高級(jí)語言及其語法描述 例 設(shè)有文法 G3 S→AB A→aA|a B→bB|b 求語言 L(G3)。 解： L(G3)={ambn|m,n≥1 } 第二章 高級(jí)語言及其語法描述 例 構(gòu)造一個(gè)文法 G4使 L(G4)={an|n≥1} 解 : G4: S→aS|a 第二章 高級(jí)語言及其語法描述 例 構(gòu)造一個(gè)文法 G5使 L(G5)={anb|n≥1} 解 : G5: S→aS|ab 第二章 高級(jí)語言及其語法描述 例 構(gòu)造一個(gè)文法 G6使 L(G6)={anbm|n≥1,m ≥1} 解 : G6: S→AB A→aA|a B→bB|b 第二章 高級(jí)語言及其語法描述 例 構(gòu)造一個(gè)文法 G7使 L(G7)={anbn|n≥0} 解 : G7: S→aSb| ? 第二章 高級(jí)語言及其語法描述 例 ： 已知語言 L={anbbn| n ?1}, 寫出產(chǎn)生 L的文法。 [解 ]： G[S]: S ?aAb A ?aAb|b 如果寫成