編譯原理精課件_第1頁(yè)
編譯原理精課件_第2頁(yè)
編譯原理精課件_第3頁(yè)
編譯原理精課件_第4頁(yè)
編譯原理精課件_第5頁(yè)
已閱讀5頁(yè),還剩118頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

編譯原理課件1可編輯課件PPT第一講引論課程信息編譯程序概述高級(jí)語(yǔ)言的語(yǔ)法描述2可編輯課件PPT§1.課程信息一、課程名稱(chēng):編譯原理基本內(nèi)容是介紹編譯程序構(gòu)造的基本原理、方法和技術(shù),包括詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生、代碼優(yōu)化及目標(biāo)代碼產(chǎn)生等。簡(jiǎn)言之,就是介紹如何將源程序翻譯成目標(biāo)代碼程序。3可編輯課件PPT二、課程性質(zhì):專(zhuān)業(yè)基礎(chǔ)課,必修編譯程序(器)出現(xiàn)于上世紀(jì)50年代后期(第一個(gè)高級(jí)語(yǔ)言1958年)60年代~70年代是研究高峰期60年代中期開(kāi)始在高校中開(kāi)設(shè)課程80年代開(kāi)始作為計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的必修基礎(chǔ)課程4可編輯課件PPT5可編輯課件PPT三、課程特點(diǎn):充分體現(xiàn)了計(jì)算學(xué)科中抽象、理論和設(shè)計(jì)三個(gè)學(xué)科形態(tài)該課程涉及多門(mén)課程的內(nèi)容綜合運(yùn)用,涉及面廣,內(nèi)容龐雜,學(xué)習(xí)艱難程序設(shè)計(jì)語(yǔ)言、計(jì)算機(jī)體系結(jié)構(gòu)、語(yǔ)言理論及算法等數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)該課程涉及的原理、方法和技術(shù)具有十分普遍的意義每一個(gè)計(jì)算機(jī)科學(xué)與技術(shù)工作者的職業(yè)生涯中反復(fù)用到,“享用一輩子”這兒接受的訓(xùn)練很難在其他地方獲得,如:抽象與形式化方法、局部與全局優(yōu)化方法、構(gòu)造技術(shù)、證明方法等6可編輯課件PPT四、學(xué)習(xí)該課程的意義編譯程序是計(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)題7可編輯課件PPT編譯方法與技術(shù)有著廣泛應(yīng)用安全技術(shù)、程序理解、軟件逆向工程、應(yīng)用軟件與軟件工具開(kāi)發(fā)、軟件測(cè)試與驗(yàn)證等編譯課程蘊(yùn)含著計(jì)算學(xué)科中解決問(wèn)題的思路、抽象和方法,這些與高等數(shù)學(xué)一樣,使你“享用一輩子”課程所涉及的內(nèi)容至今非?;钴S自然語(yǔ)言的翻譯軟件移植網(wǎng)絡(luò)安全形式化方法形式語(yǔ)義學(xué)等8可編輯課件PPT

鑒于以上所述,作為計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的學(xué)生必須學(xué)習(xí)和掌握編譯原理這門(mén)課程,當(dāng)然由于其綜合性、處理問(wèn)題的復(fù)雜性等,學(xué)習(xí)起來(lái)有一定難度,這就需要艱苦奮斗的精神和良好的學(xué)習(xí)方法9可編輯課件PPT五、學(xué)習(xí)方法編譯程序的構(gòu)造是一個(gè)龐大而復(fù)雜的系統(tǒng)工程,無(wú)論是概念還是理論、方法,對(duì)初學(xué)者來(lái)說(shuō)許多都是新的,學(xué)習(xí)起來(lái)會(huì)感到困難大一些,這一點(diǎn)必須有充分認(rèn)識(shí),為此建議學(xué)習(xí)方法上注意以下幾點(diǎn):10可編輯課件PPT課前預(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)考慮。11可編輯課件PPT理論聯(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ì)你能力的提高大有益處12可編輯課件PPT六、教材

《程序設(shè)計(jì)語(yǔ)言編譯原理》(第3版)

國(guó)防工業(yè)出版社陳火旺等內(nèi)容詳實(shí)豐富,理論與技術(shù)相結(jié)合較為全面介紹了編譯程序構(gòu)造的基本原理、方法與技術(shù)厚度適中大多數(shù)院校一直采用,碩士入學(xué)考試參考書(shū)所謂教材,實(shí)為第一參考書(shū)而已13可編輯課件PPT七、參考書(shū)目1.《編譯原理》第2版趙建華等譯,<Compilers:Principles,Techniques,&Tools>A.V.Aho,M.S.Lam,RaviSethi,J.D.Ullman著,機(jī)械工業(yè)出版社,2009;2.《編譯原理課程設(shè)計(jì)》王雷等著,機(jī)械工業(yè)出版社,2005;八、期末總評(píng)

平時(shí)成績(jī):10% 課程設(shè)計(jì):20% 期終考試:70%14可編輯課件PPT15可編輯課件PPT§2.編譯程序概述一、翻譯程序(Translator)

能夠把一種語(yǔ)言程序(稱(chēng)為源語(yǔ)言程序)轉(zhuǎn)換成邏輯上等價(jià)的另一種語(yǔ)言程序(稱(chēng)為目標(biāo)語(yǔ)言程序)的程序16可編輯課件PPT任何非機(jī)器語(yǔ)言程序都需要翻譯程序翻譯程序的工作就是進(jìn)行等價(jià)變換(映射)兩個(gè)程序邏輯上等價(jià)是指對(duì)相同輸入得到相同的輸出翻譯程序解釋程序匯編程序編譯程序17可編輯課件PPT匯編程序(Assembler)

把匯編語(yǔ)言程序轉(zhuǎn)變?yōu)闄C(jī)器語(yǔ)言程序的翻譯程序解釋程序(Interpreter)

把源程序作為輸入接收,邊解釋邊執(zhí)行的翻譯程序源程序數(shù)據(jù)解釋程序結(jié)果18可編輯課件PPT編譯程序

將高級(jí)語(yǔ)言程序轉(zhuǎn)變?yōu)榈图?jí)語(yǔ)言程序的翻譯程序源程序編譯程序目標(biāo)程序19可編輯課件PPT20可編輯課件PPT編譯程序又可根據(jù)用途和側(cè)重點(diǎn)的不同,進(jìn)一步分類(lèi)為:

①診斷編譯程序(DiagnosticCompiler)

專(zhuān)門(mén)用于幫助程序開(kāi)發(fā)和調(diào)試的編譯程序

