編譯技術(shù)原理及方法PPT完整全套教學(xué)課件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1-3程序設(shè)計(jì)語言的翻譯機(jī)制

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

1-3程序設(shè)計(jì)語言的翻譯機(jī)制

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

1-3程序設(shè)計(jì)語言的翻譯機(jī)制

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

1-3程序設(shè)計(jì)語言的翻譯機(jī)制

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

1-3程序設(shè)計(jì)語言的翻譯機(jī)制

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

源程序編譯程序目標(biāo)程序（機(jī)器語言）源程序編譯程序目標(biāo)程序（匯編語言）匯編程序目標(biāo)程序（機(jī)器語言）編譯階段編譯階段匯編階段

1-3程序設(shè)計(jì)語言的翻譯機(jī)制

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

1-3程序設(shè)計(jì)語言的翻譯機(jī)制

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

1-3程序設(shè)計(jì)語言的翻譯機(jī)制

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

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

為了提高熱點(diǎn)代碼的執(zhí)行效率，就會(huì)將這些“熱點(diǎn)代碼”編譯成與本地機(jī)器相關(guān)的機(jī)器碼，進(jìn)行各個(gè)層次的優(yōu)化。完成這個(gè)任務(wù)的編譯器就是即時(shí)編譯器（JIT）。

1-3程序設(shè)計(jì)語言的翻譯機(jī)制

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

1-3程序設(shè)計(jì)語言的翻譯機(jī)制

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

1-3程序設(shè)計(jì)語言的翻譯機(jī)制

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

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

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

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

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

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

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

這個(gè)簡(jiǎn)單程序中，可以識(shí)別出的單詞如下：

intmainfloatprintfreturn關(guān)鍵詞{}=*+()%,;““特殊符號(hào)ab標(biāo)識(shí)符03無符號(hào)整數(shù)

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

二、編譯過程舉例分析將單詞轉(zhuǎn)換為內(nèi)部編碼

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

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

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

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

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

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

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

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

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

(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)化的目標(biāo)是使得生成的目標(biāo)程序占有內(nèi)存少，運(yùn)行速度快。對(duì)上述四元式序列進(jìn)行代碼優(yōu)化，可以在編譯時(shí)將整型變量3轉(zhuǎn)換成浮點(diǎn)型變量3.0，以免在運(yùn)行時(shí)再進(jìn)行整型變量到浮點(diǎn)型變量的轉(zhuǎn)換。由于t2在四元式（3）中是單目運(yùn)算，因此可以用a代替t2。這樣再次優(yōu)化后得到的四元式序列如下(*,3.0,a,t1)(2)(+,t1,b,t2)(3)(=,t2,,a)改進(jìn)后(1)(itf,3,,t1）(2)(*,t1,a,t2)(3)(+,t2,b,t3)(4)(=,t3,,a)改進(jìn)后(*,3.0,a,t1)(2)(+,t1,b,a)

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

二、編譯過程舉例分析目標(biāo)代碼生成目標(biāo)代碼生成就是將中間語言代碼轉(zhuǎn)換成機(jī)器語言程序或匯編語言程序，最后完成翻譯。

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

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

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

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

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

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

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

二、編譯過程舉例分析（一個(gè)簡(jiǎn)單的加法表達(dá)式語言）

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

二、編譯過程舉例分析（一個(gè)簡(jiǎn)單的加法表達(dá)式語言）E∷=n|E+E

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

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

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

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

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

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

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

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

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

詞法分析識(shí)別獨(dú)立單詞并產(chǎn)生單詞流語法分析檢查語法規(guī)則和結(jié)構(gòu)語義分析同時(shí)分析語義四、編譯程序的分遍

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

多遍掃描編譯程序

優(yōu)點(diǎn)：加工充分；出錯(cuò)處理細(xì)致；目標(biāo)程序質(zhì)量高缺點(diǎn)：編譯時(shí)間長(zhǎng)，開銷大中間語言n-1第n趟掃描程序目標(biāo)程序源程序編譯程序目標(biāo)程序多遍掃描的優(yōu)點(diǎn)彌補(bǔ)了單遍的缺點(diǎn)，單遍卻避免了多遍的缺點(diǎn)

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

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

六、交叉編譯交叉編譯：如果一個(gè)A機(jī)器上編譯程序能產(chǎn)生B機(jī)器的目標(biāo)代碼，則稱這種程序?yàn)榻徊婢幾g程序。Compiling開發(fā)一個(gè)手機(jī)編譯器可以將程序編譯成手機(jī)可以運(yùn)行的機(jī)器碼嗎？

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

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

1-5編譯程序的構(gòu)造方法

八、小結(jié)利用自編譯、自展、交叉編譯和移植技術(shù)，使用系統(tǒng)程序設(shè)計(jì)語言書寫編譯程序，具有生產(chǎn)周期短、可靠性高、易修改、易擴(kuò)充與維護(hù)、易于移植等特點(diǎn)。1-6編譯技術(shù)的應(yīng)用

1-6編譯技術(shù)的應(yīng)用

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

1-6編譯技術(shù)的應(yīng)用

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

1-6編譯技術(shù)的應(yīng)用

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

