程序語(yǔ)言的語(yǔ)法描述

1、第三講 程序語(yǔ)言的語(yǔ)法描述,作業(yè)：P36（6，7，8） 其中6（2）做0127 8（1）做i+i*i,上下文無(wú)關(guān)文法語(yǔ)法范疇完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境,1）文法與語(yǔ)言文法 上下文無(wú)關(guān)文法G是一個(gè)四元式（VT，VN，S，P）。其中 VT：非空集，每個(gè)元素叫終結(jié)符 VN：非空有限集，每個(gè)元素稱為非終結(jié)符 S： 非終結(jié)符，叫做開(kāi)始符號(hào) P： 產(chǎn)生式集（有限）， 形式為 P-&

2、gt;?, 其中 P? VN, ??(VT ?VN)* 注意: 開(kāi)始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次. P-> ?1 P-> ?2 … P-> ?n 可以縮寫為 P-> ?1 | ?2 | …| ?n 每個(gè)?i 也叫 P 的一個(gè)侯選式. 討論中多以大寫字母表示非終結(jié)符,,語(yǔ)言 上下文無(wú)關(guān)文法定義語(yǔ)言的辦法: 從文法的開(kāi)始符出發(fā),

3、反復(fù)連續(xù)使用產(chǎn)生式,對(duì)非終結(jié)符實(shí)施替換和展開(kāi).E.G. 文法 E->E+E |E*E | (E) | i (P28) 據(jù)規(guī)則: E ->(E),我們說(shuō): 從“E”可以直接推出“(E)”,記為 E=>(E); 對(duì)“(E)”中“E”再用 E->E+E 便有: (E)=>(E+E), 即由 “E” 可以推出(E+E). 表示為: E=>(E)=>(E+E),,基本術(shù)語(yǔ)(P29)

4、 學(xué)員閱讀直接推出推導(dǎo)可推導(dǎo)出?1 =+> ?n?1 =*> ?n 文法的句型 文法G的句子全體形成它的語(yǔ)言 L(G)= {?| S=*> ?且??VT*}最左推導(dǎo)(最右推導(dǎo)) E=>(E)=>(E+E) => (E*E+E) => (i*E+E) => (i*i+E) => (i*i+i),,2) 語(yǔ)法樹(shù)及二義性語(yǔ)法樹(shù)（P31圖

5、2.2,侯選式中自左至右的每個(gè)符號(hào)對(duì)應(yīng)一個(gè)新結(jié)點(diǎn)) 包含了最左、最右推導(dǎo)，但不含所有可能推導(dǎo) E （ E ） E + E文法的二義性

6、 E * E i i i,,,,,,,,,,,,,文法的二義性 文法二義性 若一文法中存在某個(gè)句子,它有兩個(gè)不同的最左 (最右)推導(dǎo),或者說(shuō)一文法存在某個(gè)句子對(duì)應(yīng)兩 棵不同的語(yǔ)法樹(shù). 例: P31圖2

7、.2, P32圖2.3 (i*i+i) 語(yǔ)言的二義性 某語(yǔ)言由不同文法刻畫(huà) 兩種二義性有何不同,,P28的表達(dá)式文法可以通過(guò)規(guī)定*,+優(yōu)先順序,結(jié)合規(guī)則而構(gòu)造一無(wú)二義的文法. E -> T | E+T 概念分層思想 T -> F | T*F F -> (E) | i,,對(duì)上下文無(wú)關(guān)文法的兩點(diǎn)限制文法中不含任何 P->P 形式的產(chǎn)生式

8、 (會(huì)產(chǎn)生二義?)每個(gè)非終結(jié)符都有用處 即存在 S =*> ?? P ?, 則必有 ??VT*, 使得 P =*> ?.,,3) 形式語(yǔ)言鳥(niǎo)瞰 Chomsky 將文法分為四類: 0, 1, 2, 30: 每個(gè)產(chǎn)生式 ? ? ?滿足: ??(VN ?VT)*且至少含一個(gè)非終結(jié)符, 而 ? ?(VN ?VT)*.1: 每個(gè)產(chǎn)生式 ? ? ?滿足: