《編譯原理》第,章概述及高級語言課件

1、編譯原理,聯(lián)系方式：電 話： e-Mail: caos,1,PPT學(xué)習(xí)交流,C語言程序,void main( ) int x,y,z; x=3; y=2; z=x+y; , mov ax,3 mov x,ax mov ax,2 mov y,ax mov ax,x mov bx,y add ax,bx mov z,ax .,匯編語言程序,300 302 304 306 308 ,2,PPT學(xué)習(xí)交流,為什么要學(xué)習(xí)編譯原理？,更深刻地理解與運(yùn)用高級程序設(shè)計(jì)語言。 大型程序設(shè)計(jì)與軟件工程的經(jīng)典實(shí)例。 理論與實(shí)踐相結(jié)合的典范。 為解決實(shí)際問題提供一種新的有效途徑,3,PPT學(xué)習(xí)交流,語言種類 Progr

2、amming languages Scripts Domain-specific languages SQL, HTML, XML,4,PPT學(xué)習(xí)交流,語言參與者,5,PPT學(xué)習(xí)交流,學(xué)習(xí)本課程的目的和任務(wù),加深對編程語言設(shè)計(jì)和實(shí)現(xiàn)的理解，對和編程語言有關(guān)的理論有所了解，對宏觀上把握編程語言來說，起一個奠基的作用，提升自身的編程能力 掌握編譯程序的基本結(jié)構(gòu)，掌握常用的編譯技術(shù)和方法，將編譯原理的理論和方法應(yīng)用于一般的軟件設(shè)計(jì)中 培養(yǎng)團(tuán)隊(duì)協(xié)作能力,6,PPT學(xué)習(xí)交流,本課程的特點(diǎn),(1) 本課程理論性很強(qiáng)，學(xué)習(xí)時(shí)需要很強(qiáng)的邏輯思維能力 (2) 涉及的算法復(fù)雜，要深入地理解這些算法很困難 (3)

3、整個編譯程序的構(gòu)造方法非常精妙，就像一部走時(shí)精確的時(shí)鐘，很多齒輪、部件協(xié)調(diào)地運(yùn)轉(zhuǎn)，以驅(qū)動指針準(zhǔn)確地旋轉(zhuǎn)；編譯程序也是如此，一邊掃描源程序，一邊經(jīng)過各個部件的運(yùn)算，準(zhǔn)確地輸出為目標(biāo)語言。 (4) 編譯原理課程各個部分之間的獨(dú)立性很強(qiáng)，包括詞法分析、語法分析、存儲的組織與分配、中間語言、語法制導(dǎo)翻譯、代碼生成與優(yōu)化這幾大部分。詞法分析和語法分析是其中的重點(diǎn)，語言分析也是難點(diǎn)，需要掌握比較復(fù)雜的算法邏輯；其他部分相對來說知識性更強(qiáng)一些。各部分之間的方法也互相獨(dú)立，在學(xué)習(xí)時(shí)，便于逐個擊破。 (5) 考試考查的內(nèi)容相對來說是很穩(wěn)定的，絕大多數(shù)題目的解法都非常機(jī)械。,7,PPT學(xué)習(xí)交流,學(xué)習(xí)方法,(1)

4、盡可能地掌握編譯原理的思想，要站得高一點(diǎn)，盡可能理解算法的思想，而不是背固定的算法。應(yīng)該盡力理解為什么要這樣做，逐漸在頭腦中建立起編譯器的整體概念，而不是零零散散的一些算法。 (2) 很多題目的解法比較固定，要熟練掌握相應(yīng)的具體方法。 (3) 多做習(xí)題, 對于編譯這樣的學(xué)科，題目的規(guī)模很大，步驟繁多，而且前面的步驟一旦出錯，后面都錯。 (4) 要扎扎實(shí)實(shí)地牢記重要算法，配合大量的習(xí)題進(jìn)行練習(xí)，達(dá)到拿到題目就可以動手做的地步。 (5) 一邊學(xué)習(xí)，一邊總結(jié)，關(guān)鍵是找差異：同一問題可以用多種方法來求解，不同方法適用于不同的文法，對文法的限制和要求，相應(yīng)的表格的構(gòu)造、使用等，各個方面的差異都要關(guān)注。

