編譯技術原理及方法PPT完整全套教學課件

第一章引論編譯技術原理及方法1-1計算思維與編譯技術1-2程序設計語言及編譯技術的發(fā)展歷程1-3程序設計語言的翻譯機制1-4編譯程序的基本組成1-5編譯程序的構造方法1-6編譯技術的應用1-1計算思維與編譯技術高級程序設計語言編制的源程序0110100101011.....計算機所能夠識別的機器語言翻譯原理技術方法一、編譯的基本概念1-1計算思維與編譯技術二、編譯技術與圖靈獎艾倫?圖靈，杰出的計算機科學家，人工智能之父，最光輝的事跡就是協(xié)助盟軍破譯德國密碼系統(tǒng)“英格瑪”，從而扭轉二戰(zhàn)戰(zhàn)局提出了圖靈機的設想，發(fā)表了享譽世界的論文“機器能思考嗎”，拉開了人工智能的序幕圖靈機的原理和編譯技術息息相關AlanMathisonTuring1912-1954圖靈獎的獎杯1-1計算思維與編譯技術二、編譯技術與圖靈獎獲獎者最多的領域就是編譯理論技術領域以及與之緊密相關的程序設計語言領域AlanJ．Perlis1966年圖靈獎獲得者主要貢獻：編譯器構造BarbaraLiskov2008年圖靈獎獲得者主要貢獻：面向對象編程語言CLUAlfredAho和JeffreyUllman2020年圖靈獎獲得者主要貢獻：在編程語言實現(xiàn)領域基礎算法和理論方面的成就1-1計算思維與編譯技術二、編譯技術與圖靈獎從1966年開始，共有15位獲獎者為我們今天的《編譯原理》課程知識和內容做出了卓越的貢獻！AlfredAho和JeffreyUllman2020年圖靈獎獲得者主要貢獻：在編程語言實現(xiàn)領域基礎算法和理論方面的成就1-1計算思維與編譯技術二、編譯技術與圖靈獎中國特色社會主義的道路自信可計算理論中的Lambda演算（解釋器）以及PLT（程序語言理論）和本課程緊密相關；在底層芯片上運行的嵌入式系統(tǒng)，恰恰也和我們的編譯技術也息息相關。姚期智1946-至今2000年圖靈獎獲得者主要貢獻：可計算理論、密碼學、量子通信張首晟1963-2018美國藝術與科學院院士主要貢獻：量子自旋霍爾效應、拓撲絕緣體材料、華為5G芯片1-1計算思維與編譯技術什么是計算思維？計算思維運用計算機科學的基本概念去求解問題、設計系統(tǒng)和理解人類行為，它包括一系列廣泛的計算機科學的思維方法計算思維通過約簡、嵌入、轉化和仿真等方法，把一個看來困難的問題重新闡釋成一個我們知道問題怎樣解決的方法三、編譯技術與計算思維周以真卡內基梅隆大學教授主要貢獻：提出了“計算思維”的概念遞歸問題分解自動化抽象等價轉換權衡1-1計算思維與編譯技術三、編譯技術與計算思維編譯的過程詞法分析源程序語法分析語義分析中間代碼生成代碼優(yōu)化目標代碼生成目標程序信息表管理錯誤檢查和處理Compiling1-1計算思維與編譯技術三、編譯技術與計算思維計算思維和編譯過程的組成部分的簡單對應關系詞法分析源程序語法分析語義分析中間代碼生成代碼優(yōu)化目標代碼生成目標程序抽象自動化形式化轉化嵌入遞歸約簡分解仿真容錯1-1計算思維與編譯技術三、編譯技術與計算思維11有窮自動機、LR系列分析法、編譯程序自動生成等遞歸文法、遞歸下降分析法、語法制導翻譯文法、語言和范式定義、First和Follow集合求解有窮自動機的各類等價關系和化簡、基于DAG的基本塊等價轉換自頂向下逐步求精進行程序設計、中間語言、優(yōu)化自動化遞歸二義性文法和上下文無關文法的權衡權衡等價轉換抽象問題分解約簡形式化1-1計算思維與編譯技術三、編譯技術與計算思維遞歸在編譯原理課程中，會經常用到遞歸規(guī)則來定義遞歸文法正如英語和漢語中的語法句子結構，往往需要考慮如何利用有限的語法規(guī)則來產生無窮的句子例如：A::=Ab，其中“雙冒號+等于號”表示“定義為”或者“推導出”，用語法符號A來定義自身的規(guī)則稱之為遞歸規(guī)則

12《道德經》道生一，一生二，二生三，三生萬物。老子1-1計算思維與編譯技術三、編譯技術與計算思維問題分解編譯原理中常見的“問題分解”有：為什么要把編譯分為多個階段？為什么編譯過程要分成多遍完成？為什么要引入中間語言完成中間代碼生成？等等分而治之，各個擊破

《群經平議·周官二》巫馬下士二人醫(yī)四人。俞樾1-2程序設計語言及編譯技術的發(fā)展歷程

1-2程序設計語言及編譯技術的發(fā)展歷程

一、語言的概念和分類語言的概念語言是人類所特有的用來表達意思、交流思想的工具，是一種特殊的社會現(xiàn)象，由語音、詞匯、語法、語義構成一個系統(tǒng)。語言包括口語和書面形式。人類社會和動物世界都存在語言。

1-2程序設計語言及編譯技術的發(fā)展歷程

一、語言的概念和分類自然語言數(shù)理語言程序設計語言人與人之間交流信息的一種語言動物之間通過動物語言交流信息以數(shù)理邏輯、集合論和統(tǒng)計數(shù)學來描述的一種語言。例如，用計算機進行幾何定理的證明就得以數(shù)理語言形式進行描述是人和計算機進行信息交流的一種語言，它遵循一定的語法和語義的規(guī)則，而編譯程序的功能正是1）討論語法，檢查程序正確性2）討論語義，生成目標代碼語言的分類

1-2程序設計語言及編譯技術的發(fā)展歷程

一、語言的概念和分類自然語言舉例：小明要么唱歌要么跳舞。等價的數(shù)理語言：命題P：小明唱歌；命題Q：小明跳舞。PQ（符號表示異或）等價的程序設計語言（以C語言為例）If(p==1&&q==0)printf(“Xiaomingissinging”);elseif(p==0&&q==1)printf(“Xiaomingisdancing”);elseprintf(“error”).

1-2程序設計語言及編譯技術的發(fā)展歷程

自1946年2月14日，世界上第一臺通用電子計算機ENIAC在美國賓夕法尼亞大學誕生以來，計算機世界的語言已經超過了1000種。在不久的將來，計算機世界的語言總量就會超過人類世界語言的總量。雖然計算機世界的語言也是由不同種類的單詞和語法構成的，但人類能理解的語言和計算機能理解的語言是不同的，人和計算機之間的交流也需要“翻譯”，編譯器因此產生。編譯技術的發(fā)展歷程就是程序設計語言的發(fā)展歷程。ENIACEDSAC二、程序設計語言分類

1-2程序設計語言及編譯技術的發(fā)展歷程

1903年12月28日，在布達佩斯誕生了一位神童，這不僅給這個家庭帶來了巨大的喜悅，也值得整個計算機界去紀念。正是他，開創(chuàng)了現(xiàn)代計算機理論，其體系結構沿用至今。他，就是約翰·馮·諾依曼（JohnVonNeumann）。電子計算機之父JohnvonNeumann馮·諾依曼馮·諾依曼理論——1）計算機硬件設備由存儲器、運算器、控制器、輸入設備和輸出設備5部分組成。2）存儲程序工作原理計算機的兩個基本能力：一是能夠存儲程序，二是能夠自動地執(zhí)行程序。二、程序設計語言分類1.機器語言(第一代語言)2.匯編語言(第二代語言:50年代初期出現(xiàn))3.高級程序設計語言(第三代語言:50年代中期提出)4.超高級程序設計語言(第四代語言)

