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

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