5、(6) 親自動手實(shí)現(xiàn)書上的一些算法,完成實(shí)驗(yàn)指導(dǎo)書上給出的一個簡單的編譯程序，或者編譯程序的一部分，這樣能更靈活地掌握編譯程序構(gòu)造的精髓。,8,PPT學(xué)習(xí)交流,考 核 方 法,平時(shí)成績、作業(yè)完成：10% 要求上課不遲到早退,不曠課,有事請假 上課帶筆和草稿本,記好筆記 要求用大作業(yè)本, 不能交單張紙, 獨(dú)立完成 實(shí)驗(yàn)：20% 要求程序可運(yùn)行, 并有相關(guān)設(shè)計(jì)和使用說明 期末考試：70% 閉卷形式,9,PPT學(xué)習(xí)交流,參考資料,編譯原理（龍書） Alfred.Aho等 第二版 機(jī)械工業(yè)出版社 程序設(shè)計(jì)語言編譯方法 肖軍模 第三版 大連理工大學(xué)出版社 編譯原理 呂映芝 清華大學(xué)出版社 編譯原理 技術(shù)

6、與工具 人民郵電出版社,10,PPT學(xué)習(xí)交流,編譯技術(shù)的發(fā)展,1954年至1957年間，IBM的John Backus帶領(lǐng)一個小組開發(fā)FORTRAN語言及其編譯器?；?8個人年，非常辛苦。 幾乎與此同時(shí)，Noam Chomsky開始自然語言結(jié)構(gòu)的研究。Chomsky的研究導(dǎo)致了根據(jù)語言文法(grammar，結(jié)構(gòu)規(guī)則)的難易程度以及識別它們所需的算法來為語言分類。 在6 0年代和7 0年代進(jìn)行的分析問題(parsing problem，用于限定上下文無關(guān)語言的識別的有效算法)的研究，相當(dāng)完善地解決了語言的識別的問題，現(xiàn)在它已是編譯理論的一個標(biāo)準(zhǔn)部分。 有窮自動機(jī)(finite automata

7、)和正則表達(dá)式(regular expression) 與喬姆斯基的3型文法相對應(yīng)。對它們的研究與喬姆斯基的研究幾乎同時(shí)開始，并且引出了表示程序設(shè)計(jì)語言的單詞的符號方式。 接著又深化了生成有效的目標(biāo)代碼的方法，這就是最初的編譯器，它們被一直使用至今。人們通常將其誤稱為優(yōu)化技術(shù)(optimization technique)，但因其從未真正地得到過被優(yōu)化了的目標(biāo)代碼而僅僅改進(jìn)了它的有效性，因此實(shí)際上應(yīng)稱作代碼改進(jìn)技術(shù)(code improvement technique)。 當(dāng)分析問題變得好懂起來時(shí)，人們就在開發(fā)程序上花費(fèi)了很大的功夫來研究這一部分的編譯器的自動構(gòu)造。Lex與Yacc。 在70年

8、代后期和80年代早期，大量的項(xiàng)目都關(guān)注于編譯器其他部分的生成自動化，這其中就包括了代碼生成。這些嘗試并未取得多少成功。,11,PPT學(xué)習(xí)交流,編譯器設(shè)計(jì)最近的發(fā)展,與復(fù)雜的程序設(shè)計(jì)語言的發(fā)展結(jié)合在一起。如用于函數(shù)語言編譯的Hindley-Milner類型檢查的統(tǒng)一算法。 編譯器已成為基于窗口的交互開發(fā)環(huán)境(IDE)的一部分，IDE的標(biāo)準(zhǔn)并沒有多少，但已對標(biāo)準(zhǔn)的窗口環(huán)境進(jìn)行了開發(fā)。近年來對此進(jìn)行了大量研究，但是基本的編譯器設(shè)計(jì)近20年來沒有多大的改變，現(xiàn)在正迅速地成為計(jì)算機(jī)科學(xué)課程中的中心一環(huán)。 由多處理機(jī)的發(fā)展以及對并行處理的要求，最近的研究方向是并行編譯。 隨著嵌入式應(yīng)用的迅速增長，推動了交

9、叉編譯技術(shù)的發(fā)展；對系統(tǒng)芯片設(shè)計(jì)方法和關(guān)鍵EDA技術(shù)的研究，也帶動了專用語言VHDL等及其編譯技術(shù)的不斷深化。,12,PPT學(xué)習(xí)交流,第一章 引論,什么是編譯程序 編譯過程概述 編譯程序的結(jié)構(gòu) 編譯階段的組合 編譯程序的構(gòu)造方法,13,PPT學(xué)習(xí)交流,重點(diǎn)掌握：編譯程序工作的基本過程及其各階段的基本任務(wù)，編譯程序總框。,14,PPT學(xué)習(xí)交流,機(jī)器語言 (machine language) C7 06 0000 0002 匯編語言 (assembler language) MOV X , 2 高級語言 (high-level language) X = 2,為什么要使用編譯器？,15,PPT學(xué)習(xí)

