編譯原理（全套課件660p）（可編輯）

編譯原理（全套課件660P）編譯原理課時授課課時48實驗課時8課程性質必修/考試考試方式閉卷考試主講敬茂華JING_JMHTOM先修課程離散數(shù)學、組成原理、匯編語言、數(shù)據(jù)結構、C或其他程序設計語言第0章預備知識本門課程的目的和意義程序設計語言與程序的翻譯程序設計語言的語法描述為什么要學習編譯原理例INTFACTSTATICINTI5IFI0RETURNIELSEII1RETURNIABS1FACT/第9行,函數(shù)ABS求絕對值/MAINPRINTF“FACTOROF5D/N”,FACT上程序的運行結果是120。但是，如果把第9行的ABS1改成1的話，該程序結果是1。分析I是靜態(tài)變量，所有地方對I的操作都是對同一地址空間的操作，所以每次遞歸進入FACT函數(shù)后，上一層對I的賦值仍然有效。由于C語言的編譯機制，每次調用時，IABS1FACT中IABS1的值都先于FACT算出。所以，第1次遞歸時，所求值為5FACT，第2次遞歸時，所求值為4FACT，第3次遞歸時，所求值為3FACT，第4次遞歸時，所求值為2FACT，第5次遞歸時，所求值為1FACT，而此時FACT為1。這樣，程序相當于是求一個階乘函數(shù)54321，所以，結果為120。程序改動后結果變化，主要是和編譯時代碼生成策略有關。對于表達式IABS1FACT，因兩個子表達式都有函數(shù)調用，因此，編譯器先產生左子表達式代碼，后產生右子表達式代碼。當ABS1改為1后，左子表達式就沒有函數(shù)調用了，于是，編譯器會先產生右子表達式代碼，這樣一來，每次遞歸調用時，I1FACT中I1的值后于FACT算出。第1次遞歸時，所求值為I1FACT，第2次遞歸時，所求值為I1FACT，第5次遞歸時，所求值為I1FACT，而此時FACT為1，I為0，即實際上每次遞歸調用所求的實際都是1FACT，最后結果還是1。編譯原理課程關注的內容面向機器的語言計算機的硬件只能識別由0、1字符串組成的機器指令序列，即機器指令程序。特點不易理解，編寫程序既困難又容易出錯。用容易記憶的符號來代替0、字符串。用符號表示的指令被稱為匯編指令，匯編指令的集合被稱為匯編語言，由匯編語言編寫的指令序列被稱為匯編語言程序。面向人類的語言通用程序設計語言，如，JAVA，C；數(shù)據(jù)查詢語言，如；形式化描述語言，如EBNF、。其他面向特定應用領域的語言面向互聯(lián)網應用的6HTML、XML；面向計算機輔助設計的MATLAB；面向集成電路設計的VHDL、VERILOG；面向虛擬現(xiàn)實的VRML；語言之間的翻譯高級語言之間的翻譯，一般被稱為轉換，如FORTRAN到ADA的轉換等，或者被稱為預處理，如SQL到C/C的預處理。高級語言可以直接翻譯成機器語言，也可以翻譯成匯編語言，這兩個翻譯過程是將高級語言的源程序翻譯成低級語言的目標程序，這種翻譯被稱為編譯。將一個匯編語言匯編為可在另一平臺上運行的機器指令，則稱為交叉匯編，而建立在交叉匯編基礎之上的編譯模式稱為交叉編譯。把機器語言翻譯成匯編語言，或者把匯編語言翻譯成高級語言，分別稱它們?yōu)榉磪R編和反編譯。上述語言之間的翻譯雖然各不相同，但基本方法，特別是對源語言的分析方法是相同的。編譯原理與編譯技術編譯原理與編譯技術是兩類不同的過程。編譯原理研究的就是語言翻譯方法中所用到的基本原理，關注的是產生編譯器的理論和原理。一般并不深入討論某一具體的編譯器的實現(xiàn)和工作機制。編譯技術更關注編寫（實現(xiàn)）編譯器過程中所用到的技術。編譯原理是學習編譯技術以及深入掌握利用高級語言進行編程的基礎。通用程序設計語言的主要成份通用程序設計語言的典型特征之一是抽象，其抽象程度是以程序設計語言所支持的基本結構為特征的?？梢源笾聞澐譃槿N形式過程、模塊（抽象數(shù)據(jù)類型，ADT）和類。以過程為基本結構的程序設計語言的典型代表有C、PASCAL等；以ADT為基本結構的程序設計語言的典型代表是ADA83；而以類為基本結構的程序設計語言包括當前流行的C、JAVA和ADA95等。這三種形式經過了一個演變過程，每一次演變都使得程序設計語言的抽象程度得到一次提高，同時也為這些程序設計語言的編譯器提出了新的要求。類概念的引入，為利用程序設計語言構造類型提供了真正的支持，也是面向對象程序設計（OOP）語言的重要特征之一。程序設計語言提供的機制與程序設計的風格有著密切關系，以過程為基本抽象的程序設計語言支持的是過程式的程序設計范型（PARADIGM），以類為基本抽象的程序設計語言支持的是面向對象的程序設計范型，以ADT為基本抽象的程序設計語言介于二者之間，一般被認為是面向過程的語言，但也被認為是基于對象的語言。有些面向對象的程序設計語言是由過程式的語言發(fā)展而來的，如C、ADA95等，它們實質上是支持多范型的程序設計語言。本課程以PL/0（面向過程的語言）編譯器為例，討論把高級語言中應用最廣的通用程序設計語言翻譯成匯編語言程序所涉及的基本原理、技術和方法。這些原理、技術和方法也同樣適用于其他各類翻譯器的構造，同時有些技術和方法也可以被用于其他軟件設計。內容上以最簡單的、以過程為基本結構的程序設計語言為背景進行討論。因為無論何種形式的程序設計語言，均是由聲明和操作這樣兩個基本元素構成的，所不同的是聲明和操作的范圍和復雜程度不同。以過程為基本結構的程序設計語言的特征是把整個程序作為一個過程。過程的定義由兩類語句組成聲明性語句和操作性語句。一般來講，聲明性語句提供所操作對象的性質，如數(shù)據(jù)類型、值、作用域等。而操作性語句確定操作的計算次序，完成實際操作。本門課程的目的和意義計算機問題求解的基本途徑對問題進行抽象和形式化表示，然后進行處理。掌握形式語言與自動機理論。掌握編譯原理及方法。了解編譯程序的實現(xiàn)原理和技術。培養(yǎng)形式化描述和抽象思維能力。利用從本課程學到的知識，增強編寫和調試程序的能力。編譯原理及技術在其他方面的應用正文查找正文處理指令識別等程序設計語言與程序的翻譯一般的程序設計語言的定義都涉及語法、語義和語用三個方面。由符號（單詞）構成語法成分的規(guī)則稱為一般語法規(guī)則。由基本符號構成的符號（單詞）書寫規(guī)則特稱為詞法規(guī)則。程序設計語言的語法描述語法圖BNF范式；語法成分的定義；|表示“或者”擴充的BNF范式增加了三個符號X表示X可以出現(xiàn)0到多次。X表示X可能出現(xiàn)，也可能不出現(xiàn)。（X|Y）表示X和Y二者取一。文法口語第一章概述11什么是編譯程序12編譯的基本過程13編譯程序的邏輯結構14決定編譯階段組合的因素15與編譯器相關的程序16編譯器的翻譯步驟17編譯器中的主要數(shù)據(jù)結構18編譯器結構的其他觀點直觀印象兩數(shù)之和的程序8086/8088機器語言的程序10100000000000010000000010001010001001100000001000000000000000001110000010100010000000110000000011110100IBMPC匯編語言的程序STARTMOVAX,DSEGMOVDS,AXMOVAL,DATA1MOVAH,DATA2ADDAL,AHMOVRLT,ALHLT11什么是編譯程序COMPILER編譯程序是現(xiàn)代計算機系統(tǒng)的基本組成部分。從功能上看，一個編譯程序就是一個語言翻譯程序,它把一種語言稱作源語言書寫的程序翻譯成另一種語言稱作目標語言的等價的程序。什么是編譯程序語言轉變）換系統(tǒng)111編譯程序的功能112翻譯程序的種類匯編程序用于特定計算機上的匯編語言的翻譯程序。編譯程序將高級語言翻譯成低級語言的翻譯程序解釋程序將會話式語言翻譯成目標指令的翻譯程序編譯程序與解釋程序的根本區(qū)別113編譯程序生成的目標程序的形式可立即執(zhí)行的機器語言代碼匯編語言程序待裝配的機器語言代碼模塊114什么叫機器語言計算機提供的基本操作稱為指令。指令的全體稱為指令系統(tǒng)。指令系統(tǒng)也稱為機器語言。指令的基本形式115什么是編譯系統(tǒng)116編譯理論和編譯器的發(fā)展史12編譯的基本過程詞法分析從左至右讀字符流的源程序、識別拼單詞例POSITIONINITIALRATE60詞法分析POSITIONINITIALRATE60單詞類型單詞值標識符1ID1POSITION算符賦值標識符2ID2INITIAL算符加標識符3ID3RATE算符乘整數(shù)60分號；語法分析功能層次分析。依據(jù)源程序的語法規(guī)則把源程序的單詞序列組成語法短語表示成語法樹。POSITIONINITIALRATE60規(guī)則“”“”“”“”“”ID1ID2ID3N語義分析語義審查靜態(tài)語義上下文相關性類型匹配類型轉換語義分析中間代碼生成源程序的內部中間表示三元式、四元式、PCODE、CCODE、UCODE、BYTECODEID3T1T2T2ID3T1T2ID3T1中間代碼生成代碼優(yōu)化代碼優(yōu)化T1BCT1BCT2T10T2T1T1T3BCAT2T4T2T3AT4目標代碼生成符號表管理記錄源程序中使用的名字收集每個名字的各種屬性信息類型、作用域、分配存儲信息出錯處理檢查錯誤、報告出錯信息、排錯、恢復編譯工作13編譯程序的邏輯結構COMPONENTS詞法分析程序語法分析程序語義分析程序中間代碼生成程序代碼優(yōu)化程序目標代碼生成程序符號表管理程序出錯處理程序14決定編譯階段組合的因素分析，綜合SYNTHESIS源程序的分析線性分析層次分析語義分析目標程序的綜合編譯的前端（FRONTEND）編譯的后端（BACKEND）遍（趟）從頭到尾掃描源程序（各種形式）一遍PASS。15與編譯器相關的程序翻譯程序編譯程序（COMPLIER）解釋程序（INTERPRETOR）匯編程序（ASSEMBLER）連接程序（LINKER）裝入程序（LOADER）預處理程序（PREPROCESSOR）編輯器（EDITOR）調試程序（DEBUGGER）描述器（PROFILER）項目管理程序（PROJECTMANAGER）16編譯器的翻譯步驟例AINDEX42一、掃描程序（SCANNER）8個記號（或單詞）（TOKEN）A標識符左括號INDEX標識符右括號4數(shù)字加號2數(shù)字二、語法分析程序（PARSER）三、語義分析程序（SEMANTICANALYZER）四、源代碼優(yōu)化程序（SOURCECODEOPTIMIZER）五、代碼生成器（CODEGENERATOR）17編譯器中的主要數(shù)據(jù)結構記號（TOKEN）（也叫單詞）語法樹（SYNTAXTREE）符號表（SYMBOLTABLE）常數(shù)表（LITERALTABLE）中間代碼（INTERMEDIATECODE）臨時文件（TEMPORARYFILE）補充知識高級語言解釋系統(tǒng)INTERPRETER功能讓計算機執(zhí)行高級語言（BASIC,LISP,PROLOG與編譯程序的不同1）不生成目標代碼2）能支持交互環(huán)境（同增量式編譯系統(tǒng)）源程序初始數(shù)據(jù)解釋系統(tǒng)直接對源程序中的語句進行分析，執(zhí)行其隱含的操作。如B2AB2編譯程序WRITEA解釋程序直接將4的值輸出（顯示）編譯階段和運行階段存儲結構編譯時運行時解釋系統(tǒng)存儲結構13編譯技術的發(fā)展和應用功能程序集成環(huán)境實現(xiàn)方式手工機器語言匯編系統(tǒng)程序設計語言自動構造工具LEXYACCGCC編譯程序的發(fā)展編譯程序的發(fā)展語言范型PARADIGMS命令式IMPERATIVELANGUAGE應用式APPLICATIVE基于規(guī)則的（RULEBASED）面向對象的（OBJECTORIENTED）編譯程序執(zhí)行環(huán)境批處理交互環(huán)境嵌入系統(tǒng)環(huán)境語言范型（支持的計算模式）命令式程序特點語言執(zhí)行的解釋編譯技術發(fā)展快語句1；改變機器狀態(tài)系統(tǒng)語言語句2；內存自動化生成技術語句3；各種寄存器的內容外存與馮諾伊曼機的體系結構一般應用式（函數(shù)式）程序特點FUNCTIONNFUNETION2FUNETION1DATA程序執(zhí)行執(zhí)行一個個函數(shù)施用在數(shù)據(jù)上的變換最終得到的結果編譯語法分析容易；語義處理復雜；基于規(guī)則的語言（PROLOG,YACC程序特點使能條件1動作1使能條件2動作2使能條件3動作3面向對象語言抽象數(shù)據(jù)類型，繼承機制編譯動態(tài)綁定；執(zhí)行環(huán)境批處理環(huán)境將源程序作為整體處理排除程序錯誤不能依靠用戶的外部幫助交互環(huán)境解釋增量式編譯嵌入式系統(tǒng)環(huán)境交叉編譯分布并行環(huán)境并行編譯程序創(chuàng)建和測試環(huán)境獨立編譯編譯和調試同時設計考慮編譯技術的發(fā)展和應用結構化編譯器程序分析工具靜態(tài)分析動態(tài)分析度量工具結構度量模塊接口復雜度C分析工具SOURCEINSIGHT廣泛的語言領域數(shù)據(jù)庫系統(tǒng)查詢腳本語言置標語言SGMLHTMLXML研究領域并行編譯技術交叉編譯技術硬件描述語言及其編譯技術并行化編譯技術目的提高并行計算機體系結構的性能。超大規(guī)模計算的日益增長的需求高性能計算機并行軟件并行體系結構編譯技術支持串行程序并行化編譯技術支持并行程序設計語言編譯依賴于目標機的優(yōu)化（低層）并行算法復雜，難掌握，難編程開發(fā)并行軟件的困難并行程序的不確定行為，難調試，驗證設計新的并行算法修改已有串行程序盡量（直接用并行程序并行化（研究算法和設計語言和并行程應用的人同時工作）序庫實現(xiàn)。HPFOCCOMPVM嵌入式硬件描述語言及其編譯技術電路設計依據(jù)驗證結果如VHDL第一章小結內容1什么是編譯程序2編譯過程和編譯程序的結構3為什么要學習編譯程序本章沒有難以理解的內容,重點對編譯程序的功能和結構做一綜述,要說難點的話可能是了解編譯程序各個成分在編譯階段的邏輯關系以及他們怎樣作為一個整體完成編譯任務的。參考書TOMASPITTMN,THEARTOFCOMPILERDESIGNTHEORYANDPRACTICE,PRENTICEHALL1992ALFREDVAHO,RAVISETHI,JEFFREYDULLMAN,COMPILERSPRINCIPLES,TECHNIQUESANDTOOLSADDISSONWESLEY1986陳火旺劉春林等程序設計語言編譯原理國防工業(yè)出版社2000DAVIDAWATT（常量說明部分）VARB,C（變量說明部分）PROCEDUREP（過程說明部分）VARDPROCEDUREQVARXBEGINREADXDXWHILEX0DOCALLPENDBEGINWRITEDCALLQENDBEGINCALLPENDPL/0語言文法的EBNF表示EBNF引入的符號元符號用左右尖括號括起來的語法成分為非終結符定義為的左部由右部定義|或表示花括號內的語法成分可重復任意次或限定次數(shù)表示方括號內的語法成分為任選項表示圓括號內的成分優(yōu)先例用EBNF描述的定義|0|1|2|3|4|5|6|7|8|9或更好的寫法|01|2|3|4|5|6|7|8|90|PL/0語言是PASCAL語言的子集同PASCAL作用域規(guī)則（內層可引用包圍它的外層定義的標識符），上下文約束，過程可嵌套定義，可遞歸調用子集數(shù)據(jù)類型,只有整型數(shù)據(jù)結構,只有簡變和常數(shù)數(shù)字最多為14位標識符的有效長度是10語句種類過程最多可嵌套三層目標代碼類PCODE目標代碼類PCODE是一種假想棧式計算機的匯編語言。指令格式CONSTA10VARB,CPROCEDUREPBEGINCBAENDBEGINREADBWHILEB0DOBEGINCALLPWRITE2CREADBENDEND0JMP08轉向主程序入口1JMP02轉向過程P入口2INT03過程P入口,為過程P開辟空間3LOD13取變量B的值到棧頂4LIT010取常數(shù)10到棧頂5OPR02次棧頂與棧頂相加6STO14棧頂值送變量C中7OPR00退棧并返回調用點168INT05主程序入口開辟5個棧空間9OPR016從命令行讀入值置于棧頂10STO03將棧頂值存入變量B中11LOD03將變量B的值取至棧頂12LIT00將常數(shù)值0進棧13OPR09次棧頂與棧頂是否不等14JPC024等時轉24（條件不滿足轉）15CAL02調用過程P16LIT02常數(shù)值2進棧17LOD04將變量C的值取至棧頂18OPR04次棧頂與棧頂相乘2C19OPR014棧頂值輸出至屏幕20OPR015換行21OPR016從命令行讀取值到棧頂22STO03棧頂值送變量B中23JMP011無條件轉到循環(huán)入口1124OPR00結束退棧PL/0編譯程序的結構PL/0編譯程序的總體設計其編譯過程采用一趟掃描方式以語法、語義分析程序為核心詞法分析程序和代碼生成程序都作為一個過程，當語法分析需要讀單詞時就調用詞法分析程序，而當語法、語義分析正確，需要生成相應的目標代碼時，則調用代碼生成程序。表格管理程序實現(xiàn)變量，常量和過程標識符的信息的登錄與查找。出錯處理程序，對詞法和語法、語義分析遇到的錯誤給出在源程序中出錯的位置和與錯誤性質有關的編號，并進行錯誤恢復。PL/0編譯程序詞法分析的設計與實現(xiàn)識別的單詞保留字或關鍵字如BEGIN、END、IF、THEN等運算符如、/、等標識符用戶定義的變量名、常數(shù)名、過程名常數(shù)如10、25、100等整數(shù)界符如,、等詞法分析過程GETSYM所要完成的任務讀源程序（GETCH濾空格識別保留字識別標識符拼數(shù)識別單字符單詞拼雙字符單詞詞法分析過程GETSYM框圖（見教材圖25）程序（PROCEDUREGETSYM）當識別到標識符時先查保留字表保留字表（BEGINMAIN）WORD1BEGIN；WORD2CALL；WORD13WRITE；查到時找到相應的內部表示WSYM1BEGINSYMWSYM2CALLSYM；WSYM13WRITESYM；字符對應的單詞表SSYMPLUSSSYMMINUSSSYMSEMICOLON詞法分析如何把單詞傳遞給語法分析TYPESYMBOLNUL,IDENT,NUMBER,PLUS,VARSYM,PROCSYM；3個全程量SYMSYMBOLIDALFANUMINTEGER通過三個全程量SYM、ID和NUM將識別出的單詞信息傳遞給語法分析程序。SYM存放單詞的類別如有程序段落為BEGININITIAL60；END對應單詞翻譯后變?yōu)锽EGINBEGINSYM,INITIALIDENT,BECOMES,60NUMBER,；SEMICOLON，ENDENDSYM。ID存放用戶所定義的標識符的值如INITIAL（在SYM中放IDENT，在ID中放INITIAL）NUM存放用戶定義的數(shù)如60（在SYM中放在NUMBER在NUM中放60）使用狀態(tài)轉換圖實現(xiàn)詞法分析程序的設計方法詞法分析程序的設計使用狀態(tài)轉換圖實現(xiàn)PL/0編譯程序語法語義分析PL/0編譯程序語法分析的設計與實現(xiàn)自頂向下的語法分析遞歸子程序法自頂向下的語法分析VARABEGINREADAENDVAR；ABEGINENDREAD（）A遞歸子程序法遞歸子程序法對應每個非終結符語法單元，編一個獨立的處理過程（或子程序）。語法分析從讀入第一個單詞開始，由非終結符（即開始符）出發(fā)，沿語法描述圖箭頭所指出的方向進行分析。當遇到非終結符時，則調用相應的處理過程，從語法描述圖看，也就進入了一個語法單元，再沿當前所進入的語法單元所指箭頭方向繼續(xù)進行分析。當遇到描述圖中是終結符時，則判斷當前讀入的單詞是否與圖中的終結符相匹配，若匹配，再讀取下一個單詞繼續(xù)分析。遇到分支點時，將當前的單詞與分支點上多個終結符逐個相比較，若都不匹配時可能是進入下一個非終結符語法單位或是出錯。編譯程序總體流程圖PL/0編譯程序語義分析的設計與實現(xiàn)PL/0編譯程序語法、語義分析的的核心程序是BLOCK過程，說明部分的分析與處理表格管理過程體語句）的分析與處理說明部分的分析與處理對每個過程（含主程序）說明的對象（變量，常量和過程）造符號表登錄標識符的屬性。標識符的屬性種類，所在層次,值和分配的相對位置。登錄信息由ENTER過程完成。符號表TXTABLE表的下標指針,是以值參數(shù)形式使用的。DX計算每個變量在運行棧中相對本過程基地址的偏移量，放在TABLE表中的ADR域，生成目標代碼時再放在CODE中的A域過程體的處理對語句進行語法分析語義分析當遇到標識符的引用時就調用POSITION函數(shù)查TABLE表，看是否有過正確定義，若已有，則從表中取相應的有關信息，供代碼的生成使用。若無定義則錯。當語法語義正確時，就生成相應語句功能的目標代碼代碼生成代碼生成是由過程GEN完成。GEN有3個參數(shù)，分別代表目標代碼的功能碼，層差和位移量。例如GENOPR,0,16GENSTO,LEVLEVEL,ADRLEV當前處理的過程層次LEVEL被引用變量或過程所在層次CX為目標代碼CODE數(shù)組的下標指針PL/0編譯程序錯誤處理的實現(xiàn)對語法錯誤的兩種處理方法1對于易于校正的錯誤，如丟了逗號，分號等，指出出錯位置，加以校正，繼續(xù)進行分析。2對于難于校正的錯誤，給出錯誤的位置與性質，跳過后面的一些單詞，直到下一個可以進行正常語法分析的語法單位。在進入某個語法單位時，調用TEST,檢查當前符號是否屬于該語法單位的開始符號集合。若不屬于，則濾去開始符號和后繼符號集合外的所有符號。在語法單位分析結束時，調用TEST,檢查當前符號是否屬于調用該語法單位時應有的后繼符號集合。若不屬于，則濾去后繼符號和開始符號集合外的所有符號。類PCODE代碼解釋器的實現(xiàn)類PCODE解釋器的結構目標代碼解釋執(zhí)行時數(shù)據(jù)棧的布局（運行棧的存儲分配）類PCODE解釋器的結構目標代碼存放在數(shù)組CODE中。解釋程序定義一個一維整型數(shù)組S作為運行棧棧頂寄存器（指針）T，基址寄存器（指針）B，程序地址寄存器P，指令寄存器I目標代碼解釋執(zhí)行時數(shù)據(jù)棧的布局（運行棧的存儲分配）在每個過程調用時在棧頂分配3個聯(lián)系單元SL靜態(tài)鏈，指向定義該過程的直接外過程（或主程序）運行時最新數(shù)據(jù)段的基地址。DL動態(tài)鏈，指向調用該過程前正在運行過程的數(shù)據(jù)段基地址。RA返回地址，記錄調用該過程時目標程序的斷點，即調用過程指令的下一條指令的地址。目標代碼的解釋執(zhí)行運行棧SM調用過程Q目標代碼的解釋執(zhí)行幾條特殊指令在CODE中的位置和功能INT0A在過程目標程序的入口處，開辟A個單元的數(shù)據(jù)段。A為局部變量的個數(shù)3。OPR00在過程目標程序的出口處，釋放數(shù)據(jù)段（退棧），恢復調用該過程前正在運行的過程的數(shù)據(jù)段基址寄存器B和棧頂寄存器T的值，并將返回地址送到指令地址寄存器P中，以使調用前的程序從斷點開始繼續(xù)執(zhí)行。目標代碼的解釋執(zhí)行幾條特殊指令在CODE中的位置和功能CALLA調用過程，還完成填寫靜態(tài)鏈、動態(tài)鏈、返回地址，給出被調用過程的基地址值，送入基址寄存器B中，目標程序的入口地址A的值送指令地址寄存器P中，使指令從A開始執(zhí)行。附運行時數(shù)據(jù)棧S的變化狀態(tài)教材25頁第三章文法和語言本章目的為語言的語法描述尋求工具工具要對程序設計語言給出精確無二義的語法描述。（嚴謹、簡潔、易讀）形式工具形式語言抽象地定義為一個數(shù)學系統(tǒng)。“形式”是指這樣的事實語言的所有規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述本章知識點內容引言和預備知識文法和語言的形式定義文法的類型上下文無關文法及其語法樹上下文無關文法的句型分析有關文法實用中的一些說明31文法的直觀概念和語言概述當我們表述一種語言時，無非是說明這種語言的句子，如果語言只含有有窮多個句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的語言來講，存在著如何給出它的有窮表示的問題給出一些規(guī)則，用這些規(guī)則來說明或者定義句子的組成結構?！拔沂谴髮W生”。是漢語的一個句子句子主語謂語主語代詞名詞代詞我你他名詞王明大學生工人英語謂語動詞直接賓語動詞是學習直接賓語代詞名詞有了一組規(guī)則以后，按照如下方式用它們導出句子開始去找左端的帶有句子的規(guī)則并把它由右端的符號串代替，這個動作表示成句子主語謂語，然后在得到的串主語謂語中，選取主語或謂語，再用相應規(guī)則的右端代替之。比如，選取了主語，并采用規(guī)則主語代詞，那么得到主語謂語代詞謂語，重復做下去，句子“我是大學生”的全部動作過程是句子主語謂語代詞謂語我謂語我動詞直接賓語我是直接賓語我是名詞我是大學生“我是大學生”的構成符合上述規(guī)則，而“我大學生是”不符合上述規(guī)則，我們說它不是句子。這些規(guī)則成為我們判別句子結構合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。這里僅僅涉及漢語句子的結構描述。其中一種描述元語言稱為文法。注用于產生其他語言的語言稱為元語言。32編譯原理所涉及到的一些數(shù)學概念和運算集合笛卡兒乘積關系符號串321集合概念表示法（1）枚舉法1,2,3（2）謂詞法X|X32特性（1）唯一性（2）確定性集合間的關系相等、不相等、子集集合的運算并集、交集、差集、冪集322笛卡兒乘積序偶由兩個按一定次序排列的客體組成的序列，記為（X，Y）N重序組由N個按一定次序排列的客體組成的序列，記為（X1，X2，XN）笛卡兒乘積A、B為任意兩個集合，若序偶的第一個成員是集合A的一個元素，第二個成員是集合B的一個元素，則所有這樣的序偶組成的集合稱為集合A和B的笛卡兒乘積。323關系定義關系矩陣和關系圖關系的基本性質1、自反2、非自反3、對稱4、非對稱5、傳遞關系的乘積關系的傳遞閉包自反傳遞閉包33有關定義和記號符號可以相互區(qū)別的記號（元素）。字母表符號（元素）的非空有窮集合。符號串由字母表中的符號組成的任何有窮序列稱為該字母表上的符號串。1空符號串沒有符號的符號串是上的符號串2若X是上的符號串,A是的元素,則XA是上的符號串3Y是上的符號串,當且僅當它可以由1和2導出。例如A,B,A,B,AA,AB,AABBA都是上的符號串介紹有關符號串的一些運算符號串的頭,尾，固有頭和固有尾如果ZXY是一符號串，那么X是Z的頭，Y是Z的尾，如果X是非空的，那么Y是固有尾；同樣如果Y非空，那么X是固有頭。舉個例子設ZABC,那么Z的頭是,A,AB,ABC,除ABC外，其它都是固有頭；Z的尾是,C,BC,ABC,Z的固有尾是,C,BC。當對符號串ZXY的頭感興趣而對其余部分不感興趣時，采用省略寫法ZX；如果只是為了強調X在符號串Z中的某處出現(xiàn)，則可表示為ZX；符號T是符號串Z的第一個符號，則表示為ZT。符號串的連接設X和Y是符號串，它們的連接XY是把Y的符號寫在X的符號之后得到的符號串由于的含義，顯然有XXX。例如XST，YABU，則它們的連接XYSTABU，看出X2，Y3，XY5符號串的方冪符號串自身連接N次得到的符號串AN定義為AAAAN個AA1A,A2AA且A0例；若XAB則X0X1ABX2ABABX3ABABABXNXXN1XN1XN0符號串集合若集合A中所有元素都是某字母表上的符號串，則稱A為字母表上的符號串集合。兩個符號串集合A和B的乘積定義為ABXY|XA且YB若集合AAB,CDEB0,1則ABAB1,AB0,CDE0,CDE1使用表示上的一切符號串（包括）組成的集合。稱為的閉包。上的除外的所有符號串組成的集合記為。稱為的正閉包。例A,B,A,B,AA,AB,BA,BB,AAA,AAB,A,B,AA,AB,BA,BB,AAA,AAB,有關定義和記號語言是由句子組成的集合，是由一組符號所構成的集合。換言之,字母表上的一個語言是上的一些符號串的集合字母表上的每個語言是的一個子集。例如字母表A,B,A,B,AA,AB,BA,BB,AAA,AAB,集合AB,AABB,AAABBB,ANBN,或表示為W|W且WANBN,N1為字母表上的一個語言。集合A,AA,AAA,或表示為W|W且WAN,N1為字母表上的一個語言。是一個語言。即是一個語言。34文法和語言的形式定義語言是由句子組成的集合，是由一組符號所構成的集合。漢語所有符合漢語語法的句子的全體英語所有符合英語語法的句子的全體程序設計語言所有該語言的程序的全體每個句子構成的規(guī)律研究語言每個句子的含義每個句子和使用者的關系程序設計語言的概念和描述方法程序設計語言是形式語言，其定義和描述包括語法、語義和語用三個方面。程序設計語言的語法實際上是一組規(guī)則。程序設計語言的語句可分為兩大類1、非執(zhí)行語句2、可執(zhí)行語句描述程序程序設計語言的語法規(guī)則的有效工具是文法中的上下文無關文法。語言研究的三個方面語法SYNTAX語義SEMANTICS語用PRAGMATICS語法表示構成語言句子的各個記號之間的組合規(guī)律，即句子的組成結構。語義表示各個記號的特定含義。（各個記號和記號所表示的對象之間的關系）語用表示在各個記號所出現(xiàn)的行為中，它們的來源、使用和影響。每種語言具有兩個可識別的特性，即語言的形式和該形式相關聯(lián)的意義。語言的實例若在語法上是正確的，其相關聯(lián)的意義可以從兩個觀點來看，其一是該句子的創(chuàng)立者所想要表示的意義，另一是接收者所檢驗到的意義。這兩個意義并非總是一樣的，前者稱為語言的語義，后者是其語用意義。幽默、雙關語和謎語就是利用這兩方面意義間的差異。如果不考慮語義和語用，即只從語法這一側面來看語言，這種意義下的語言稱作形式語言。形式語言抽象地定義為一個數(shù)學系統(tǒng)?！靶问健笔侵高@樣的事實語言的所有規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述。形式語言理論是對符號串集合的表示法、結構及其特性的研究。是程序設計語言語法分析研究的基礎。文法和語言的形式定義如何來描述一種語言如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示如果語言是無窮的，找出語言的有窮表示。語言的有窮表示有兩個途經生成方式（文法）語言中的每個句子可以用嚴格定義的規(guī)則來構造。識別方式（自動機）用一個過程，當輸入的一任意串屬于語言時，該過程經有限次計算后就會停止并回答“是”，若不屬于，要麼能停止并回答“不是”，（要麼永遠繼續(xù)下去。）文法即是生成方式描述語言的語言中的每個句子可以用嚴格定義的規(guī)則來構造下面給出文法的定義進而在文法的定義的基礎上，給出推導的概念，句型、句子和語言的定義。定義文法G定義為四元組VN，VT，P，S其中VN為非終結符號或語法實體，或變量集；VT為終結符號集；P為產生式也稱規(guī)則的集合；VN，VT和P是非空有窮集。S稱作識別符號或開始符號，它是一個非終結符，至少要在一條產生式中作為左部出現(xiàn)。VN和VT不含公共的元素，即VNVT用V表示VNVT，稱為文法G的字母表或字匯表規(guī)則，也稱重寫規(guī)則、產生式或生成式，是形如或的，有序對，其中是字母表V的正閉包V中的一個符號，是V中的一個符號。稱為規(guī)則的左部，稱作規(guī)則的右部。文法的定義例文法G（VN，VT，P，S）VNS,VT0,1PS0S1,S01S為開始符號例文法G（VN，VT，P，S）VN標識符，字母，數(shù)字VTA,B,C,X,Y,Z,0,1,9PA,Z0,9S文法的寫法1GSAABAABAAABA2GSAABAAABASASB3GSAAB|AAB|SASB元符號|習慣表示大寫字母終結符小寫字母非終結符SABAAX|YBZ推導的定義直接推導“”是文法G的產生式，若有V,W滿足V,W,其中V,V則稱V直接推導到W,記作VW也稱W直接歸約到V例GS0S1，S010S100S1100S11000S111000S11100001111S0S1VARBEGINREADENDVARABEGINREADEND推導的定義若存在VW0W1WNW,N0則記為VW，V推導出W，或W歸約到V若有VW，或VW，則記為VW例GS0S1，S010S100S1100S11000S111000S11100001111S0S100S11000S11100001111S00001111SS00S1100S11句型、句子的定義句型有文法G，若SX，則稱X是文法G的句型。句子有文法G，若SX，且XVT，則稱X是文法G的句子。例GS0S1，S01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,01例GEEET|TTTF|FFE|AEETTTFTATATFAFFAAFAAA句子用符號A，和構成的算術表達式文法，語言的定義由文法G生成的語言記為LG,它是文法G的一切句子的集合LGX|SX，其中S為文法的開始符號，且XVT例GS0S1，S01LG0N1N|N1例文法GS（1）SASBE（2）SABE（3）EBBE（4）ABAB（5）BBBB（6）BEBE（7）EEEEL（G）ANBNEN|N1SASBESASBEAABEBESABEAABEBEABABAABBEEEBBEAABBEE（BBBBAABBEE（BEBEAABBEE（EEEEG生成的每個串都在LG中LG中的每個串確實能被G生成使用產生式1N1次，得到推導序列SAN1SBEN1，然后使用產生式2一次，得到SAN1SBEN1ANBEN。然后從ANBEN繼續(xù)推導，總是對EB使用產生式3的右部進行替換，而最終在得到的串中，所有的B都先于所有的E。例如，若N3,AAABEBEBEAAABBEEBEAAABBEBEEAAABBBEEE。即有SANBNEN接著，使用產生式4一次，得到SANBBN1EN，然后使用產生式5N1次得到SANBNEN，最后使用產生式6一次，使用產生式7N1次，得到SANBNEN也能證明，對于N1，串ANBNEN是唯一形式的終結符號串文法的等價若L（G1）L（G2），則稱文法G1和G2是等價的。如文法G1AA0R與G2SS0S1等價A01S01RA1文法的類型通過對產生式施加不同的限制，CHOMSKY將文法分為四種類型0型文法對任一產生式，都有VNVT，VNVT1型文法對任一產生式，都有|，僅僅S除外2型文法對任一產生式，都有VN，VNVT3型文法任一產生式的形式都為AAB或AA，其中AVN，BVN，AVT文法的類型例1型（上下文有關）文法文法GSSCDABBACACABAABCBCBBBBBADADCBDBDDAABD文法的類型例2型（上下文無關）文法文法GSSABABS|0BSA|13型文法GSS0A|1B|0A0A|1B|0SB1B|1|0GIILTILTLTTDTTLTD文法的類型四種文法之間的逐級“包含”關系文法和語言0型文法產生的語言稱為0型語言1型文法或上下文有關文法（CSG）產生的語言稱為1型語言或上下文有關語言（CSL）2型文法或上下文無關文法（CFG）產生的語言稱為2型語言或上下文無關語言（CFL）3型文法或正則（正規(guī)）文法（RG）產生的語言稱為3型語言正則（正規(guī)）語言（RL）根據(jù)形式語言理論,文法和識別系統(tǒng)間有這樣的關系0型文法（短語結構文法）的能力相當于圖靈機，可以表征任何遞歸可枚舉集，而且任何0型語言都是遞歸可枚舉的1型文法（上下文有關文法）產生式的形式為1A212，即只有A出現(xiàn)在1和2的上下文中時，才允許取代A。其識別系統(tǒng)是線性界限自動機。2型文法（上下文無關文法CFG）產生式的形式為A，取代A時與A的上下文無關。其識別系統(tǒng)是不確定的下推自動機。3型文法（正規(guī)文法RG）產生的語言是有窮自動機（FA）所接受的集合上下文無關文法及其語法樹上下文無關文法有足夠的能力描述程序設計語言的語法結構語法樹句型推導的直觀表示例文法GE,I,P,E其中P為EI,EEE,EEE,EEE表示算術表達式,I表示程序的“變量”，該文法定義了由變量，,和組成的算術表達式的語法結構，即變量是算術表達式；若E1和E2是算術表達式，則E1E2，E1E2和E1也是算術表達式描述一種簡單賦值語句的產生式賦值語句IE描述條件語句的產生式條件語句IF條件THEN語句IF條件THEN語句ELSE語句句型、推導GEEET|TTTF|FFE|AEETTTFTATATFAFFAAFAAAEETETFETAEFAEAATAAFAAAAAEETTTTTFFTFFFFAFFAFAAAA規(guī)范推導規(guī)范句型最左（最右）推導在推導的任何一步，其中、是句型，都是對中的最左（右）非終結符進行替換最右推導被稱為規(guī)范推導。由規(guī)范推導所得的句型稱為規(guī)范句型語法樹設GVN,VT,P,S為一上下文無關文法，若一棵樹滿足下列4個條