語言處理器引論ppt課件

《語言處理器引論ppt課件》由會員分享，可在線閱讀，更多相關(guān)《語言處理器引論ppt課件（46頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

第一章 引論,1,第一章：引論,翻譯器的不同形式 編譯器、解釋器、混合編譯器 典型編譯器結(jié)構(gòu) 編譯系統(tǒng) 程序設(shè)計(jì)語言發(fā)展歷程,2,1.1 語言處理器（1.1）,翻譯器 能夠完成從一種語言到另一種語言變換的軟件,源語言,目標(biāo)語言,翻譯器,3,,1.1 語言處理器,翻譯器,,,編譯器,解釋器,混合編譯器,4,編程語言排行榜,TIOBE Index for February 2018,5,1.1 語言處理器,一個語言處理系統(tǒng)：圖1.5 預(yù)處理器 編譯器 匯編器 連接器/加載器,6,1.1 語言處理器,編譯器 編譯器是一種翻譯器 特點(diǎn)：目標(biāo)語言比源語言低級 編程語言 傳統(tǒng)程序設(shè)計(jì)語言：Pascal、C++、Java 專用語言：Lisp、Prolog、LaTeX,編程語言,機(jī)器語言,編譯器,7,1.1 語言處理器,編譯器 編譯器是一種翻譯器 特點(diǎn)：目標(biāo)語言比源語言低級 機(jī)器語言（操作：寄存器BX的內(nèi)容送到AX中) 機(jī)器指令 1000100111011000 匯編指令 mov ax,bx,編程語言,機(jī)器語言,編譯器,8,1.1 語言處理器,編譯器 編譯器是一種翻譯器 特點(diǎn)：目標(biāo)語言比源語言低級,編程語言,機(jī)器語言,編譯器,9,1.2 編譯器結(jié)構(gòu)（1.2）,分析部分 前端：源程序-中間表示 綜合部分 后端：中間表示-目標(biāo)程序,10,1.2 編譯器結(jié)構(gòu),一個編譯器的各個步驟 圖1.6 編譯器的工作可以分成若干階段，每個階段把源程序從一種表示變換成另一種表示。 符號表管理器 出錯管理器,11,1.2 編譯器結(jié)構(gòu),一個編譯器的各個步驟 實(shí)例：圖1.7一個賦值語句的翻譯,12,1.2 編譯器結(jié)構(gòu),,前端,,后端,13,1.2 編譯器結(jié)構(gòu),編譯器的前端與后端 前端：只依賴于源語言 后端：編譯器中依賴于目標(biāo)機(jī)器的部分，一般獨(dú)立于源語言，而與中間語言有關(guān)。 前端+后端：組合 取一個編譯器前端，重寫它的后端以產(chǎn)生同一源語言在另一機(jī)器上的編譯器 把幾種不同的語言編譯成同一種中間語言，讓不同的前端使用同一后端，從而得到一臺機(jī)器上的幾個編譯器 編譯的幾個階段常用一趟/遍（pass）掃描來實(shí)現(xiàn)，一趟/遍掃描包括讀一個輸入文件和寫一個輸出文件。,14,1.2 編譯器結(jié)構(gòu),詞法分析 逐個讀構(gòu)成源程序的字符，把它們組成詞法單元(token)流。 實(shí)例：position = initial + rate * 60 （１）標(biāo)識符（position） （２）賦值號（:=） （３）標(biāo)識符（initial） （４）加號（＋） （５）標(biāo)識符（rate） （６）乘號（＊） （７）數(shù)（60）,15,1.2 編譯器結(jié)構(gòu),詞法分析 逐個讀構(gòu)成源程序的字符，把它們組成詞法單元(token)流。 實(shí)例： 編譯器的詞法分析也叫做線性分析或掃描。,詞法分析,position = initial + rate * 60,,16,1.2 編譯器結(jié)構(gòu),語法分析 把詞法記號流依照語言的語法結(jié)構(gòu)按層次分組，以形成語法短語。 實(shí)例： position = initial + rate * 60 的語法分析樹,17,1.2 編譯器結(jié)構(gòu),語法分析 表達(dá)式、語句等程序?qū)哟谓Y(jié)構(gòu)通常由遞歸的規(guī)則表示 實(shí)例：表達(dá)式 任何一個標(biāo)識符都是表達(dá)式； 任何一個數(shù)都是表達(dá)式； 如果ｅ１和ｅ２都是表達(dá)式，那么ｅ１＋ ｅ２、ｅ１＊ ｅ２、（ｅ１）、（ｅ2）也都是表達(dá)式。,18,1.2 編譯器結(jié)構(gòu),語法分析 表達(dá)式、語句等程序?qū)哟谓Y(jié)構(gòu)通常由遞歸的規(guī)則表示 實(shí)例：語句 如果identifier是標(biāo)識符，expression是表達(dá)式，那么 identifier := expression是語句。 如果 expression 是表達(dá)式，statement是語句，那么 while (expression) do statement if (expression) then statement 也都是語句。,19,1.2 編譯器結(jié)構(gòu),語法分析 把詞法記號流依照語言的語法結(jié)構(gòu)按層次分組，以形成語法短語。 實(shí)例：position = initial + rate * 60 的語法樹,20,1.2 編譯器結(jié)構(gòu),語義分析 檢查程序的語義正確性，以保證程序各部分能有意義地結(jié)合在一起，為后面代碼生成階段收集類型信息。 類型轉(zhuǎn)換 類型檢查 語法制導(dǎo)翻譯,,real型,21,1.2 編譯器結(jié)構(gòu),中間代碼生成 中間代碼位于高級編程語言和機(jī)器語言（目標(biāo)程序）之間 后綴表示: 9+5-2 ? 95+2- 抽象語法樹: 三地址碼,22,1.2 編譯器結(jié)構(gòu),代碼優(yōu)化 改進(jìn)代碼，以產(chǎn)生執(zhí)行較快的機(jī)器代碼。,,23,1.2 編譯器結(jié)構(gòu),目標(biāo)代碼生成 生成可重定位的機(jī)器代碼或匯編碼 為源程序所用的每個變量選擇存儲單元，并且把中間代碼翻譯成等價的機(jī)器指令序列。 關(guān)鍵問題是寄存器分配。,,24,1.2 編譯器結(jié)構(gòu),符號表管理 編譯器的一項(xiàng)重要工作是記錄源程序中使用的標(biāo)識符，并收集每個標(biāo)識符的各種屬性。 這些屬性提供標(biāo)識符的存儲分配、類型和作用域信息。 如果是過程標(biāo)識符，還有參數(shù)的個數(shù)和類型、參數(shù)傳遞方式和返回值類型。 符號表是為每個標(biāo)識符保存一個記錄的數(shù)據(jù)結(jié)構(gòu)，記錄的域是標(biāo)識符的屬性。 該數(shù)據(jù)結(jié)構(gòu)允許我們迅速地找到一個標(biāo)識符的記錄，在此記錄中存儲和讀取數(shù)據(jù)。,25,1.2 編譯器結(jié)構(gòu),符號表管理 實(shí)例 語句 position = initial + rate * 60 詞法分析器發(fā)現(xiàn)源程序的標(biāo)識符時，把該標(biāo)識符填入符號表。但是，詞法分析期間不能確定一個標(biāo)識符的屬性。 例如： 其余的階段把標(biāo)識符的信息填入符號表，然后以不同的方式使用這些信息,26,1.2 編譯器結(jié)構(gòu),出錯管理 每個階段都可能發(fā)現(xiàn)源程序的錯誤。發(fā)現(xiàn)錯誤后，該階段必須處理此錯誤，使得編譯可以繼續(xù)進(jìn)行，以便進(jìn)一步發(fā)現(xiàn)源程序的其他錯誤。 詞法分析：當(dāng)前被掃描的字符串不能形成語言的詞法記號。 語法分析：記號流違反語言的語法規(guī)則。 語義分析：編譯器試圖找出語法正確但對所含的操作來說是無意義的結(jié)構(gòu)，如相加的兩個標(biāo)識符，其一是數(shù)組名，另一個是過程名。,27,1.3 編譯系統(tǒng),除了編譯器外，還需要一些其他工具的幫助，才能得到可執(zhí)行的目標(biāo)程序，這些工具包括預(yù)處理器、匯編器和連接器等 C語言的編譯系統(tǒng) Java語言的編譯系統(tǒng),28,1.3 編譯系統(tǒng),C語言的編譯系統(tǒng) 一個語言處理系統(tǒng)：圖1.5 設(shè)有兩個文件 main.c swap.c gcc–v–o swap main.c swap.c -v 可以輸出該編譯系統(tǒng)各步驟執(zhí)行的命令和執(zhí)行結(jié)果 -o 指示生成的可執(zhí)行文件的名字,29,1.3 編譯系統(tǒng),C語言的編譯系統(tǒng) 預(yù)處理器 實(shí)現(xiàn)文件包含 #include 實(shí)現(xiàn)宏展開 #define pi 3.1415926 條件編譯 #if 、#ifdef,30,1.3 編譯系統(tǒng),C語言的編譯系統(tǒng) 匯編器：對輸入進(jìn)行兩遍掃描 第一遍，匯編器掃描輸入，將表示存儲單元的所有標(biāo)識符都存入符號表，并分配地址。 第二遍，匯編器再次掃描輸入，把每個操作碼翻譯成機(jī)器語言中代表那個操作的位串，并把代表存儲單元的每個標(biāo)識符翻譯成符號表中為這個標(biāo)識符分配的地址。 gcc –S main.c as –o main.o main.s,31,1.3 編譯系統(tǒng),C語言的編譯系統(tǒng) 連接器：收集、組織程序所需的不同代碼和數(shù)據(jù) 靜態(tài)連接器：將多個可重定位目標(biāo)文件組成一個可執(zhí)行目標(biāo)文件（也可以組成一個可重定位目標(biāo)文件） 動態(tài)連接器：支持在內(nèi)存中的可執(zhí)行程序在執(zhí)行時與共享目標(biāo)文件進(jìn)行動態(tài)的連接。,32,1.3 編譯系統(tǒng),Java語言的編譯系統(tǒng) 一般的高級語言程序如果要在不同的平臺上運(yùn)行，至少需要編譯成不同的目標(biāo)代碼。 Java虛擬機(jī)技術(shù)是實(shí)現(xiàn)Java平臺無關(guān)性特點(diǎn)的關(guān)鍵。 Java虛擬機(jī)語言（簡稱JVML） JVML程序只需要與虛擬機(jī)交互，不需要關(guān)心底層的硬件和操作系統(tǒng)。,33,1.3 編譯系統(tǒng),Java語言的編譯系統(tǒng),34,1.4 程序設(shè)計(jì)語言發(fā)展歷程（1.3）,程序設(shè)計(jì)語言發(fā)展歷程 機(jī)器語言（第一代）： 20世紀(jì)40年代 匯編語言（第二代） ：20世紀(jì)50年代早期 高級語言 ：20世紀(jì)50年代晚期+ 通用（第三代）： Fortran、Cobol、C、C++、C#、Java 專用（第四代）：SQL、Postscript 邏輯（第五代）：Prolog、LISP,35,1.4 程序設(shè)計(jì)語言發(fā)展歷程,C語言的產(chǎn)生 The Development of the C Language：C history – Written by Dennis Ritchie BCPL ? B語言 ? New B語言 ? C語言,Ken Thompson (left) with Dennis Ritchie,DEC PDP-7, as used for initial work on C and Unix,36,1.4 程序設(shè)計(jì)語言發(fā)展歷程,第一屆（1966年）圖靈獎得主：Alan J．Perlis 貢獻(xiàn)領(lǐng)域：高級程序設(shè)計(jì)技巧，編譯器構(gòu)造,37,1.4 程序設(shè)計(jì)語言發(fā)展歷程,1983年圖靈獎得主：Ken Thompson, Dennis Ritchie 貢獻(xiàn)領(lǐng)域：C語言和Unix操作系統(tǒng),38,1.4 程序設(shè)計(jì)語言發(fā)展歷程,2006年圖靈獎得主：Frances E. Allen 貢獻(xiàn)領(lǐng)域：優(yōu)化編譯器,,,,,39,1.4 程序設(shè)計(jì)語言發(fā)展歷程,編譯性語言、解釋性語言和腳本語言 高級語言翻譯成機(jī)器語言，計(jì)算機(jī)才能執(zhí)行高級語言編寫的程序。 翻譯有兩種方式 編譯：一次性編譯成機(jī)器語言文件，不用重新編譯，效率高 解釋：每個語句都是執(zhí)行的時候才翻譯，每執(zhí)行一次就翻譯一次，效率比較低 腳本語言 一種解釋性語言：JavaScript，ASP,PHP,PERL Java語言 既要編譯，又要解釋；編譯只有一次，程序執(zhí)行時解釋執(zhí)行；通過編譯器，把java程序翻譯成一種中間代碼——字節(jié)碼，然后通過JVM解釋成相應(yīng)平臺的語言。,40,1.4 程序設(shè)計(jì)語言發(fā)展歷程,主流編譯理論會議 PLDI（ACM Symposium on Programming Language Design and Implementation，編程語言設(shè)計(jì)與實(shí)現(xiàn)） POPL（ACM Symposium on Principles of Programming Languages，編程語言原理） PPoPP（ACM Symposium on Principles and Practice of Parallel Programming，并行編程原理與實(shí)踐） OOPSLA（ACM Conference on Object-Oriented Programming Systems, Languages and Applications，面向?qū)ο蟮木幊滔到y(tǒng)、語言和應(yīng)用）,41,第一章：總結(jié),自然語言處理vs編譯原理 詞法分析,42,第一章：總結(jié),自然語言處理vs編譯原理 語法分析,43,第一章：總結(jié),第一章總結(jié)（1.7）,44,作業(yè),給定一個后綴表示，比如95+2- 求輸出結(jié)果 C++實(shí)現(xiàn),45,重點(diǎn),什么是編譯器？ 編譯器，解釋器的區(qū)別？ 一個語言處理系統(tǒng)由哪些部分組成？ 編譯器的前端分析由哪些部分構(gòu)成？ 編譯器的后端分析由哪些部分構(gòu)成？ 什么是詞法分析？ 什么是語法分析？ 什么是標(biāo)識符，表達(dá)式，語句？ 中間代碼有哪三種表達(dá)方式？ 什么是符號表？ 什么是出錯管理？,46,