編譯原理課件

1、a1a2 第一講 引論u課程信息u編譯程序概述u高級(jí)語(yǔ)言的語(yǔ)法描述a31.課程信息一、課程名稱：編譯原理v基本內(nèi)容是介紹編譯程序構(gòu)造的基本原理、方法和技術(shù)，包括詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生、代碼優(yōu)化及目標(biāo)代碼產(chǎn)生等。簡(jiǎn)言之，就是介紹如何將源程序翻譯成目標(biāo)代碼程序。a4二、課程性質(zhì)：專業(yè)基礎(chǔ)課，必修v編譯程序（器）出現(xiàn)于上世紀(jì)50年代后期（第一個(gè)高級(jí)語(yǔ)言1958年）v60年代70年代是研究高峰期v60年代中期開(kāi)始在高校中開(kāi)設(shè)課程v80年代開(kāi)始作為計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的必修基礎(chǔ)課程a5a6三、課程特點(diǎn)三、課程特點(diǎn)：v充分體現(xiàn)了計(jì)算學(xué)科中抽象、理論和設(shè)計(jì)三個(gè)學(xué)科形態(tài)v該課程涉及多門(mén)課程

2、的內(nèi)容綜合運(yùn)用，程序設(shè)計(jì)語(yǔ)言、計(jì)算機(jī)體系結(jié)構(gòu)、語(yǔ)言理論及算法等數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)v該課程涉及的原理、方法和技術(shù)具有十分普遍的意義每一個(gè)計(jì)算機(jī)科學(xué)與技術(shù)工作者的職業(yè)生涯中反復(fù)用到，“享用一輩子”這兒接受的訓(xùn)練很難在其他地方獲得，如：抽象與形式化方法、局部與全局優(yōu)化方法、構(gòu)造技術(shù)、證明方法等a7四、學(xué)習(xí)該課程的意義v編譯程序是計(jì)算機(jī)系統(tǒng)不可缺少的重要組成部分對(duì)程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)與實(shí)現(xiàn)能有更深刻的理解對(duì)程序設(shè)計(jì)語(yǔ)言有關(guān)理論有所了解從宏觀上把握程序設(shè)計(jì)語(yǔ)言掌握了編譯原理后，就不能再說(shuō)：“某語(yǔ)言未學(xué)過(guò)，所以不會(huì)”有助于快速理解、定位和解決程序調(diào)試與運(yùn)行中出現(xiàn)的問(wèn)題a8v編譯方法與技術(shù)有著廣泛應(yīng)用安全技術(shù)

3、、程序理解、軟件逆向工程、應(yīng)用軟件與軟件工具開(kāi)發(fā)、軟件測(cè)試與驗(yàn)證等v編譯課程蘊(yùn)含著計(jì)算學(xué)科中解決問(wèn)題的思路、抽象和方法，這些與高等數(shù)學(xué)一樣，使你“享用一輩子”v課程所涉及的內(nèi)容至今非?；钴S自然語(yǔ)言的翻譯軟件移植網(wǎng)絡(luò)安全形式化方法形式語(yǔ)義學(xué)等a9 鑒于以上所述，作為計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的學(xué)生必須學(xué)習(xí)和掌握編譯原理這門(mén)課程，當(dāng)然由于其綜合性、處理問(wèn)題的復(fù)雜性等，學(xué)習(xí)起來(lái)有一定難度，這就需要艱苦奮斗的精神和良好的學(xué)習(xí)方法a10五、學(xué)習(xí)方法v編譯程序的構(gòu)造是一個(gè)龐大而復(fù)雜的系統(tǒng)工程，無(wú)論是概念還是理論、方法，對(duì)初學(xué)者來(lái)說(shuō)許多都是新的，學(xué)習(xí)起來(lái)會(huì)感到困難大一些，這一點(diǎn)必須有充分認(rèn)識(shí)，為此建議學(xué)習(xí)方法上注

4、意以下幾點(diǎn)：a11課前預(yù)習(xí)，課堂認(rèn)真聽(tīng)講，課后復(fù)習(xí)加深理解，特別要經(jīng)常有意識(shí)地將前后內(nèi)容聯(lián)系起來(lái)融會(huì)貫通。因?yàn)榫幾g程序是一個(gè)龐大的程序系統(tǒng)，講解過(guò)程必須“分而治之”（這也是人們處理復(fù)雜問(wèn)題的基本方法），這就要求大家在學(xué)習(xí)過(guò)程中，始終以處理過(guò)程為主線，把前后聯(lián)系起來(lái)考慮。a12理論聯(lián)系實(shí)際親自動(dòng)手，構(gòu)造一個(gè)演示性編譯程序，至少要完成掃描器和語(yǔ)法分析器，以及語(yǔ)法制導(dǎo)翻譯產(chǎn)生中間代碼（課程設(shè)計(jì)）認(rèn)真完成作業(yè)，進(jìn)一步鞏固并加深理解所學(xué)知識(shí)特別要下功夫認(rèn)真學(xué)習(xí)如何從實(shí)際問(wèn)題進(jìn)行抽象并形式化，最終建立實(shí)際問(wèn)題的模型（上升為理性認(rèn)識(shí)），并借助模型進(jìn)一步設(shè)計(jì)實(shí)現(xiàn)，這將對(duì)你能力的提高大有益處a13六、教材程序設(shè)

5、計(jì)語(yǔ)言編譯原理（第3版）國(guó)防工業(yè)出版社 陳火旺等內(nèi)容詳實(shí)豐富，理論與技術(shù)相結(jié)合較為全面介紹了編譯程序構(gòu)造的基本原理、方法與技術(shù)厚度適中大多數(shù)院校一直采用，碩士入學(xué)考試參考書(shū)1.所謂教材，實(shí)為第一參考書(shū)而已a(bǔ)14 七、參考書(shū)目1.編譯原理第2版 趙建華等譯， A.V.Aho, M.S.Lam,Ravi Sethi, J.D.Ullman著，機(jī)械工業(yè)出版社，2009；2.編譯原理課程設(shè)計(jì) 王雷等著，機(jī)械工業(yè)出版社，2005；八、期末總評(píng)平時(shí)成績(jī)：10%課程設(shè)計(jì)：20%期終考試：70%a15a162.編譯程序概述一、翻譯程序（Translator）能夠把一種語(yǔ)言程序（稱為源語(yǔ)言程序）轉(zhuǎn)換成另一種語(yǔ)言

6、程序（稱為目標(biāo)語(yǔ)言程序）的程序a17v任何非機(jī)器語(yǔ)言程序都需要翻譯程序v翻譯程序的工作就是進(jìn)行等價(jià)變換（映射）v兩個(gè)程序邏輯上等價(jià)是指對(duì)相同輸入得到相同的輸出翻譯程序解釋程序匯編程序編譯程序a18匯編程序(Assembler)把匯編語(yǔ)言程序轉(zhuǎn)變?yōu)闄C(jī)器語(yǔ)言程序的翻譯程序解釋程序(Interpreter)把源程序作為輸入接收，邊解釋邊執(zhí)行的翻譯程序源程序數(shù)據(jù)解釋程序結(jié)果a19編譯程序?qū)⒏呒?jí)語(yǔ)言程序轉(zhuǎn)變?yōu)榈图?jí)語(yǔ)言程序的翻譯程序源 程 序編譯程 序目 標(biāo)程 序a20a21v編譯程序又可根據(jù)用途和側(cè)重點(diǎn)的不同，進(jìn)一步分類為： 診斷編譯程序(Diagnostic Compiler) 專門(mén)用于幫助程序開(kāi)發(fā)和

7、調(diào)試的編譯程序 優(yōu)化編譯程序(Optimizing Compiler) 著重于提高目標(biāo)代碼效率的編譯程序 交叉編譯程序(Cross Compiler) 能夠產(chǎn)生不同于其宿主機(jī)機(jī)器代碼的編譯程序 可變目標(biāo)編譯程序(Retargetable complier) 無(wú)須重寫(xiě)與機(jī)器無(wú)關(guān)部分就能改變目標(biāo)機(jī)的 編譯程序a22二、與編譯程序相關(guān)的程序 本講義只介紹編譯程序（器）構(gòu)造的基本原理、方法與技術(shù)，但在一個(gè)完整的語(yǔ)言開(kāi)發(fā)（或稱程序設(shè)計(jì)）環(huán)境中，除了編譯器這一主要工具外，還需要其他一些工具，如編輯器、連接器、裝入程序等?，F(xiàn)代計(jì)算機(jī)系統(tǒng)常將這些相互獨(dú)立的程序設(shè)計(jì)工具集成起來(lái)，構(gòu)成一個(gè)集成化的程序開(kāi)發(fā)環(huán)境，以