②優(yōu)化編譯程序(OptimizingCompiler)

著重于提高目標(biāo)代碼效率的編譯程序

③交叉編譯程序(CrossCompiler)

能夠產(chǎn)生不同于其宿主機(jī)機(jī)器代碼的編譯程序

④可變目標(biāo)編譯程序(Retargetablecomplier)

無(wú)須重寫(xiě)與機(jī)器無(wú)關(guān)部分就能改變目標(biāo)機(jī)的編譯程序21可編輯課件PPT二、與編譯程序相關(guān)的程序本講義只介紹編譯程序(器)構(gòu)造的基本原理、方法與技術(shù),但在一個(gè)完整的語(yǔ)言開(kāi)發(fā)(或稱(chēng)程序設(shè)計(jì))環(huán)境中,除了編譯器這一主要工具外,還需要其他一些工具,如編輯器、連接器、裝入程序等。現(xiàn)代計(jì)算機(jī)系統(tǒng)常將這些相互獨(dú)立的程序設(shè)計(jì)工具集成起來(lái),構(gòu)成一個(gè)集成化的程序開(kāi)發(fā)環(huán)境,以提高程序設(shè)計(jì)效率和程序的質(zhì)量。如TurboC、VisualC++等語(yǔ)言環(huán)境都是集成化的程序設(shè)計(jì)環(huán)境。而Ada語(yǔ)言的集成環(huán)境是這方面的典型代表。22可編輯課件PPT如Ada語(yǔ)言的集成環(huán)境是一個(gè)分層的程序開(kāi)發(fā)環(huán)境編譯程序MAPSE編輯程序連接程序宿主機(jī)OSAPSE工具界面用戶界面KAPSE調(diào)試程序配置管理程序命令解釋程序其他工具23可編輯課件PPT這兒要強(qiáng)調(diào)的是:盡管本課程只介紹編譯的基本理論、方法和技術(shù),但這些基本理論、方法與技術(shù)對(duì)其他工具的構(gòu)造同樣起作用!24可編輯課件PPT編輯器(Editor)

完成源程序輸入、編輯并產(chǎn)生標(biāo)準(zhǔn)文件(如ASCII文件)的程序。近來(lái)已與編譯器和其他程序捆綁進(jìn)一個(gè)交互開(kāi)發(fā)環(huán)境——IDE中盡管這樣的編輯器仍生成標(biāo)準(zhǔn)文件,但會(huì)轉(zhuǎn)向正被討論的程序設(shè)計(jì)語(yǔ)言的格式或結(jié)構(gòu)(稱(chēng)為基于結(jié)構(gòu)的),且已包含了編譯器的某些操作;因此在程序編寫(xiě)時(shí)而不是編譯時(shí)就可得知錯(cuò)誤,甚至也可調(diào)用編譯器25可編輯課件PPT預(yù)處理程序(Preprocessor)

在真正翻譯開(kāi)始之前產(chǎn)生編譯程序的輸入的程序處理宏及注釋?zhuān)汉晔潜唤?jīng)常使用的較長(zhǎng)結(jié)構(gòu)的縮寫(xiě)處理文件包含:把頭文件包含到程序正文中(如C的文件包含include<….h>)“理解”預(yù)處理器:把現(xiàn)代控制流和數(shù)據(jù)結(jié)構(gòu)機(jī)制添加到比較老式的語(yǔ)言中語(yǔ)言擴(kuò)充:通過(guò)大量的內(nèi)部宏定義來(lái)增強(qiáng)語(yǔ)言的能力,如Equel語(yǔ)言是一種嵌套在C語(yǔ)言中的數(shù)據(jù)庫(kù)查詢(xún)語(yǔ)言26可編輯課件PPT連接程序(Linker)——又稱(chēng)為連接編輯器。將分別在不同的目標(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í)行代碼更加靈活27可編輯課件PPT調(diào)試程序(Debugger)

可在被編譯了的程序中判定執(zhí)行錯(cuò)誤的程序它經(jīng)常與編譯程序一起放在IDE中運(yùn)行一個(gè)帶有調(diào)試程序的程序與直接執(zhí)行不同,這是因?yàn)檎{(diào)試程序保存著所有的或大多數(shù)源代碼信息,它可以在預(yù)先指定的位置(斷點(diǎn)BreakPoint)暫停執(zhí)行,并提供有關(guān)信息(已調(diào)用的函數(shù)、變量名的當(dāng)前值等)28可編輯課件PPT其他有關(guān)的還有描述器(Profiler)——執(zhí)行中搜集目標(biāo)程序行為統(tǒng)計(jì)的程序項(xiàng)目管理程序(ProjectManager)——如Unix系統(tǒng)中的SCCS(源代碼控制系統(tǒng))和RCS(修正控制系統(tǒng))和匯編程序等綜上所述可給出一個(gè)“語(yǔ)言處理系統(tǒng)”的圖示:29可編輯課件PPT我們這個(gè)課只介紹編譯程序這一部分30可編輯課件PPT三、編譯過(guò)程與編譯程序結(jié)構(gòu)

1.編譯過(guò)程:

輸入輸出(高級(jí)語(yǔ)言源程序)(低級(jí)語(yǔ)言目標(biāo)程序)

編譯程序工作過(guò)程如下:識(shí)別出一個(gè)個(gè)的單詞分析句子的語(yǔ)法結(jié)構(gòu)分析句子的語(yǔ)義并進(jìn)行初步翻譯對(duì)初步翻譯進(jìn)行優(yōu)化整理出目標(biāo)程序?qū)σ陨线^(guò)程進(jìn)一步整理可得如下編譯程序結(jié)構(gòu)總框:編譯程序31可編輯課件PPT2.編譯程序總框:詞法分析器語(yǔ)法分析器語(yǔ)義分析與中間代碼產(chǎn)生器優(yōu)化器目標(biāo)代碼生成器單詞符號(hào)語(yǔ)法單位中間代碼中間代碼出錯(cuò)處理表格管理源程序目標(biāo)代碼32可編輯課件PPT3.五個(gè)階段簡(jiǎn)介第一階段:詞法分析——依據(jù)語(yǔ)言構(gòu)詞規(guī)則,識(shí)別出一個(gè)個(gè)單詞(符號(hào))

單詞種類(lèi)保留字:forifwhile算符:+-×/界符:,;(){}標(biāo)識(shí)符:a1a2pi常數(shù):910244.86E6無(wú)窮性有窮性思考:識(shí)別有窮集合VS識(shí)別無(wú)窮集合33可編輯課件PPT

詞法分析工作由詞法分析器(或稱(chēng)掃描器)完成。