10、交流,1.1 什么叫編譯程序,編譯程序（Compiler）將高級程序設(shè)計(jì)語言程序翻譯成邏輯上等價(jià)的低級語言(匯編語言,機(jī)器語言)程序的翻譯程序。 功能,編譯程序,源程序,目標(biāo)程序,計(jì)算機(jī)運(yùn)行,輸入數(shù)據(jù),結(jié)果,16,PPT學(xué)習(xí)交流,解釋程序,解釋程序（Interpreter）將高級程序設(shè)計(jì)語言寫的源程序作為輸入，邊解釋邊執(zhí)行源程序本身，而不產(chǎn)生目標(biāo)程序的翻譯程序。 功能,解釋程序,源程序,輸入數(shù)據(jù),結(jié)果,17,PPT學(xué)習(xí)交流,操作系統(tǒng) 匯編語言,編譯程序所處的層次,計(jì)算機(jī)硬件,18,PPT學(xué)習(xí)交流,計(jì)算機(jī)中的語言層次和轉(zhuǎn)換關(guān)系,19,PPT學(xué)習(xí)交流,1.1 什么叫編譯程序,翻譯程序：能夠?qū)⒛撤N語

11、言寫的程序轉(zhuǎn)換成另一種語言的程序，而且后者與前者在邏輯上是等價(jià)的。 編譯程序：是一種將高級語言程序(源程序)翻譯成低級語言(目標(biāo)程序)的程序 解釋程序：接受某高級語言的一個語句輸入，進(jìn)行解釋并控制計(jì)算機(jī)執(zhí)行，馬上得到這句的執(zhí)行結(jié)果，然后再接受下一句。 診斷編譯程序、優(yōu)化編譯程序、交叉編譯程序,20,PPT學(xué)習(xí)交流,對編譯程序的一些說明,編譯程序?qū)嵸|(zhì)上是一個翻譯程序，要注意等價(jià)變換 本課程的任務(wù)就是講解在這個轉(zhuǎn)換過程中所涉及到的一些理論和方法，最后，使用這些理論和方法，自己編寫一個小的編譯器 轉(zhuǎn)換是一個總體的功能，要抓住總體結(jié)構(gòu)，逐層細(xì)分，寫編譯器時(shí)要體現(xiàn)軟件工程中軟件設(shè)計(jì)的原則，自頂向下，逐層

12、分解。 編譯器要完成的轉(zhuǎn)換任務(wù)相當(dāng)復(fù)雜，實(shí)現(xiàn)編譯器時(shí)必須分步驟分階段實(shí)現(xiàn)。分階段實(shí)現(xiàn)的好處是能夠簡化程序的設(shè)計(jì)，當(dāng)然也可以不分階段實(shí)現(xiàn)。,21,PPT學(xué)習(xí)交流,與編譯程序相關(guān)的程序 解釋程序(Interpreter) 匯編程序(assembler) 連接程序(linker) 連接系統(tǒng)函數(shù)與系統(tǒng)資源 裝入程序(loader) 重定位(relocation) 預(yù)處理器(Preprocessor) 編輯器(editor) Debugger , Profiler , Project Manager,22,PPT學(xué)習(xí)交流,3、什么是編譯原理 編譯原理是討論編譯程序設(shè)計(jì)的基本理論、基本概念、基本方法,23

13、,PPT學(xué)習(xí)交流,1.2 編譯過程概述,1、邏輯上分五個階段：詞法分析、語法分析、語義分析與中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成 每個階段把源程序從一種表示變換成另一種表示,24,PPT學(xué)習(xí)交流,按照詞法分析、語法分析、語義分析等這種方式來劃分階段的原因是：每個階段的復(fù)雜程度不同，所依據(jù)的理論基礎(chǔ)不同，實(shí)現(xiàn)時(shí)采用的方法也不同。主要是方便理解和實(shí)現(xiàn)。 劃分階段的依據(jù)是什么？每個階段所實(shí)現(xiàn)的功能相對獨(dú)立。,25,PPT學(xué)習(xí)交流,第一階段：詞法分析,任務(wù):從左到右掃描源程序，識別出每個單詞 附加任務(wù)：a、濾掉空格 b、識別單詞 單詞符號是語言的基本組成成分 詞法分析的工作主要依據(jù)語言的詞法規(guī)則，描述