8、提高程序設(shè)計(jì)效率和程序的質(zhì)量。如Turbo C、Visual C+等語(yǔ)言環(huán)境都是集成化的程序設(shè)計(jì)環(huán)境。而Ada語(yǔ)言的集成環(huán)境是這方面的典型代表。a23如Ada語(yǔ)言的集成環(huán)境是一個(gè)分層的程序開(kāi)發(fā)環(huán)境編譯程序MAPSE編輯程序連接程序宿主機(jī)OSAPSE工具界面用戶界面KAPSE調(diào)試程序配置管理程序命令解釋程序其他工具a24 這兒要強(qiáng)調(diào)的是：盡管本課程只介紹編譯的基本理論、方法和技術(shù)，但這些基本理論、方法與技術(shù)對(duì)其他工具的構(gòu)造同樣起作用！a25編輯器(Editor)完成源程序輸入、編輯并產(chǎn)生標(biāo)準(zhǔn)文件（如ASCII文件）的程序。v近來(lái)已與編譯器和其他程序捆綁進(jìn)一個(gè)交互開(kāi)發(fā)環(huán)境IDE中v盡管這樣的編輯器

9、仍生成標(biāo)準(zhǔn)文件，但會(huì)轉(zhuǎn)向正被討論的程序設(shè)計(jì)語(yǔ)言的格式或結(jié)構(gòu)（稱為基于結(jié)構(gòu)的），且已包含了編譯器的某些操作；因此在程序編寫(xiě)時(shí)而不是編譯時(shí)就可得知錯(cuò)誤，甚至也可調(diào)用編譯器a26預(yù)處理程序(Preprocessor)在真正翻譯開(kāi)始之前產(chǎn)生編譯程序的輸入的程序v處理宏及注釋：宏是被經(jīng)常使用的較長(zhǎng)結(jié)構(gòu)的縮寫(xiě)v處理文件包含：把頭文件包含到程序正文中（如C的文件包含include ）v“理解”預(yù)處理器：把現(xiàn)代控制流和數(shù)據(jù)結(jié)構(gòu)機(jī)制添加到比較老式的語(yǔ)言中v語(yǔ)言擴(kuò)充：通過(guò)大量的內(nèi)部宏定義來(lái)增強(qiáng)語(yǔ)言的能力，如Equel語(yǔ)言是一種嵌套在C語(yǔ)言中的數(shù)據(jù)庫(kù)查詢語(yǔ)言a27連接程序(Linker)又稱為連接編輯器。將分別在不

10、同的目標(biāo)文件中編譯（或匯編）的代碼、所用標(biāo)準(zhǔn)庫(kù)函數(shù)的代碼以及操作系統(tǒng)提供的資源（如存儲(chǔ)分配程序及輸入/輸出設(shè)備）收集到一個(gè)可直接執(zhí)行的文件中的程序裝配程序(Loader) 完成程序的裝入和連接編輯兩項(xiàng)功能。 裝入過(guò)程包括讀入可重定位機(jī)器代碼、修改可重定位地址、并將修改后的指令和數(shù)據(jù)放到內(nèi)存的適當(dāng)位置。 裝入程序使得可執(zhí)行代碼更加靈活a28調(diào)試程序(Debugger) 可在被編譯了的程序中判定執(zhí)行錯(cuò)誤的程序v它經(jīng)常與編譯程序一起放在IDE中v運(yùn)行一個(gè)帶有調(diào)試程序的程序與直接執(zhí)行不同，這是因?yàn)檎{(diào)試程序保存著所有的或大多數(shù)源代碼信息，它可以在預(yù)先指定的位置（斷點(diǎn)BreakPoint）暫停執(zhí)行，并提供

11、有關(guān)信息（已調(diào)用的函數(shù)、變量名的當(dāng)前值等）a29其他有關(guān)的還有v描述器(Profiler)執(zhí)行中搜集目標(biāo)程序行為統(tǒng)計(jì)的程序v項(xiàng)目管理程序(Project Manager)如Unix系統(tǒng)中的SCCS（源代碼控制系統(tǒng)）和RCS（修正控制系統(tǒng)）和匯編程序等綜上所述可給出一個(gè)“語(yǔ)言處理系統(tǒng)”的圖示：a30我們這個(gè)課只介紹編譯程序這一部分a31三、編譯過(guò)程與編譯程序結(jié)構(gòu)三、編譯過(guò)程與編譯程序結(jié)構(gòu) 1.編譯過(guò)程： 輸入 輸出（高級(jí)語(yǔ)言源程序） （低級(jí)語(yǔ)言目標(biāo)程序） 編譯程序工作過(guò)程如下：l識(shí)別出一個(gè)個(gè)的單詞l分析句子的語(yǔ)法結(jié)構(gòu)l分析句子的語(yǔ)義并進(jìn)行初步翻譯l對(duì)初步翻譯進(jìn)行優(yōu)化l整理出目標(biāo)程序?qū)σ陨线^(guò)程進(jìn)一

12、步整理可得如下編譯程序結(jié)構(gòu)總框：編譯程序a322.編譯程序總框：詞法分析器語(yǔ)法分析器語(yǔ)義分析與中間代碼產(chǎn)生器優(yōu)化器目標(biāo)代碼生成器單詞符號(hào)語(yǔ)法單位中間代碼中間代碼出錯(cuò)處理表格管理源程序源程序目標(biāo)代碼目標(biāo)代碼a333.五個(gè)階段簡(jiǎn)介l第一階段：詞法分析依據(jù)語(yǔ)言構(gòu)詞規(guī)則，識(shí)別出一個(gè)個(gè)單詞（符號(hào)）單詞種類l保留字：for if whilel算符： l界符： ， ；（） l標(biāo)識(shí)符：a1 a2 pil常數(shù)：9 1024 4.8 6E6無(wú)窮性有窮性思考：識(shí)別有窮集合 VS 識(shí)別無(wú)窮集合 a34 詞法分析工作由詞法分析器（或稱掃描器）完成。 掃描器輸出為等長(zhǎng)度的單詞符號(hào)（二元式）流。 例：Position =

13、initial+rate*60詞法分析（掃描器）保留字表(06,Position) (11,) (06,initial) (12,) (06,rate) (13, ) (07,60的二進(jìn)制)a35l第二階段：語(yǔ)法分析依據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把掃描器提供的單詞符號(hào)串分解成各種語(yǔ)法單位（范疇），如“ 短 語(yǔ) ” 、 “ 子句”、“句子”乃至“程序”。同時(shí)進(jìn)行語(yǔ)法檢查，以確定輸入串是否正確，該工作是由語(yǔ)法分析器完成的。如：Position=initial+rate*60 是一個(gè)“賦值表達(dá)式”（C語(yǔ)言中）Position =表達(dá)式表達(dá)式表達(dá)式+表達(dá)式標(biāo)識(shí)符表達(dá)式*表達(dá)式initial標(biāo)識(shí)符常數(shù)rate60

14、標(biāo)識(shí)符a36l第三階段：語(yǔ)義分析與中間代碼產(chǎn)生針對(duì)各類不同的語(yǔ)法范疇，按語(yǔ)言的語(yǔ)義規(guī)則進(jìn)行語(yǔ)義分析和初步翻譯工作，產(chǎn)生某種中間語(yǔ)言形式的中間代碼（即一種結(jié)構(gòu)簡(jiǎn)單，含義明確的記號(hào)系統(tǒng)）。該階段工作通常包括兩個(gè)方面的工作：對(duì)每種語(yǔ)法范疇進(jìn)行靜態(tài)語(yǔ)義檢查，包括：l變量是否定義過(guò)l類型是否正確l是否用了0作除數(shù) a37l將語(yǔ)法范疇翻譯成某種形式的中間代碼，如四元式：a38l第四階段：優(yōu)化對(duì)前階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出高效（節(jié)省時(shí)、空）的目標(biāo)代碼，這一任務(wù)是由優(yōu)化器來(lái)完成的l根 據(jù) 優(yōu) 化 的 范 圍 不 同 ， 可 分 為 ：局部?jī)?yōu)化，循環(huán)優(yōu)化和全局優(yōu)化l一個(gè)循環(huán)優(yōu)化的例子