掃描器輸出為等長(zhǎng)度的單詞符號(hào)(二元式)流。

例:Position=initial+rate*60詞法分析(掃描器)保留字表(06,‘Position’)

(11,─)

(06,‘initial’)

(12,─)

(06,‘rate’)

(13,─)

(07,’60的二進(jìn)制’)34可編輯課件PPT第二階段:語(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標(biāo)識(shí)符35可編輯課件PPT第三階段:語(yǔ)義分析與中間代碼產(chǎn)生——針對(duì)各類(lèi)不同的語(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ǔ)義檢查,包括:變量是否定義過(guò)類(lèi)型是否正確是否用了0作除數(shù)……36可編輯課件PPT將語(yǔ)法范疇翻譯成某種形式的中間代碼,如四元式:37可編輯課件PPT第四階段:優(yōu)化——對(duì)前階段產(chǎn)生的中間代碼進(jìn)行加工變換,以期在最后階段能產(chǎn)生出高效(節(jié)省時(shí)、空)的目標(biāo)代碼,這一任務(wù)是由優(yōu)化器來(lái)完成的根據(jù)優(yōu)化的范圍不同,可分為:

局部?jī)?yōu)化,循環(huán)優(yōu)化和全局優(yōu)化一個(gè)循環(huán)優(yōu)化的例子:38可編輯課件PPT循環(huán)

For(k=1;k<=100;k++){M=I+10*k;N=J+10*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次加39可編輯課件PPT第五階段:目標(biāo)代碼生成——把中間代碼翻譯成目標(biāo)代碼顯然這階段要依賴(lài)于硬體系統(tǒng)結(jié)構(gòu)和指令系統(tǒng)涉及存貯分配、寄存器調(diào)度這一階段工作是由代碼生成器完成的說(shuō)明:以上各階段(或稱(chēng)工序)并不是截然分開(kāi)的,尤其編譯程序結(jié)構(gòu)十分復(fù)雜、體積相當(dāng)龐大,所以有時(shí)人們把幾個(gè)階段的工作有機(jī)地組合在一起、穿插進(jìn)行,構(gòu)成遍。40可編輯課件PPT遍(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ì)人員的情況等41可編輯課件PPT如某PL/0編譯程序的結(jié)構(gòu)詞法分析程序語(yǔ)法語(yǔ)義分析程序代碼生成程序PL/0源程序目標(biāo)程序表格管理程序出錯(cuò)處理程序42可編輯課件PPT

4.前端與后端:概念上講,編譯程序的五個(gè)階段可進(jìn)一步劃分為前端和后端:前端:主要由與源語(yǔ)言有關(guān)而與目標(biāo)機(jī)無(wú)關(guān)的部分組成,包括詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼產(chǎn)生。代碼優(yōu)化一般也包含在前端。后端:主要由與目標(biāo)機(jī)有關(guān)的部分組成,包括目標(biāo)代碼生成和與目標(biāo)機(jī)有關(guān)的優(yōu)化等。43可編輯課件PPT源程序詞法分析語(yǔ)法分析語(yǔ)義分析和中間代碼產(chǎn)生中間語(yǔ)言中間代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼優(yōu)化目標(biāo)語(yǔ)言前端后端44可編輯課件PPT劃分前端和后端,就可以?xún)H改寫(xiě)后端而生成不同目標(biāo)機(jī)上的目標(biāo)程序,當(dāng)然也可考慮對(duì)不同語(yǔ)言?xún)H稍加改變前端而產(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ī)代碼——Bytecode中間語(yǔ)言,都是定義良好的中間語(yǔ)言。45可編輯課件PPTJava的傳統(tǒng)環(huán)境Java源程序(.java)編譯環(huán)境Java編譯器Java字節(jié)碼(.class)Java字節(jié)碼(本地或網(wǎng)絡(luò)傳輸)運(yùn)行環(huán)境類(lèi)加載程序字節(jié)碼驗(yàn)證Java類(lèi)庫(kù)Java解釋器即時(shí)編譯器Java虛擬機(jī)硬件46可編輯課件PPT5.表格與表格管理表格記錄源程序中的各類(lèi)有用信息——名字、函數(shù)、標(biāo)號(hào)、過(guò)程、數(shù)值等每個(gè)階段的工作都要與表格打交道:查、填、改等表格的結(jié)構(gòu)與處理方法:統(tǒng)一的大表與分類(lèi)的小表統(tǒng)一大表名字欄為主欄(關(guān)鍵字欄),信息欄又分成若干子欄——種屬、類(lèi)型等47可編輯課件PPT分類(lèi)小表:每類(lèi)一張表,如:符號(hào)名表(SNT)

常數(shù)表(CT)

48可編輯課件PPT入口表(ENT)

標(biāo)號(hào)表(LBT)

基本字表(KWT)49可編輯課件PPT6.出錯(cuò)處理:這是編譯程序的又一重要組成部分,因?yàn)榫幾g的各個(gè)階段都有可能發(fā)現(xiàn)源程序中的錯(cuò)誤。一旦發(fā)現(xiàn)這樣或那樣的錯(cuò)誤,就應(yīng)把錯(cuò)誤的性質(zhì)及位置報(bào)告給用戶,并且使編譯能繼續(xù)下去。

思考:如何準(zhǔn)確地報(bào)告錯(cuò)誤如何從錯(cuò)誤中恢復(fù)過(guò)來(lái)50可編輯課件PPT四、編譯程序的構(gòu)造過(guò)程1.需求分析,確定語(yǔ)言文本(1)確定語(yǔ)言的種類(lèi):

按語(yǔ)言范型分類(lèi),當(dāng)今大多數(shù)程序語(yǔ)言可分為四類(lèi):過(guò)程式(強(qiáng)制式語(yǔ)言):命令驅(qū)動(dòng),面向語(yǔ)句,如FORTRAN、PASCAL、Ada及C等函數(shù)式(應(yīng)用式)語(yǔ)言:功能驅(qū)動(dòng),面向函數(shù),如LISP、SNOBOL及ML等邏輯式(基于規(guī)則的)語(yǔ)言:依據(jù)條件進(jìn)行邏輯推演,如Prolog等OO語(yǔ)言:支持封裝性、繼承性、多態(tài)性及動(dòng)態(tài)聚束等,以對(duì)象為運(yùn)行單位,如Smalltalk、Java、C++等51可編輯課件PPT

