程序語言的語法描述

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

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

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

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

5、2.2,侯選式中自左至右的每個符號對應一個新結點) 包含了最左、最右推導，但不含所有可能推導 E （ E ） E + E文法的二義性

6、 E * E i i i,,,,,,,,,,,,,文法的二義性 文法二義性 若一文法中存在某個句子,它有兩個不同的最左 (最右)推導,或者說一文法存在某個句子對應兩 棵不同的語法樹. 例: P31圖2

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

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