15、：a39 循環(huán)循環(huán) For(k=1;k=100;k+) M=I+10For(k=1;k=100;k+) M=I+10* *k; N=J+10k; N=J+10* *k;k;優(yōu)化前用了兩個(gè)臨時(shí)工作單元(T1,T2), 優(yōu)化后沒(méi)有用臨時(shí)單元優(yōu)化前循環(huán)體中要做300次加、200次乘， 優(yōu)化后循環(huán)體內(nèi)只做300次加a40l第五階段：目標(biāo)代碼生成把中間代碼翻譯成目標(biāo)代碼l顯然這階段要依賴于硬體系統(tǒng)結(jié)構(gòu)和指令系統(tǒng)l涉及存貯分配、寄存器調(diào)度這一階段工作是由代碼生成器完成的說(shuō)明： 以上各階段（或稱工序）并不是截然分開(kāi) 的，尤其編譯程序結(jié)構(gòu)十分復(fù)雜、體積相當(dāng)龐大，所以有時(shí)人們把幾個(gè)階段的工作有機(jī)地組合在一起、穿

16、插進(jìn)行，構(gòu)成遍。a41v遍（Pass）：對(duì)源程序或源程序的中間代碼從頭到尾掃描一次并做相應(yīng)處理加工分遍的好處是結(jié)構(gòu)清晰、節(jié)省內(nèi)存（每遍都從外存獲取前一遍的結(jié)果作為開(kāi)始，工作結(jié)果仍記入外存，每遍幾乎可使用全部?jī)?nèi)存）分不分遍、如何分遍要視具體情況計(jì)算機(jī)內(nèi)存容量、源語(yǔ)言的繁簡(jiǎn)、從事編譯程序設(shè)計(jì)人員的情況等a42如某PL/0編譯程序的結(jié)構(gòu)詞法分析程詞法分析程序序語(yǔ)法語(yǔ)義分析程序語(yǔ)法語(yǔ)義分析程序代碼生成程序代碼生成程序PL/0PL/0源程序源程序目標(biāo)程序目標(biāo)程序表格管理程序出錯(cuò)處理程序a43 4.前端與后端：概念上講，編譯程序的五個(gè)階段可進(jìn)一步劃分為前端和后端：前端：主要由與源語(yǔ)言有關(guān)而與目標(biāo)機(jī)無(wú)關(guān)的部

17、分組成，包括詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼產(chǎn)生。代碼優(yōu)化一般也包含在前端。后端：主要由與目標(biāo)機(jī)有關(guān)的部分組成，包括目標(biāo)代碼生成和與目標(biāo)機(jī)有關(guān)的優(yōu)化等。a44源程序詞法分析語(yǔ)法分析語(yǔ)義分析和中間代碼產(chǎn)生中間語(yǔ)言中間代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼優(yōu)化目標(biāo)語(yǔ)言前端前端后端后端a45l 劃分前端和后端，就可以僅改寫(xiě)后端而生成不同目標(biāo)機(jī)上的目標(biāo)程序，當(dāng)然也可考慮對(duì)不同語(yǔ)言僅稍加改變前端而產(chǎn)生相同的中間代碼，經(jīng)同一后端生成相同目標(biāo)機(jī)的目標(biāo)代碼。就目前來(lái)說(shuō)，針對(duì)相同中間代碼適應(yīng)不同目標(biāo)機(jī)的工作較多，如Ada語(yǔ)言的APSE(Ada程序設(shè)計(jì)環(huán)境)中使用的Diana中間代碼，Java語(yǔ)言定義的虛擬機(jī)代碼By

18、tecode中間語(yǔ)言，都是定義良好的中間語(yǔ)言。a46Java的傳統(tǒng)環(huán)境Java源程序(.java)編譯環(huán)境編譯環(huán)境Java編譯器Java字節(jié)碼(.class)Java 字節(jié)碼（本地或網(wǎng)絡(luò)傳輸）運(yùn)行環(huán)境運(yùn)行環(huán)境類加載程序字節(jié)碼驗(yàn)證Java類庫(kù)Java解釋器即時(shí)編譯器Java虛擬機(jī)硬件a475.表格與表格管理表格記錄源程序中的各類有用信息名字、函數(shù)、標(biāo)號(hào)、過(guò)程、數(shù)值等每個(gè)階段的工作都要與表格打交道：查、填、改等表格的結(jié)構(gòu)與處理方法：統(tǒng)一的大表與分類的小表統(tǒng)一大表名字欄為主欄（關(guān)鍵字欄），信息欄又分成若干子欄種屬、類型等a48分類小表：每類一張表，如：符號(hào)名表(SNT)常數(shù)表(CT)a49入口表(E

19、NT)標(biāo)號(hào)表(LBT)基本字表 (KWT)a506.出錯(cuò)處理： 這是編譯程序的又一重要組成部分，因?yàn)榫幾g的各個(gè)階段都有可能發(fā)現(xiàn)源程序中的錯(cuò)誤。一旦發(fā)現(xiàn)這樣或那樣的錯(cuò)誤，就應(yīng)把錯(cuò)誤的性質(zhì)及位置報(bào)告給用戶，并且使編譯能繼續(xù)下去。思考：l如何準(zhǔn)確地報(bào)告錯(cuò)誤l如何從錯(cuò)誤中恢復(fù)過(guò)來(lái)a51四、編譯程序的構(gòu)造過(guò)程1.需求分析，確定語(yǔ)言文本(1)確定語(yǔ)言的種類： 按語(yǔ)言范型分類，當(dāng)今大多數(shù)程序語(yǔ)言可分為四類：v過(guò)程式(強(qiáng)制式語(yǔ)言)：命令驅(qū)動(dòng)，面向語(yǔ)句，如FORTRAN、PASCAL、Ada及C等v函數(shù)式(應(yīng)用式)語(yǔ)言：功能驅(qū)動(dòng)，面向函數(shù)，如LISP、SNOBOL及ML等v邏輯式(基于規(guī)則的)語(yǔ)言：依據(jù)條件進(jìn)行

20、邏輯推演，如Prolog等vOO語(yǔ)言：支持封裝性、繼承性、多態(tài)性及動(dòng)態(tài)聚束等，以對(duì)象為運(yùn)行單位，如Smalltalk、Java、C+等a52通過(guò)用戶提供的應(yīng)用范圍，決定采用何種語(yǔ)言。 例如： 偏重于科學(xué)計(jì)算的則選用Fortran； 偏重于符號(hào)處理的則選用Lisp或Snobol； 偏重于事務(wù)處理的則選用Cobol或數(shù)據(jù)庫(kù)管理語(yǔ)言； a53(2)深刻理解語(yǔ)言的結(jié)構(gòu)、語(yǔ)法及語(yǔ)義 這就是說(shuō)不僅僅是用程序設(shè)計(jì)語(yǔ)言編幾個(gè)程序的問(wèn)題，而是要在語(yǔ)法和語(yǔ)義方面下一些功夫。具體說(shuō)來(lái)有以下幾個(gè)方面：程序語(yǔ)言的定義： 任何程序語(yǔ)言都是某個(gè)確定的字符集上的符號(hào)按照一定規(guī)則組成的有窮序列。 這里所謂的規(guī)則是從兩個(gè)方面來(lái)談