通過(guò)用戶提供的應(yīng)用范圍,決定采用何種語(yǔ)言。例如:偏重于科學(xué)計(jì)算的則選用Fortran;偏重于符號(hào)處理的則選用Lisp或Snobol;偏重于事務(wù)處理的則選用Cobol或數(shù)據(jù)庫(kù)管理語(yǔ)言;

……52可編輯課件PPT(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)談的:

·語(yǔ)法規(guī)則:用于形成和產(chǎn)生一個(gè)正確的程序的一組規(guī)則。

·語(yǔ)義規(guī)則:用于定義程序意義的一組規(guī)則。53可編輯課件PPT例如:從語(yǔ)法的角度看,標(biāo)識(shí)符和名字是一個(gè)東西,都是以字母開(kāi)頭的字母數(shù)字串;但從語(yǔ)義的角度看,標(biāo)識(shí)符是一個(gè)沒(méi)有任何意義的字符序列,而名字卻有確定的意義和屬性,而且具有一定的作用域和定義域,即有局部和全部之分。又如:程序從語(yǔ)法角度看,是一些語(yǔ)法范疇構(gòu)成的如下層次結(jié)構(gòu):54可編輯課件PPT程序分程序或子程序(過(guò)程、函數(shù)等)語(yǔ)句表達(dá)式數(shù)據(jù)引用算符函數(shù)調(diào)用而從語(yǔ)義的角度來(lái)說(shuō),程序是描述一定的數(shù)據(jù)結(jié)構(gòu)及其處理過(guò)程。55可編輯課件PPT②程序結(jié)構(gòu):現(xiàn)代高級(jí)語(yǔ)言程序通常由若干子程序段(過(guò)程、函數(shù)等)構(gòu)成,許多語(yǔ)言還引入了類(lèi)、程序包等更高級(jí)的結(jié)構(gòu)。例如,F(xiàn)ortran、C程序是塊結(jié)構(gòu)的;Pascal程序是過(guò)程嵌套的;Algol既有分程序嵌套,又有過(guò)程嵌套;Java與C++是面向?qū)ο蟮?,它們很重要的方面是?lèi)和繼承的概念,同時(shí)支持多態(tài)性和動(dòng)態(tài)聚束等特性;而在Ada中引入了程序包,它可以把數(shù)據(jù)和操作代碼封裝在一起,支持?jǐn)?shù)據(jù)抽象。(詳見(jiàn)教材P15-18)56可編輯課件PPT③語(yǔ)言的基本成分:包括數(shù)據(jù)類(lèi)型、表達(dá)式、語(yǔ)句、過(guò)程或函數(shù)等,這些在學(xué)習(xí)語(yǔ)言課時(shí)都已經(jīng)學(xué)過(guò)了,但從編譯的角度出發(fā),應(yīng)如何了解這些基本成分呢?

·初等數(shù)據(jù)類(lèi)型:牽扯到存儲(chǔ)空間的問(wèn)題;

·結(jié)構(gòu)數(shù)據(jù)類(lèi)型:牽扯到下標(biāo)、維數(shù)、存放方式、分配時(shí)間----動(dòng)態(tài)與靜態(tài)等;

·表達(dá)式:牽扯到運(yùn)算分量、運(yùn)算符、形成規(guī)則、運(yùn)算順序等;

·語(yǔ)句:順序、控制、循環(huán)等;

·過(guò)程與參數(shù)傳遞:傳地址、傳值、傳名、得結(jié)果等;

·存儲(chǔ)管理:靜態(tài)存儲(chǔ)分配、動(dòng)態(tài)存儲(chǔ)分配;57可編輯課件PPT2.由程序設(shè)計(jì)環(huán)境確定編譯程序構(gòu)造的方式和方法最早是直接使用機(jī)器語(yǔ)言或匯編語(yǔ)言現(xiàn)在一般使用高級(jí)語(yǔ)言Pascal或C語(yǔ)言

好處:編譯方式還是解釋方式便于閱讀、理解和移植提高程序設(shè)計(jì)效率易于查錯(cuò)和修改58可編輯課件PPT任何一個(gè)編譯程序至少要涉及三種語(yǔ)言:源語(yǔ)言(S)、目標(biāo)語(yǔ)言(T)和編譯程序?qū)崿F(xiàn)語(yǔ)言(I),可用如下T型圖來(lái)表示三者之間的關(guān)系:59可編輯課件PPT如若A機(jī)上已經(jīng)有了一個(gè)用A機(jī)器語(yǔ)言(稱(chēng)A代碼)實(shí)現(xiàn)的C語(yǔ)言編譯程序,則可用C語(yǔ)言作為工具編寫(xiě)Ada語(yǔ)言的編譯程序。這樣Ada語(yǔ)言的編譯程序經(jīng)過(guò)C語(yǔ)言編譯程序編譯后就可得到A代碼的Ada語(yǔ)言編譯程序??蓤D示如下:60可編輯課件PPT現(xiàn)在常用構(gòu)造編譯程序的方式除高級(jí)語(yǔ)言實(shí)現(xiàn)外,經(jīng)常還用:自展(自編譯):類(lèi)似于滾雪球。先確定一個(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ā)工作量。61可編輯課件PPT交叉編譯:在機(jī)器A上產(chǎn)生機(jī)器B的目標(biāo)代碼,這種編譯程序稱(chēng)為交叉編譯。這兒A稱(chēng)宿主機(jī),B稱(chēng)為目標(biāo)機(jī)。這種情況一般是宿主機(jī)上有豐富的工具軟件,而B(niǎo)機(jī)上沒(méi)有任何高級(jí)語(yǔ)言可用。圖示為:62可編輯課件PPT移植:如果一個(gè)程序能比較容易地從一臺(tái)機(jī)器上搬到另一臺(tái)機(jī)器上運(yùn)行,則稱(chēng)其為可移植的,移植一個(gè)程序的工作量要遠(yuǎn)小于開(kāi)發(fā)它的工作量才有意義。

顯然一個(gè)編譯程序要可移植,則其前端與后端的界面要清晰、簡(jiǎn)單,這樣僅需改寫(xiě)后端即可。改寫(xiě)后亦可通過(guò)交叉編譯的方法得到。63可編輯課件PPT編譯程序生成器:根據(jù)語(yǔ)言要求、設(shè)計(jì)實(shí)現(xiàn)的算法,能自動(dòng)產(chǎn)生編譯程序的工具軟件??蓤D示為:64可編輯課件PPT3.確定編譯方法:本課程要介紹若干方法,但不可能全采用,只能根據(jù)語(yǔ)言特點(diǎn)采用其中一種或二種4.總體設(shè)計(jì):分不分遍、分幾遍、前端與后端接口并畫(huà)出總框5.詳細(xì)設(shè)計(jì):進(jìn)一步細(xì)劃總框6.實(shí)現(xiàn)及調(diào)試:采用何種方式實(shí)現(xiàn)、分調(diào)與連調(diào)等65可編輯課件PPT本節(jié)目的:為語(yǔ)言的語(yǔ)法描述尋求形式化工具

