哈工大編譯原理第二章語言概述.ppt

1、高級(jí)語言及其文法,2.1 語言概述 2.2 基本定義 2.3 文法(Grammar)的定義 2.4 CFG的分析樹（Parse Tree） 2.5 文法的分類 2.6 文法的構(gòu)造,本章主要內(nèi)容,2.1 語言概述,什么是語言？,2.1 語言概述,語言特征 自然語言(Natural Language) 是人與人的通訊工具 語義(semantics):環(huán)境、背景知識(shí)、語氣、二義性難以形式化 計(jì)算機(jī)語言(Computer Language) 計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具 嚴(yán)格的語法(Grammar)、語義(semantics) 易于形式化：嚴(yán)格,2.1語言概述,語言的描述方法現(xiàn)狀 自然語言：自然、方便

2、-非形式化 數(shù)學(xué)語言（符號(hào)）：嚴(yán)格、準(zhǔn)確-形式化 形式化描述 高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的計(jì)算機(jī)表示。,2.1 語言概述,語言形式化的內(nèi)容提取 語言(Language)：滿足一定條件的句子集合 句子(Sentence)：滿足一定規(guī)則的單詞序列 單詞(Token)：滿足一定規(guī)則的字符(Character)串 語言是字和組合字的規(guī)則 例（自然語言：第譯始一天課今開編上節(jié)） 今天開始上第一節(jié)編譯課,2.1 語言概述,語言是字及其組合規(guī)則的統(tǒng)一體,2.1 語言概述,程序設(shè)計(jì)語言形式化的內(nèi)容提取 程序設(shè)計(jì)語言(Programming Language)：組成程序的所有語句的集合。 程序(Progr

3、am)：滿足語法規(guī)則的語句序列。 語句(Sentence) ：滿足語法規(guī)則的單詞序列。 單詞(Token) ：滿足詞法規(guī)則的字符串。 例：變量:=表達(dá)式 if 條件 then 語句 while條件 do 語句 call 過程名(參數(shù)表),2.1 語言概述,描述形式文法 語法語句 語句的組成規(guī)則 描述方法：BNF范式、語法(描述)圖 詞法單詞 單詞的組成規(guī)則 描述方法：BNF范式、正規(guī)式,形式語言于自動(dòng)機(jī)理論的產(chǎn)生與作用,語言學(xué)家Chomsky最初從產(chǎn)生語言的角度研究語言。 1956年，通過抽象，他將語言形式地定義為是由一個(gè)字母表中的字母組成的一些串的集合。可以在字母表上按照一定的規(guī)則定義一個(gè)文

4、法（Grammar），該文法所能產(chǎn)生的所有句子組成的集合就是該文法產(chǎn)生的語言。 克林（Kleene）在1951年到1956年間，從識(shí)別語言的角度研究語言，給出了語言的另一種描述。 克林是在研究神經(jīng)細(xì)胞中，建立了自動(dòng)機(jī)，他用這種自動(dòng)機(jī)來識(shí)別語言：對(duì)于按照一定的規(guī)則構(gòu)造的任一個(gè)自動(dòng)機(jī)，該自動(dòng)機(jī)就定義了一個(gè)語言，這個(gè)語言由該自動(dòng)機(jī)所能識(shí)別的所有句子組成。,形式語言于自動(dòng)機(jī)理論的產(chǎn)生與作用,1959年，Chomsky通過深入研究，將他本人的研究成果與克林的研究成果結(jié)合了起來，不僅確定了文法和自動(dòng)機(jī)分別從生成和識(shí)別的角度去表達(dá)語言，而且證明了文法與自動(dòng)機(jī)的等價(jià)性。 20世紀(jì)50年代，人們用巴科斯范式（B