21、的： 語(yǔ)法規(guī)則：用于形成和產(chǎn)生一個(gè)正確的程序的 一組規(guī)則。 語(yǔ)義規(guī)則：用于定義程序意義的一組規(guī)則。 a54例如： 從語(yǔ)法的角度看，標(biāo)識(shí)符和名字是一個(gè)東西，都是以字母開(kāi)頭的字母數(shù)字串；但從語(yǔ)義的角度看，標(biāo)識(shí)符是一個(gè)沒(méi)有任何意義的字符序列，而名字卻有確定的意義和屬性，而且具有一定的作用域和定義域，即有局部和全部之分。又如： 程序從語(yǔ)法角度看，是一些語(yǔ)法范疇構(gòu)成的如下層次結(jié)構(gòu)：a55程序分程序或子程序（過(guò)程、函數(shù)等）語(yǔ)句表達(dá)式數(shù)據(jù)引用算符函數(shù)調(diào)用而從語(yǔ)義的角度來(lái)說(shuō)，程序是描述一定的數(shù)據(jù)結(jié)構(gòu)及其處理過(guò)程。a56程序結(jié)構(gòu)： 現(xiàn)代高級(jí)語(yǔ)言程序通常由若干子程序段（過(guò)程、函數(shù)等）構(gòu)成，許多語(yǔ)言還引入了類、程序

22、包等更高級(jí)的結(jié)構(gòu)。 例如，F(xiàn)ortran 、C程序是塊結(jié)構(gòu)的；Pascal程序是過(guò)程嵌套的；Algol既有分程序嵌套，又有過(guò)程嵌套；Java與C+是面向?qū)ο蟮?，它們很重要的方面是類和繼承的概念，同時(shí)支持多態(tài)性和動(dòng)態(tài)聚束等特性；而在Ada中引入了程序包，它可以把數(shù)據(jù)和操作代碼封裝在一起，支持?jǐn)?shù)據(jù)抽象。 （詳見(jiàn)教材 P15-18）a57語(yǔ)言的基本成分： 包括數(shù)據(jù)類型、表達(dá)式、語(yǔ)句、過(guò)程或函數(shù)等，這些在學(xué)習(xí)語(yǔ)言課時(shí)都已經(jīng)學(xué)過(guò)了，但從編譯的角度出發(fā)，應(yīng)如何了解這些基本成分呢？ 初等數(shù)據(jù)類型：牽扯到存儲(chǔ)空間的問(wèn)題； 結(jié)構(gòu)數(shù)據(jù)類型：牽扯到下標(biāo)、維數(shù)、存放方式、 分配時(shí)間-動(dòng)態(tài)與靜態(tài)等； 表達(dá)式：牽扯到運(yùn)算

23、分量、運(yùn)算符、形成規(guī)則、 運(yùn)算順序等； 語(yǔ)句：順序、控制、循環(huán)等； 過(guò)程與參數(shù)傳遞：傳地址、傳值、傳名、得結(jié)果 等； 存儲(chǔ)管理：靜態(tài)存儲(chǔ)分配、動(dòng)態(tài)存儲(chǔ)分配；a582.由程序設(shè)計(jì)環(huán)境確定編譯程序構(gòu)造的方式和方法最早是直接使用機(jī)器語(yǔ)言或匯編語(yǔ)言現(xiàn)在一般使用高級(jí)語(yǔ)言Pascal或C語(yǔ)言好處：編譯方式還是解釋方式便于閱讀、理解和移植提高程序設(shè)計(jì)效率易于查錯(cuò)和修改a59 任何一個(gè)編譯程序至少要涉及三種語(yǔ)言：源語(yǔ)言（S）、目標(biāo)語(yǔ)言（T）和編譯程序?qū)崿F(xiàn)語(yǔ)言（I），可用如下T型圖來(lái)表示三者之間的關(guān)系：a60 如若A機(jī)上已經(jīng)有了一個(gè)用A機(jī)器語(yǔ)言（稱A代碼）實(shí)現(xiàn)的C語(yǔ)言編譯程序，則可用C語(yǔ)言作為工具編寫(xiě)Ada語(yǔ)言

24、的編譯程序。這樣Ada語(yǔ)言的編譯程序經(jīng)過(guò)C語(yǔ)言編譯程序編譯后就可得到A代碼的Ada語(yǔ)言編譯程序?？蓤D示如下：a61l現(xiàn)在常用構(gòu)造編譯程序的方式除高級(jí)語(yǔ)言實(shí)現(xiàn)外，經(jīng)常還用：v自展（自編譯）：類似于滾雪球。先確定一個(gè)非常簡(jiǎn)單的核心L0，用低級(jí)語(yǔ)言寫(xiě)出其編譯程序C0。再把L0擴(kuò)充為L(zhǎng)1 ， ，并用L0來(lái)編寫(xiě)L1的編譯程序。如此逐漸擴(kuò)展下去，可得到一個(gè)系統(tǒng)編程語(yǔ)言族：而Lk便是我們要編譯的語(yǔ)言，其編譯程序Ck可用Lk-1編寫(xiě)。這種滾雪球式的自展方法可大大減少開(kāi)發(fā)工作量。kLLLL21010LL a62交叉編譯：在機(jī)器A上產(chǎn)生機(jī)器B的目標(biāo)代碼 ，這種編譯程序稱為交叉編譯。這兒A稱宿主機(jī)，B稱為目標(biāo)機(jī)。這

25、種情況一般是宿主機(jī)上有豐富的工具軟件，而B(niǎo)機(jī)上沒(méi)有任何高級(jí)語(yǔ)言可用。圖示為：a63移植：如果一個(gè)程序能比較容易地從一臺(tái)機(jī)器上搬到另一臺(tái)機(jī)器上運(yùn)行，則稱其為可移植的，移植一個(gè)程序的工作量要遠(yuǎn)小于開(kāi)發(fā)它的工作量才有意義。 顯然一個(gè)編譯程序要可移植，則其前端與后端的界面要清晰、簡(jiǎn)單，這樣僅需改寫(xiě)后端即可。改寫(xiě)后亦可通過(guò)交叉編譯的方法得到。a64編譯程序生成器：根據(jù)語(yǔ)言要求、設(shè)計(jì)實(shí)現(xiàn)的算法，能自動(dòng)產(chǎn)生編譯程序的工具軟件?？蓤D示為：a653.確定編譯方法：本課程要介紹若干方法，但不可能全采用，只能根據(jù)語(yǔ)言特點(diǎn)采用其中一種或二種4.總體設(shè)計(jì)：分不分遍、分幾遍、前端與后端接口并畫(huà)出總框5.詳細(xì)設(shè)計(jì)：進(jìn)一步細(xì)

26、劃總框6.實(shí)現(xiàn)及調(diào)試：采用何種方式實(shí)現(xiàn)、分調(diào)與連調(diào)等a66本節(jié)目的：本節(jié)目的：為語(yǔ)言的語(yǔ)法描述尋求形式化工具為語(yǔ)言的語(yǔ)法描述尋求形式化工具 工具就是對(duì)程序設(shè)計(jì)語(yǔ)言給出精確無(wú)二工具就是對(duì)程序設(shè)計(jì)語(yǔ)言給出精確無(wú)二義的語(yǔ)法描述。（嚴(yán)謹(jǐn)、簡(jiǎn)潔、易讀）義的語(yǔ)法描述。（嚴(yán)謹(jǐn)、簡(jiǎn)潔、易讀） 形式化工具就是將形式語(yǔ)言抽象地定義形式化工具就是將形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)。為一個(gè)數(shù)學(xué)系統(tǒng)?！靶问叫问健笔侵高@樣的事是指這樣的事實(shí)：語(yǔ)言的所有規(guī)則是以什麼符號(hào)串能出實(shí)：語(yǔ)言的所有規(guī)則是以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳述?，F(xiàn)的方式來(lái)陳述。 3.高級(jí)語(yǔ)言的語(yǔ)法描述a67本節(jié)主要內(nèi)容本節(jié)主要內(nèi)容預(yù)備知識(shí)上下文無(wú)關(guān)上下文無(wú)關(guān)