工具就是對(duì)程序設(shè)計(jì)語(yǔ)言給出精確無(wú)二義的語(yǔ)法描述。(嚴(yán)謹(jǐn)、簡(jiǎn)潔、易讀)形式化工具就是將形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)?!靶问健笔侵高@樣的事實(shí):語(yǔ)言的所有規(guī)則是以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳述。

§3.高級(jí)語(yǔ)言的語(yǔ)法描述66可編輯課件PPT本節(jié)主要內(nèi)容

預(yù)備知識(shí)

上下文無(wú)關(guān)文法及其語(yǔ)言的形式定義

文法的等價(jià)性

語(yǔ)法樹(shù)及文法二義性

文法的類(lèi)型

語(yǔ)法分析的一些思考67可編輯課件PPT一、預(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ǔ)。例如:68可編輯課件PPT“我是大學(xué)生”是漢語(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)串代替,于是表示成:69可編輯課件PPT

〈句子〉

〈主語(yǔ)〉〈謂語(yǔ)〉

然后在得到的串〈主語(yǔ)〉〈謂語(yǔ)〉中,選取〈主語(yǔ)〉或〈謂語(yǔ)〉,再用相應(yīng)規(guī)則的∷=右端代替之。比如,選取了〈主語(yǔ)〉,并采用規(guī)則〈主語(yǔ)〉∷=〈代詞〉,那么得到:

〈主語(yǔ)〉〈謂語(yǔ)〉

〈代詞〉〈謂語(yǔ)〉

依此類(lèi)推,句子“我是大學(xué)生”的全部導(dǎo)出過(guò)程是:

〈句子〉

〈主語(yǔ)〉〈謂語(yǔ)〉

〈代詞〉〈謂語(yǔ)〉

我〈謂語(yǔ)〉

我〈動(dòng)詞〉〈直接賓語(yǔ)〉

我是〈直接賓語(yǔ)〉

我是〈名詞〉

我是大學(xué)生70可編輯課件PPT“我是大學(xué)生”的構(gòu)成符合上述規(guī)則,而“我大學(xué)生是”不符合上述規(guī)則,我們說(shuō)它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)。換句話說(shuō),這些規(guī)則看成是一種元語(yǔ)言,用它描述漢語(yǔ),僅僅涉及漢語(yǔ)句子的結(jié)構(gòu)描述。這里“

”讀作“導(dǎo)出”或“派生出”。而“::=”(通常又簡(jiǎn)記為“→”)讀作“定義為”或“由…組成”,而每一條規(guī)則又稱(chēng)作是產(chǎn)生式或重寫(xiě)式。這樣的一種描述形式就稱(chēng)作是BNF(Backus-NaurForm)。71可編輯課件PPT例:賦值表達(dá)式可描述為

<賦值表達(dá)式>→<左部>=<右部><左部>→<標(biāo)識(shí)符><右部>→<表達(dá)式><表達(dá)式>→<表達(dá)式><算符><表達(dá)式><表達(dá)式>→<標(biāo)識(shí)符>|<常數(shù)><標(biāo)識(shí)符>→a1|b123|salary|stu_age

<常數(shù)>→18|123|4.5|<算符>→+|-|*|/72可編輯課件PPT2.語(yǔ)言概述語(yǔ)言是由句子組成的集合。漢語(yǔ)--所有符合漢語(yǔ)語(yǔ)法的句子的全體。英語(yǔ)--所有符合英語(yǔ)語(yǔ)法的句子的全體。程序設(shè)計(jì)語(yǔ)言--所有符合該語(yǔ)言語(yǔ)法的程序的全體。

每個(gè)句子構(gòu)成的規(guī)則研究語(yǔ)言每個(gè)句子的含義每個(gè)句子和使用者的關(guān)系73可編輯課件PPT研究程序設(shè)計(jì)語(yǔ)言每個(gè)程序構(gòu)成的規(guī)則每個(gè)程序的含義每個(gè)程序和使用者的關(guān)系語(yǔ)言研究的三個(gè)方面:

語(yǔ)法(Syntax)--表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的組合規(guī)則語(yǔ)義(Semantics)--表示各個(gè)記號(hào)的特定含義。(各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系)語(yǔ)用(Pragmatics)--表示在各個(gè)記號(hào)所出現(xiàn)的行為中,它們的來(lái)源、使用和影響。74可編輯課件PPT每種語(yǔ)言具有兩個(gè)可識(shí)別的特性,即語(yǔ)言的形式和該形式相關(guān)聯(lián)的意義。語(yǔ)言的實(shí)例若在語(yǔ)法上是正確的,其相關(guān)聯(lián)的意義可以從兩個(gè)觀點(diǎn)來(lái)看,其一是該句子的創(chuàng)立者所想要表示的意義,另一是接收者所檢驗(yàn)到的意義。這兩個(gè)意義并非總是一樣的,前者稱(chēng)為語(yǔ)言的語(yǔ)義,后者是其語(yǔ)用意義。幽默、雙關(guān)語(yǔ)和謎語(yǔ)就是利用這兩方面意義間的差異。75可編輯課件PPT如果不考慮語(yǔ)義和語(yǔ)用,即只從語(yǔ)法這一側(cè)面來(lái)看語(yǔ)言,這種意義下的語(yǔ)言稱(chēng)作形式語(yǔ)言。形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)。該數(shù)學(xué)系統(tǒng)稱(chēng)為文法?!靶问健笔侵高@樣的事實(shí):語(yǔ)言的所有規(guī)則描述什麼符號(hào)串以什么方式出現(xiàn)。形式語(yǔ)言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究,是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的基礎(chǔ)。76可編輯課件PPT3.有關(guān)定義和記號(hào)—回顧符號(hào):可以相互區(qū)別的記號(hào)(元素)。字母表

:符號(hào)(元素)的非空有窮集合。符號(hào)串(字):由字母表

中的符號(hào)組成的任何有窮序列稱(chēng)為該字母表上的符號(hào)串。

①空字ε(沒(méi)有符號(hào)的符號(hào)串)是

上的符號(hào)串;

②若x是

上的符號(hào)串,a是

的元素,則xa是

上的符號(hào)串;

③y是

上的符號(hào)串,當(dāng)且僅當(dāng)它可以由①和②導(dǎo)出。