5、ackus Nour Form 或 Backus Normal Form，簡記為BNF）成功地對(duì)高級(jí)語言ALGOL-60進(jìn)行了描述。實(shí)際上，巴科斯范式就是上下文無關(guān)文法（Context Free Grammar）的一種表示形式。這一成功，使得形式語言在20世紀(jì)60年代得到了大力的發(fā)展。,形式語言于自動(dòng)機(jī)理論的產(chǎn)生與作用,形式語言與自動(dòng)機(jī)理論除了在計(jì)算機(jī)科學(xué)領(lǐng)域中的直接應(yīng)用外，更在計(jì)算學(xué)科人才的計(jì)算思維的培養(yǎng)中占有極其重要的地位 計(jì)算思維能力的培養(yǎng)，主要是由基礎(chǔ)理論系列課程實(shí)現(xiàn)的，該系列主要由從數(shù)學(xué)分析開始到形式語言結(jié)束的一些數(shù)學(xué)和抽象程度比較高的內(nèi)容的課程組成。 它們構(gòu)成的是一個(gè)梯級(jí)訓(xùn)練系統(tǒng)。

6、在此系統(tǒng)中，連續(xù)數(shù)學(xué)、離散數(shù)學(xué)、計(jì)算模型等三部分內(nèi)容要按階段分開，三個(gè)階段對(duì)應(yīng)與本學(xué)科的學(xué)生在大學(xué)學(xué)習(xí)期間的思維方式和能力的變化與提高過程的三個(gè)步驟。,計(jì)算思維能力的培養(yǎng)過程,中學(xué)數(shù)學(xué)數(shù)學(xué)分析 離散數(shù)學(xué) 具體.靜止變量.運(yùn)動(dòng)離散.抽象 形式.模型 (基本運(yùn)算系統(tǒng)) (計(jì)算系統(tǒng)) 實(shí) 數(shù) 抽象 集合 單一、具體的計(jì)算 一般、形式化的計(jì)算 （實(shí)例計(jì)算） （模型化計(jì)算）,高水平計(jì)算專業(yè)人才的計(jì)算思維能力的漸進(jìn)培養(yǎng),2.2 基本定義,字母表（Alphabet）是一個(gè)非空有窮集合，字母表中的元素稱為該字母表的一個(gè)字母（Letter），也叫字符（Character）。 例 以下是不同的字母表： a，b，c

7、，d a，b，c，z 0，1 (4) ASCII字母表,2.2 基本定義,符號(hào)串的定義 (1) 是上的一個(gè)符號(hào)串。 (2) 若x是上的符號(hào)串，而a是的元素, 則xa是上的符號(hào)串。 (3) y是上的符號(hào)串,當(dāng)且僅當(dāng)它由(1)和(2)導(dǎo)出。 由字母表中的符號(hào)所組成的任何有窮序列被稱之為該字母表上的符號(hào)串,也稱作字。,2.2 基本定義,設(shè)s是符號(hào)串，則s的 前綴：移走s的尾部的零個(gè)或多于零個(gè)符號(hào) 后綴：刪去s的頭部的零個(gè)或多于零個(gè)符號(hào) 子串: 從s中刪去一個(gè)前綴和一個(gè)后綴 子序列: 從s中刪去零或多于零個(gè)符號(hào)(這些符號(hào)不要求連續(xù)） 逆轉(zhuǎn)（用SR表示）：將S中的符號(hào)按相反次序?qū)懗龆玫降姆?hào)串 長度：

8、是該符號(hào)串中的符號(hào)的數(shù)目。例如|aab|=3,|=0。,2.2 基本定義,符號(hào)串的連接和方冪 1.連接：設(shè)x和y是符號(hào)串，它們的連接xy是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串。例如，x=ba,y=nana,xy=banana. 2.方冪：x0=; x1=x; x2=xx; ； xn=xn-1x; 例如, 設(shè)x=ba, 則 x1= ba, x2=baba, x3=bababa, ,2.2 基本定義,定義1 設(shè)1、2是兩個(gè)字母表，1與2 的乘積(Product)定義為12=ab|a1，b2 例:1=0,1, 2=a,b, 12 =0a,0b,1a,1b 定義2 設(shè)是一個(gè)字母表，的n次冪(Powe

9、r)遞歸地定義為： 0= n=n-1 n1 例： 13 =000,001,010,011,100,101,110,111,2.2 基本定義,定義3 設(shè)是一個(gè)字母表，的正閉包(Positive Closure)定義為： +=234 的克林閉包(Kleene Closure)為： *=0+ =023,2.2 基本定義,例 0,1+ = 0，1，00，01，11，000，001，010，011，100， a，b，c，d+ = a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc,2.2 基本定義,例 0,1* = ，0，1，00，01