27、文法及其語(yǔ)言的形式定義文法及其語(yǔ)言的形式定義文法的等價(jià)性文法的等價(jià)性語(yǔ)法樹(shù)及文法二義性語(yǔ)法樹(shù)及文法二義性文法的類型文法的類型語(yǔ)法分析的一些思考語(yǔ)法分析的一些思考a68一、預(yù)備知識(shí)一、預(yù)備知識(shí)1.文法的直觀概念文法的直觀概念 當(dāng)我們表述一種語(yǔ)言時(shí)，無(wú)非是說(shuō)明這種語(yǔ)言的句子，如果語(yǔ)言只含有有窮多個(gè)句子，則只需列出句子的有窮集就行了，但對(duì)于含有無(wú)窮多個(gè)句子的語(yǔ)言來(lái)講，存在著如何給出它有窮表示的問(wèn)題。 以自然語(yǔ)言為例，人們無(wú)法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來(lái)說(shuō)明(或者定義)句子的組成結(jié)構(gòu)，比如漢語(yǔ)句子可以是由主語(yǔ)后隨謂語(yǔ)而成，構(gòu)成謂語(yǔ)的是動(dòng)詞和直接賓語(yǔ)。 例如： a69 “我是大學(xué)

28、生我是大學(xué)生”是漢語(yǔ)的一個(gè)句子是漢語(yǔ)的一個(gè)句子對(duì)該句子我們可以通過(guò)下列一組規(guī)則描述： 句子 =主語(yǔ)謂語(yǔ) 主語(yǔ) =代詞名詞 代詞 = 我你他 名詞 = 王明大學(xué)生工人英語(yǔ) 謂語(yǔ) =動(dòng)詞直接賓語(yǔ) 動(dòng)詞 = 是學(xué)習(xí) 直接賓語(yǔ) =代詞名詞有了這組規(guī)則以后，可按如下方式導(dǎo)出句子： 先找 =左端的帶有句子的規(guī)則，并將它用 =右端的符號(hào)串代替，于是表示成：a70 句子句子 主語(yǔ)主語(yǔ)謂語(yǔ)謂語(yǔ) 然后在得到的串主語(yǔ)謂語(yǔ)中，選取主語(yǔ)或謂語(yǔ)，再用相應(yīng)規(guī)則的 =右端代替之。比如，選取了主語(yǔ)，并采用規(guī)則主語(yǔ) =代詞，那么得到： 主語(yǔ)主語(yǔ)謂語(yǔ)謂語(yǔ) 代詞代詞謂語(yǔ)謂語(yǔ) 依此類推，句子“我是大學(xué)生”的全部導(dǎo)出過(guò)程是： 句子句子

29、主語(yǔ)主語(yǔ)謂語(yǔ)謂語(yǔ) 代詞代詞謂語(yǔ)謂語(yǔ) 我我謂語(yǔ)謂語(yǔ) 我我動(dòng)詞動(dòng)詞直接賓語(yǔ)直接賓語(yǔ) 我是我是直接賓語(yǔ)直接賓語(yǔ) 我是我是名詞名詞 我是大學(xué)生我是大學(xué)生 a71 “我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大學(xué)生是”不符合上述規(guī)則，我們說(shuō)它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)。換句話說(shuō)，這些規(guī)則看成是一種元語(yǔ)言，用它描述漢語(yǔ)，僅僅涉及漢語(yǔ)句子的結(jié)構(gòu)描述。 這里“ ”讀作“導(dǎo)出導(dǎo)出”或或“派生出派生出”。 而“:=”（通常又簡(jiǎn)記為“”）讀作“定義為定義為”或“由組成”，而每一條規(guī)則又稱作是產(chǎn)生式產(chǎn)生式或重寫(xiě)式。這樣的一種描述形式就稱作是BNF（Backus-Naur Form）。a72v例：

30、賦值表達(dá)式可描述為 = = | a1|b123|salary|stu_age 18|123|4.5| + |- |* |/a732.語(yǔ)言概述語(yǔ)言概述語(yǔ)言是由句子組成的集合。語(yǔ)言是由句子組成的集合。漢語(yǔ)漢語(yǔ)-所有符合漢語(yǔ)語(yǔ)法的句子的全體。所有符合漢語(yǔ)語(yǔ)法的句子的全體。英語(yǔ)英語(yǔ)-所有符合英語(yǔ)語(yǔ)法的句子的全體。所有符合英語(yǔ)語(yǔ)法的句子的全體。程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言-所有符合該語(yǔ)言語(yǔ)法的程序的全體。所有符合該語(yǔ)言語(yǔ)法的程序的全體。 每個(gè)句子構(gòu)成的規(guī)則每個(gè)句子構(gòu)成的規(guī)則研究語(yǔ)言研究語(yǔ)言 每個(gè)句子的含義每個(gè)句子的含義 每個(gè)句子和使用者的關(guān)系每個(gè)句子和使用者的關(guān)系a74研究程序設(shè)計(jì)語(yǔ)言研究程序設(shè)計(jì)語(yǔ)言 每個(gè)

31、程序構(gòu)成的規(guī)則每個(gè)程序構(gòu)成的規(guī)則 每個(gè)程序的含義每個(gè)程序的含義 每個(gè)程序和使用者的關(guān)系每個(gè)程序和使用者的關(guān)系語(yǔ)言研究的三個(gè)方面語(yǔ)言研究的三個(gè)方面: 語(yǔ)法語(yǔ)法(Syntax) - 表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之 間的組合規(guī)則間的組合規(guī)則 語(yǔ)義語(yǔ)義(Semantics) - 表示各個(gè)記號(hào)的特定含義。表示各個(gè)記號(hào)的特定含義。 （各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系）（各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系） 語(yǔ)用語(yǔ)用(Pragmatics) -表示在各個(gè)記號(hào)所出現(xiàn)的行表示在各個(gè)記號(hào)所出現(xiàn)的行 為中，它們的來(lái)源、使用和影響。為中，它們的來(lái)源、使用和影響。a75 每種語(yǔ)言具有兩個(gè)

32、可識(shí)別的特性，即語(yǔ)每種語(yǔ)言具有兩個(gè)可識(shí)別的特性，即語(yǔ)言的形式和該形式相關(guān)聯(lián)的意義。言的形式和該形式相關(guān)聯(lián)的意義。 語(yǔ)言的實(shí)例若在語(yǔ)法上是正確的，其相語(yǔ)言的實(shí)例若在語(yǔ)法上是正確的，其相關(guān)聯(lián)的意義可以從兩個(gè)觀點(diǎn)來(lái)看，其一是該關(guān)聯(lián)的意義可以從兩個(gè)觀點(diǎn)來(lái)看，其一是該句子的創(chuàng)立者所想要表示的意義，另一是接句子的創(chuàng)立者所想要表示的意義，另一是接收者所檢驗(yàn)到的意義。這兩個(gè)意義并非總是收者所檢驗(yàn)到的意義。這兩個(gè)意義并非總是一樣的，前者稱為語(yǔ)言的語(yǔ)義，后者是其語(yǔ)一樣的，前者稱為語(yǔ)言的語(yǔ)義，后者是其語(yǔ)用意義。幽默、雙關(guān)語(yǔ)和謎語(yǔ)就是利用這兩用意義。幽默、雙關(guān)語(yǔ)和謎語(yǔ)就是利用這兩方面意義間的差異。方面意義間的差異。a

33、76 如果不考慮語(yǔ)義和語(yǔ)用，即只從語(yǔ)法如果不考慮語(yǔ)義和語(yǔ)用，即只從語(yǔ)法這一側(cè)面來(lái)看語(yǔ)言，這種意義下的語(yǔ)言稱這一側(cè)面來(lái)看語(yǔ)言，這種意義下的語(yǔ)言稱作形式語(yǔ)言。形式語(yǔ)言抽象地定義為一個(gè)作形式語(yǔ)言。形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)。該數(shù)學(xué)系統(tǒng)稱為數(shù)學(xué)系統(tǒng)。該數(shù)學(xué)系統(tǒng)稱為文法文法?！靶问叫问健笔侵高@樣的事實(shí)：是指這樣的事實(shí)：語(yǔ)言的所有規(guī)則描述什語(yǔ)言的所有規(guī)則描述什麼符號(hào)串以什么方式出現(xiàn)麼符號(hào)串以什么方式出現(xiàn)。形式語(yǔ)言理論。形式語(yǔ)言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究，是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的的研究，是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的基礎(chǔ)?；A(chǔ)。a773.有關(guān)定