例如:Σ={a,b}ε,a,b,aa,ab,aabba…都是

上的符號(hào)串77可編輯課件PPT符號(hào)串s的前綴:符號(hào)串s的任何首部。如:ε、b、ba、…都是符號(hào)串banana的前綴.符號(hào)串s的后綴:符號(hào)串s的任何尾部。如:ε、a、na、…都是符號(hào)串banana的后綴.符號(hào)串s的子串:從s中刪去一個(gè)前綴和一個(gè)后綴得到的符號(hào)串.如:ana是符號(hào)串banana的一個(gè)子串.符號(hào)串s的真前綴:x≠s且x≠ε的任何前綴x。s的真后綴,真子串可以類(lèi)似地定義。78可編輯課件PPT符號(hào)串的運(yùn)算:

符號(hào)串的長(zhǎng)度:符號(hào)串中符號(hào)的個(gè)數(shù).符號(hào)串s的長(zhǎng)度記為|s|。ε的長(zhǎng)度為0連接:符號(hào)串x、y的連接,是把y的符號(hào)寫(xiě)在x的符號(hào)之后得到的符號(hào)串xy

如x=ab,y=cd則xy=abcd

又如εa=aε方冪:符號(hào)串自身連接n次得到的符號(hào)串

an定義為aa……aan個(gè)aa0=ε,a1=a,a2=aa…79可編輯課件PPT符號(hào)串集合:若集合A中所有元素都是某字母表

上的符號(hào)串,則稱(chēng)A為字母表

上的符號(hào)串集合。符號(hào)串集合A和B的乘積:

AB=xy|xA且yB若集合A=ab,cdeB=0,1則AB=ab1,ab0,cde0,cde1Σ的閉包:

上的一切符號(hào)串(包括ε)組成的集合,記為

*

。Σ的正閉包:

上的除ε外的所有符號(hào)串組成的集合,記為

+

。80可編輯課件PPT例:Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}

81可編輯課件PPT語(yǔ)言:由句子構(gòu)成的集合。換言之,字母表上的一個(gè)語(yǔ)言是

上的一些符號(hào)串的集合(字母表上的每個(gè)語(yǔ)言是*的一個(gè)子集)。例如:字母表Σ={a,b},Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}

集合{ab,aabb,aaabbb,…,anbn,…}或表示為{w|w∈Σ*且w=anbn,n≥1}為字母表上的一個(gè)語(yǔ)言。

集合{a,aa,aaa,…}或表示為{w|w∈Σ*且w=an,n≥1}為字母表上的一個(gè)語(yǔ)言。

ε

是一個(gè)語(yǔ)言,即也是一個(gè)語(yǔ)言。82可編輯課件PPT二、上下文無(wú)關(guān)文法及其語(yǔ)言的形式定義1.如何來(lái)描述一種語(yǔ)言?如果語(yǔ)言是有窮的(只含有有窮多個(gè)句子),可以將句子逐一列出來(lái)表示;如果語(yǔ)言是無(wú)窮的,找出語(yǔ)言的有窮表示。語(yǔ)言的有窮表示有兩個(gè)途徑:生成方式:語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造。識(shí)別方式:用一個(gè)過(guò)程,當(dāng)輸入的一任意串屬于語(yǔ)言時(shí),該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是”,若不屬于,要麼能停止并回答“不是”,要麼永遠(yuǎn)繼續(xù)下去。83可編輯課件PPT

文法是從生成方式描述語(yǔ)言的,而自動(dòng)機(jī)則是從識(shí)別的角度來(lái)描述語(yǔ)言的。本節(jié)僅介紹有關(guān)文法的概念。前面關(guān)于“我是大學(xué)生”及“賦值表達(dá)式”的例子中,涉及到如下的概念:<...>所表示的是一個(gè)類(lèi)概念,通常稱(chēng)作語(yǔ)法范疇或語(yǔ)法變量,如果用一個(gè)符號(hào)來(lái)代替,也稱(chēng)為非終結(jié)符(nonterminal)。所有規(guī)則中的非終結(jié)符構(gòu)成了一個(gè)非空有窮集,記為VN。上述兩例中的“句子”及“賦值表達(dá)式”顯然是最大的語(yǔ)法范疇,也是我們最感興趣的非終結(jié)符,通常稱(chēng)作開(kāi)始符號(hào),記為S?!按髮W(xué)生”、“我”、“是”、“a”、“+”等表示的是一個(gè)具體概念,用一個(gè)符號(hào)來(lái)表示,則稱(chēng)為終結(jié)符(terminal)。所有這樣的符號(hào)同樣構(gòu)成了一個(gè)非空有窮集,記為VT。<代詞>→我、<數(shù)字>→8等稱(chēng)作產(chǎn)生式(production)。所有產(chǎn)生式的集合顯然是有窮的,記為P。這樣我們可以將文法抽象為如下的一個(gè)數(shù)學(xué)系統(tǒng):84可編輯課件PPT2.文法的形式定義一個(gè)文法G定義為一個(gè)四元式(VN,VT,S,

P)其中:VN為非終結(jié)符號(hào)的非空有窮集;VT為終結(jié)符號(hào)的非空有窮集,VN∩

VT=φ;P為產(chǎn)生式的集合;產(chǎn)生式也稱(chēng)重寫(xiě)規(guī)則或生成式,形如A→α,其中:A∈VN,α∈(VN∪

VT)*。A稱(chēng)為產(chǎn)生式的左部,α稱(chēng)作產(chǎn)生式的右部。

S稱(chēng)作識(shí)別符號(hào)或開(kāi)始符號(hào),S∈VN且至少要在一條產(chǎn)生式中作為左部出現(xiàn)。

VN∪

VT中的符號(hào)統(tǒng)稱(chēng)為文法符號(hào)。85可編輯課件PPT例1文法G=(VN,VT,S,P) VN={S},VT={0,1} P={S→0S1,S→01} S為開(kāi)始符號(hào)例2文法G=(VN,VT,S,P) VN={<標(biāo)識(shí)符>,<字母>,<數(shù)字>} VT={a,b,c,…x,y,z,0,1,…,9} P={<標(biāo)識(shí)符>→<字母>, <標(biāo)識(shí)符>→<標(biāo)識(shí)符><字母>, <標(biāo)識(shí)符>→<標(biāo)識(shí)符><數(shù)字>,<字母>→a,…,<字母>→z,<數(shù)字>→0,…,

<數(shù)字>→9} S=<標(biāo)識(shí)符>86可編輯課件PPT

文法的寫(xiě)法

①.G:S→aAb