10、，11，000，001，010，011，100， a，b，c，d* = ，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc，,2.2 基本定義,定義5 設(shè)是一個(gè)字母表，L *，L稱為字母表上的一個(gè)語言（Language），xL，x叫做L的一個(gè)句子。 例： 字母表0，1上的語言 0，1 00，11 0，1，00，11 0，1，00，11，01，10 00，11* 01，10*,2.3 文法的定義,如何實(shí)現(xiàn)語言結(jié)構(gòu)的形式化描述？,考慮一個(gè)句子文法要素的提取,分析：The grey wolf will eat the goat,句

11、子 主語 謂語 （1） 主語 冠詞 形容詞 名詞 （2） 冠詞the 形容詞 grey 謂語 動(dòng)詞 直接賓語 （5） 動(dòng)詞 助動(dòng)詞 動(dòng)詞原形 （6） 助動(dòng)詞will 動(dòng)詞原形 eat 直接賓語 冠詞 名詞 （9） 名詞wolf 名詞 goat,句子的組成規(guī)則,問題：如何用符號(hào)來描述？即如何形式化？,終結(jié)符號(hào)集VT = the，grey, wolf,will, eat, goat 非終結(jié)符號(hào)集VN = 句子，主語， 謂語，冠詞， 形容詞，名詞 ， 動(dòng)詞 ，直接賓語 ，助動(dòng)詞 ，動(dòng)詞原形 語法規(guī)則集P = 句子 主語 謂語， 開始符號(hào)S = 句子,定義句子的規(guī)則的語法組成 _終結(jié)符號(hào)集，非終結(jié)符號(hào)

12、集，語法規(guī)則，開始符號(hào),問題：有了定義句子的規(guī)則，如何判定某一句子是否屬于某語言？,句子 主語 謂語 冠詞 形容詞 名詞 謂語 the 形容詞 名詞 謂語 the grey名詞 謂語 the grey wolf 謂語 the grey wolf 動(dòng)詞 直接賓語 . the grey wolf will eat the goat,句子的派生（推導(dǎo)）-從產(chǎn)生語言的角度句子的歸約 -從識(shí)別語言的角度,-均根據(jù)規(guī)則,句子 the grey wolf will eat the goat the grey wolf will eat the wolf the grey goat will eat the

13、wolf the grey goat will eat the grey wolf 符合語法且符合語義的句子僅是： the grey wolf will eat the goat,句子的語義要求,文法G 的形式定義,文法G為一個(gè)四元組: = (T，N，) T：終結(jié)符(Terminal)集 N：非終結(jié)符(Variable)集，TN= 語法成分代表某個(gè)語言的各種子結(jié)構(gòu) ：開始符號(hào)(Start Symbol)，SN 代表文法所定義的語言，至少在產(chǎn)生式左側(cè)出現(xiàn)一次,文法G 的形式定義,：產(chǎn)生式(Product)集合 ，被稱為產(chǎn)生式（定義式），讀作：定義為。其中(TN)+，且中至少有N中元素的一個(gè)出現(xiàn)。