34、義和記號(hào)有關(guān)定義和記號(hào)回顧回顧符號(hào)：可以相互區(qū)別的記號(hào)（元素）。符號(hào)：可以相互區(qū)別的記號(hào)（元素）。字母表字母表 ：符號(hào)（元素）的非空有窮集合。：符號(hào)（元素）的非空有窮集合。符號(hào)串符號(hào)串(字字)：由字母表：由字母表 中的符號(hào)組成的任何有中的符號(hào)組成的任何有窮序列稱為該字母表上的符號(hào)串。窮序列稱為該字母表上的符號(hào)串。 空字空字(沒(méi)有沒(méi)有符號(hào)的符號(hào)串符號(hào)的符號(hào)串)是是 上的符號(hào)串；上的符號(hào)串； 若若x是是 上的符號(hào)串上的符號(hào)串,a是是 的元素的元素,則則xa是是 上上 的符號(hào)串的符號(hào)串 ； y是是 上的符號(hào)串上的符號(hào)串,當(dāng)且僅當(dāng)它可以由當(dāng)且僅當(dāng)它可以由和和 導(dǎo)出。導(dǎo)出。 例如：例如： =a,b =a

35、,b ,a,b,aa,ab,aabba ,a,b,aa,ab,aabba都都是是 上的符號(hào)串上的符號(hào)串a(chǎn)78符號(hào)串符號(hào)串s的前綴：符號(hào)串的前綴：符號(hào)串s的任何首部。的任何首部。 如如:、b、ba、都是符號(hào)串都是符號(hào)串banana的前綴的前綴. 符號(hào)串符號(hào)串s的后綴：符號(hào)串的后綴：符號(hào)串s的任何尾部。的任何尾部。 如如: 、a、na、都是符號(hào)串都是符號(hào)串banana的后綴的后綴.符號(hào)串符號(hào)串s的子串：從的子串：從s中刪去一個(gè)前綴和一個(gè)后綴中刪去一個(gè)前綴和一個(gè)后綴得到的符號(hào)串得到的符號(hào)串. 如如:ana是符號(hào)串是符號(hào)串banana的一個(gè)子串的一個(gè)子串.符號(hào)串符號(hào)串s的真前綴：的真前綴： xs且且x

36、的任何前綴的任何前綴x。s的真后綴，真子串可以類似地定義。的真后綴，真子串可以類似地定義。a79符號(hào)串的運(yùn)算：符號(hào)串的運(yùn)算： 符號(hào)串的長(zhǎng)度：符號(hào)串中符號(hào)的個(gè)數(shù)符號(hào)串的長(zhǎng)度：符號(hào)串中符號(hào)的個(gè)數(shù).符號(hào)串符號(hào)串s 的長(zhǎng)度的長(zhǎng)度 記為記為|s|。 的長(zhǎng)度為的長(zhǎng)度為0連接：符號(hào)串連接：符號(hào)串x x、y y的連接的連接, ,是把是把y y的符號(hào)寫(xiě)在的符號(hào)寫(xiě)在x x的符號(hào)的符號(hào) 之后得到的符號(hào)串之后得到的符號(hào)串xy xy 如如 x=ab,y=cd x=ab,y=cd 則則 xy=abcd xy=abcd 又如又如a = a a = a 方冪：符號(hào)串自身連接方冪：符號(hào)串自身連接n n次得到的符號(hào)串次得到的符號(hào)

37、串 a an n 定義為定義為 aaaa aaaa n n個(gè)個(gè)a a a a0 0=,a=,a1 1=a, a=a, a2 2=aa =aa a80符號(hào)串集合：若集合符號(hào)串集合：若集合A中所有元素都是某字母中所有元素都是某字母表表 上的符號(hào)串，則稱上的符號(hào)串，則稱A為字母表為字母表 上的符號(hào)上的符號(hào)串集合。串集合。符號(hào)串集合符號(hào)串集合A和和B的乘積：的乘積： AB = xy|xxy|x A A且且y y B B 若若 集合集合A= ab,cdeab,cde B = 0,10,1 則則 AB = ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1 的閉包：的閉包： 上的一切符號(hào)

38、串（包括上的一切符號(hào)串（包括）組成）組成的集合，記為的集合，記為 * 。的正閉包：的正閉包： 上的上的除除外外的所有符號(hào)串組的所有符號(hào)串組成的集合，記為成的集合，記為 + 。a81例：例：=a,b=a,b * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab, + +=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab,.2*.32*a82語(yǔ)言：語(yǔ)言：由句子構(gòu)成的集合。換言之,字母表上的一個(gè)語(yǔ)言是上的一些符號(hào)串的集合 (字母表上的每個(gè)語(yǔ)言是*的一個(gè)子集)。例如：字母表=a,b, *=,a,b,

39、aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示為w|w*且w=anbn,n1為字母表上的一個(gè)語(yǔ)言。集合a,aa,aaa,或表示為w|w*且w=an,n1 為字母表上的一個(gè)語(yǔ)言。 是一個(gè)語(yǔ)言，即 也是一個(gè)語(yǔ)言。a83二、上下文無(wú)關(guān)文法及其語(yǔ)言的形式定義二、上下文無(wú)關(guān)文法及其語(yǔ)言的形式定義1.如何來(lái)描述一種語(yǔ)言？如何來(lái)描述一種語(yǔ)言？ 如果語(yǔ)言是有窮的（只含有有窮多個(gè)句子），可如果語(yǔ)言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來(lái)表示；以將句子逐一列出來(lái)表示； 如果語(yǔ)言是無(wú)窮的，找出語(yǔ)言的有窮表示。如果語(yǔ)言是無(wú)窮的，找出語(yǔ)言的有窮表示。語(yǔ)言的有窮表示

40、有兩個(gè)途徑：語(yǔ)言的有窮表示有兩個(gè)途徑： 生成方式生成方式 ：語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的：語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造。規(guī)則來(lái)構(gòu)造。 識(shí)別方式：用一個(gè)過(guò)程，當(dāng)輸入的一任意串屬于識(shí)別方式：用一個(gè)過(guò)程，當(dāng)輸入的一任意串屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是是”，若不屬于，要麼能停止并回答，若不屬于，要麼能停止并回答“不是不是”，要麼永遠(yuǎn)繼續(xù)下去。要麼永遠(yuǎn)繼續(xù)下去。 a84 文法是從生成方式描述語(yǔ)言的，而自動(dòng)機(jī)則是從識(shí)別的角度來(lái)描述語(yǔ)言的。本節(jié)僅介紹有關(guān)文法的概念。 前面關(guān)于“我是大學(xué)生”及“賦值表達(dá)式”的例子中，涉及到如下的概

41、念：l所表示的是一個(gè)類類概念，通常稱作語(yǔ)法范疇語(yǔ)法范疇或語(yǔ)法變量，如果用一個(gè)符號(hào)來(lái)代替,也稱為非終結(jié)符非終結(jié)符(nonterminal)。所有規(guī)則中的非終結(jié)符構(gòu)成了一個(gè)非空有窮集，記為V VN N。l上述兩例中的“句子”及“賦值表達(dá)式”顯然是最大的語(yǔ)法范疇，也是我們最感興趣的非終結(jié)符，通常稱作開(kāi)始符號(hào)，記為S S。l“大學(xué)生”、“我”、“是”、“a”、“+”等表示的是一個(gè)具體概念，用一個(gè)符號(hào)來(lái)表示，則稱為終結(jié)符終結(jié)符(terminal)。所有這樣的符號(hào)同樣構(gòu)成了一個(gè)非空有窮集，記為V VT T。l我、8等稱作產(chǎn)生式(production)。所有產(chǎn)生式的集合顯然是有窮的，記為P。 這樣我們可以將

42、文法抽象為如下的一個(gè)數(shù)學(xué)系統(tǒng)：a852. 文法的形式定義文法的形式定義一個(gè)文法G定義為一個(gè)四元式(VN, VT, S , P) 其中： VN為非終結(jié)符號(hào)的非空有窮集； VT為終結(jié)符號(hào)的非空有窮集， VN VT = ； P為產(chǎn)生式的集合；產(chǎn)生式產(chǎn)生式也稱重寫(xiě)規(guī)則或生成式，形如A，其中： A VN ,(VN VT)* 。 A稱為產(chǎn)生式的左部， 稱作產(chǎn)生式的右部。 S稱作識(shí)別符號(hào)或開(kāi)始符號(hào)，S VN 且至少要在一條產(chǎn)生式中作為左部出現(xiàn)。 VN VT中的符號(hào)統(tǒng)稱為文法符號(hào)。a86例1 文法G=（VN，VT， S ， P ）VN = S , VT = 0, 1 P= S0S1, S01 S為開(kāi)始符號(hào)例2