1-2程序設計語言及編譯技術的發(fā)展歷程

二、程序設計語言分類機器語言（第一代語言）定義：由機器指令構成的語言稱機器語言，即用二進制編碼組成。如01110101機器指令：是二進制編碼，基本上是由操作碼和地址碼兩部分組成，所以要用機器語言編制程序一定要知道多種不同的操作碼。指令系統(tǒng)：一種計算機所能識別的一組不同指令系統(tǒng)。

1-2程序設計語言及編譯技術的發(fā)展歷程

二、程序設計語言分類匯編語言（第二代語言）定義：用容易記憶的符號來代替機器指令中操作碼和地址碼的一種語言。如：ADD代表“+”SUB代表“-”MOV代表“傳遞”。匯編語言的發(fā)展歷經了宏指令和子程序時期。特點：優(yōu)點——(1)程序直觀容易閱讀；(2)編程工作量相對小。缺點——(1)只能在一種型號機器上運行；(2)不能直接在計算機上運行。以人類進化史來比喻，對編譯器來說此時處于開始學會使用各種工具的類人猿

1-2程序設計語言及編譯技術的發(fā)展歷程

1-2程序設計語言及編譯技術的發(fā)展歷程

高級程序設計語言（第三代語言）1956年，第一個高級程序設計語言FORTRAN(FORmulaTRANslator)正式開始使用，這標志著更高效率的程序編寫拉開序幕。定義：高級程序設計語言是一種面向過程或者面向對象的語言，不面向機器，用一些符號或者數(shù)字對求解的問題或者現(xiàn)實世界進行描述。高級程序設計語言的發(fā)展分為以下四個階段：二、程序設計語言分類初始時期發(fā)展時期結構程序設計時期多范型發(fā)展時期

1-2程序設計語言及編譯技術的發(fā)展歷程

高級程序設計語言（第三代語言）——初始時期FORTRAN主要用于公式翻譯。ALGOL語言最大的貢獻在于第一次采用形式化語法描述體系——BNF范式(BackusNormalForm巴科斯-諾爾范式)，為編譯理論的發(fā)展奠定了基石。COBOL語言是第一個用于商務和數(shù)據處理的經典語言。在高級程序設計語言發(fā)展初期，編譯技術和理論開始萌芽，但大多數(shù)編譯器仍然依賴于機器語言和匯編語言編寫。二、程序設計語言分類

1-2程序設計語言及編譯技術的發(fā)展歷程

高級程序設計語言（第三代語言）——初始時期FORTRAN主要用于公式翻譯。二、程序設計語言分類IBM704約翰-巴科斯1954-1957巴科斯（1924.12.3-2007.3.17）。美國計算機科學家，在IBM支持研制出FORTRAN語言。之后，巴克斯參加了ALGOL（算法語言）語言的設計工作，首先在ALGOL-58中實做出巴科斯范式，稱為巴科斯范式，后為許多其他語言所采用。巴科斯于1977年獲圖靈獎。

1-2程序設計語言及編譯技術的發(fā)展歷程

高級程序設計語言（第三代語言）——初始時期ALGOL語言最大的貢獻在于第一次采用形式化語法描述體系——BNF范式(BackusNormalForm巴科斯-諾爾范式)，為編譯理論的發(fā)展奠定了基石。二、程序設計語言分類1977年圖靈獎2005年圖靈獎〈標識符〉∷=〈字母〉|〈標識符〉〈字母〉|〈標識符〉〈數(shù)字〉〈字母〉∷=A|B|C|D|…|Z|a|b|c|d|…|z〈數(shù)字〉∷=0|1|2|…|9FORTRAN編譯程序產生時，編譯技術方法還缺乏理論基礎，1960年ALGOL60提出，并用巴科斯范式BNF對語言語法進行嚴格定義，因而提出了高級程序設計語言編譯程序技術方法，包括：簡單優(yōu)先法、算符優(yōu)先法、LL分析法和LR分析法。

1-2程序設計語言及編譯技術的發(fā)展歷程

高級程序設計語言（第三代語言）——發(fā)展時期二、程序設計語言分類在60年代初期編譯技術與理論研究受到高度重視，并得到發(fā)展，這也促使了多種新程序設計語言的研制。除了若干普通過程性程序設計語言外，還研制了一些其它風格的程序設計語言如：LISP、APL、SNOBOL、PL/1、SIMULA和BASIC等。SIMULABASICPL/1

1-2程序設計語言及編譯技術的發(fā)展歷程

高級程序設計語言（第三代語言）——結構程序設計時期結構化程序設計思想，即任何程序都可以用順序、選擇、循環(huán)這三種結構語句來構造。從1968年開始，不同的結構程序設計語言陸續(xù)問世，如：PASCAL、Ada、C等，這些高級程序設計語言的出現(xiàn)極大推動了如自編譯、交叉編譯等編譯技術的發(fā)展。二、程序設計語言分類

1-2程序設計語言及編譯技術的發(fā)展歷程

高級程序設計語言（第三代語言）——多范型發(fā)展時期這一時期，科學家們把注意力轉向其它風格、其它范型程序設計語言的研究，如：函數(shù)式語言、邏輯式語言、面向對象語言和網絡語言等，以用于應對80年代出現(xiàn)的軟件危機。面向對象語言已經成為主流的高級程序設計語言，繼承、封裝和多態(tài)成為其主要特征，Smalltalk、C++、Java、C#、Python等都是面向對象的高級程序設計語言。二、程序設計語言分類

1-2程序設計語言及編譯技術的發(fā)展歷程

超高級程序設計語言（第四代語言）超高級程序設計語言是80年代出現(xiàn)的一種非過程程序設計語言。第三代程序設計語言要求程序設計者具有較高的技術，不僅要告訴計算機做什么還要告訴如何做，而第四代語言則只要指出做什么就行了。例如我們的SQL語言就具備這樣的特征。二、程序設計語言分類

1-2程序設計語言及編譯技術的發(fā)展歷程

三、小結程序設計語言的發(fā)展見證了編譯理論和技術的發(fā)展歷程。編譯理論和技術恰恰也是為程序設計語言服務的。用戶至上的原則1-3程序設計語言的翻譯機制

1-3程序設計語言的翻譯機制

一、翻譯程序的概念翻譯程序（語言處理程序）一種將某種語言編寫的程序（稱為源程序）進行等價分析處理的程序，這種源程序可能被語言處理程序直接改造成另一種等價的語言程序（稱為目標程序），或者在語言處理程序的分析處理下直接利用用戶提供的輸入執(zhí)行源程序中指定的操作。書寫源程序的語言稱為源語言。書寫目標程序的語言稱為目標語言。我只接受1和0組成的二級制符號串哦源程序翻譯

1-3程序設計語言的翻譯機制

二、翻譯程序的分類匯編程序解釋程序編譯程序把匯編語言寫的源程序翻譯成機器語言的目標程序，這個翻譯過程稱為匯編。將高級語言寫的源程序作為輸入數(shù)據，但并不產生目標程序，而是邊解釋邊執(zhí)行源程序本身的一種程序。編譯程序是將高級語言寫的源程序翻譯成目標語言（匯編語言、機器語言）的程序。

1-3程序設計語言的翻譯機制

二、翻譯程序的分類匯編程序：把匯編語言寫的源程序翻譯成機器語言的目標程序，這個翻譯過程稱為匯編。匯編程序一般對源程序進行兩遍掃描來完成。第一遍：進行存貯分配，造出第二遍掃描時用的各種表格；第二遍：用機器語言操作碼來代替匯編符號操作碼。匯編源程序匯編程序目標程序結果數(shù)據初始數(shù)據