A→abA→aAb

A→ε

②.G[S]:S→aSbA→abA→aAbA→ε③.G[S]:S→aSbA→ab|aAb|ε

元符號(hào):→∷=|<>

習(xí)慣表示:大寫(xiě)英文字母:非終結(jié)符/集合字母表中靠前的小寫(xiě)英文字母:終結(jié)符字母表中靠后的小寫(xiě)英文字母:字符串87可編輯課件PPT上下文無(wú)關(guān)文法:它所定義的語(yǔ)法范疇是完全獨(dú)立于這種范疇所能出現(xiàn)的環(huán)境。程序設(shè)計(jì)語(yǔ)言的詞:a+b/3a1<a2…自然語(yǔ)言的詞:丟了錢(qián),他很難過(guò)。我家門(mén)前的溝很難過(guò)去。有誰(shuí)不愿意跟我走,我就讓他跟你走!上下文無(wú)關(guān)文法不能完整地表述自然語(yǔ)言,但對(duì)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō),大多數(shù)情況下都可以準(zhǔn)確表述。因此,我們只關(guān)注上下文無(wú)關(guān)文法(Context-FreeGrammar,CFG)。其實(shí),前面給出的定義,就是CFG的形式定義。文法的范疇更廣一些。88可編輯課件PPT3.推導(dǎo)與規(guī)約(1)直接推導(dǎo)“”A→γ是文法G的產(chǎn)生式,若有v,w滿足:v=αAβ,w=αγβ,其中α,β∈(VN∪VT)*則稱(chēng)v直接推導(dǎo)出w,記作v

w;也稱(chēng)w直接歸約到v,就是說(shuō)歸約是推導(dǎo)的逆過(guò)程。例:G:S→0S1,S→01

0S100S1100S11000S111000S11100001111S0S189可編輯課件PPT(2)推導(dǎo)若存在v=w0w1...wn=w,(n>0),則記為

v+w,v推導(dǎo)出w,或w歸約到v。若有v+w,或v=w,則記為v*w。例:G:S→0S1,S→01S0S10S100S1100S11000S111000S11100001111S0S100S11000S11100001111S

+00001111S

*S00S11

*00S1190可編輯課件PPT(3)最左(最右)推導(dǎo)最左(最右)推導(dǎo):在推導(dǎo)的任何一步α

β,都是對(duì)α中的最左(右)非終結(jié)符進(jìn)行替換。最右推導(dǎo)被稱(chēng)為規(guī)范推導(dǎo)。也就是說(shuō),規(guī)范推導(dǎo)具有最右性。規(guī)范推導(dǎo)的逆過(guò)程稱(chēng)為規(guī)范規(guī)約。也就是說(shuō),規(guī)范規(guī)約具有最左性。由規(guī)范推導(dǎo)所得的句型稱(chēng)為規(guī)范句型。91可編輯課件PPT4.句型、句子句型:有文法G,若S

*x,x∈(VN∪VT)*,則稱(chēng)x是文法G的句型。句子:有文法G,若S

*x,且x∈VT*,則稱(chēng)x是文法G的句子。例1:G:S→0S1,S→01S0S100S11000S11100001111G的句型:S,0S1,00S11,000S111,00001111G的句子:00001111,0192可編輯課件PPT例2:G[E]:E→E+T|T

T→T*F|F

F→(E)|a

這個(gè)文法都能推導(dǎo)出什么句子?

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a用符號(hào)a,+,*,(和)構(gòu)成的算術(shù)表達(dá)式思考:寫(xiě)出一個(gè)不同的文法,同樣能夠產(chǎn)生這些句子93可編輯課件PPT5.語(yǔ)言的定義

由文法G生成的語(yǔ)言記為L(zhǎng)(G),它是文法G的所有句子的集合。

L(G)={x|S

+x,S為開(kāi)始符號(hào),且x∈VT*}

例1G:S→0S1,S→01L(G)={0n1n|n≥1}

例2文法G[S]: (1)S→aSBE

(2)S→aBE

(3)EB→BE

(4)aB→ab

(5)bB→bb

(6)bE→be

(7)eE→ee

L(G)={anbnen|n≥1}這個(gè)文法生成什么語(yǔ)言?這個(gè)文法與前面見(jiàn)過(guò)的文法有什么不同?94可編輯課件PPTS

aSBE(S→aSBE)

aaBEBE(S→aBE)

aabEBE (aB→ab)

aabBEE (EB→BE)

aabbEE (bB→bb)

aabbeE (bE→be)

aabbee (eE→ee)類(lèi)似推導(dǎo)可以看出a,b,e在句子中出現(xiàn)的順序及個(gè)數(shù)滿足L(G)當(dāng)然要進(jìn)一步說(shuō)明:

G生成的每個(gè)句子都在L(G)中L(G)中的每個(gè)句子確實(shí)能被G生成95可編輯課件PPT使用產(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。然后從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ì)于n≥1,串a(chǎn)nbnen是唯一形式的終結(jié)符號(hào)串。96可編輯課件PPT三、文法的等價(jià)性1.定義:若L(G1)=L(G2),則稱(chēng)文法G1和G2是等價(jià)的。如文法G1[A]:A→0R與G2[S]:S→0S1等價(jià)