1-6編譯技術(shù)的應(yīng)用

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

1-6編譯技術(shù)的應(yīng)用

一、編譯技術(shù)的應(yīng)用網(wǎng)頁(yè)瀏覽器簡(jiǎn)介：網(wǎng)頁(yè)瀏覽器本質(zhì)上是一個(gè)HTML和XML的解釋器。瀏覽器獲取由HTML或XML描述的信息后對(duì)其進(jìn)行分析，并根據(jù)分析的結(jié)果將網(wǎng)頁(yè)內(nèi)容以相應(yīng)的形式顯示出來技術(shù)：詞法分析、語法分析和語義處理顯示的網(wǎng)頁(yè)HTML語言

1-6編譯技術(shù)的應(yīng)用

一、編譯技術(shù)的應(yīng)用自然語言處理簡(jiǎn)介：自然語言處理過程是計(jì)算機(jī)識(shí)別人類語言的過程，如信息抽取、機(jī)器翻譯、情感分析等。為了使計(jì)算機(jī)可以識(shí)別語言符號(hào)，必須對(duì)語言符號(hào)進(jìn)行一定的處理，其中包括分詞與詞性標(biāo)注、句法分析、語義角色標(biāo)注等技術(shù)：詞法分析、語法分析和語義處理信息抽取機(jī)器翻譯情感分析自然語言理解語法分析語義處理詞法分析應(yīng)用層認(rèn)知層基礎(chǔ)層自然語言處理

1-6編譯技術(shù)的應(yīng)用

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

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

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

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

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

2-2字母表和符號(hào)串的基本概念五、符號(hào)串的集合的運(yùn)算1）符號(hào)串集合的連接假設(shè)L1是定義在Σ1上的符號(hào)串集合，L2是定義在Σ2上的符號(hào)串集合，L1和L2的連接運(yùn)算由以下公式定義：L1L2={xy|x∈L1,y∈L2}從該公式可以看出，符號(hào)串集合的連接運(yùn)算和集合的笛卡爾積運(yùn)算非常相似，但只有兩個(gè)符號(hào)串集合在同一個(gè)集合上定義，才能進(jìn)行笛卡爾積運(yùn)算，而連接運(yùn)算對(duì)此沒有要求如：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字母表和符號(hào)串的基本概念五、符號(hào)串的集合的運(yùn)算1）符號(hào)串集合的連接這里特別注意——假設(shè)令Φ表示空集，A為任意非空的符號(hào)串集合，則：ΦA(chǔ)=AΦ=Φ而，對(duì)于含有空符號(hào)串的集合：{ε}有：{ε}A=A{ε}=A2-2字母表和符號(hào)串的基本概念五、符號(hào)串的集合的運(yùn)算2）符號(hào)串集合的方冪設(shè)符號(hào)串集合AV*則A0={ε},A1=A,A2=AA,A3=AAA,…An=AAA…A如：設(shè)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字母表和符號(hào)串的基本概念五、符號(hào)串的集合的運(yùn)算3）符號(hào)串集合的閉包與正閉包如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,…}符號(hào)串集合L是定義在∑上的集合，L的閉包記為L(zhǎng)*，其定義如下：（1）L0={ε}；（2）對(duì)于n≥1，Ln=LLn-1；（3）L*=∪Ln，n∈{0,1,2,…}。符號(hào)串集合L的正閉包記為L(zhǎng)+，L+=∪Ln（n≥1），顯然L*=L+∪{ε}2-2字母表和符號(hào)串的基本概念五、符號(hào)串的集合的運(yùn)算3）符號(hào)串集合的閉包與正閉包假設(shè)A為符號(hào)串集合，我們可以證明：A+=AA*=A*AAA*=A（A0∪A1∪A2∪…An∪…）=A1∪A2∪…An∪…=A+2-2字母表和符號(hào)串的基本概念六、行集合因?yàn)椤票旧硪彩亲帜副怼粕系姆?hào)串集合，因此將符號(hào)串集合∑的閉包∑*稱為行集合，表示字母表∑中的符號(hào)組成的任意長(zhǎng)度的符號(hào)串所組成的集合（包括ε符號(hào)串）。顯然對(duì)于∑上定義的任何符號(hào)串集合V都是行集合∑*的子集，任何符號(hào)串集合的閉包V*都是行集合∑*的子集?！?V*A*2-1什么是形式語言2-2字母表和符號(hào)串的基本概念2-3用文法產(chǎn)生法描述語言2.3.1通過文法產(chǎn)生語言的方式2.3.2為已知的語言構(gòu)造相應(yīng)的文法2-4句型分析2.4.1短語和簡(jiǎn)單短語2.4.2文法的二義性和語言的二義性2-5文法和語言的分類2-6文法的其他表示方法2-7C--語言的形式定義2-8小結(jié)

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

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

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

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

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

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

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

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

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

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

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

四、字匯表（3）實(shí)例

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

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

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

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

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

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

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

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

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

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

六、推導(dǎo)和歸約實(shí)例22.3.1通過文法產(chǎn)生語言的方式文法G[S]:S→0S|01S01S0S001S0S00S0001

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

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

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

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

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

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