14、詞法規(guī)則的有效工具是正規(guī)式和有限自動機(jī)。 單詞的種類： （1） 標(biāo)識符 （2） 關(guān)鍵字（char、int、if、else、switch、while、for等） （3） 運(yùn)算符（即運(yùn)算符號 +、*、/、,例:,27,PPT學(xué)習(xí)交流,第二階段：語法分析,任務(wù): 在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，將單詞符號串分解成各類語法短語(例：程序、語句、表達(dá)式)。 確定整個輸入串是否構(gòu)成語法上正確的程序。 根據(jù)規(guī)則判定：賦值語句：標(biāo)識符：表達(dá)式 表達(dá)式：標(biāo)識符、常數(shù)是表達(dá)式； 表達(dá)式的運(yùn)算也是表達(dá)式 例：識別符號串id1:=int1 + id2 * id3 + id2 * id3（即 result:=

15、5B * CB * C）是一個賦值語句， 而int1 + id2 * id3 + id2 * id3 （5B * CB * C） 是一個表達(dá)式,28,PPT學(xué)習(xí)交流,語法分析所依據(jù)的是語言的語法規(guī)則， 表示語法規(guī)則的工具是上下文無關(guān)文法,用下推自動機(jī)實(shí)現(xiàn)。,id1:=int1 + id2 * id3 + id2 * id3,29,PPT學(xué)習(xí)交流,第三階段：語義分析和中間代碼生成,任務(wù)：對語法分析所識別出的各類語法范疇分析其含義，進(jìn)行初步的翻譯(翻譯成中間代碼)。 靜態(tài)語義審查 變量定義 類型匹配 類型轉(zhuǎn)換 例：C:=A*B (檢查C與、類型) 中間代碼的翻譯 中間代碼有多種形式，如： 四元式:

16、 (運(yùn)算符，運(yùn)算對象1，運(yùn)算對象2，結(jié)果),30,PPT學(xué)習(xí)交流,例：對賦值語句： id1:=int1 + id2 * id3 + id2 * id3 1. 檢查result、C是否定義、類型 2. 生成中間代碼,(運(yùn)算符，運(yùn)算對象1，運(yùn)算對象2，結(jié)果) (*, id2, id3, T1) (+, int1, T1, T2) (*, id2, id3, T3) (+, T2, T3, T4) (:=, T4, _, id1),id1:=int1 + id2 * id3 + id2 * id3,31,PPT學(xué)習(xí)交流,第四階段： 代碼優(yōu)化,任務(wù)：對已產(chǎn)生的中間代碼進(jìn)行加工變換，使生成的目標(biāo)代碼更為

17、高效(時(shí)間和空間)。 優(yōu)化方法包括：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼等。 代碼的優(yōu)化依據(jù)的是程序的等價(jià)變換規(guī)則。,32,PPT學(xué)習(xí)交流,第五階段：目標(biāo)代碼的生成,任務(wù)：把中間代碼(或經(jīng)優(yōu)化的中間代碼)變換成特定機(jī)器上的低級語言代碼。 依賴于機(jī)器的硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令的含義 目標(biāo)代碼可以是：絕對指令代碼、可重定位的指令代碼、匯編指令代碼,33,PPT學(xué)習(xí)交流,1.3編譯程序的結(jié)構(gòu),由左圖可以看出，詞法分析是實(shí)現(xiàn)編譯器的基礎(chǔ)，語法分析是實(shí)現(xiàn)編譯器的關(guān)鍵。 因此按照這個順序來實(shí)現(xiàn)編譯器 每一步的實(shí)現(xiàn)都依賴于一定的理論基礎(chǔ)。 數(shù)學(xué)，尤其是離散數(shù)學(xué)是程序設(shè)計(jì)方法學(xué)的理論基礎(chǔ),34,PPT學(xué)習(xí)