14、(TN)*。稱為產(chǎn)生式的左部(Left Part)，稱為產(chǎn)生式的右部(Right Part)。 產(chǎn)生式定義各個(gè)語法成分的結(jié)構(gòu)（組成規(guī)則）,例2-1 算術(shù)表達(dá)式的文法,遞歸定義中綴表示 標(biāo)識(shí)符(id)（常數(shù)、變量）是表達(dá)式(E)； 表達(dá)式加一個(gè)表達(dá)式是表達(dá)式； 表達(dá)式減一個(gè)表達(dá)式是表達(dá)式； 表達(dá)式乘一個(gè)表達(dá)式是表達(dá)式； 表達(dá)式除一個(gè)表達(dá)式是表達(dá)式； 表達(dá)式加上括號(hào)后是表達(dá)式；,例2-1 算術(shù)表達(dá)式的文法,考慮簡單算術(shù)表達(dá)式組成的語言 G =(id，+，*，(，)，E，P，E) P: EE + E EE * E E( E ) Eid 約定：只寫產(chǎn)生式 簡寫 E E + E | E * E | (

15、E ) | id （2.1）,產(chǎn)生式的簡寫,對(duì)一組有相同左部的產(chǎn)生式 1，2，n 可以簡單地記為： 1|2|n 讀作：定義為或者1，或者2，或者n。并且稱它們?yōu)楫a(chǎn)生式。1，2，n稱為候選式(Candidate)。,基于產(chǎn)生式的變換-推導(dǎo)或歸約,E E + E | E * E | ( E ) | id E由第一個(gè)候選式可以變成E+E E+E中的第一個(gè)E由第二個(gè)候選式可以變成E*E，從而E+E變成E*E+E 根據(jù)第4個(gè)候選式，E*E+E中的E都可以變成id: E*E+E 變成id*E+E id*E+E變成id*E+id id*E+id變成id*id+id 也就是說，根據(jù)第4個(gè)候選式， E*E+E經(jīng)

16、3步變換變成id*id+id,直接推導(dǎo)與歸約,根據(jù)產(chǎn)生式對(duì)符號(hào)串進(jìn)行變換的過程 是文法的一個(gè)產(chǎn)生式， 且、（TN）*， 稱直接推導(dǎo)/派生(Derive)出，也稱 直接歸約(Reduce)為。 記為 例： id + Eid + E * E,（多步）推導(dǎo),012 n 記為 0n n (恰用n步) 0+ n （至少一步） 0* n （若干步:零步或多步）,推導(dǎo)/歸約舉例,E E + E （1） 串中含有變量 id + E （4） 串中含有變量 id + E * E （2） 串中含有變量 id + id * E（4） 串中含有變量 id + id * id（4） 串中沒有變量 到此串中已經(jīng)沒有（語法）

17、變量了，不能再推導(dǎo)了,1、EE + E 2、EE * E 3、E( E ) 4、Eid,句型與句子,E 5 id + id * id 句子:如果S * x，且xT* ，則稱x是G產(chǎn)生的一個(gè)句子(Sentence) E E + E E + E * E E 4 id + id * E 句型:如果S*，(TN)*則稱是G產(chǎn)生的一個(gè)句型(Sentential Form),文法G產(chǎn)生的語言,()x* x and xT* 文法 EE+E|E*E|(E)|id可以派生出多少個(gè)句子？ 文法G的作用語言的有窮描述 以有限的規(guī)則描述無限的語言現(xiàn)象 有限： 產(chǎn)生式集合、終結(jié)符集合、非終結(jié)符集合 無限： 可以導(dǎo)出無窮

18、多個(gè)句子（L也可是有窮）,id+id*id的不同推導(dǎo)EE+E|E*E|(E)|id,E E+E id+E id+E*E id+id*E id+id*id,E E+E E+E*E E+E*id E+id*id id+id*id,E E*E E+E*E E+id*E id+id*E id+id*id,不做限制 句型 (sentential Form) （歸約） E * id+id*id,施于最右變量 右句型/規(guī)范句型 (canonical ) (最左/規(guī)范歸約) E + id+id*id,施于最左變量 左句型(left-) （最右歸約） E5 id+id*id,最左推導(dǎo)與最右推導(dǎo),最左推導(dǎo)(Lef

19、t-most Derivation) 每次推導(dǎo)都施加在句型的最左邊的語法變量上。與最右歸約對(duì)應(yīng) 最右推導(dǎo)(Right-most Derivation) 每次推導(dǎo)都施加在句型的最右邊的語法變量上。與最左歸約（規(guī)范規(guī)約）對(duì)應(yīng)的規(guī)范(Canonical)句型,短語(Phrase),什么叫短語？ 如果* and A+，則稱是句型的相對(duì)于變量A的短語 如果* and A，則稱是句型的相對(duì)于變量A的直接短語 最左直接短語叫做句柄(Handle),例：(直接)短語,EE+T T+T F+T (E)+T (E+T)+T,(E+T)+T (T+T)+T (F+T)+T (id+T)+T (a+T*F)+T (a

20、+F*F)+T (a+b*F)+T (a+b*c)+T (a+b*c)+F (a+b*c)+d,EE+T|T TT* F|F F( E )| id,句柄(Handle)：最左直接短語,EE+T|T TT* F|F F( E )| id EE+T T+T F+T (E)+T (E+T)+T (E+T)+T,(T+T)+T (F+T)+T (id+T)+T (a+T*F)+T (a+F*F)+T (a+b*F)+T (a+b*c)+T (a+b*c)+F (a+b*c)+d,例2-2 標(biāo)識(shí)符的文法1,S L|LT T L|N|TL|TN L a|b|c|d letter N 0|1|2|3|4|5

