《語言處理器引論ppt課件》由會員分享，可在線閱讀，更多相關《語言處理器引論ppt課件（46頁珍藏版）》請在裝配圖網上搜索。

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