1-3程序設計語言的翻譯機制

二、翻譯程序的分類解釋程序：將高級語言寫的源程序作為輸入數(shù)據，但并不產生目標程序，而是邊解釋邊執(zhí)行源程序本身的一種程序。解釋程序適合于會話型語言，如BASIC語言。解釋程序主要優(yōu)點是易于為用戶提供調試功能，對源程序的語法分析及出錯處理都很及時，修改調試也很方便，但是解釋程序執(zhí)行速度較慢，運行效率低。結果數(shù)據解釋程序源程序初始數(shù)據

1-3程序設計語言的翻譯機制

二、翻譯程序的分類編譯程序：是將高級語言寫的源程序翻譯成目標語言（匯編語言、機器語言）的程序。這種翻譯過程稱為編譯。編譯程序的執(zhí)行過程如下：

源程序編譯程序目標程序（機器語言）源程序編譯程序目標程序（匯編語言）匯編程序目標程序（機器語言）編譯階段編譯階段匯編階段

1-3程序設計語言的翻譯機制

二、翻譯程序的分類目標程序，再加上運行系統(tǒng)（如服務子程序、動態(tài)分配程序、裝配程序等）就可獲得計算結果，整個系統(tǒng)稱為編譯系統(tǒng)。目標程序（機器語言）運行系統(tǒng)可執(zhí)行程序結果數(shù)據運行階段

1-3程序設計語言的翻譯機制

三、典型的翻譯機制示例（1）典型的C語言翻譯機制（GCC）

1-3程序設計語言的翻譯機制

三、典型的翻譯機制示例（2）Java處理器對java源程序的處理過程《深入JAVA虛擬機》JVM即時編譯器（JustInTimeCompiler)簡稱JIT

JAVA程序最初是通過解釋器（Interpreter）進行解釋執(zhí)行的，當JVM發(fā)現(xiàn)某個方法或代碼塊運行特別頻繁的時候，就會認為這是“熱點代碼”（HotSpotCode)。

為了提高熱點代碼的執(zhí)行效率，就會將這些“熱點代碼”編譯成與本地機器相關的機器碼，進行各個層次的優(yōu)化。完成這個任務的編譯器就是即時編譯器（JIT）。

1-3程序設計語言的翻譯機制

三、典型的翻譯機制示例（3）C#等處理器對源程序的處理過程Java與C#——開源與壟斷Bytecode的引入是為了讓同一種Java語言通過使用不同的虛擬機，使之能在不同的操作系統(tǒng)和硬件平臺上運行MSIL的引入是為了讓微軟支持的不同種類語言能夠都在微軟的操作系統(tǒng)上運行

1-3程序設計語言的翻譯機制

四、小結編譯程序和匯編程序以一種靜態(tài)的方式（并不執(zhí)行程序）對程序員編寫的源程序加以理解，并將其轉換成另一種等價的代碼，這種機制稱為編譯機制。解釋程序是另一種形式的語言處理程序，它把翻譯和運行結合在一起，邊翻譯源程序，邊執(zhí)行翻譯的結果，這種機制稱為解釋機制。如果以翻譯英文原著作為類比對象，原著相當于源程序，譯著相當于目標程序，計算機的運行相當于閱讀。編譯程序和匯編程序對源程序的處理過程與筆譯類似，產生了文本型的譯著，也可以稱為“離線方式（Offline）”；解釋程序的工作相當于現(xiàn)場口譯，翻譯人員一邊看原著，一邊翻譯給在場的讀者聽，也可以稱為“在線方式（Online）”。上述三種翻譯程序，匯編程序最容易實現(xiàn)，其次是解釋程序，編譯程序最難。所以只要掌握了編譯程序實現(xiàn)方法，匯編程序和解釋程序就迎刃而解了。

1-3程序設計語言的翻譯機制

四、小結從上述對源程序的處理過程可以看出現(xiàn)代高級程序設計語言編譯程序的發(fā)展趨勢：從“一次編譯”非托管到“編譯+解釋”或“編譯+編譯”的二次托管。目前很多新出現(xiàn)的程序設計語言采用二次托管方式對源程序進行處理。1-4編譯程序的基本組成

1-4編譯程序的基本組成

一、編譯程序的組成框架詞法分析源程序語法分析語義分析中間代碼生成代碼優(yōu)化目標代碼生成目標程序讀取字母識別單詞潤色修飾分析語義關系構成語法關系初步寫出譯文最終定稿信息表管理錯誤檢查和處理

1-4編譯程序的基本組成

二、編譯過程舉例分析一個簡單的C語言的例子intmain{floata,b;a=3*a+b;printf(“a=%d”,a);return0;}讀入源程序之后，去除換行符變成符號串intmain{floata,b;a=3*a+b;printf(“a=%d”,a);return0;}

1-4編譯程序的基本組成

二、編譯過程舉例分析詞法分析階段1)掃描源程序進行讀符號，刪除無用字符（如空格、注釋等）2)將一個個有獨立意義的單詞識別出來，并且轉換成統(tǒng)一長度的內部編碼。3)建立有關表格（如名字特征表、常數(shù)表），進行詞法檢查以供語法和語義分析用。

這個簡單程序中，可以識別出的單詞如下：

intmainfloatprintfreturn關鍵詞{}=*+()%,;““特殊符號ab標識符03無符號整數(shù)

1-4編譯程序的基本組成

二、編譯過程舉例分析將單詞轉換為內部編碼

在本例中，可以采用0/1/2/3來分別標記關鍵詞、特殊符號、標識符和無符號整數(shù)的單詞類型；對于關鍵詞和特殊符號等，單詞值采用專用的編碼來表述：例如關鍵詞main的內部編碼如下：對于標識符、無符號整數(shù)以及其它無限的集合，往往用其存儲的相對地址來表述其單詞值：例如標識符a的內部編碼如下：單詞類型單詞值長度統(tǒng)一的單詞內部編碼的格式單詞類型專用編碼0000單詞類型相對地址2402

1-4編譯程序的基本組成

二、編譯過程舉例分析語法分析階段經詞法分析后，源程序轉換成為內部編碼形式，作為語法分析的輸入；語法分析階段就是將詞法分析后所有單詞組成句子，根據不同高級語言不同語法規(guī)則來分析這些句子乃至程序是否正確。在本例中，主要檢查賦值語句和輸出語句的語法正確性：〈變量〉:=〈表達式〉〈輸出語句〉:=printf(〈“.....”〉,〈變量1〉，〈變量2〉，〈變量3〉)若發(fā)現(xiàn)不合語法規(guī)則的就輸出出錯信息，否則作為正確程序提供給語義分析使用。

1-4編譯程序的基本組成

二、編譯過程舉例分析語句a=3*a+b;經過分析后可以表示成語法樹和抽象語法樹語法樹抽象語法樹

1-4編譯程序的基本組成

二、編譯過程舉例分析語義分析階段語義就是源程序中各種語句的含義。如：a=3*a+b是賦值語句，表示將賦值號右邊表達式送給左部變量。根據語義分析語句的含義，可將源程序表示成一種內部形式（中間語言）或直接生成目標程序。在語義分析時，語法分析器還會進行相應的語義檢查，以保證源程序在語義上的正確性。例如，要檢查表達式中賦值符號兩邊的數(shù)據類型是否一致；對于語句a=3*a+b;中的整數(shù)3，在語義分析階段應該將其轉換為實數(shù)，再與a進行乘法運算。

1-4編譯程序的基本組成