18、交流,1.3 編譯程序的結(jié)構(gòu)(續(xù)),幾個概念 符號表：登記源程序中出現(xiàn)的名字以及名字的各種屬性 遍：對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。 編譯前端：主要指與源語言有關(guān)，與目標(biāo)語言無關(guān)的部分，通常包括詞法分析、語法分析、語義分析和中間代碼生成，與機(jī)器無關(guān)部分的代碼優(yōu)化 編譯后端：指與目標(biāo)機(jī)器有關(guān)的部分。如與機(jī)器有關(guān)的優(yōu)化、目標(biāo)代碼生成,35,PPT學(xué)習(xí)交流,為什么生成中間代碼,36,PPT學(xué)習(xí)交流,1.3 編譯程序的結(jié)構(gòu)(續(xù)),(1) 記號(token) 當(dāng)掃描程序?qū)⒆址占揭粋€記號中時(shí)，它通常是以符號表示這個記號；這也就是說，作為一個枚

19、舉數(shù)據(jù)類型的值來表示源程序的記號集。,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):,37,PPT學(xué)習(xí)交流,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu),(2) 語法樹（syntax tree） 如果分析程序確實(shí)生成了語法樹，它的構(gòu)造通常為基于指針的標(biāo)準(zhǔn)結(jié)構(gòu)，在進(jìn)行分析時(shí)動態(tài)分配該結(jié)構(gòu)，則整棵樹可作為一個指向根節(jié)點(diǎn)的單個變量保存。結(jié)構(gòu)中的每一個節(jié)點(diǎn)都是一個記錄，它的域表示由分析程序和之后的語義分析程序收集的信息。,38,PPT學(xué)習(xí)交流,(3) 符號表（symbol table） 這個數(shù)據(jù)結(jié)構(gòu)中的信息與標(biāo)識符有關(guān)：函數(shù)、變量、常量以及數(shù)據(jù)類型。符號表幾乎與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識符輸入到表格中的語義分析程序；語

20、義分析程序?qū)⒃黾訑?shù)據(jù)類型和其他信息；優(yōu)化階段和代碼生成階段也將利用由符號表提供的信息選出恰當(dāng)?shù)拇a。因?yàn)閷Ψ柋淼脑L問如此頻繁，所以插入、刪除和訪問操作都必須比常規(guī)操作更有效。盡管可以使用各種樹的結(jié)構(gòu)，但雜湊表卻是達(dá)到這一要求的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。有時(shí)在一個列表或棧中可使用若干個表格。,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):,39,PPT學(xué)習(xí)交流,(4) 常數(shù)表（literal table） 常數(shù)表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常數(shù)表中也十分重要。但是，在其中卻無需刪除，這是因?yàn)樗臄?shù)據(jù)全程應(yīng)用于程序而且常量或字符串在該表中只出現(xiàn)一次。,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):,40,PPT學(xué)習(xí)

21、交流,(5) 中間代碼（intermediate code） 根據(jù)中間代碼的類型（例如三元式代碼）和優(yōu)化的類型，該代碼可以是文本串的數(shù)組、臨時(shí)文本文件或是結(jié)構(gòu)的連接列表。對于進(jìn)行復(fù)雜優(yōu)化的編譯器，應(yīng)特別注意選擇允許簡單重組的表示。,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):,41,PPT學(xué)習(xí)交流,(6) 臨時(shí)文件（t e m p o r a ry file） 計(jì)算機(jī)過去一直未能在編譯器時(shí)將整個程序保留在存儲器中。這一問題已經(jīng)通過使用臨時(shí)文件來保存翻譯時(shí)中間步驟的結(jié)果或通過“匆忙地”編譯（也就是只保留源程序早期部分的足夠信息用以處理翻譯）解決了。,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):,42,PPT學(xué)習(xí)交流,1.4 構(gòu)造編

22、譯程序,一般生成編譯程序的方法有： 1.直接用機(jī)器語言編寫編譯程序 2.用匯編語言編寫編譯程序 注：編譯程序核心部分常用匯編語言編寫 3.用高級語言編寫編譯程序 注：這是普遍采用的方法 4.自編譯 5.用編譯工具自動生成:LEX(詞法分析)與YACC(用于自動產(chǎn)生LALR分析表) 6.移植（同種語言的編譯程序在不同類型的機(jī)器之間移植）,43,PPT學(xué)習(xí)交流,1.4 構(gòu)造編譯程序(續(xù)),構(gòu)造編譯程序要掌握以下幾方面的內(nèi)容： 源語言：理解其結(jié)構(gòu)和含義 目標(biāo)語言：必須清楚硬件的系統(tǒng)結(jié)構(gòu)和指令的格式等 編譯方法,44,PPT學(xué)習(xí)交流,編譯技術(shù)的應(yīng)用,語言的結(jié)構(gòu)化編輯器 :Turbo-Edit、edit