A→01S→01R→A1因?yàn)長(zhǎng)(G1)=L(G2)={0n1n∣n≥1}。97可編輯課件PPT2.關(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:E→E+E∣E*E∣(E)∣iG2:S→EE→E+E∣E*E∣(E)∣i

具體做法:加一條單個(gè)非產(chǎn)生式S→E即可。(2)對(duì)任一文法G1都可以構(gòu)造文法G2,使得L(G1)=L(G2),但G2的每個(gè)非終結(jié)符都能導(dǎo)出一個(gè)終結(jié)符號(hào)串。可給出如下證明:98可編輯課件PPT證明:①令β={A∣A→t∈G1&t∈VT+};②遞歸擴(kuò)充:β=β∪{W∣W→x&x∈(VT∪β)+}由于G1的非終結(jié)符號(hào)是有窮的,上述過(guò)程一定是收斂的;③從G1的VN中刪除不包含在β中的非終結(jié)符,并從其產(chǎn)生式集中刪除其左部或右部中包含不屬于β中的符號(hào)的產(chǎn)生式,這樣得到的文法即為所要的G2。99可編輯課件PPT例:G1[A]:A→Bed∣dDB→bD→Ea∣AD∣DBE→Da∣Eb①β={B}②β={B}∪{A}={A,B},到此為止;于是D,E及相關(guān)D,E的產(chǎn)生式均可刪除,得到:G2[A]:A→BedB→b可以證明L(G1)=L(G2)。類(lèi)似還可以給出如下定理:(3)對(duì)任一文法G1都可以構(gòu)造文法G2,使得L(G1)=L(G2),但G2的每個(gè)非終結(jié)符都出現(xiàn)在某一句型中。證明?100可編輯課件PPT(4)對(duì)任一文法G1都可以構(gòu)造文法G2,使得L(G1)=L(G2),但G2中不含單個(gè)非產(chǎn)生式。如:G1[A]:A→B∣dDG2[A]:A→dD∣b∣c

B→A∣C∣bD→d∣Da

C→B∣c

D→d∣Da(5)對(duì)任一文法G1都可以構(gòu)造文法G2,使得L(G1)=L(G2),但G2中不含空產(chǎn)生式。形如E→ε的產(chǎn)生式稱(chēng)為空產(chǎn)生式。(6)對(duì)任一文法G1都可以構(gòu)造文法G2,使得L(G1)=L(G2),但G2中不含有左遞歸。形如E→E+T的產(chǎn)生式稱(chēng)為左遞歸的。遞歸哪里去了101可編輯課件PPT四、語(yǔ)法樹(shù)和文法二義性

1.語(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)間都有一條連線。于是,可給出如下的定義:102可編輯課件PPT設(shè)G=(VN,VT,S,P)為一CFG,若一棵樹(shù)滿足下列4個(gè)條件,則此樹(shù)稱(chēng)作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,則肯定A∈VN4.如果結(jié)點(diǎn)n有標(biāo)記A,其直接子孫結(jié)點(diǎn)從左到右的次序是n1,n2,…,nk,其標(biāo)記分別為A1,A2,…,Ak,那么A→A1A2,…,Ak一定是P中的一個(gè)產(chǎn)生式語(yǔ)法樹(shù)的結(jié)果:從左到右讀出葉子的標(biāo)記而構(gòu)成的串謂之句型。103可編輯課件PPT給定文法G=(VN,VT,P,S),對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)(推導(dǎo)樹(shù))。定理:G為上下文無(wú)關(guān)文法, 對(duì)于α≠ε,有S

*

α,當(dāng)且僅當(dāng) 文法G有以α為結(jié)果的一棵語(yǔ)法樹(shù)(推導(dǎo)樹(shù))這里對(duì)該定理不作證明。104可編輯課件PPT例如:文法G[E]:

E→E+E∣E*E∣(E)∣i

顯然(i+i)*i是該文法產(chǎn)生的一個(gè)句子,它的推導(dǎo)過(guò)程可以用右邊的語(yǔ)法樹(shù)來(lái)描述。

子樹(shù)與簡(jiǎn)單子樹(shù)

只有單層分支的子樹(shù)代次21345EE*E(E)E+Eiii105可編輯課件PPT

在一棵語(yǔ)法樹(shù)生長(zhǎng)過(guò)程中的任何時(shí)刻,所有葉結(jié)點(diǎn)從左到右依次排列起來(lái)就是一個(gè)句型。這就是說(shuō),一棵語(yǔ)法樹(shù)表示了一個(gè)句型種種可能的(但未必是所有的)不同推導(dǎo)過(guò)程,包括最左(最右)推導(dǎo)。如果我們堅(jiān)持使用最左(最右)推導(dǎo),那么一棵語(yǔ)法樹(shù)就完全等價(jià)于一個(gè)最左(最右)推導(dǎo)。106可編輯課件PPT文法G[E]:

E→i E→E+E E→E*E E→(E)EE+EE*EiiiEE*EiE+Eii句型i*i+i的兩個(gè)不同的最左推導(dǎo):推導(dǎo)1:EE+EE*E+Ei*E+Ei*i+Ei*i+i推導(dǎo)2:EE*Ei*Ei*E+Ei*i+Ei*i+i

但是,一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢?一個(gè)句型是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?不盡然。試看下例:107可編輯課件PPT2.文法二義性

若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù),則稱(chēng)這個(gè)文法是二義的;或者,若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左(右)推導(dǎo),則稱(chēng)這個(gè)文法是二義的。顯然,上例中的文法就是一個(gè)二義文法。

108可編輯課件PPT3.二義性問(wèn)題是不可判定的

不能設(shè)計(jì)一個(gè)算法,在有窮的步驟內(nèi)確切地判定一個(gè)文法是否為二義性的。因此,我們所能做的工作只能是為二義性尋找一組充分(而非必要)條件來(lái)改造二義性文法。例如對(duì)前面提到的二義性文法G(E):E→E+E∣E*E∣(E)∣i

可將其改造為如下無(wú)二義文法G′:

G′(E):E→T∣E+TT→F∣T*FF→i∣(E)如此改造,所依何據(jù)??jī)?yōu)先級(jí)&結(jié)合規(guī)則109可編輯課件PPT以代數(shù)運(yùn)算為例,說(shuō)明操作符的:結(jié)合規(guī)則左結(jié)合:當(dāng)一個(gè)操作數(shù)的左右兩側(cè)都有+時(shí),它將被左側(cè)的+使用。4+5+9=(4+5)+9右結(jié)合:523=58優(yōu)先級(jí)優(yōu)先級(jí)表左結(jié)合:+-左結(jié)合:*/右結(jié)合:冪110可編輯課件PPT

注意:文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G′,L(G)=L(G′),其中G是二義的,但是G′卻是無(wú)二義的。上面的例子很好地說(shuō)明了這一點(diǎn)。如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的,則說(shuō)此語(yǔ)言是先天二義的。對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō),常常希望它的文法是無(wú)二義的,因?yàn)橄M麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。111可編輯課件PPT

語(yǔ)法樹(shù)是了解句子語(yǔ)法結(jié)構(gòu)的一種輔助工具,也是語(yǔ)法分析的輔助工具,因此又稱(chēng)為語(yǔ)法分析樹(shù)。這樣一來(lái),就存在著自上而下和自下而上兩種分析方法?!鲈谧陨隙碌姆治龇椒ㄖ腥绾芜x擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)? 假定要被代換的最左非終結(jié)符號(hào)是B,且有n條規(guī)則:B→A1|A2|…|An,那么如何確定用哪個(gè)右部去替代B?■在自下而上的分析方法中如何識(shí)別可歸約的串? 在分析程序工作的每一步,都是從當(dāng)前串中選擇一個(gè)子串,將它歸約到某個(gè)非終結(jié)符號(hào),該子串稱(chēng)為“可歸約串”。

結(jié)合前面的例子

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論