21、 digit 問題：正整數(shù)的文法? 正實(shí)數(shù)的文法？,2. 文法的分類(Chomsky體系),根據(jù)語言結(jié)構(gòu)的復(fù)雜程度（形式語言） 涉及文法的復(fù)雜程度、分析方法的選擇 反映文法描述語言的能力 如果G滿足文法定義的要求，則是型文法（短語結(jié)構(gòu)文法PSG: Phrase Structure Grammar ）。 L(G)為PSL。,上下文有關(guān)文法(CSG),若產(chǎn)生式集合中所有， 除 外，則是型文法 即：上下文有關(guān)文法（CSGContext Sensitive Grammar） L(G)為1型/上下文有關(guān)/敏感語言(CSL),上下文無關(guān)文法(CFG),若 N，(NT)*，則 是型文法 即：上下文無關(guān)文法(

22、CFG: Context Free Grammar) L(G)為2型/上下文無關(guān)語言（CFL） CFG能描述程序設(shè)計(jì)語言的多數(shù)語法成分,例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 N 1T|2T|3T|4T|5T,正規(guī)文法(RG),設(shè)、N，T或?yàn)?右線性(Right Linear)文法：或 左線性(Left Linear)文法：或 都是型文法(正規(guī)文法 Regular Grammar -RG) L(G)

23、為3型/正規(guī)集/正則集/正則語言（RL） 能描述程序設(shè)計(jì)語言的多數(shù)單詞 左、右線性文法不可混用,例 非CFL的文法,L=anbncn|n0的文法 SaBC|aSBC CBBC aBab bBbb bCbc,“可以證明”不存在CFG G ,使L(G)=L,在我們使用的程序設(shè)計(jì)語言中,有些語言結(jié)構(gòu)不能用上下文無關(guān)文法來描述。 例2.9 L1=wcw|wa,b+。例,aabcaab就是L1的一個(gè)句子。這個(gè)語言是檢查程序中標(biāo)識(shí)符的聲明應(yīng)先于引用的抽象。 例2.10 L2=anbmcndm|n,m0，它是檢查過程聲明的形參個(gè)數(shù)和過程引用的參數(shù)個(gè)數(shù)是否一致問題的抽象。,非上下文無關(guān)的語言結(jié)構(gòu),Chomsk

24、y體系總結(jié), = (T，N，)是一個(gè)文法, P *G是0型文法，L(G)是0型語言； -其能力相當(dāng)于圖靈機(jī) *|:G是1型文法，L(G)是1型語言(除); -其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī) *N : G是2型文法，L(G)是2型語言; -其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī) *AaB或Aa: G是右線性文法，L(G)是3型語言 ABa或A: G是左線性文法，L(G)是3型語言 -其識(shí)別系統(tǒng)是有窮自動(dòng)機(jī),文法的類型,四種文法之間的關(guān)系是將產(chǎn)生式作進(jìn)一步限制而定義的。 四種文法之間的逐級(jí)“包含”關(guān)系如下：,范式Backus-Naur FormBackus-Normal Form,表示為 非終結(jié)符用“”括起來