23、plus和Ultraedit等 語言程序的調(diào)試工具 語言程序的測試工具 高級語言之間的轉(zhuǎn)換工具 交叉編譯程序,45,PPT學(xué)習(xí)交流,作業(yè)1：,將13題寫在作業(yè)本上，思考第5題。 1. 什么是編譯程序 ？ 2. 編譯過程分哪些階段？各階段的功能和任務(wù)是什么? 3. 寫出C語言中字符集、單詞、數(shù)據(jù)類型、各種表達(dá)式、語句和程序的組成 4. 自學(xué)2.5節(jié) 5. 設(shè)計(jì)一種計(jì)算機(jī)語言，該語言可以用來解決實(shí)際問題，比如，該語言的應(yīng)用等。,46,PPT學(xué)習(xí)交流,第二章 程序語言的語法描述(P25),掌握：上下文無關(guān)文法基本概念 推導(dǎo)、句型、句子、語言 語法樹 文法的二義性 理解：文法的語言生成過程,47,PP

24、T學(xué)習(xí)交流,以C和PASCAL為例復(fù)習(xí)高級語言 1 語言的基本字符集的定義(字母, 數(shù)字, 界符) 2 單詞集的定義 3 數(shù)據(jù)類型的定義 4 表達(dá)式的定義 5 語句的定義 6 程序定義 PASCAL和C的主要區(qū)別,48,PPT學(xué)習(xí)交流,程序語言定義的基本概念,1. 字母表：是元素的有窮非空集合 2. 符號：字母表中的每個元素，因此字母表也稱為符號集。 不同的語言可以有不同的字母表，例如英文的字母表中26個字母、數(shù)字及標(biāo)點(diǎn)符號等。 PASCAL語言的字母表是由字母、數(shù)字、若干專用符號組成。 符號是該語言能識別的符號，字母表是該語言能識別的所有符號的全體（字符集）。,49,PPT學(xué)習(xí)交流,基本概念

25、(續(xù)),3. 符號串: 由字母表中的符號組成的任何有窮序列稱為符號串，例如00 11 10 是字母表 =0，1上的符號串. 字母表A=a,b,c上的一些符號串有：a,b,c,ab,aaca等。 在符號串中，符號的順序是很重要的，符號串a(chǎn)b就不同于ba,abca和aabc也不同。 符號串STR表示“由符號S、T和R，并按此順序組成.,50,PPT學(xué)習(xí)交流,基本概念(續(xù)),4. 符號串的運(yùn)算 a. 字符串的連接： 字符串稱為字符串和的連接 符號串的長度 :符號串中符號的個數(shù)，例如: 某符號串中有m個符號,則稱其長度為m，表示為x=m，如001110的長度是6。 空符號串: 即不包含任何符號的符號串

26、，用表示，其長度為0， 即=0。 用 *表示上所有的符號串的全體(長度為0，1，2，)。,51,PPT學(xué)習(xí)交流,集合的運(yùn)算 b. *的子集U、V的積 ： UV = | U & V 長度相加 即: 集合UV中的符號串是由U和V的符號串連接而成。 c. 集合的方冪：n個相同符號連接 Vn =VVVV . V 規(guī)定V0 = d. 閉包、正則閉包的運(yùn)算,52,PPT學(xué)習(xí)交流,例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,使用 * 表示上的一切符號串（包括）組成的集合。 稱為的閉包。 上的除外的所有符號串組成的集合記為+ 。稱為

27、的正閉包。,U = aa,bb V=00,11 則UV=? V=0,1 V* = ? V+ = ?,53,PPT學(xué)習(xí)交流,文 法,文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則。是一種工具，它可用于嚴(yán)格定義句子的結(jié)構(gòu)；用有窮的規(guī)則刻劃無窮的集合 文法是被用來精確而無歧義地描述語言的句子的構(gòu)成方式. 文法描述語言的時(shí)候不考慮語言的含義。,54,PPT學(xué)習(xí)交流,引 例,例1：有如下規(guī)則 (表示由組成) | 我 大學(xué)生 是 | 現(xiàn)要求根據(jù)如上規(guī)則得出句子：我是大學(xué)生 = = =我是大學(xué)生,55,PPT學(xué)習(xí)交流,句子“我是大學(xué)生”也可以如下圖示分析,在有規(guī)則的情況下，每一次用上述規(guī)則的右邊去替換左邊，得到“我是大