二、編譯過程舉例分析中間代碼生成階段中間代碼的形式有很多種，包含：后綴表達式、三元式、四元式等，具體將在第五章中詳細介紹；生成中間代碼的目標是為了實現(xiàn)代碼優(yōu)化，以便生成更高質量的目標代碼。在本例中，我們以賦值語句a=3*a+b為例，如果將其轉換為后綴表達式，則為a3a*b+=；如果轉換為三元式系列，如下所示：如果轉換為四元式系列，如下所示：

(1)(itf,3,)(2)(*,(1),a)(3)(+,(2),b,)(4)(=,a,(3))(1)(itf,3,,t1）(2)(*,t1,a,t2)(3)(+,t2,b,t3)(4)(=,t3,,a)

1-4編譯程序的基本組成

二、編譯過程舉例分析代碼優(yōu)化階段代碼優(yōu)化的目標是使得生成的目標程序占有內存少，運行速度快。對上述四元式序列進行代碼優(yōu)化，可以在編譯時將整型變量3轉換成浮點型變量3.0，以免在運行時再進行整型變量到浮點型變量的轉換。由于t2在四元式（3）中是單目運算，因此可以用a代替t2。這樣再次優(yōu)化后得到的四元式序列如下(*,3.0,a,t1)(2)(+,t1,b,t2)(3)(=,t2,,a)改進后(1)(itf,3,,t1）(2)(*,t1,a,t2)(3)(+,t2,b,t3)(4)(=,t3,,a)改進后(*,3.0,a,t1)(2)(+,t1,b,a)

1-4編譯程序的基本組成

二、編譯過程舉例分析目標代碼生成目標代碼生成就是將中間語言代碼轉換成機器語言程序或匯編語言程序，最后完成翻譯。

以匯編語言為例，利用寄存器R1和R2，經過優(yōu)化的中間代碼可生成如下目標代碼：MOVa,R1MUL3.0,R1MOVb,R2ADDR1,R2MOVR2,R1a=3.0*a+b

1-4編譯程序的基本組成

二、編譯過程舉例分析符號表管理符號表管理（SymbolTableManagement）也被稱為表格管理，即管理編譯過程中產生的各種表格。其主要功能是，按照編譯過程中的信息需求，生成不同用途的符號表（如常數(shù)表、名字特征表、循環(huán)層次表等），并提供合適的方式查詢、修改和維護這些表格。完成造表并對表格進行增、刪、查、改的程序被稱為符號表管理程序。例如，對于floata,b;這條說明語句，詞法分析器識別出標識符a和b后，將其插入名字特征表，但a和b的各種屬性在后續(xù)階段才能填入：標識符的數(shù)據類型要在語義分析階段確認；標識符的地址可能要在目標代碼生成階段確定。

1-4編譯程序的基本組成

二、編譯過程舉例分析錯誤處理由不同用戶編寫的程序難免會包含各種類型的錯誤。編譯程序不僅要能及時地發(fā)現(xiàn)這些錯誤，而且還要將錯誤信息（如錯誤類型、出錯位置等）以恰當?shù)男问郊皶r地通知用戶。為了盡可能地多發(fā)現(xiàn)錯誤，編譯程序要設法將錯誤的影響限制在盡可能小的范圍內（這種處理方式稱為錯誤的局部化），以保證編譯程序在發(fā)現(xiàn)錯誤以后還能繼續(xù)完成剩余部分的分析處理（這種處理方式稱為續(xù)編譯）。更高級的錯誤處理程序還能夠糾正某些錯誤。課前測1、第一次采用形式化語法描述體系——BNF范式(BackusNormalForm巴科斯-諾爾范式)描述其語言語法體系結構的語言是？2、判斷(1)編譯程序是一個應用軟件。(2)編譯程序與具體的語言無關。(3)編譯程序與具體的機器有關。(4)對編譯程序而言,代碼優(yōu)化是不可缺少的一部分。(5)對編譯程序而言,中間代碼生成是不可缺少的一部分。(6)編譯程序生成的目標程序一定是可執(zhí)行的程序。(7)含有優(yōu)化部分的編譯程序的執(zhí)行效率高。

/learn/1000002001?tid=1000003000#/learn/content?type=detail&id=1000023011

1-4編譯程序的基本組成

二、編譯過程舉例分析（一個簡單的加法表達式語言）

1-4編譯程序的基本組成

二、編譯過程舉例分析（一個簡單的加法表達式語言）E∷=n|E+E

1-4編譯程序的基本組成

二、編譯過程舉例分析（一個簡單的加法表達式語言）add(){x=pop();y=pop();z=x+y;pushz;}

1-4編譯程序的基本組成

三、編譯程序的前端與后端詞法分析源程序語法分析語義分析中間代碼生成代碼優(yōu)化目標代碼生成目標程序讀取字母識別單詞潤色修飾分析語義關系構成語法關系初步寫出譯文最終定稿信息表管理錯誤檢查和處理前端前端

1-4編譯程序的基本組成

詞法分析識別獨立單詞并產生單詞流語法分析檢查語法規(guī)則和結構語義分析同時分析語義1.定義與源語言相關的部分被稱為編譯前端，包括詞法分析、語法分析、語義分析及中間代碼生成3個階段；與目標語言相關的部分被稱為編譯后端，包括代碼優(yōu)化和目標代碼生成2個階段。將編譯程序劃分為編譯前端和編譯后端，不僅有利于代碼優(yōu)化，而且對目標代碼的生成和移植更有利。三、編譯程序的前端與后端(1)可以給同一個編譯前端配不同的編譯后端，這樣就能在不同的計算機上構造出同一語言的編譯程序。例如，Java處理器就采用了這種思想，對不同的計算機，Java處理器的編譯前端是相同的，產生同一種類型的中間代碼——字節(jié)碼，而不同的計算機上配置了能夠解釋執(zhí)行這種中間代碼的編譯后端。(2）可以給不同的編譯前端配同一編譯后端，這樣就可以在同一計算機上生成多種語言的編譯程序。例如，被廣泛使用的GCC，其編譯前端是多種程序設計語言的不同分析器，支持C、C++、Objective-C++、Java、FORTRAN、Pascal、COBOL、Ada、Go等語言。GCC以這些語言的源程序文件作為輸入，經過詞法分析、語法分析和語義分析，產生一種抽象語法樹（AbstractSyntaxTree，AST）形式的中間代碼；GCC的編譯后端對AST形式的中間代碼進行分析處理，最終產生目標代碼。

1-4編譯程序的基本組成

詞法分析識別獨立單詞并產生單詞流語法分析檢查語法規(guī)則和結構語義分析同時分析語義1.定義從頭到尾掃描一遍源程序或等價源程序，并做有關加工處理，稱趟程(遍)。每經過一趟源程序都要進行等價變換并更接近目標程序。如果通過對源程序一遍掃描直接生成目標代碼程序，則說編譯程序是單遍的。把源程序分為幾遍來編譯，每遍只完成編譯程序中的一部分或幾個部分工作，稱為多遍的。比如第一遍進行詞法、語法分析，檢查語法錯誤；第二遍生成中間語言進行存儲分配；第三遍生成可運行的目標程序。如：IBMPCDOSPASCAL就是一個多遍掃描編譯程序。四、編譯程序的分遍

1-4編譯程序的基本組成

詞法分析識別獨立單詞并產生單詞流語法分析檢查語法規(guī)則和結構語義分析同時分析語義四、編譯程序的分遍

一遍掃描編譯程序源程序第一遍掃描程序中間語言1····

多遍掃描編譯程序

優(yōu)點：加工充分；出錯處理細致；目標程序質量高缺點：編譯時間長，開銷大中間語言n-1第n趟掃描程序目標程序源程序編譯程序目標程序多遍掃描的優(yōu)點彌補了單遍的缺點，單遍卻避免了多遍的缺點

1-4編譯程序的基本組成

識別獨立單詞并產生單詞流四、編譯程序的分遍2.決定分遍的因素（1）計算機存貯容量大?。唬?）編譯程序功能強弱；（3）源語言繁簡；（4）目標程序優(yōu)化程度；（5）設計和實現(xiàn)編譯程序時使用工具的先進性（6）參加人員多少和素質等。1-5編譯程序的構造方法

1-5編譯程序的構造方法

一、編譯程序的編寫語言直接用機器語言編寫編譯程序機器語言是早期編寫編譯程序的唯一工具，但由于機器語言難讀難寫，現(xiàn)在幾乎沒有人再使用。用匯編語言編寫編譯程序匯編語言太依賴于硬件環(huán)境，且程序過于冗長，很難開發(fā)大型的、邏輯復雜的編譯程序。由于匯編語言產生目標代碼效率較高，常用于編寫編譯程序的核心部分。機器語言匯編語言

1-5編譯程序的構造方法

機器語言和匯編語言直接編寫編譯程序優(yōu)點針對具體機器，充分發(fā)揮計算機系統(tǒng)功能生成的程序效率高缺點難讀難寫易出錯、難維護生產效率低一、編譯程序的編寫語言

1-5編譯程序的構造方法

用系統(tǒng)程序語言編寫編譯程序20世紀80年代以后，幾乎所有編譯程序都用高級語言編寫。系統(tǒng)程序設計語言：能夠編寫編譯程序或其他系統(tǒng)軟件的高級語言，如Pascal、C、C++、Java等。編譯器編譯器語言目標語言GCCC/C++C、C++、Fortran、Java、Go等ClangC++C、C++、Objective-C一、編譯程序的編寫語言

1-5編譯程序的構造方法

編譯程序的自動生成：源語言的定義以及機器語言的描述輸入到軟件中，自動生成該語言編譯程序詞法分析程序：Lex、Flex等語法分析程序：Yacc、ANTLR等編譯程序自動生成器L語言的編譯程序L語言的語法描述語義描述目標語言或機器描述二、編譯程序的自動生成自動化

1-5編譯程序的構造方法

T型圖：是用于描述編譯器實現(xiàn)時的一種輔助工具，可以用來表示源語言S、目標語言D、和編譯程序書寫語言W之間的關系。簡記為每個T型圖相當于一個編譯程序。SWDS表示源語言D表示目標語言W表示書寫語言JavaC語言機器碼源語言為Java目標語言為本機機器碼書寫語言為C語言三、T型圖

1-5編譯程序的構造方法

自編譯語言：如果一種高級語言與之相應的編譯程序也能直接用該語言本身寫出來，具有這種性質的語言稱為自編譯語言。一般說來，自編譯語言不但可以用來書寫其自身的編譯程序，而且也能用來書寫其他語言的編譯程序。C語言C語言A機器語言JavaC語言A機器語言四、自編譯

1-5編譯程序的構造方法

四、自編譯C語言A機器語言A機器語言C語言A機器語言A機器語言C語言C語言A機器語言C語言A機器語言A機器語言利用C語言開發(fā)C語言的自編譯過程①①②③A機器本身有編譯器

1-5編譯程序的構造方法

四、自編譯C語言A機器語言A機器語言JavaC語言A機器語言JavaA機器語言A機器語言利用C語言開發(fā)Java語言的自編譯過程

1-5編譯程序的構造方法

五、自展A機器語言A機器語言A機器語言A機器語言A機器語言利用語言開發(fā)語言的自編譯過程A機器語言A機器語言A機器語言A機器語言A機器語言利用語言開發(fā)語言的自編譯過程……自展過程，實際上就是用低級語言先實現(xiàn)一個簡單的編譯器，然后用這個編譯器的語言再去編寫一個更高級的編譯器的過程。自展：自展技術是利用自編譯技術，將一個功能較小的編譯程序，一級一級擴充而變成一個功能較強的編譯程序。

1-5編譯程序的構造方法

六、交叉編譯交叉編譯：如果一個A機器上編譯程序能產生B機器的目標代碼，則稱這種程序為交叉編譯程序。Compiling開發(fā)一個手機編譯器可以將程序編譯成手機可以運行的機器碼嗎？

1-5編譯程序的構造方法

六、交叉編譯CompilingInstallation利用電腦上的編譯程序，將軟件程序編譯為手機可以運行的機器碼。

1-5編譯程序的構造方法

六、交叉編譯目的平臺上不允許或不能夠安裝我們所需要的編譯器。目的平臺上的資源匱乏，無法運行我們所需要的編譯器。目的平臺還沒有建立。為什么需要交叉編譯？

1-5編譯程序的構造方法

六、交叉編譯（1）首先需要有一個可以在A機器上編譯高級語言L的編譯器①。LA機器語言A機器語言①（2）接下來使用L語言寫一個能夠產生B機器語言目標代碼的編譯程序②。LLB機器語言②（3）然后通過L語言的編譯程序就可以生成在A機器上可以運行的產生B機器代碼的編譯程序③。LA機器語言A機器語言①LLB機器語言②LA機器語言B機器語言③

1-5編譯程序的構造方法

七、移植移植技術是編譯程序開發(fā)中一項十分重要的技術。移植就是把一臺計算機上的軟件移植到另一臺計算機上去。移植方法有多種，下面簡單地介紹兩種典型的方法。①綜合幾種型號的計算機硬件特性，抽象出一種通用的匯編語言。每種型號的計算機上配有一個簡單的匯編程序，用來把通用的匯編語言書寫的程序翻譯成機器語言程序。采用這種方法抽象一種通用的匯編語言較為困難，因為這個通用的匯編語言既要便于書寫編譯程序，又要能夠在各種不同型號的計算機上高效運行。②利用交叉編譯技術將一臺計算機上由自編譯語言編寫的編譯程序移植到另一臺計算機上。

1-5編譯程序的構造方法

七、移植移植：將A機器上具有自編譯性的高級語言編譯程序移植到B機器上。（1）首先需要有一個可以在A機器上編譯高級語言L的編譯器①。LA機器語言A機器語言①（2）接下來使用L去寫一個能夠產生B機器語言目標代碼的編譯程序②。LLB機器語言②

1-5編譯程序的構造方法

七、移植（3）然后通過L語言的編譯程序就可以生成在A機器上可以運行的產生B機器代碼的編譯程序③。LA機器語言A機器語言①LLB機器語言②LA機器語言B機器語言③（4）最后使用編譯程序③編譯一遍②就可以得到能在B機器上運行的B機器代碼的編譯程序④。LA機器語言A機器語言①LLB機器語言②LA機器語言B機器語言③LLB機器語言②LB機器語言B機器語言④

1-5編譯程序的構造方法

八、小結利用自編譯、自展、交叉編譯和移植技術，使用系統(tǒng)程序設計語言書寫編譯程序，具有生產周期短、可靠性高、易修改、易擴充與維護、易于移植等特點。1-6編譯技術的應用

1-6編譯技術的應用

文本編輯器技術：詞法分析、語法分析、語法制導翻譯等簡介：文本編輯器通過對輸入文檔進行分析，實現(xiàn)關鍵字高亮、語法檢查（例如左右括號配對）等功能，引導用戶編輯出符合語言規(guī)范的程序文檔，提高開發(fā)效率關鍵字高亮和語法檢查一、編譯技術的應用

1-6編譯技術的應用

一、編譯技術的應用文本檢索工具簡介：諸如Word、VisualStudioCode等工具支持正則表達式文本檢索，正則表達式使用單個字符串來描述、匹配一系列匹配某個句法規(guī)則的字符串技術：詞法分析技術的串匹配技術Word使用通配符查找示例

1-6編譯技術的應用

一、編譯技術的應用文本格式化工具簡介：利用工具將源程序重新排版，輸出易讀清晰的程序結構。例如，關鍵字以不同的顏色出現(xiàn)，注釋用一種專門的字體標注，語句的嵌套層次結構采用縮進格式等技術：詞法分析、語法分析、語法制導翻譯等FineReader可將PDF轉換為各種格式

1-6編譯技術的應用

一、編譯技術的應用文本加密工具簡介：關鍵詞加密工具把文本中滿足特定特征的文本提取出來，并對提取出來的文本進行加密處理。文本加密工具本質上編寫詞法分析程序，對符合某種規(guī)則的單詞進行提取，再對所提取的單詞符號串進行加密技術：詞法分析待編碼內容HELLOWORLD關鍵詞HELLO加密后文本DAJJNWNRJO解密后文本HELLOWORLD置換密碼文本加密工具示例

1-6編譯技術的應用

一、編譯技術的應用網頁瀏覽器簡介：網頁瀏覽器本質上是一個HTML和XML的解釋器。瀏覽器獲取由HTML或XML描述的信息后對其進行分析，并根據分析的結果將網頁內容以相應的形式顯示出來技術：詞法分析、語法分析和語義處理顯示的網頁HTML語言

1-6編譯技術的應用

一、編譯技術的應用自然語言處理簡介：自然語言處理過程是計算機識別人類語言的過程，如信息抽取、機器翻譯、情感分析等。為了使計算機可以識別語言符號，必須對語言符號進行一定的處理，其中包括分詞與詞性標注、句法分析、語義角色標注等技術：詞法分析、語法分析和語義處理信息抽取機器翻譯情感分析自然語言理解語法分析語義處理詞法分析應用層認知層基礎層自然語言處理

1-6編譯技術的應用

本章通過介紹編譯技術的發(fā)展歷史和程序設計語言的發(fā)展過程，引出了編譯和解釋兩種程序設計語言的翻譯機制。隨后，介紹了編譯的過程、編寫編譯程序的一般方法和編譯程序的開發(fā)技術，展示了編譯技術的應用。二、小結第二章形式語言的基本知識2-1什么是形式語言2-2字母表和符號串的基本概念2-3用文法產生法描述語言2.3.1通過文法產生語言的方式2.3.2為已知的語言構造相應的文法2-4句型分析2.4.1短語和簡單短語2.4.2文法的二義性和語言的二義性2-5文法和語言的分類2-6文法的其他表示方法2-7C--語言的形式定義2-8小結2-1什么是形式語言2-2字母表和符號串的基本概念2-3用文法產生法描述語言2.3.1通過文法產生語言的方式2.3.2為已知的語言構造相應的文法2-4句型分析2.4.1短語和簡單短語2.4.2文法的二義性和語言的二義性2-5文法和語言的分類2-6文法的其他表示方法2-7C--語言的形式定義2-8小結2-1什么是形式語言源程序編譯程序目標程序如何確切地描述或定義高級程序設計語言????形式語言一、形式語言的提出2-1什么是形式語言形式語言是研究符號的語言，它僅考慮符號間的關系，不考慮含義。即用數(shù)學方法（主要是代數(shù)方法）對語言進行形式化描述。從非形式化的角度來講，語言是人們交流思想的工具，從語言學本身來說，也是一門古老的科學，在很早以前人們就用數(shù)學方法開始對語言學進行研究。1847年，俄國數(shù)學家布拉庫夫斯基就用概率論進行語法詞源及語言歷史比較研究。1904年，波蘭語言學家指出，語言學家不僅要掌握初等數(shù)學而且還要掌握高等數(shù)學。1931年，俄國數(shù)學家就用概率論研究俄語元音字母和輔音字母序列。特別是1946年電子計算機問世以來更加促使數(shù)學和語言學結合研究。一、形式語言的提出2-1什么是形式語言一、形式語言的提出1956年，28歲的N.Chomsky（喬姆斯基）在《信息論雜志》上發(fā)表了《語言描寫的三個模型》，他首次采用Markov模型來描寫自然語言，對于有限狀態(tài)模型、短語結構模型和轉換模型等三個模型，從語言學和數(shù)學的角度進行了理論上的分析，建立了形式語言理論，具有劃時代意義。2-1什么是形式語言一、形式語言的提出喬姆斯基將語言形式地定義為由一個字母表的字母組成的一些串的集合。對于任意一個語言，有一個字母表，可以在字母表上按照一定的形成規(guī)則定義一個文法，這個文法所產生的所有句子組成的集合就是這個文法所產生的語言。

例如：“我愛你”這條句子如何產生呢？我們可以這樣定義產生這條句子的規(guī)則：〈語句〉∷=〈主語〉〈謂語〉〈賓語〉〈主語〉::=我|你〈謂語〉::=愛|恨〈賓語〉::=他|你巴科斯-諾爾范式（BackusNormalForm，簡稱為巴科斯范式，簡記為BNF范式）2-1什么是形式語言一、形式語言的提出彼得·諾爾（PeterNaur）2005年圖靈獎獲得者約翰·巴克斯（John.WarnerBackus）1977年圖靈獎獲得者2-1什么是形式語言二、形式語言初探在剛才的例子中，我們看到了使用巴科斯范式描述產生句子的規(guī)則。我們——以“∷=”符號（或“→”符號）表示“定義為”；以“|”符號表示“或”，表示可選項；以“〈〉”符號表示語法實體（語法單位）。

〈語句〉∷=〈主語〉〈謂語〉〈賓語〉〈主語〉::=我|你〈謂語〉::=愛|恨〈賓語〉::=他|你2-1什么是形式語言二、形式語言初探那么：“我愛你”這條句子如何產生呢？〈語句〉∷=〈主語〉〈謂語〉〈賓語〉〈主語〉::=我|你〈謂語〉::=愛|恨〈賓語〉::=他|你〈語句〉〈主語〉〈謂語〉〈賓語〉+我愛你2-1什么是形式語言二、形式語言初探

〈語句〉∷=〈主語〉〈謂語〉〈賓語〉〈主語〉::=我|你〈謂語〉::=愛|恨〈賓語〉::=他|你〈語句〉〈主語〉〈謂語〉〈賓語〉+我愛你〈語句〉〈主語〉〈謂語〉〈賓語〉+我愛他〈語句〉〈主語〉〈謂語〉〈賓語〉+你愛他〈語句〉〈主語〉〈謂語〉〈賓語〉+你愛你〈語句〉〈主語〉〈謂語〉〈賓語〉+我恨你〈語句〉〈主語〉〈謂語〉〈賓語〉+我很他〈語句〉〈主語〉〈謂語〉〈賓語〉+你很他〈語句〉〈主語〉〈謂語〉〈賓語〉+你很你2-1什么是形式語言三、形式語言與自動機理論誕生1951-1956年期間，美國數(shù)學家Kleene（克林）在研究神經細胞時建立了自動機模型，使用該模型來識別一個語言。

控制部件輸入文件存儲輸出2-1什么是形式語言三、形式語言與自動機理論誕生形式語言與自動機理論正式誕生，迅速在計算機科學技術領域的得到了應用，成為計算機科學理論一個重要分支。文法生成法：就是用有限個規(guī)則來產生出語言中無限個句子，這種規(guī)則集合稱文法。自動機識別法：用自動機對語言中的句子進行識別，自動機是描述離散變量的一個系統(tǒng)（數(shù)學模型），在形式語言中稱為識別器，也可看成是一個識別程序。喬姆斯基1959將形式語言的研究成果和自動機的研究成果結合。2-1什么是形式語言三、形式語言與自動機理論誕生形式語言理論研究的對象不僅是自然語言，也有人工語言（包括計算機編程的高級語言）。喬姆斯基的形式語言理論得到了多重驗證，于是才為語言學界和計算機科學界所折服，“引發(fā)了語言學中的伽利略式的科學革命的開端”喬姆斯基的形式語言理論得到過計算機科學的三重驗證：驗證一、喬姆斯基的四型文法與四種語言自動機一一對應驗證二、計算機所使用的各種高級程序設計語言（ALGOL\C\Java等）都遵循一種程序語言文法描述的范式，即巴科斯范式驗證三、喬姆斯基用形式語言理論的思想證明了計算機科學的一個重大理論問題：計算機程序語言是否有歧義是不可判定的。2-1什么是形式語言2-2字母表和符號串的基本概念2-3用文法產生法描述語言2.3.1通過文法產生語言的方式2.3.2為已知的語言構造相應的文法2-4句型分析2.4.1短語和簡單短語2.4.2文法的二義性和語言的二義性2-5文法和語言的分類2-6文法的其他表示方法2-7C--語言的形式定義2-8小結2-2字母表和符號串的基本概念有限個元素的非空集合稱字母表，也稱符號集。它是組成一個語言最基本的成分。字母表中元素稱符號。習慣上用V、Σ或其它大寫字母表示。例如V={a,b,c}，V={α,β…ω}等都是字母表。|V|表示字母表中符號的個數(shù)。對于不同程序設計語言有不同字母表。例如，機器語言字母表={0,1}，PASCAL語言的字母表由字母、數(shù)字以及一些特殊符號，如+，-，*，/，·，(，)，=，…等組成。注意：在一個語言中不能出現(xiàn)字母表以外的符號。一、字母表2-2字母表和符號串的基本概念一、字母表109（１）Ｃ語言字母表是什么？（２）Java語言字母表是什么？2-2字母表和符號串的基本概念二、符號串1）定義——符號串是字母表中的符號所組成的任何有窮序列例如：設V={a,b,c},則符號串有a,b,c,aa,ab,ac,ba,abc…又如：設V={0,1},則符號串有0，1，00，01，10，11，000…由上例可以看出，符號串與符號組成順序有關，如符號串ab不同于ba，符號串01不同于10，今后我們常用t,u,v,…x,y,z等小寫字母表示符號串。2-2字母表和符號串的基本概念2）空符號串——不包含任何符號的符號串稱為空符號串，記為ε。3）符號串長度——符號串中所含符號個數(shù)稱為該符號串的長度，設符號串為x，則用|x|來表示x的長度。例如：x=abc，則|x|=3,顯然,|ε|=？|ε|=0二、符號串字母表Σ上的符號串是字母表中的符號組成的任何有窮序列，可以按照下述規(guī)則定義：（1）ε是Σ上的符號串，稱為“空符號串”，它不包含Σ中的任何符號；（2）Σ中的每個符號都是Σ上的符號串；（3）如果x是Σ上的符號串，y是Σ上的符號串，則xy也是Σ上的符號串（xy被稱為符號串x和符號串y的連接）2-2字母表和符號串的基本概念二、符號串2-2字母表和符號串的基本概念三、符號串的運算1）符號串的聯(lián)結設有符號串X和Y，則它們的聯(lián)結XY是將符號串Y直接拼接在符號串X之后，即X=x1x2x3…xm,Y=y1y2y3…yn則XY=x1x2x3…xmy1y2y3…ynεX=？，Xε=？顯然εX=X，Xε=X2-2字母表和符號串的基本概念三、符號串的運算2）符號串的方冪設有符號串X,則X的n次聯(lián)結稱為X的n次方冪則：X0=ε，X1=x，X2=XX，X3=XXX，…Xn=XX…X如若X=abc則X0=ε,X1=abc,X2=abcabcX3=abcabcabc2-2字母表和符號串的基本概念三、符號串的運算3）符號串的頭、尾和子串設有符號串X，把X的尾部去掉若干符號（包括0個符號）之后所余下部分稱為X的頭。設有符號串X，把X的頭部去掉若干符號（包括0個符號）之后所余下部分稱為X的尾。若X的頭（尾）不是X本身，則稱X的真頭（尾）。2-2字母表和符號串的基本概念三、符號串的運算3）符號串的頭、尾和子串從一個符號串中刪去一個頭和尾后所余下的部分稱為此符號串的子串，如果刪去的頭和尾不同時為ε，則該子串是真子串。如X=abcX的頭：ε、a、ab、abc X的尾：ε、c、bc、abcX的真頭：ab、a、ε X的真尾：ε、c、bc、X的子串：ε、a、b、c、ab、bc、abcX的真子串：ε、a、b、c、ab、bc

2-2字母表和符號串的基本概念四、符號串的集合若集合A中的一切元素都是字母表上符號串，則稱A為該字母表上的符號串集合。每個形式語言都是某個字母表上按照某種規(guī)則構成的所有符號串的集合，因此也可以把符號串集合A稱為字母表Σ上定義的某種語言用大寫字母A、B、C……來表示字母表上符號串集合。例如：設V={0，1},則符號串集合A={ε，0，1，01}B={0，11，00，111}對于符號串集合不可能窮盡一切元素時，可以用集合中符號串所應滿足的條件來刻畫一個符號串集合，即{x|x滿足條件C}。例如：{x|x全由1組成}

2-2字母表和符號串的基本概念五、符號串的集合的運算1）符號串集合的連接假設L1是定義在Σ1上的符號串集合，L2是定義在Σ2上的符號串集合，L1和L2的連接運算由以下公式定義：L1L2={xy|x∈L1,y∈L2}從該公式可以看出，符號串集合的連接運算和集合的笛卡爾積運算非常相似，但只有兩個符號串集合在同一個集合上定義，才能進行笛卡爾積運算，而連接運算對此沒有要求如：V={0，1}W={a,b}若，A={0，101}B={10，11，110}C={a,ab}則，AB={010，011，0110，10110，10111，101110}AC={0a,0ab,101a,101ab}2-2字母表和符號串的基本概念五、符號串的集合的運算1）符號串集合的連接這里特別注意——假設令Φ表示空集，A為任意非空的符號串集合，則：ΦA=AΦ=Φ而，對于含有空符號串的集合：{ε}有：{ε}A=A{ε}=A2-2字母表和符號串的基本概念五、符號串的集合的運算2）符號串集合的方冪設符號串集合AV*則A0={ε},A1=A,A2=AA,A3=AAA,…An=AAA…A如：設A={a,b}，則A0={ε},A1={a,b}，A2={a,b}{a,b}={aa,ab,ba,bb}A3={aaa,aab,aba,abb,baa,bab,bba,bbb}∩2-2字母表和符號串的基本概念五、符號串的集合的運算3）符號串集合的閉包與正閉包如A={a,b}則A+={a,b}∪{aa,ab,ba,bb}∪…={a,b,aa,ab,ba,bb,aaa,…,bbb,…}A*={ε,a,b,aa,ab,ba,bb,aaa,…bbb,…}符號串集合L是定義在∑上的集合，L的閉包記為L*，其定義如下：（1）L0={ε}；（2）對于n≥1，Ln=LLn-1；（3）L*=∪Ln，n∈{0,1,2,…}。符號串集合L的正閉包記為L+，L+=∪Ln（n≥1），顯然L*=L+∪{ε}2-2字母表和符號串的基本概念五、符號串的集合的運算3）符號串集合的閉包與正閉包假設A為符號串集合，我們可以證明：A+=AA*=A*AAA*=A（A0∪A1∪A2∪…An∪…）=A1∪A2∪…An∪…=A+2-2字母表和符號串的基本概念六、行集合因為∑本身也是字母表∑上的符號串集合，因此將符號串集合∑的閉包∑*稱為行集合，表示字母表∑中的符號組成的任意長度的符號串所組成的集合（包括ε符號串）。顯然對于∑上定義的任何符號串集合V都是行集合∑*的子集，任何符號串集合的閉包V*都是行集合∑*的子集?！?V*A*2-1什么是形式語言2-2字母表和符號串的基本概念2-3用文法產生法描述語言2.3.1通過文法產生語言的方式2.3.2為已知的語言構造相應的文法2-4句型分析2.4.1短語和簡單短語2.4.2文法的二義性和語言的二義性2-5文法和語言的分類2-6文法的其他表示方法2-7C--語言的形式定義2-8小結

2-3語言和文法的形式定義

枚舉法，如果一個語言僅包含有限條句子，就可以采用枚舉法來描述此語言，把語言中每條句子都列舉出來即可；自動機識別法，在這種方法中，每種語言對應一種自動機（即某種算法），由它判定一個符號串是否在該語言中；文法產生法，這種方法是為每種語言定義一組文法規(guī)則，從而產生該語言中的每條句子。本小節(jié)主要介紹一種利用巴科斯-諾爾范式（BackusNormalForm，簡稱為巴科斯范式，簡記為BNF范式）產生語言的方法。一、描述語言的三種方式句子是由本語言字母表上符號按照一定規(guī)則組成的符號串。2.3.1通過文法產生語言的方式

2-3語言和文法的形式定義

二、巴科斯-諾爾范式巴科斯范式是描述語法規(guī)則一種表示方法，它是由巴科斯為了在ALGOL60報告中來描述ALGOL語言首先提出的。采用這種形式體系方式定義語法規(guī)則,可以用簡潔的公式把各種語法規(guī)則嚴格而清晰描述出來。例如，在高級語言中大家所熟知的〈標識符〉這種語法成分，它用巴科斯范式描述為:〈標識符〉∷=〈字母〉|〈標識符〉〈字母〉|〈標識符〉〈數(shù)字〉而〈字母〉∷=a|b|c|d|…|z〈數(shù)字〉∷=0|1|2|…|92.3.1通過文法產生語言的方式

2-3語言和文法的形式定義

二、巴科斯-諾爾范式〈標識符〉∷=〈字母〉|〈標識符〉〈字母〉|〈標識符〉〈數(shù)字〉而〈字母〉∷=a|b|c|d|…|z〈數(shù)字〉∷=0|1|2|…|9這樣便刻畫出了〈標識符〉是以字母開始的一串字母和數(shù)字任意組合這種特點。在剛才的例子中，我們看到了使用巴科斯范式描述產生句子的規(guī)則。我們——以“∷=”符號（或“→”符號）表示“定義為”；以“|”符號表示“或”，表示可選項；以“〈〉”符號表示語法實體（語法單位）。2.3.1通過文法產生語言的方式

2-3語言和文法的形式定義

三、產生式產生式是只有一個候選式的文法規(guī)則，是一個非空符號串和另一個符號串的有序偶（α,β），記為α∷=β或α→β。α稱為產生式的左部，β是產生式的右部。α→β表示左部α定義為右部β。2.3.1通過文法產生語言的方式如果α有多個候選式（α∷=β1，α∷=β2，…，α∷=βn），那么可以寫成合并規(guī)則α∷=β1|β2|…|βn。

2-3語言和文法的形式定義

四、字匯表（1）定義用于產生式左部和右部中所有符號形成集合為字匯表，記為V。（2）字匯表的分類1）非終結符號出現(xiàn)在產生式左部，且能派生出符號或符號串的那些符號稱為非終結符，也稱語法實體或語法單位，它們的全體構成一個非終結符的集合，記為VN2）終結符號產生式中不屬于VN的那些符號稱為終結符，它們的全體組成終結符的集合，記為VT。終結符一般出現(xiàn)在規(guī)則的右部。顯然，V=VN∪VT，VN∩VT=?，2.3.1通過文法產生語言的方式

2-3語言和文法的形式定義

四、字匯表（3）實例

由此得：VN={〈字母〉,〈數(shù)字〉,〈標識符〉}VT={a,b,…,z,0,1,…9,}〈標識符〉∷=〈字母〉|〈標識符〉〈字母〉|〈標識符〉〈數(shù)字〉而〈字母〉∷=a|b|c|d|…|z〈數(shù)字〉∷=0|1|2|…|92.3.1通過文法產生語言的方式

2-3語言和文法的形式定義

五、文法（1）定義：文法是規(guī)則的有窮集合,形式定義為四元組形式為G=(VN,VT,P,Z)其中：VN是非終結符集合, VT是終結符集合, P代表產生式集, Z∈VN是文法G開始符號，也稱識別符號，它至少要在一條產生式左部出現(xiàn)。文法G通常記為G［Z］。2.3.1通過文法產生語言的方式

2-3語言和文法的形式定義

五、文法（2）實例1標識符文法可定義如下:G［Z］=(VN,VT,P,Z)VN={〈字母〉,〈數(shù)字〉,〈標識符〉}VT={a,b,…,z,0,1,…9}P由下列規(guī)則組成:〈標識符〉∷=<字母>|<標識符><字母>|<標識符><數(shù)字>〈字母〉∷=a|b|…|z〈數(shù)字〉∷=0|1|…|9Z=〈標識符〉2.3.1通過文法產生語言的方式

2-3語言和文法的形式定義

五、文法（3）實例2例如：文法G=(VN,VT,P,S)VN={A,B}VT={c,d}P={A→Bc,B→d}S=A通常情況下，在對文法的描述時可以省略VN和VT，文法的開始符號也可以不需要“顯式地”指定，僅需將開始符號寫在G后的中括號中即可。上述文法可以描述為：G[A]:A→Bc，B→d2.3.1通過文法產生語言的方式

2-3語言和文法的形式定義

六、推導和歸約定義1：文法G=(VN,VT,P,S)有一條產生式α→β，α∈(VN∪VT)+，β∈(VN∪VT)*，假設存在符號串x,y∈(VN∪VT)*，使得有符號串v和w滿足v=xαy和w=xβy，則稱符號串v直接推導出符號串w，符號串w直接歸約到符號串v，并把符號串w叫做符號串v的直接派生式，記為：vw顯然，如果x=y=ε，對于文法G的任何規(guī)則α→β，一定有αβ，一次直接推導其實就是用產生式右部去替換左部的過程。一個產生式就是一個直接推導。實例1：G[A]:A→Bc，B→d而A直接推導到Bc，而Bc直接歸約到A。2.3.1通過文法產生語言的方式

2-3語言和文法的形式定義

六、推導和歸約實例22.3.1通過文法產生語言的方式文法G[S]:S→0S|01S01S0S001S0S00S0001

2-3語言和文法的形式定義

六、推導和歸約實例32.3.1通過文法產生語言的方式G[<標識符>]：<標識符>∷=<字母>|<下劃線>|<標識符><字母>|<標識符><下劃線>|<標識符><數(shù)字><字母>∷=a|b|c|…|z<下劃線>∷=_<數(shù)字>∷=0|1|2…|9<標識符><字母><標識符><字母>A<標識符><標識符><數(shù)字><字母><數(shù)字>a<數(shù)字>a4

2-3語言和文法的形式定義

六、推導和歸約定義2：設u0,u1,u2,…,un均為V*上符號串,若w是v經過一系列直接推導得到的。即：v=u0u1u2…un-1un=w(n>0)則稱v推導到w，或稱w歸約到v，記作：v+w稱這個直接推導序列為長度為n的推導。如果v+w或者v=w（表示0步推導），則記作v*w稱v廣義推導到w或稱w廣義歸約到v。2.3.1通過文法產生語言的方式

2-3語言和文法的形式定義

六、推導和歸約顯然，直接推導的長度為1，推導+的長度≥1，而廣義推導*的長度≥0例如對于文法G[S]:S∷=0SS∷=01,S0S