25、 終結(jié)符：基本符號(hào)集 其他 (1|2|n)1|2|n | ,范式Backus Normal Form,例 簡單算術(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,一棵樹！,2.5 CFG的分析樹,Parse Tree 用樹的形式表示句型的生成 樹根： 開始符號(hào) 中間結(jié)點(diǎn)： 非終結(jié)符 葉結(jié)點(diǎn)： 終結(jié)符或者非終結(jié)符 每個(gè)推導(dǎo)對(duì)應(yīng)一個(gè)中間結(jié)點(diǎn)及其兒子一個(gè)二級(jí)子樹-直接短語 又稱為語法分析樹,短語：一棵子樹的所有葉子自左至右排列起

26、來形成一個(gè)相對(duì)于子樹根的短語。 直接短語：僅有父子兩代的一棵子樹，它的 所有葉子自左至右排列起來所形成的符號(hào)串。 句柄：一個(gè)句型的分析樹中最左那棵只有父子兩代的子樹的所有葉子的自左至右排列。 例如，對(duì)表達(dá)式文法GE和句子a1+a2*a3，挑選出推導(dǎo)過程中產(chǎn)生的句型中的短語，直接短語，句柄。,用子樹解釋短語，直接短語，句柄,E,E+T,T+T,F+T, a1+T, a1+T*F, a1+F * F, a1+a2 *F,E+T,T,T+T,F,F+T,a1, a1+T,a1, T*F, a1+T*F,a1, F,F*F, a1+F*F,a1, a2,a1+ a2 *F, a2 *F,a1, a2,

27、 a3, a2 * a3 a1+ a2 *a3,E,E,+,T,T,F,a1,T,*,F,F,a2,a3,a1+a2 *a3,短語,例 短語與分析樹 (文法EE+E|E*E|(E)|id ）,一棵子樹的葉子！,二義性文法與先天二義性語言,對(duì)同一句子存在兩棵語法分析樹 在理論上不可判定,1. 描述一個(gè)句子的文法不是唯一的； 2. 對(duì)于一個(gè)句子的分析應(yīng)是唯一的。 考慮表達(dá)式下面的文法 GE,其產(chǎn)生式如下： EE+EE*E (E) a 對(duì)于句子a+a*a, 有如下兩個(gè)最左推導(dǎo)： EE+E a+E a+E*E a+a*E a+a*a E E*E E+E*E a+E*E a+a*E a+a*a,文法的二

28、義性,EE+E a+E a+E*E a+a*E a+a*a,E E*EE+E*E a+E*Ea+a*E a+a*a,E,E,+,E,E,*,E,a,a,a,E,E,*,E,+,E,E,a,a,a,最左推導(dǎo),EE+E E+E*E E+E*a E+a*a a+a*a,E E*EE*a E+E*aE+a*a a+a*a,E,E,+,E,E,*,E,a,a,a,E,E,*,E,+,E,E,a,a,a,最右推導(dǎo),如果一個(gè)文法的句子存在兩棵分析樹,那么,該句子是二義性的。如果一個(gè)文法包含二義性的句子,則稱這個(gè)文法是二義性的; 否則，該文法是無二義性的。幾點(diǎn)說明： 1 . 一般來說，程序語言存在無二義性文法

29、， 對(duì)于表達(dá)式來說，文法（2 .1）是二義性的。對(duì)于條件語句，經(jīng)常使用二義性文法描述它： S if expr then S if expr then S else S other 二義性的句子: if e1 then if e2 then s1 else s2,二義性（歧義性，ambiquity)的定義,下面是 Smatched_s unmatched_s matched_s if expr then matched_s else matched_s other unmatched_s if expr then S if expr then matched_s else unmatched_s 它顯然比較復(fù)雜，因此： 2. 在能駕馭的情況下，使用二義性文法。,描述if語句的無二義性文法的產(chǎn)生式,3. 對(duì)于任意一個(gè)上下文無關(guān)文法，不存在一個(gè)算法，判定它是無二義性的；但能給出一組充分條件，滿足這組充分