43、 文法G=（VN，VT， S ， P ） VN =， VT =a,b,c,x,y,z,0,1,9 P=, , , a, z, 0, 9 S=a87文法的寫(xiě)法文法的寫(xiě)法 . G. G：SaASaAb Aab Aab AaA AaAb A A . GS. GS： SaSSaSb Aab AaA Aab AaAb A A . GSGS： SaSSaSb Aab |aA Aab |aAb | |元元符號(hào)： = | = | 習(xí)慣表示： 大寫(xiě)英文字母：非終結(jié)符/集合 字母表中靠前的小寫(xiě)英文字母：終結(jié)符 字母表中靠后的小寫(xiě)英文字母：字符串a(chǎn)88v上下文無(wú)關(guān)文法：它所定義的語(yǔ)法范疇是完全獨(dú)立于這種范疇所能出現(xiàn)

44、的環(huán)境。程序設(shè)計(jì)語(yǔ)言的詞：a+b/3 a10)，則記為，則記為 v + w，v推導(dǎo)出推導(dǎo)出w，或，或w歸約到歸約到v。若有。若有v + w， 或或v=w，則記為，則記為v * w。例：例：G G： S0S1， S01 S 0S1 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S + 00001111 S * S 00S11 * 00S11a91(3)最左（最右）推導(dǎo)最左（最右）推導(dǎo)最左（最右）推導(dǎo)：在推導(dǎo)的任何一步最左（最右）推導(dǎo)：在推導(dǎo)的任何一步，都是對(duì)，都是對(duì)中的最左（右）非終結(jié)中的最左（右）非終

45、結(jié)符進(jìn)行替換。符進(jìn)行替換。最右推導(dǎo)被稱為最右推導(dǎo)被稱為規(guī)范推導(dǎo)規(guī)范推導(dǎo)。也就是說(shuō)，規(guī)范。也就是說(shuō)，規(guī)范推導(dǎo)具有最右性。推導(dǎo)具有最右性。規(guī)范推導(dǎo)的逆過(guò)程稱為規(guī)范推導(dǎo)的逆過(guò)程稱為規(guī)范規(guī)約規(guī)范規(guī)約。也就是說(shuō)，。也就是說(shuō)，規(guī)范規(guī)約具有最左性。規(guī)范規(guī)約具有最左性。由規(guī)范推導(dǎo)所得的句型稱為由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。規(guī)范句型。a924.句型、句子句型、句子句型：句型：有文法有文法G，若，若S * x， x (V(VN NVVT T) )* *, ,則稱則稱x是文是文法法G的句型。的句型。句子：句子：有文法有文法G，若，若S * x，且，且xVVT T* *，則稱，則稱x是文法是文法G的句子。的句子。

46、例例1 1：G G： S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型:S,0S1 ,00S11 ,000S111,00001111 G的句子:00001111, 01a93例例2：GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|a這個(gè)文法都能推導(dǎo)出什么句子？EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a用符號(hào)用符號(hào)a a，+ +，* *，( ( 和和 ) ) 構(gòu)成的算術(shù)表達(dá)式構(gòu)成的算術(shù)表達(dá)式思考：寫(xiě)出一個(gè)不同的文法，同樣能夠產(chǎn)生這些句子思考：寫(xiě)出一個(gè)不同的文法，同樣能夠產(chǎn)生這些

47、句子a945.語(yǔ)言的定義語(yǔ)言的定義 由文法G生成的語(yǔ)言記為L(zhǎng)(G),它是文法G的所有句子的集合。 L(G)=x|S + x, S為開(kāi)始符號(hào),且x VT* 例例1 G1 G： S0S1， S01 L(G)=0n1n|n1 例例2 2 文法文法GSGS：（1 1）SaSBESaSBE（2 2）SaBESaBE（3 3）EBBEEBBE（4 4）aBabaBab（5 5）bBbbbBbb（6 6）bEbebEbe（7 7）eEeeeEee L（G）= anbnen | n1 這個(gè)文法生成什么語(yǔ)言？這個(gè)文法與前面見(jiàn)過(guò)的文法有什么不同？a95S a S BE (SaSBE) a aBEBE (SaBE)

48、 aabEBE ( aBab ) aabBEE ( EBBE ) aabbEE （bBbb) aabbeE （bEbe) aabbee （eEee)類似推導(dǎo)可以看出類似推導(dǎo)可以看出a,b,e在句子中出現(xiàn)的順序及個(gè)數(shù)滿足在句子中出現(xiàn)的順序及個(gè)數(shù)滿足L(G)當(dāng)然要進(jìn)一步說(shuō)明：當(dāng)然要進(jìn)一步說(shuō)明： G G生成的每個(gè)句子都在生成的每個(gè)句子都在L(G)L(G)中中 L(G) L(G)中的每個(gè)句子確實(shí)能被中的每個(gè)句子確實(shí)能被G G生成生成a96 使用產(chǎn)生式(1) n-1次，得到推導(dǎo)序列： S *an-1S(BE)n-1，然后使用產(chǎn)生式(2)一次，得到：S * an-1S(BE)n-1 an(BE)n。然后從

49、an(BE)n繼續(xù)推導(dǎo)，總是對(duì)EB使用產(chǎn)生式(3)的右部進(jìn)行替換，而最終在得到的串中，所有的B都先于所有的E。例如，若n=3, aaaBEBEBE aaaBBEEBE aaaBBEBEE aaaBBBEEE。 即有：S * anBnEn 再使用產(chǎn)生式(4)一次，得到S * anbBn-1En，然后使用產(chǎn)生式(5) n-1次得到：S * anbnEn，進(jìn)而使用產(chǎn)生式(6)一次，使用產(chǎn)生式(7) n-1次，最后得到：S * anbnen 。 也能證明，對(duì)于n1，串a(chǎn)nbnen是唯一形式的終結(jié)符號(hào)串。 a97 三、文法的等價(jià)性三、文法的等價(jià)性1.定義：定義： 若若L(GL(G1 1)=L(G)=L(

50、G2 2) )，則稱文法，則稱文法G G1 1和和G G2 2是等價(jià)的。是等價(jià)的。如文法如文法G1A：A0R 與與 G2S：S0S1 等價(jià)等價(jià) A01 S01 RA1因?yàn)橐驗(yàn)長(zhǎng)（G1）=L（G2）=0n1n n1。a982.關(guān)于文法等價(jià)變換的幾個(gè)定理關(guān)于文法等價(jià)變換的幾個(gè)定理(1)對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，但G2的開(kāi)始符號(hào)不出現(xiàn)在任何產(chǎn)生式的右部。例1： G1: EE+EE*E(E)i G2: SE EE+EE*E(E)i 具體做法：加一條單個(gè)非產(chǎn)生式SE即可。(2)對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，但G2的每個(gè)非終結(jié)符都能導(dǎo)出一

51、個(gè)終結(jié)符號(hào)串。 可給出如下證明：a99v證明：令=AAtG1&tVT+；遞歸擴(kuò)充：=WWx&x(VT)+ 由于G1的非終結(jié)符號(hào)是有窮的，上述過(guò)程一定是收斂的；從G1的VN中刪除不包含在中的非終結(jié)符，并從其產(chǎn)生式集中刪除其左部或右部中包含不屬于中的符號(hào)的產(chǎn)生式，這樣得到的文法即為所要的G2。a100例：G1A: ABeddD Bb DEaADDB EDaEb =B =BA=A,B,到此為止； 于是D,E及相關(guān)D,E的產(chǎn)生式均可刪除，得到： G2A: ABed Bb 可以證明L(G1)=L(G2)。類似還可以給出如下定理：(3)對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1) =