28、學(xué)生”是符合上述規(guī)則的句子,56,PPT學(xué)習(xí)交流,上下文無關(guān)文法的形式定義,由四部分組成： 終結(jié)符號：是組成該語言的最基本的符號，是不可再分的基本符號,如保留字、標(biāo)識符等。 非終結(jié)符號：規(guī)則中用尖括號括起來的符號，表示一些語法成分，可以推導(dǎo)出其他的語法成分,表示一定符號串的集合，是一個類，如表達(dá)式。 開始符號：規(guī)則中的一個特殊的非終結(jié)符號，語言中的句子都從它開始推導(dǎo),如程序、句子 產(chǎn)生式：定義語法成分的規(guī)則，其中：,57,PPT學(xué)習(xí)交流,文法的形式定義(續(xù)),一個文法G抽象地表示為四元組 G=（Vn,Vt,P,S） 其中Vn表示非終結(jié)符號 Vt表示終結(jié)符號，VnVt=(字母表)，VnVt= S

29、是開始符號， P是產(chǎn)生式，形如：(V+且至少含有一個非終結(jié)符號，V*),58,PPT學(xué)習(xí)交流,上例中： G=（Vn,Vt,P,） Vn=（，） Vt= (我，是，大學(xué)生) P =, | 我 大學(xué)生 是 |,59,PPT學(xué)習(xí)交流,產(chǎn)生式的形式為：A ,左部符號，非終結(jié)符,右部，可以含有非終結(jié)符和終結(jié)符,又稱為一條規(guī)則 有時(shí)一個產(chǎn)生式不足以描述該語法范疇，就用多個產(chǎn)生式，如算術(shù)表達(dá)式的描述為：(遞歸定義) E E + E E E * E E i 相同左部的一個右部又稱一個候選式,60,PPT學(xué)習(xí)交流,上下文無關(guān)文法所定義的語法成分獨(dú)立于它可能出現(xiàn)的環(huán)境，即不考慮上下文。,61,PPT學(xué)習(xí)交流,算術(shù)

30、表達(dá)式的文法定義,變量是表達(dá)式 表達(dá)式 + 表達(dá)式是表達(dá)式 表達(dá)式 * 表達(dá)式是表達(dá)式 (表達(dá)式) 是 表達(dá)式,E E + E E E * E E ( E ) E i,E E+E | E*E | (E) | i,62,PPT學(xué)習(xí)交流,上下文無關(guān)文法產(chǎn)生句子的方法:從文法的開始符號出發(fā),反復(fù)連續(xù)使用產(chǎn)生式,對左邊的非終結(jié)符進(jìn)行替換和展開 例：表達(dá)式定義規(guī)則,E E + E E E * E E ( E ) E i,( i+i ),E=( E ) =( E+E ) =( i+E ) =( i + i ),63,PPT學(xué)習(xí)交流,推導(dǎo): 連續(xù)使用產(chǎn)生式右部去替換左部某個非終結(jié)符的過程,得到的連續(xù)序列稱為

31、一個推導(dǎo)。 直接推導(dǎo)：又稱一步推導(dǎo)(用 符號=表示),就是用某條規(guī)則的右部去替換該規(guī)則的左部,64,PPT學(xué)習(xí)交流,幾個概念的形式定義,直接推導(dǎo): 如果是文法 G=（Vn,Vt,P,S）的產(chǎn)生式，和是*中的任意符號，若有符號串v,w滿足：v=,w=,則說v直接產(chǎn)生w，(w是v的直接推導(dǎo))記作：v=w 例：S01, 0S0=0010(直接推導(dǎo),) 如果存在v=w0=w1=w2.=Wn=w(n0)，則稱v推導(dǎo)出w（長度為n），記作v=w(至少一步) 若有=w或v=w，則記作v=w(0步或若干步),*,+,65,PPT學(xué)習(xí)交流,例3 : G = (E, i, +, *, (, ) , P , E)

32、(1.1) P： E E+E | E*E | (E) | i 表達(dá)式(i)和(i+i)*i的推導(dǎo)：,E (E) (i)E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i,E E 0步推導(dǎo) E (i + i)*i 6步推導(dǎo) E (i + i)*i 6步推導(dǎo) E (E) 直接推導(dǎo),66,PPT學(xué)習(xí)交流,句型：設(shè)(s)是一文法，如果符號串x是從開始符號推導(dǎo)出來的，即有s=x,則稱x是文法G(s)的一個句型。 即: 任何由開始符推導(dǎo)出來的符號串都是句型。 句子：若x僅由終結(jié)符號組成，則稱x為G(S)的句子,*,練習(xí) 文法G：SaAcB | Bd AA

