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

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