52、L(G2)，但G2的每個(gè)非終結(jié)符都出現(xiàn)在某一句型中。證明？a101(4)對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，但G2中不含單個(gè)非產(chǎn)生式單個(gè)非產(chǎn)生式。如：G1A: ABBdD G2A: dD G2A: AdDbcdDbc BAACb Cb DdDadDa CBBcc DdDadDa(5)對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，但G2中不含空產(chǎn)生式空產(chǎn)生式。 形如 E的產(chǎn)生式稱為空產(chǎn)生式。(6)對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，但G2中不含有左遞歸左遞歸。 形如 EE+T的產(chǎn)生式稱為左遞歸的。遞歸哪里去了a102四、語(yǔ)法樹(shù)和

53、文法二義性四、語(yǔ)法樹(shù)和文法二義性 1.語(yǔ)法樹(shù)：語(yǔ)法樹(shù)： 語(yǔ)法樹(shù)是了解句子語(yǔ)法結(jié)構(gòu)的一種輔助工具。樹(shù)根即為開(kāi)始符號(hào)所標(biāo)記的結(jié)點(diǎn)。隨著推導(dǎo)的展開(kāi)，某個(gè)非終結(jié)符被它的產(chǎn)生式右部所替換時(shí)，則產(chǎn)生出下一代新結(jié)點(diǎn)。每個(gè)新結(jié)點(diǎn)和其父結(jié)點(diǎn)間都有一條連線。 于是，可給出如下的定義：a103設(shè)G=( VN,VT, S, P)為一CFG，若一棵樹(shù)滿足下列4個(gè)條件，則此樹(shù)稱作G的語(yǔ)法樹(shù)(推導(dǎo)樹(shù))(派生樹(shù)）：1. 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)2. 根的標(biāo)記是S3. 若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則肯定AVN4. 如果結(jié)點(diǎn)n有標(biāo)記A,其直接子孫結(jié)點(diǎn)從左到右的次序是n1，n2，nk，其標(biāo)

54、記分別為A1，A2，Ak，那么AA1A2，Ak一定是P中的一個(gè)產(chǎn)生式語(yǔ)法樹(shù)的結(jié)果：語(yǔ)法樹(shù)的結(jié)果：從左到右讀出葉子的標(biāo)記而構(gòu)成的串謂之句型。a104給定文法給定文法G=(VN,VT,P,S)，對(duì)于，對(duì)于G的任何句型都的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)(推導(dǎo)樹(shù)推導(dǎo)樹(shù))。定理：定理：G為上下文無(wú)關(guān)文法，為上下文無(wú)關(guān)文法，對(duì)于對(duì)于，有，有S * ，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)文法文法G有以有以為結(jié)果的一棵語(yǔ)法樹(shù)為結(jié)果的一棵語(yǔ)法樹(shù)(推導(dǎo)樹(shù)推導(dǎo)樹(shù))這里對(duì)該定理不作證明。這里對(duì)該定理不作證明。a105v例如：文法GE: EE+EE*E(E)i 顯然(i+i)*i是該文法產(chǎn)生的一個(gè)句子，它的推導(dǎo)過(guò)

55、程可以用右邊的語(yǔ)法樹(shù)來(lái)描述。 子樹(shù)子樹(shù)與簡(jiǎn)單子樹(shù)簡(jiǎn)單子樹(shù) 只有單層分支的子樹(shù)代次21345EE*E(E)E+Eiiia106 在一棵語(yǔ)法樹(shù)生長(zhǎng)過(guò)程中的任何時(shí)刻，所有葉結(jié)點(diǎn)從左到右依次排列起來(lái)就是一個(gè)句型句型。這就是說(shuō)，一棵語(yǔ)法樹(shù)表示了一個(gè)句型種種可能的（但未必是所有的）不同推導(dǎo)過(guò)程，包括最左（最右）推導(dǎo)最左（最右）推導(dǎo)。如果我們堅(jiān)持使用最左（最右）推導(dǎo)，那么一棵語(yǔ)法樹(shù)就完全等價(jià)于一個(gè)最左（最右）推導(dǎo)。a107文法文法GE:GE:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E

56、 E * * E E i E + E i E + E i i i i句型句型 i i* *i+i i+i 的兩個(gè)不同的最左推導(dǎo)：的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)推導(dǎo)1 1：E E E+E E+E E E* *E+E E+E i i* *E+E E+E i i* *i+E i+E i i* *i+ii+i推導(dǎo)推導(dǎo)2 2：E E E E* *E E i i* *E E i i* *E+E E+E i i* *i+E i+E i i* *i+ii+i 但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢?一個(gè)句型是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?不盡然。試看下例：a1082.文法二義性文法二義性 若一個(gè)文法存在

57、某個(gè)句子對(duì)應(yīng)若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的兩棵不同的語(yǔ)法樹(shù)語(yǔ)法樹(shù)，則稱這個(gè)文法是，則稱這個(gè)文法是二義二義的；或者，若的；或者，若一個(gè)文法存在某個(gè)句子有一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左兩個(gè)不同的最左（右）推導(dǎo)（右）推導(dǎo)，則稱這個(gè)文法是二義的。，則稱這個(gè)文法是二義的。 顯然，上例中的文法就是一個(gè)二義文法。顯然，上例中的文法就是一個(gè)二義文法。 a1093.二義性問(wèn)題是不可判定的二義性問(wèn)題是不可判定的 不能設(shè)計(jì)一個(gè)算法，在有窮的步驟內(nèi)確切地判定一個(gè)文法是否為二義性的。 因此，我們所能做的工作只能是為二義性尋找一組充分（而非必要）條件來(lái)改造二義性文法。 例如對(duì)前面提到的二義性文法G(E): E

58、E+EE*E(E)i 可將其改造為如下無(wú)二義文法G： G(E): ETE+T TFT*F Fi(E)如此改造，所依如此改造，所依何據(jù)？何據(jù)？?jī)?yōu)先級(jí)優(yōu)先級(jí)&結(jié)合規(guī)則結(jié)合規(guī)則a110以代數(shù)運(yùn)算為例，說(shuō)明操作符的：以代數(shù)運(yùn)算為例，說(shuō)明操作符的：v結(jié)合規(guī)則左結(jié)合：當(dāng)一個(gè)操作數(shù)的左右兩側(cè)都有+時(shí)，它將被左側(cè)的+使用。4+5+9=(4+5)+9右結(jié)合：523 =58v優(yōu)先級(jí)優(yōu)先級(jí)表v左結(jié)合：+ -v左結(jié)合：* /v右結(jié)合：冪a111 注意注意：文法的二義性和語(yǔ)言的二義性是兩個(gè)不：文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法G G和和GG，

59、L(G)=L(G)L(G)=L(G)，其中，其中G G是二義的，但是是二義的，但是GG卻是無(wú)二卻是無(wú)二義的。上面的例子很好地說(shuō)明了這一點(diǎn)。義的。上面的例子很好地說(shuō)明了這一點(diǎn)。 如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)此語(yǔ)言是先天二義的。對(duì)于一個(gè)程二義的，則說(shuō)此語(yǔ)言是先天二義的。對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義的，序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。a112 語(yǔ)法樹(shù)是了解句子語(yǔ)法結(jié)構(gòu)的一種輔助工具，也是語(yǔ)法樹(shù)是了解句子語(yǔ)法結(jié)構(gòu)的一種輔助工具，也是語(yǔ)

60、法分析的輔助工具，因此又稱為語(yǔ)法分析樹(shù)。這樣一語(yǔ)法分析的輔助工具，因此又稱為語(yǔ)法分析樹(shù)。這樣一來(lái)，就存在著自上而下和自下而上兩種分析方法。來(lái)，就存在著自上而下和自下而上兩種分析方法。 在自上而下的分析方法中在自上而下的分析方法中如何如何選擇選擇使用使用哪個(gè)哪個(gè)產(chǎn)生式產(chǎn)生式進(jìn)行推導(dǎo)進(jìn)行推導(dǎo)？ 假定要被代換的最左非終結(jié)符號(hào)是假定要被代換的最左非終結(jié)符號(hào)是B，且有，且有n條規(guī)條規(guī)則：則：BA1|A2|An，那么如何確定用哪個(gè)右部去替，那么如何確定用哪個(gè)右部去替代代B？ 在自下而上的分析方法中在自下而上的分析方法中如何如何識(shí)別可歸約的串識(shí)別可歸約的串？ 在分析程序工作的每一步，都是從當(dāng)前串中在分析程序工作的每一步，都是從當(dāng)