高級(jí)語言及其文法.pptVIP

第2章 高級(jí)語言 及其文法（3）,本章主要內(nèi)容,2.1 語言概述 2.2 基本定義(語言、句子、形式化方法、串、字母表、串的連接與冪、產(chǎn)生式) 2.3 文法(Grammar)的定義 2.4 CFG的語法(分析)樹(Parse Tree) 2.5 文法的分類 2.6 文法的構(gòu)造,2. 文法的分類(Chomsky體系),語言結(jié)構(gòu)的復(fù)雜程度（形式語言） 涉及文法的復(fù)雜程度、分析方法的選擇 如果G滿足文法定義的要求，則是型文法（短語結(jié)構(gòu)文法PSG: Phrase Structure Grammar ）。 L(G)為PSL。,2.4.1文法與語言的分類,0型文法（或稱短語文法）,特點(diǎn)：產(chǎn)生式行如， (VNVT)*且至少包含一個(gè)非終結(jié)符，而,0型文法又稱為無限制文法，有時(shí)也稱為短語文法（phase structure grammar, PSG）。 0型文法對(duì)應(yīng)的語言稱為0型語言或稱遞歸可枚舉集，它們的識(shí)別系統(tǒng)為圖靈機(jī)（Turing機(jī)）。,1型文法（或稱上下文有關(guān)文法）,特點(diǎn)：限制P中的每個(gè)產(chǎn)生式都要滿足| 。,1型文法相對(duì)應(yīng)的語言稱為1型語言或上下文有關(guān)語言，它的識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)。,1型文法的另一種定義方法是文法G(S)的每一個(gè)產(chǎn)生式具有下列形式：,另一定義：,2型文法（或稱上下文無關(guān)文法）,特點(diǎn)：每個(gè)產(chǎn)生式的形式限制為A ，其中A為單個(gè)非終結(jié)符，,2型文法相對(duì)應(yīng)的語言稱為2型語言或上下文無關(guān)語言，它的識(shí)別系統(tǒng)為下推自動(dòng)機(jī)(PDA)。,3型文法（或稱正規(guī)文法、正則文法）,特點(diǎn)：文法中每個(gè)產(chǎn)生式的形式為,AaB或,Aa，其中A、BVN，,A、B、a都是單,個(gè)符號(hào)。,3型文法對(duì)應(yīng)的語言稱為3型語言或正規(guī)語言（正則語言，或正則集）。,例2-3 標(biāo)識(shí)符的文法2,S L|LT T L|N|TL|TN L a|b|c|d N 0|1|2|3|4|5,S a|b|c|d S aT|bT|cT|dT T a|b|c|d|0|1|2|3|4|5 T aT|bT|cT|dT|0T T 1T|2T|3T|4T|5T,例2-4 標(biāo)識(shí)符的文法3,S a|b|c|d S aT|bT|cT|dT T a|b|c|d T 0|1|2|3|4|5 T aT|bT|cT|dT|0T T 1T|2T|3T|4T|5T,S a|b|c|d S Ha|Hb|Hc|Hd|H0 S H1|H2|H3|H4|H5 H Ha|Hb|Hc|Hd|H0 H H1|H2|H3|H4|H5 H a|b|c|d,正規(guī)文法(RG),設(shè)A、BVN，aVT 右線性(Right Linear)文法：AaB或Aa 左線性(Left Linear)文法：ABa或Aa 都是型文法(正規(guī)文法 Regular Grammar -RG) L(G)為3型/正規(guī)集/正則集/正則語言（RL） 例：程序設(shè)計(jì)語言的多數(shù)詞法特性 左、右線性文法不可混用,例 非CFL的文法,L=anbncn|n0的文法 SaBC|aSBC CBBC aBab bBbb bCbc cC cc,“可以證明”不存在CFG G ,使L(G)=L,在我們使用的程序語言中,有些語言結(jié)構(gòu)并不是總能用上下文無關(guān)文法描述的。 例 L1=wcw|wa,b+。例,aabcaab就是L1的一個(gè)句子。這個(gè)語言是檢查程序中標(biāo)識(shí)符的聲明應(yīng)先于引用的抽象。 例 L2=anbmcndm|n,m0，它是檢查過程聲明的形參個(gè)數(shù)和過程引用的參數(shù)個(gè)數(shù)是否一致問題的抽象。,高級(jí)語言中的非CFL結(jié)構(gòu),Chomsky體系總結(jié),Chomsky體系總結(jié), = (T，N，)是一個(gè)文法, P * G是0型文法，L(G)是0型語言； -其能力相當(dāng)于圖靈機(jī)(TM) * |:G是1型文法，L(G)是1型語言(除); -其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)(LBA) * N : G是2型文法，L(G)是2型語言; -其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)(PDA) * AaB或Aa: G是右線性文法，L(G)是3型語言 ABa或A: G是左線性文法，L(G)是3型語言 -其識(shí)別系統(tǒng)是有窮自動(dòng)機(jī)(FA),四種文法之間的關(guān)系是將產(chǎn)生式作進(jìn)一步限制而定義的 四種文法之間的逐級(jí)“包含”關(guān)系如下：,Chomsky體系總結(jié),范式Backus-Naur Form Backus-Normal Form,表示為 非終結(jié)符用“”括起來 終結(jié)符：基本符號(hào)集 其他 (1|2|n)1|2|n 1|2|n ul l=0,u=m 1|2|nm | ,范式Backus Normal Form,例 簡(jiǎn)單算術(shù)表達(dá)式(只寫產(chǎn)生式) + * () id 即：+| *|()|id 哪些是終結(jié)符？哪些是變量？,例2-5 句子結(jié)構(gòu)的表示 (文法EE+E|E*E|(E)|id ）,EE+Eid+Eid+E*Eid+id*Eid+id*id,一棵樹！,1. 描述一個(gè)句子的文法不是唯一的； 2. 對(duì)于一個(gè)句子的分析應(yīng)是唯一的。 考慮表達(dá)式下面的文法 GE,其產(chǎn)生式如下： EE+EE*E (E) id,文法的二義性(歧義性/ambiquity),文法的二義性,一個(gè)句子有兩棵不同的語法樹,EE+E a1+E a1+E*E a1+a2*E a1+a2*a3,E E*E E+E*E a1+E*E a1+a2*E a1+a2*a3,E,E,兩個(gè)不同的最左推導(dǎo),對(duì)應(yīng)兩不同的語法樹,E E*E E*a3 E+E*a3 E+a2*a3 a1+a2 *a3,E,E,兩個(gè)不同的最右推導(dǎo),對(duì)應(yīng)兩不同的語法樹,EE+E E+E*E E+E*a3 E+a2*a3 a1+a2*a3,如果一個(gè)文法的句子存在兩棵分析樹,那么,該句子是二義性的 如果一個(gè)文法包含二義性的句子,則稱這個(gè)文法是二義性的; 否則，該文法是無二義性的,文法的二義性,1 . 一般來說,高級(jí)程序設(shè)計(jì)語言存在無二義性文法,但有時(shí)用二義性文法。如：表達(dá)式文法、條件語句文法 S if expr then S if expr then S else S other 二義性的句子: if e1 then if e2 then s1 else s2 EE+E|E-E|E*E|E/E|( E )| id 無二義性文法較復(fù)雜 EE+T|E-T|T TT*F|T/F|F F( E )| id,文法的二義性,文法的二義性,1 . 一般來說,高級(jí)程序設(shè)計(jì)語言存在無二義性文法,但有時(shí)用二義性文法。如：表達(dá)式文法、條件語句文法 S if expr then S if expr then S else S |other 二義性的句子: if e1 then if e2 then s1 else s2,文法的二義性,2. 對(duì)于任意一個(gè)CFG，不存在算法判定它是無二義性的；但能給出一組充分條件，滿足這組充分條件的文法是無二義性的 一個(gè)文法是否為二義性的不可判定,文法的二義性,3. 存在先天二義性語言。例如，語言 aibicji,j1 aibjcji,j1 存在二義性的句子akbkck 一個(gè)語言是否為先天二義性的，在理論上不可判定,文法的二義性,4. 在能駕馭的情況下，使用二義性文法簡(jiǎn)單 EE+E|E-E|E*E|E/E|( E )| id 無二義性文法較復(fù)雜 EE+T|E-T|T TT*F|T/F|F F( E )| id,參考書：(抽象)語法樹不同,2.6 文法的構(gòu)造為了更好地理解文法,目的：給出語言的有窮描述 途徑：刻畫語言的結(jié)構(gòu) 做法： 給出定義的形式化描述 根據(jù)經(jīng)驗(yàn)給出描述,文法舉例,x|x是長(zhǎng)度為偶數(shù)的0、1串 RL S00S|01S|10S|11S| 0 m 1 n |m,n 1 RL S0S|0A A1A|1 0 n 1 n |n 1 CFL S0S1|01,例2-7：w|w為十進(jìn)制數(shù),R N|N.D N 1|2|3|4|5|6|7|8|9 N N0|N1|N2|N3|N4|N5|N6|N7|N8|N9 D 1|2|3|4|5|6|7|8|9 D 0D|1D|2D|3D|4D|5D|6D|7D|8D|9D,R 0|0.D|N.0|0.0,無用產(chǎn)生式與無用符號(hào),E T | E + T | E - T T F | T * F | T / F F ( E ) | id E E | H + T T FH | TQ+PF | EQF M ( E ) | id 單一產(chǎn)生式、派生不出終極符號(hào)行(H、Q、P)、從開始符號(hào)無法派生出來(M),文法構(gòu)造小結(jié),明確描述對(duì)象語言 合法的語言結(jié)構(gòu) 確定基本符號(hào)集