33、aB | c BbScA | b 寫出句型aAcbBdcc和句子acabcbbdcc的推導(dǎo)過程。,67,PPT學(xué)習(xí)交流,文法G所產(chǎn)生的語言定義為： L(G)=x|S=x,其中S為文法的開始符號，xVt* 。即: 一個文法G可以推導(dǎo)出的所有句子構(gòu)成的一個集合, 就確定了一個語言。,*,68,PPT學(xué)習(xí)交流,例2.1 (P30) 考慮文法G1: 它定義了什么語言。,S bA A aA|a,推導(dǎo)過程 ：S=bA =ba S=bA =baA=baa . S=bA =baA= =baa,歸納得： L(G1) = ban | n1,69,PPT學(xué)習(xí)交流,練習(xí)：文法(A,B,S,a,b,c,P,S) S A

34、c|aB A ab B bc寫出(G)的全部元素,L(G) = abc,70,PPT學(xué)習(xí)交流,例2.2(P30) 考慮文法G2: 它定義的語言是：,S AB A aA|a B bB|b,L(G2) = ambn |m,n1,71,PPT學(xué)習(xí)交流,思考：構(gòu)造一個文法G3使得：,L(G3) = anbn |n1 ,S aSb S ab,a,b的個數(shù)相同,則文法G3為：,72,PPT學(xué)習(xí)交流,文法等價(jià)： 若文法G1和文法G2所產(chǎn)生的語言相同，即L(G1) = L(G2)，則稱文法G1和文法G2等價(jià)。,73,PPT學(xué)習(xí)交流,例：有如下兩個文法，判斷它們是否等價(jià)？ G1=（S，0，S，S0S，S0） G

35、2=（S，0，S，SS0，S0）,S0 S0S00 S0S 00S 0000,L(G1) = 0n | n1,對于G2：,對于G1 ：,SS0 S00 0000,L(G2) = 0n | n1,G1G2，但L(G1) = L(G2)，文法G1和G2等價(jià),74,PPT學(xué)習(xí)交流,例3 : G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 表達(dá)式 (i+i)*i的推導(dǎo)過程： (1) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i (2) E E*E E*i (E)* i

36、(E + E)*i (E+ i)*i (i + i)*i,得到一個語言，是通過利用所有的產(chǎn)生式推導(dǎo)出所有可能的句子，構(gòu)成一個集合。 但是一個句型到另一個句型(句子)的推導(dǎo)過程不是唯一的。,75,PPT學(xué)習(xí)交流,最左推導(dǎo): 在整個推導(dǎo)過程中,任何一步推導(dǎo)=都是對中最左邊的非終結(jié)符進(jìn)行替換。 最右推導(dǎo):,在推導(dǎo)之前確定推導(dǎo)的順序，是對句子進(jìn)行確定性分析所必須的,例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i (i+i)*i的最左推導(dǎo)過程： E E*E (E)*E (E + E)*E (i + E)*E (i + i

37、)*E (i + i)*i 最右推導(dǎo)過程： E E*E E*i (E + E)*i (E+ i)*i (i + i)*i,76,PPT學(xué)習(xí)交流,用語法樹表示上下文無關(guān)文法的推導(dǎo),語法樹：推導(dǎo)的形式化表示，有助于理解句子語法結(jié)構(gòu)的層次 每個結(jié)點(diǎn)都有一個標(biāo)記，該標(biāo)記屬字母集中的一個符號，根由開始符號標(biāo)記。 當(dāng)某個非終結(jié)符被它的某個候選式所替換時(shí)，就產(chǎn)生相應(yīng)的下一層的結(jié)點(diǎn)，候選式中自左至右的每個符號對應(yīng)一個新的結(jié)點(diǎn)，并標(biāo)記它，畫出其與父結(jié)點(diǎn)之間的連線。,77,PPT學(xué)習(xí)交流,例：對文法G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子(i+i)*i 的語法樹：,在語法樹的推導(dǎo)過程中的任何時(shí)刻，沒有后代的端末結(jié)點(diǎn)自左至右排列起來就是一個句型 一棵語法樹表示了一個句型很多可能的不同推導(dǎo)過程。(包括最左推導(dǎo)和最右推導(dǎo)),78,PPT學(xué)習(xí)交流,例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子 ( i * i + i)的語法樹： (1) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i),(2) E (E) (E * E) (i*E) (i * E + E)