編譯原理教案

PAGEPAGE1編譯原理教案說(shuō)明：一、參考書(shū)：1、陳意云、張昱：《編譯原理》，高等教育出版社，2003年。2、陳意云、張昱：《編譯原理習(xí)題精選》，中國(guó)科技大學(xué)出版社，2003年。3、呂映芝、張素琴、蔣維杜：《編譯原理》，清華大學(xué)出版社，1998年第二版。4、王生原、呂映芝、張素琴：《編譯原理課程輔導(dǎo)》，清華大學(xué)出版社，2007年。5、伍春香：《編譯原理習(xí)題與解析》，清華大學(xué)出版社，2001年。6、AndrewW.Appel：《現(xiàn)代編譯原理—C語(yǔ)言描述》，人民郵電出版社，2005年。7、NoamNison等：《計(jì)算機(jī)系統(tǒng)要素》，電子工業(yè)出版社，2007年。8、RandallHyde：《編程卓越之道（第二卷）》，電子工業(yè)出版社，2007年。二、教學(xué)目的：通過(guò)學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)理論、詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼優(yōu)化和生成等內(nèi)容使學(xué)生掌握構(gòu)造編譯程序的基本原理和基本方法，并通過(guò)上機(jī)實(shí)習(xí)使學(xué)生進(jìn)一步掌握開(kāi)發(fā)應(yīng)用程序的基本方法，為深入理解計(jì)算機(jī)系統(tǒng)、程序設(shè)計(jì)語(yǔ)言與開(kāi)發(fā)大型應(yīng)用程序打下良好的基礎(chǔ)。三、教學(xué)時(shí)數(shù)：課堂教學(xué)51學(xué)時(shí)，上機(jī)實(shí)驗(yàn)30學(xué)時(shí)。四、授課內(nèi)容：第一章編譯程序概述第二章PL/0編譯程序的實(shí)現(xiàn)第三章文法和語(yǔ)言第四章詞法分析第五章自頂向下語(yǔ)法分析方法第六章自底向上優(yōu)先分析方法第七章LR分析方法第八章語(yǔ)法制導(dǎo)翻譯和中間代碼生成第九章符號(hào)表第一○章目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織第一一章代碼優(yōu)化第一二章代碼生成第一章概述一、說(shuō)明：1、教學(xué)目的與要求：了解編譯程序的概念、結(jié)構(gòu)以及工作流程。2、主要內(nèi)容：什么是編譯程序、編譯過(guò)程概述、編譯程序的結(jié)構(gòu)、編譯階段的組合、編譯技術(shù)和軟件工具以及實(shí)例分析。3、教學(xué)重點(diǎn)：編譯程序的結(jié)構(gòu)以及每一階段的任務(wù)。4、教學(xué)難點(diǎn)：理解編譯程序各模塊的判錯(cuò)功能、編譯方式和解釋方式執(zhí)行速度上的不同。二、教學(xué)內(nèi)容第一節(jié)編譯程序1、機(jī)器語(yǔ)言：直接用計(jì)算機(jī)能夠識(shí)別的二進(jìn)制代碼指令來(lái)編寫(xiě)程序的語(yǔ)言。由二進(jìn)制的指令代碼組成。1+3表示為100000010000000100000011。是最底層的計(jì)算機(jī)語(yǔ)言，不需要翻譯就可以直接被計(jì)算機(jī)硬件識(shí)別。對(duì)應(yīng)不同的計(jì)算機(jī)硬件有不同的機(jī)器語(yǔ)言。特點(diǎn)：執(zhí)行速度快，但編寫(xiě)程序的難度大，修改、調(diào)試不方便，直觀性差，不易移植。2、匯編語(yǔ)言：又稱為符號(hào)語(yǔ)言。與機(jī)器語(yǔ)言一一對(duì)應(yīng)，采用能幫助記憶的英文縮寫(xiě)符號(hào)（指令助記符）來(lái)代替機(jī)器語(yǔ)言指令中的操作碼，用地址符號(hào)來(lái)代替地址碼。用指令助記符及地址符號(hào)書(shū)寫(xiě)的指令稱為匯編指令，用匯編指令編寫(xiě)的程序稱為匯編語(yǔ)言源程序。將X、Y中的內(nèi)容相加表示為ADDXY。機(jī)器不能直接識(shí)別匯編語(yǔ)言程序，必須把它翻譯為機(jī)器語(yǔ)言程序才能執(zhí)行。特點(diǎn)：比機(jī)器語(yǔ)言直觀，容易理解和記憶，比高級(jí)語(yǔ)言的執(zhí)行效率高，但通用性和移植性較差。3、高級(jí)語(yǔ)言：與具體的計(jì)算機(jī)硬件無(wú)關(guān)，是面向問(wèn)題的程序設(shè)計(jì)語(yǔ)言，其表達(dá)方式接近于自然語(yǔ)言和數(shù)學(xué)語(yǔ)言，易于人們接受和掌握。采用類似于數(shù)學(xué)公式的書(shū)寫(xiě)方式：x=1+3。特點(diǎn)：獨(dú)立于具體的計(jì)算機(jī)硬件，程序的編制和調(diào)試方便，通用性和可移植性好。在計(jì)算機(jī)執(zhí)行之前，需要通過(guò)編譯程序翻譯成目標(biāo)語(yǔ)言程序，或需要通過(guò)解釋程序邊解釋，邊執(zhí)行。時(shí)間與空間效率比較低。目前比較流行的高級(jí)語(yǔ)言有：C++,VisualBasic,Java，Pascal，4、什么是編譯程序：編譯程序把高級(jí)語(yǔ)言程序翻譯成等價(jià)的低級(jí)語(yǔ)言程序：源程序編譯程序目標(biāo)程序。編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分。從功能上看，一個(gè)編譯程序就是一個(gè)語(yǔ)言翻譯程序，它把一種語(yǔ)言(稱作源語(yǔ)言)書(shū)寫(xiě)的程序翻譯成另一種語(yǔ)言(稱作目標(biāo)語(yǔ)言)的等價(jià)的程序。高級(jí)語(yǔ)言源程序的執(zhí)行通常分兩個(gè)階段:源程序源程序(高級(jí)語(yǔ)言)編譯程序計(jì)算機(jī)目標(biāo)程序(機(jī)器語(yǔ)言)編譯階段初始數(shù)據(jù)目標(biāo)程序計(jì)算機(jī)運(yùn)行系統(tǒng)計(jì)算結(jié)果運(yùn)行階段若編譯生成的目標(biāo)程序是匯編語(yǔ)言形式,則在編譯與運(yùn)行階段之間還要添加一個(gè)匯編階段。高級(jí)語(yǔ)言源程序也可通過(guò)解釋程序來(lái)執(zhí)行,如BASIC。解釋程序與編譯程序的主要區(qū)別是：編譯程序?qū)⒄麄€(gè)源程序全部翻譯成目標(biāo)程序后再執(zhí)行該目標(biāo)程序；解釋程序則逐條讀出源程序中的語(yǔ)句并解釋執(zhí)行，在解釋程序執(zhí)行過(guò)程中并不產(chǎn)生目標(biāo)程序。源程序源程序(高級(jí)語(yǔ)言)初始數(shù)據(jù)解釋程序計(jì)算機(jī)計(jì)算結(jié)果第二節(jié)編譯程序結(jié)構(gòu)編譯程序的工作過(guò)程是指從輸入源程序開(kāi)始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)過(guò)程。編譯程序內(nèi)部包括了許多步驟或稱為階段，它們執(zhí)行不同的邏輯操作。將這些階段設(shè)想為編譯程序中一個(gè)個(gè)單獨(dú)的片斷是很有用的，盡管在應(yīng)用中它們是經(jīng)常組合在一起的，但它們確實(shí)是作為單獨(dú)的代碼操作來(lái)編寫(xiě)的。編譯工作的基本過(guò)程是：詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成等6個(gè)階段。每個(gè)階段都有表格管理和出錯(cuò)處理部分。1、詞法分析：像翻譯英文句子一樣，先要分析單詞，弄清各單詞的意義和句中的作用，才能對(duì)句子進(jìn)行翻譯。主要任務(wù)：從左到右一個(gè)字符一個(gè)字符地讀入源程序，對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解，從而識(shí)別出一個(gè)個(gè)單詞。單詞包括：保留字、標(biāo)識(shí)符、運(yùn)算符、分界符等。例：position:=initial+rate*60;單詞類型 單詞值標(biāo)識(shí)符(id1) position算符(賦值) :=標(biāo)識(shí)符(id2) initial算符(加) +標(biāo)識(shí)符(id3) rate算符(乘) *整數(shù) 60界符 ；有關(guān)術(shù)語(yǔ)：lexicalanalysisorscanning--Thestreamofcharactersmakingupasourceprogramisreadfromlefttorightandgroupedintotokens,whicharesequencesofcharactersthathaveacollectivemeaning.單詞token保留字reservedword標(biāo)識(shí)符identifier(user-definedname)如一個(gè)C源程序片斷：inta;a=a+2;詞法分析后可能返回:單詞類型 單詞值保留字 int標(biāo)識(shí)符(變量名) a界符 ;標(biāo)識(shí)符(變量名) a算符(賦值) =標(biāo)識(shí)符(變量名) a算符(加) +整數(shù) 2界符 ；2、語(yǔ)法分析：語(yǔ)法分析程序與自然語(yǔ)言中句子的語(yǔ)法分析類似。語(yǔ)法分析定義了程序的結(jié)構(gòu)元素及其關(guān)系。通常將語(yǔ)法分析的結(jié)果表示為分析樹(shù)或語(yǔ)法樹(shù)。主要任務(wù)：在詞法分析的基礎(chǔ)上，將單詞分解成各類語(yǔ)法短語(yǔ)。一般語(yǔ)法短語(yǔ)可表示成語(yǔ)法樹(shù)。功能：據(jù)源程序的語(yǔ)法規(guī)則把源程序的單詞序列組成語(yǔ)法短語(yǔ)(表示成語(yǔ)法樹(shù)).<賦值語(yǔ)句>::=<標(biāo)識(shí)符>“:=”<表達(dá)式><表達(dá)式>::=<表達(dá)式>“+”<表達(dá)式>|<表達(dá)式>::=<表達(dá)式>“*”<表達(dá)式><表達(dá)式>::=“(”<表達(dá)式>“)”|<標(biāo)識(shí)符>|<整數(shù)>|<實(shí)數(shù)>有關(guān)術(shù)語(yǔ)：syntaxanalysisorparsing--Thepurposeofsyntaxanalysisistodeterminethesourceprogram’sphrasestructure.Thisprocessisalsocalledparsing.Thesourceprogramisparsedtocheckwhetheritconformstothesourcelanguage’ssyntax,andtoconstructasuitablerepresentationofitsphrasestructure.如：id1:=id2+id3*N的分析結(jié)果為：3、語(yǔ)義分析：按照語(yǔ)法樹(shù)的層次關(guān)系和先后次序，逐個(gè)語(yǔ)句地進(jìn)行語(yǔ)義處理。主要任務(wù)：進(jìn)行類型審查，審查每個(gè)算符是否符合語(yǔ)言規(guī)范，不符合時(shí)應(yīng)報(bào)告錯(cuò)誤。例： programp(); varrate:real; procedureinitial; … position:=initial+rate*60/*error*//*error*//*warning*/; …有關(guān)術(shù)語(yǔ)：semanticanalysis--Theparsedprogramisfurtheranalyzedtodeterminewhetheritconformstothesourcelanguage’scontextualconstraints:scoperules,typerulese.g.Torelateeachappliedoccurrenceofanidentifierinthesourceprogramtothecorrespondingdeclaration.4、中間代碼生成：語(yǔ)法分析和語(yǔ)義分析之后，有時(shí)將源程序變成一種內(nèi)部表示形式，這種內(nèi)部表示形式叫中間代碼，該代碼是一種簡(jiǎn)單的記號(hào)系統(tǒng)。三元式、四元式等。四元式的形式為：(算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象2，結(jié)果)。如下列語(yǔ)句的生成序列： sum:=first+count*10： (inttoreal,10,_,t1) (*, id3,t1,t2) (+,id2,t2,t3) (:=,t3,-,id1)有關(guān)術(shù)語(yǔ)：intermediatecodegeneration--Thisiswheretheintermediaterepresentationofthesourceprogramiscreated.Wewantthisrepresentationtobeeasytogenerate,andeasytotranslateintothetargetprogram.Therepresentationcanhaveavarietyofforms,butacommononeiscalledthree-addresscodeor4-tuplecode.5、代碼優(yōu)化：對(duì)中間代碼進(jìn)行變換，使目標(biāo)代碼更為高效。（節(jié)省時(shí)間和空間），如：id1:=id2+id3*60(1) (inttoreal,60,-,t1)(2) (*,id3,t1,t2)(3) (+,id2,t2,t3)(4) (:=,t3,-,id1)變換為(1) (*,id3,60.0,t1)(2) (+,id2,t1,id1)有關(guān)術(shù)語(yǔ)：codeoptimization--Intermediatecodeoptimization.Theoptimizeracceptsinputintheintermediaterepresentationandoutputaversionstillintheintermediaterepresentation.Inthisphase,thecompilerattemptstoproducethesmallest,fastestandmostefficientrunningresultbyapplyingvarioustechniques.6、目標(biāo)代碼生成：將中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的匯編指令代碼。主要與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)。如：(*,id3,60.0,t1)(+,id2,t1,id1)MOV id3,R2MUL #60.0,R2MOV id2,R1ADD R2,R1MOV R1,id17、符號(hào)表管理：記錄源程序中使用的名字；收集每個(gè)名字的各種屬性信息類型、作用域、分配存儲(chǔ)信息。有關(guān)術(shù)語(yǔ)：Symboltableisadatastructurewhichisemployedtoassociateidentifierswiththeirattributes.Anidentifier’sattributeconsistsofinformationrelevanttocontextualanalysis,andisobtainedfromtheidentifier’sdeclaration.8、出錯(cuò)處理：編譯程序在各個(gè)階段應(yīng)診斷和報(bào)告源程序中的錯(cuò)誤，包括詞法錯(cuò)誤，語(yǔ)法錯(cuò)誤，語(yǔ)義錯(cuò)誤；編譯程序應(yīng)報(bào)告出錯(cuò)地點(diǎn)，并給出簡(jiǎn)明準(zhǔn)確的提示信息。有關(guān)術(shù)語(yǔ)：errorhandling(errorreportinganderrorrecovery)--Thecompilershouldreportthelocationofeacherror,togetherwithsomeexplanation.Themajorcategoriesofcompile-timeerror:syntaxerror,scopeerror,typeerror.Afterdetectingandreportinganerror,thecompilershouldattempterrorrecovery,meansthatthecompilershouldtrytogetitselfintoastatewhereanalysisofthesourceprogramcancontinueasnormallyaspossible.9、有關(guān)概念：前端和后端：前端后端：源程序中間代碼目標(biāo)代碼僅依賴源程序僅依賴目標(biāo)計(jì)算機(jī)遍(PASS)：對(duì)輸入文件（源程序或其等價(jià)的中間形式）從頭到尾掃視，完成預(yù)定的處理。編譯過(guò)程可分為一遍、兩遍或多遍完成，每一遍完成所規(guī)定的任務(wù)。例如，第一遍只完成詞法分析的任務(wù)，第二遍完成語(yǔ)法分析和語(yǔ)義加工并生成中間代碼，第三遍實(shí)現(xiàn)代碼優(yōu)化和目標(biāo)代碼生成。一個(gè)編譯程序應(yīng)分成幾遍、如何劃分？和源程序語(yǔ)言結(jié)構(gòu)及目標(biāo)機(jī)器的特征有關(guān)。分多遍完成編譯過(guò)程可使整個(gè)編譯程序的邏輯結(jié)構(gòu)更清晰，但多遍會(huì)增加讀寫(xiě)中間文件的次數(shù)，從而消耗過(guò)多的時(shí)間。10、用到編譯原理與技術(shù)的常見(jiàn)軟件工具：（1）語(yǔ)言的結(jié)構(gòu)化編輯器：提供關(guān)鍵字及其匹配的關(guān)鍵字?？蓽p少語(yǔ)法錯(cuò)誤，加快源程序調(diào)試。（2）語(yǔ)言程序的調(diào)試工具：提供判定程序的算法與功能是否正確。（3）程序格式化工具：使程序呈現(xiàn)清晰的結(jié)構(gòu)（4）語(yǔ)言程序的測(cè)試工具：Junit（5）高級(jí)語(yǔ)言之間的轉(zhuǎn)換工具：一種高級(jí)語(yǔ)言轉(zhuǎn)化成另一種高級(jí)語(yǔ)言。11、編譯程序的開(kāi)發(fā)：編譯程序的開(kāi)發(fā)通常采用自編譯、交叉編譯、自展、移植等技術(shù)來(lái)實(shí)現(xiàn)。目前已經(jīng)出現(xiàn)了一些編譯程序的自動(dòng)生成系統(tǒng)，如UNIX操作系統(tǒng)下的軟件工具LEX和YACC等。（1）自編譯：用某種高級(jí)語(yǔ)言書(shū)寫(xiě)自己的編譯程序稱為自編譯。例如,假定A機(jī)器上已有一個(gè)PASCAL語(yǔ)言編譯程序,則可用PASCAL語(yǔ)言編寫(xiě)一個(gè)功能更強(qiáng)的PASCAL語(yǔ)言編譯程序，然后借助于原有的編譯程序?qū)π戮帉?xiě)的PASCAL編譯程序進(jìn)行編譯,從而得到一個(gè)能在A機(jī)器上運(yùn)行的功能更強(qiáng)的PASCAL編譯程序。（2）交叉編譯：用A機(jī)器上的編譯程序來(lái)產(chǎn)生可在B機(jī)器上運(yùn)行的目標(biāo)代碼稱為交叉編譯。例如,若A機(jī)器上已有C語(yǔ)言編譯程序,則可用A機(jī)器中的C語(yǔ)言書(shū)寫(xiě)一個(gè)編譯程序,該編譯程序的源程序是C語(yǔ)言程序,而產(chǎn)生的目標(biāo)程序則是基于B機(jī)器的,即產(chǎn)生在B機(jī)器上執(zhí)行的低級(jí)語(yǔ)言程序。上述兩種方法假定已有一個(gè)編譯程序,若沒(méi)有,則可采用自展或移植法。（3）自展：首先確定一個(gè)非常簡(jiǎn)單的核心語(yǔ)言L0，然后用機(jī)器語(yǔ)言或匯編語(yǔ)言書(shū)寫(xiě)出其編譯程序T0；再把語(yǔ)言L0擴(kuò)充到L1，L0L1，并用L0編寫(xiě)L1的編譯程序T1(自編譯)；然后再把語(yǔ)言L1擴(kuò)充為L(zhǎng)2，L1L2，并用L1編寫(xiě)L2的編譯程序T2；……這樣不斷擴(kuò)展，直到完成所要求的編譯程序?yàn)橹?。?）移植：移植是指A機(jī)器上的某種高級(jí)語(yǔ)言的編譯程序稍加改動(dòng)后能在B機(jī)器上運(yùn)行。一個(gè)程序若能較容易地從A機(jī)器移到B機(jī)器上運(yùn)行,則稱該程序是可移植的。用系統(tǒng)已有的程序設(shè)計(jì)語(yǔ)言來(lái)書(shū)寫(xiě)編譯程序雖縮短了開(kāi)發(fā)周期,但實(shí)現(xiàn)的自動(dòng)化程序不高。編譯程序示例1#defineEoF256#defineDIGIT257charstrBuffer[1000];intnPos;charstrCode[100][100];intnPosCode;charresult[100];voidError(char*msg){throw("Errorfromdemocompiler:%s\n",msg);}typedefstruct{intToken_class;charrepr;}Token_type;staticintLayout_char(intch){switch(ch){case'':case'\t':case'\n':return1;default:return0;}}/*PUBLIC*/Token_typeToken;voidget_next_token(void){intch;do{ ch=strBuffer[nPos++];if(ch==0){Token.Token_class=EoF;Token.repr='#';return;}}while(Layout_char(ch));/*classifyit:*/if('0'<=ch&&ch<='9'){Token.Token_class=DIGIT;}else{Token.Token_class=ch;}Token.repr=ch;}typedefintOperator;typedefstruct_expression{chartype;/*'D'or'P'*/intvalue;/*for'D'*/struct_expression*left,*right;/*for'P'*/Operatoroper;/*for'P'*/struct_expression*successor;/*threadtonextnode*/}Expression;typedefExpressionAST_node;/*thetopnodeisanExpression*/staticExpression*new_expression(void){return(Expression*)malloc(sizeof(Expression));}staticvoidfree_expression(Expression*expr){free((void*)expr);}staticintParse_operator(Operator*oper_p);staticintParse_expression(Expression**expr_p);/*PUBLIC*/intParse_program(AST_node**icode_p){Expression*expr;get_next_token();/*startthelexicalanalyzer*/if(Parse_expression(&expr)){if(Token.Token_class!=EoF){Error("Garbageafterendofprogram");}*icode_p=expr;return1;}return0;}staticintParse_operator(Operator*oper){if(Token.Token_class=='+'){*oper='+';get_next_token();return1;}if(Token.Token_class=='*'){*oper='*';get_next_token();return1;}return0;}staticintParse_expression(Expression**expr_p){Expression*expr=*expr_p=new_expression();/*trytoparseadigit:*/if(Token.Token_class==DIGIT){expr->type='D';expr->value=Token.repr-'0';get_next_token();return1;}/*trytoparseaparenthesizedexpression:*/if(Token.Token_class=='('){expr->type='P';get_next_token();if(!Parse_expression(&expr->left)){Error("Missingexpression");}if(!Parse_operator(&expr->oper)){Error("Missingoperator");}if(!Parse_expression(&expr->right)){Error("Missingexpression");}if(Token.Token_class!=')'){Error("Missing)");}get_next_token();return1;}/*failedonbothattempts*/free_expression(expr);return0;}staticvoidCode_gen_expression(Expression*expr){ charbuf[100];switch(expr->type){case'D':wsprintf(buf,"PUSH%d\n",expr->value); strcpy(strCode[nPosCode++],buf);break;case'P':Code_gen_expression(expr->left);Code_gen_expression(expr->right);switch(expr->oper){//case'+':printf("ADD\n");break; case'+': strcpy(strCode[nPosCode++],"ADD"); break;//case'*':printf("MULT\n");break; case'*': strcpy(strCode[nPosCode++],"MULT"); break;}break;}}/*PUBLIC*/voidProcess(AST_node*icode){Code_gen_expression(icode);printf("PRINT\n");}intMain(void){AST_node*icode; nPos=0; nPosCode=0;if(!Parse_program(&icode))Error("Notop-levelexpression");Process(icode);return0;}intstack[100];intsp;#definePush(v)(stack[sp++]=(v))#definePop()(stack[--sp])staticAST_node*Last_node;staticvoidThread_expression(Expression*expr){switch(expr->type){case'D':Last_node->successor=expr;Last_node=expr;break;case'P':Thread_expression(expr->left);Thread_expression(expr->right);Last_node->successor=expr;Last_node=expr;break;}}/*PUBLIC*/AST_node*Thread_start;voidThread_AST(AST_node*icode){AST_nodeDummy_node;Last_node=&Dummy_node;Thread_expression(icode);Last_node->successor=(AST_node*)0;Thread_start=Dummy_node.successor;}/*PRIVATE*/staticAST_node*Thread_expression(Expression*expr,AST_node*succ){switch(expr->type){case'D':expr->successor=succ;returnexpr;break;case'P':expr->successor=succ;returnThread_expression(expr->left,Thread_expression(expr->right,expr));break;}}staticAST_node*Active_node_pointer;staticvoidInterpret_iteratively(void){while(Active_node_pointer!=0){/*thereisonlyonenodetype,Expression:*/Expression*expr=Active_node_pointer;switch(expr->type){case'D':Push(expr->value);break;case'P':{inte_left=Pop();inte_right=Pop();switch(expr->oper){case'+':Push(e_left+e_right);break;case'*':Push(e_left*e_right);break;}}break;}Active_node_pointer=Active_node_pointer->successor;}wsprintf(result,"%d\n",Pop());/*printtheresult*/}/*PUBLIC*/voidProcess_Interpreter(AST_node*icode){Thread_AST(icode); Active_node_pointer=Thread_start;Interpret_iteratively();}intMain_Int(void){AST_node*icode; nPos=0; nPosCode=0;if(!Parse_program(&icode))Error("Notop-levelexpression");Process(icode); Process_Interpreter(icode);return0;}

第二章PL/0編譯程序的實(shí)現(xiàn)一、說(shuō)明：1、教學(xué)目的與要求：以PL/0為實(shí)例（編譯程序示例2）,了解語(yǔ)言的描述、編譯程序的結(jié)構(gòu)以及工作流程、解釋程序。2、主要內(nèi)容：PL/0語(yǔ)言、PL/0編譯程序、PL/0解釋程序。3、教學(xué)重點(diǎn)：編譯程序的結(jié)構(gòu)以及每一階段的任務(wù)。4、教學(xué)難點(diǎn)：源代碼分析。二、教學(xué)內(nèi)容PL/0語(yǔ)言描述1、PL/0程序示例consta=45,b=27;varx,y,g,m;procedureswap; vartemp; begin temp:=x;x:=y;y:=temp; end;proceduremod; x:=x-x/y*y;begin x:=a;y:=b;callmod; whilex<>0dobegin callswap;callmod;end; g:=y;m:=a*b/g;write(g,m);end.2、PL/0的EBNF表示<程序>::=<分程序><分程序>::=[<常量說(shuō)明>][<變量說(shuō)明>][<過(guò)程說(shuō)明>]<語(yǔ)句><常量說(shuō)明>::=const<常量定義>{,<常量定義>}<常量定義>::=<標(biāo)識(shí)符>=<無(wú)符號(hào)整數(shù)><標(biāo)識(shí)符>::=<字母>|{<字母>|<數(shù)字>}<字母>::=a|b|c...x|y|z<無(wú)符號(hào)整數(shù)>::=<數(shù)字>{<數(shù)字>}<數(shù)字>::=0|1|2|3|4|5|6|7|8|9<變量說(shuō)明>::=var<標(biāo)識(shí)符>{,<標(biāo)識(shí)符>}<過(guò)程說(shuō)明>::=<過(guò)程首部><分程序>{,<過(guò)程說(shuō)明>}<過(guò)程首部>::=procedure<標(biāo)識(shí)符>;<語(yǔ)句>::=<賦值語(yǔ)句>|<條件語(yǔ)句>|<當(dāng)循環(huán)語(yǔ)句>|<過(guò)程調(diào)用語(yǔ)句>|<復(fù)合語(yǔ)句>|<讀語(yǔ)句> |<寫(xiě)語(yǔ)句>|<空><賦值語(yǔ)句>::=<標(biāo)識(shí)符>:=<表達(dá)式><表達(dá)式>::=[+|-]<項(xiàng){<加法運(yùn)算符><項(xiàng)>}<項(xiàng)>::=<因子>{<乘法運(yùn)算符><因子>}<因子>::=<標(biāo)識(shí)符>|<無(wú)符號(hào)整數(shù)>|'('<表達(dá)式>')'<加法運(yùn)算符>::=+|-<乘法運(yùn)算符>::=*|/<條件語(yǔ)句>::=if<條件>then<語(yǔ)句><條件>::=<表達(dá)式><關(guān)系運(yùn)算符><表達(dá)式>|odd<表達(dá)式><關(guān)系運(yùn)算符>::=<|<=|>|>=|<>|=<當(dāng)循環(huán)語(yǔ)句>::=while<條件>do<語(yǔ)句><過(guò)程調(diào)用語(yǔ)句>::=call<標(biāo)識(shí)符><復(fù)合語(yǔ)句>::=begin<語(yǔ)句>{;<語(yǔ)句>}<讀語(yǔ)句>::=read'('<標(biāo)識(shí)符>{,<標(biāo)識(shí)符>}')'<寫(xiě)語(yǔ)句>::=write'('<表達(dá)式>{,<表達(dá)式>}')'3、單詞的種類基本字：也可稱為保留字或關(guān)鍵字，如BEGIN，END，IF，THEN等。運(yùn)算符：如：+、-、*、／、∶=、#、＞=、＜=等。標(biāo)識(shí)符：用戶定義的變量名、常數(shù)名、過(guò)程名。常數(shù)：如：10，25，100等整數(shù)。界符：如：‘;’、‘(’、‘)’等。

基本字、運(yùn)算符、界符稱為語(yǔ)言固有的單詞。標(biāo)識(shí)符、常數(shù)稱為用戶定義的單詞。對(duì)語(yǔ)言固有的單詞只給出類別存放在SYM中，而對(duì)用戶定義的單詞既給類別又給值，其類別放在SYM中，值放在ID或NUM中4、變量作用域規(guī)則varx,y,g,m;procedurep1; vara; proceduremod; varb; begin x:=a-b; end;begin x:=a;y:=b;end;begin g:=y;m:=a*b/g;write(g,m);end.5、類pcode代碼指令的結(jié)構(gòu)PL/0編譯程序所產(chǎn)生的目標(biāo)代碼是一個(gè)假想棧式計(jì)算機(jī)的匯編語(yǔ)言，可稱為類PCODE指令代碼，它不依賴任何具體計(jì)算機(jī)，其格式如下：aalf其中f代表功能碼，l表示層次差，也就是變量或過(guò)程被引用的分程序與說(shuō)明該變量或過(guò)程的分程序之間的層次差。a的含意對(duì)不同的指令有所區(qū)別，對(duì)存取指令表示位移量，而對(duì)其它的指令則分別有不同的含義。6、類pcode指令LIT：將常量值取到運(yùn)行棧頂。a域?yàn)槌?shù)值。LOD：將變量放到棧頂。a域?yàn)樽兞吭谒f(shuō)明層中的相對(duì)位置,l為調(diào)用層與說(shuō)明層的層差值。STO：將棧頂?shù)膬?nèi)容送入某變量單元中。a,l域的含意同LOD指令。CAL：調(diào)用過(guò)程的指令。a為被調(diào)用過(guò)程的目標(biāo)程序入口地址，l為層差。INT：為被調(diào)用的過(guò)程(或主程序)在運(yùn)行棧中開(kāi)辟數(shù)據(jù)區(qū)。a域?yàn)殚_(kāi)辟的單元個(gè)數(shù)。JMP：無(wú)條件轉(zhuǎn)移指令，a為轉(zhuǎn)向地址。JPC：條件轉(zhuǎn)移指令，當(dāng)棧頂?shù)牟紶栔禐?時(shí)，轉(zhuǎn)向a域的地址，否則順序執(zhí)行。LIT：將常量值取到運(yùn)行棧頂。a域?yàn)槌?shù)值。LOD：將變量放到棧頂。a域?yàn)樽兞吭谒f(shuō)明層中的相對(duì)位置,l為調(diào)用層與說(shuō)明層的層差值。STO：將棧頂?shù)膬?nèi)容送入某變量單元中。a,l域的含意同LOD指令。CAL：調(diào)用過(guò)程的指令。a為被調(diào)用過(guò)程的目標(biāo)程序入口地址，l為層差。INT：為被調(diào)用的過(guò)程(或主程序)在運(yùn)行棧中開(kāi)辟數(shù)據(jù)區(qū)。a域?yàn)殚_(kāi)辟的單元個(gè)數(shù)。JMP：無(wú)條件轉(zhuǎn)移指令，a為轉(zhuǎn)向地址。JPC：條件轉(zhuǎn)移指令，當(dāng)棧頂?shù)牟紶栔禐?時(shí)，轉(zhuǎn)向a域的地址，否則順序執(zhí)行。OPR：關(guān)系運(yùn)算和算術(shù)運(yùn)算指令等。具體操作由a域值給出。OPR00：過(guò)程調(diào)用結(jié)束后,返回調(diào)用點(diǎn)并退棧OPR01：棧頂元素取反OPR02：次棧頂與棧頂相加，退兩個(gè)棧元素， 結(jié)果值進(jìn)棧OPR03：次棧頂減去棧頂，退兩個(gè)棧元素， 結(jié)果值進(jìn)棧OPR04：次棧頂乘以棧頂，退兩個(gè)棧元素， 結(jié)果值進(jìn)棧OPR05：次棧頂除以棧頂，退兩個(gè)棧元素， 結(jié)果值進(jìn)棧OPR06：棧頂元素的奇偶判斷，結(jié)果值在棧頂OPR08：次棧頂與棧頂是否相等，退兩個(gè)棧元素，結(jié)果進(jìn)棧OPR09：次棧頂與棧頂是否不等，退兩個(gè)棧元素，結(jié)果進(jìn)棧OPR010：次棧頂是否小于棧頂，并退棧，結(jié)果值進(jìn)棧OPR011：次棧頂是否大于等于棧頂，退兩個(gè)棧元素，結(jié)果進(jìn)棧OPR012：次棧頂是否大于棧頂，退兩個(gè)棧元素，結(jié)果進(jìn)棧OPR013：次棧頂是否小于等于棧頂，退兩個(gè)棧元素，結(jié)果進(jìn)棧OPR014：棧頂值輸出至屏幕OPR015：屏幕輸出換行OPR016：從命令行讀入一個(gè)輸入置于棧頂7、PL/0語(yǔ)言的出錯(cuò)信息表1：常數(shù)說(shuō)明中的“=”寫(xiě)成“∶=”。2：常數(shù)說(shuō)明中的“=”后應(yīng)是數(shù)字。3：常數(shù)說(shuō)明中的標(biāo)識(shí)符后應(yīng)是“=”。4：const,var,procedure后應(yīng)為標(biāo)識(shí)符。5：漏掉了‘，’或‘；’。6：過(guò)程說(shuō)明后的符號(hào)不正確(應(yīng)是語(yǔ)句開(kāi)始符，或過(guò)程定義符)。7：應(yīng)是語(yǔ)句開(kāi)始符。8：程序體內(nèi)語(yǔ)句部分的后跟符不正確。9：程序結(jié)尾丟了句號(hào)‘.’。10：語(yǔ)句之間漏了‘；’。11：標(biāo)識(shí)符未說(shuō)明。12：賦值語(yǔ)句中，賦值號(hào)左部標(biāo)識(shí)符屬性應(yīng)是變量。13：賦值語(yǔ)句左部標(biāo)識(shí)符后應(yīng)是賦值號(hào)‘∶=’。14：call后應(yīng)為標(biāo)識(shí)符。15：call后標(biāo)識(shí)符屬性應(yīng)為過(guò)程。16：條件語(yǔ)句中丟了‘then’。17：丟了‘end“或’；‘。18：while型循環(huán)語(yǔ)句中丟了‘do’。19：語(yǔ)句后的符號(hào)不正確。20：應(yīng)為關(guān)系運(yùn)算符。21：表達(dá)式內(nèi)標(biāo)識(shí)符屬性不能是過(guò)程。22：表達(dá)式中漏掉右括號(hào)‘)’。23：因子后的非法符號(hào)。24：表達(dá)式的開(kāi)始符不能是此符號(hào)。31：數(shù)越界。32：read語(yǔ)句括號(hào)中的標(biāo)識(shí)符不是變量。8、PL/0語(yǔ)言的實(shí)現(xiàn)9、程序的數(shù)據(jù)棧：procedureA:…procedureB:…procedureC:…callB:…程序體B…callC:…程序體A… callB:…主程序…callA:…10、符號(hào)表table:array[0..txmax]ofrecord name:alfa; casekind:categoryof const_category:(val:integer); var_category, proc_category:(level,adr,size:integer);end;11、程序的編譯和運(yùn)行

第三章文法和語(yǔ)言一、說(shuō)明：1、教學(xué)目的與要求：為語(yǔ)言的語(yǔ)法描述尋求工具。要求熟練掌握形式語(yǔ)言中基本概念及知識(shí)。2、主要內(nèi)容：文法的直觀概念、符號(hào)和符號(hào)串、文法與語(yǔ)言的形式定義、文法的分類、上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)、句型的分析、有關(guān)文法實(shí)用中的一些說(shuō)明。3、教學(xué)重點(diǎn)：與編譯技術(shù)密切相關(guān)的一些術(shù)語(yǔ)和概念。4、教學(xué)難點(diǎn)：句型的分析。二、教學(xué)內(nèi)容第一節(jié)文法的概念1、語(yǔ)法：是一組規(guī)則，定義符號(hào)如何排列，排列與符號(hào)含義無(wú)關(guān)。2、語(yǔ)義：研究語(yǔ)法的含義3、語(yǔ)言=語(yǔ)法+語(yǔ)義例：<句子>∷=<主語(yǔ)><謂語(yǔ)><主語(yǔ)>∷=<代詞>|<名詞><代詞>∷=我|你|他<名詞>∷=王明|大學(xué)生|教師|英語(yǔ)<謂語(yǔ)>∷=<動(dòng)詞><直接賓語(yǔ)><動(dòng)詞>∷=是|學(xué)習(xí)<直接賓語(yǔ)〉∷=<代詞>|<名詞>寫(xiě)出以下語(yǔ)言的文法“你是大學(xué)生” 對(duì)“我是教師” 對(duì)“我大學(xué)生是” 錯(cuò)“我學(xué)習(xí)大學(xué)生” 對(duì)<句子><主語(yǔ)><謂語(yǔ)><代詞><謂語(yǔ)>我<謂語(yǔ)>我<動(dòng)詞><直接賓語(yǔ)>我是<名詞>第二節(jié)符號(hào)和符號(hào)串PASCAL等程序設(shè)計(jì)語(yǔ)言是由所有C、PASCAL程序組成的集合。程序是由一些基本符號(hào)組成的。從字面上看，每個(gè)程序都是一個(gè)基本符號(hào)串。設(shè)有一個(gè)基本符號(hào)集，C、PASCAL等程序設(shè)計(jì)語(yǔ)言可看成是在這個(gè)基本符號(hào)集上定義的，按一定規(guī)則構(gòu)成的一切基本符號(hào)串組成的集合。母表—符號(hào)集：是字母的有窮非空集合。漢語(yǔ)字母表包括：漢字、數(shù)字、標(biāo)點(diǎn)符號(hào)等Pascal語(yǔ)言字母表包括：字母、數(shù)字以及Begin、if等保留字。號(hào)串—字母表的符號(hào)組成的任何有窮序列。符號(hào)集∑={0，1}，符號(hào)串有：0，1，00，01，10，11。符號(hào)集∑={a，b，c}，符號(hào)串有：a，b，c，ab，aaca。符號(hào)串的長(zhǎng)度：符號(hào)串x有m個(gè)符號(hào)，則長(zhǎng)度就為m，表示為|x|=m。ababa的長(zhǎng)度是5。空符號(hào)串：用表示長(zhǎng)度為0符號(hào)串。符號(hào)串x,都有x=x=x。符號(hào)串的運(yùn)算：符號(hào)串的頭和尾、固有頭和固有尾、連接、方冪、集合、閉包、正閉包。(1)符號(hào)串的頭和尾：若z=xy,則x是z的頭，y是z的尾。例：設(shè)z=abc,z的頭是：，a，ab，abcz的尾是：，c，bc，abc（2）符號(hào)串的固有頭和固有尾：若z=xy符號(hào)串，x非空，則y是固有尾；若y非空，則x是固有頭。例：設(shè)z=abc，z的固有頭是：、、ab，z的固有尾是：、c、bc。（3）符號(hào)串的連接：設(shè)x，y是符號(hào)串，連接xy是y符號(hào)寫(xiě)在x符號(hào)后。例：x=ab,y=MN，則xy=abMN。（4）符號(hào)串的方冪：設(shè)x是符號(hào)串，則z=xx……xx，稱z為x的方冪,記為z=xn。因此x0=e,x1=x,x2=xx,x3=xxx，顯然n>0時(shí),有xn=x·xn-1＝xn-1·x（5）符號(hào)串的集合：若集合A中的一切元素都是某字母表上的符號(hào)串，則稱A為該字母表上的符號(hào)串集合。兩個(gè)符號(hào)串集合A、B乘積定義：AB={xy|x∈A且y∈b}。例：A={a,b}，B={c,d}，則AB={ac，ad，bc，bd}。（6）閉包（∑*）：字母表∑，用∑*表示∑上所有有窮長(zhǎng)的串集合，∑*稱為∑的閉包。例：字母表∑={0,1}，則∑*={,0,1,00,01,10,11,000,001,010……}=∑0∪∑1∪∑2∪…∪∑n。（7）正閉包(∑+)：∑+=∑1∪∑2∪…∪∑n，稱為∑的正閉包。顯然：∑*＝∑0∪∑+，∑+＝∑∑*＝∑*∑。第三節(jié)文法和語(yǔ)言的定義1、規(guī)則（重寫(xiě)規(guī)則、產(chǎn)生式、生成式）形如→或::=， 是字母表V的正閉包V+的一個(gè)符號(hào)；是字母表V的閉包V*的一個(gè)符號(hào)；稱規(guī)則的左部，稱規(guī)則的右部。2、文法的定義（1）文法G定義為四元組（VN，VT，P，S）其中： VN——非終結(jié)符號(hào)集VT——終結(jié)符號(hào)集 P——產(chǎn)生式（規(guī)則）S——開(kāi)始符號(hào)或稱作識(shí)別號(hào)，它是一個(gè)非終結(jié)符，至少要在一條規(guī)則中作為左部出現(xiàn)。規(guī)定：（1）VN，VT，P是有窮非空集合；（2）VN∩VT＝（不含公共元素）例1：文法G=(VN,VT,P,S)，其中VN={S}，VT={0，1}，P={S→0S1，S→01}。非終結(jié)符集中只含一個(gè)元素S；終結(jié)符集由兩個(gè)元素0和1組成；有兩條產(chǎn)生式；開(kāi)始符號(hào)是S。問(wèn)：從終結(jié)符可推出哪些符號(hào)串？ S＝{01，0011，000111，00001111…}例2：文法G=(VN,VT,P,S)，其中VN={標(biāo)識(shí)符,字母,數(shù)字}，VT={a,b,c,…,x,y,z,0,1,…,9}，P={<標(biāo)識(shí)符>→<字母><標(biāo)識(shí)符>→<標(biāo)識(shí)符><字母><標(biāo)識(shí)符>→<標(biāo)識(shí)符><數(shù)字><字母>→a|b|c…z<數(shù)字>→1|2|3…9}，S=<標(biāo)識(shí)符>例3：文法G=(VN,VT,P,S)，其中VN={S}，VT={0,1}，P={S→0S1,S→01}。 文法G的第二種表示法：G:S→0S1S→01 文法G的第三種表示法：G[S]:S→0S1S→01一般約定，第一條產(chǎn)生式的左部是識(shí)別符號(hào)；用尖括號(hào)括起來(lái)的是非終結(jié)符號(hào)，不用尖括號(hào)括起來(lái)的是終結(jié)符號(hào)，或者用大寫(xiě)字母表示非終結(jié)符號(hào)，小寫(xiě)字母表示終結(jié)符號(hào)。3、直接推導(dǎo)的定義：→是文法G=VN,VT，P，S）的規(guī)則，和是V*中的任意符號(hào)，若有符號(hào)串V，W滿足：V=，W＝，則V是直接產(chǎn)生W或W是V的直接推導(dǎo)或W直接規(guī)約到V，記作VW。例4：G:S→0S1，S→01，V＝0S1，W=0011，W是否V的直接推導(dǎo)？V=S，W＝0S1，W是否V的直接推導(dǎo)？V=0S1，W=00S11，W是否V的直接推導(dǎo)？若存在直接推導(dǎo)的序列：V=W0W1W2…Wn=W(n>0)，則稱V推導(dǎo)W（或W規(guī)約到V），記V+W。若有VW，或V=W，則記作V*W。如：V＝0S100S11000S11100001111＝W記作：0S1+00001111或0S1*000011114、句型的定義：設(shè)G[S]是文法，如果符號(hào)串x是從識(shí)別符號(hào)（開(kāi)始符號(hào)）推導(dǎo)出來(lái)的（即Sx）,則稱x是文法G[S]的句型。若x僅由終結(jié)符號(hào)組成（Sx，xVT*），則稱x為G[S]的句子。例：S，0S1，000111都是文法G的句型，000111是G的句子。注意：句子一定是句型，句型不一定是句子。5、語(yǔ)言的定義：文法G產(chǎn)生的語(yǔ)言定義為G產(chǎn)生的句子的集合{x|Sx，S為文法開(kāi)始符號(hào)，xVT*}，該集合為語(yǔ)言，用L(G)表示。從定義可知：x是句型且x是文法G的句子。例：設(shè)G:S→0S1|01，G定義的語(yǔ)言是什么？L(G)＝｛0n1nn1｝。例：設(shè)G=(VN,VT,P,S)，VN={S,B,E},VT={a,b,e}，P為： (1)S→aSBE (2)S→aBE(3)EB→BE(4)aB→ab(5)bB→bb(6)bE→be(7)eE→ee問(wèn)：L(G)表示是什么語(yǔ)言？L(G)={anbnen|n1}如：SaSBEaaSBEBEaaaSBEBEBE…aaaSBBEBEEaaaSBBBEEEaaaaBEBBBEEEaaaaBBEBBEEEaaaaBBBEBEEEaaaaBBBBEEEEaaaabBBBEEEEaaaabbBBEEEEaaaabbbBEEEEaaaabbbbEEEEaaaabbbbeEEEaaaabbbbeeEEaaaabbbbeeeEaaaabbbbeeeea4b4e4第四節(jié)文法的類型語(yǔ)言學(xué)家Chomsky把文法分成以下四種類型：其中，正規(guī)文法一定也是上下文無(wú)關(guān)文法1、0型文法：設(shè)G=(VN,VT,P,S)，如果它的每一個(gè)產(chǎn)生式滿足：(VN∪VT)*且至少包含一個(gè)非終結(jié)符，(VN∪VT)*，則G是0型文法。2、1型文法：設(shè)G=(VN,VT,P,S)，如果它的每一個(gè)產(chǎn)生式滿足：||≥||，僅僅S除外，則文法G是1型文法。1型文法又稱為上下文有關(guān)文法，它的每一個(gè)產(chǎn)生式也可描述為：1A212,其中1、2及都在(VN∪VT)*中,A在VN中。只有A出現(xiàn)在12的上下文中，才允許用取代A。3、2型文法：設(shè)G=(VN,VT,P,S)，如果它的每一個(gè)產(chǎn)生式滿足：是一非終結(jié)符，(VN∪VT)*，則此文法稱為2型文法。例：G＝({S,A,B},{a,b},P,S)，P定義如下：（1）S→aB|bA（2）A→bAA|a|aS（3）B→b|bS|aBB4、3型文法（正規(guī)文法）：設(shè)G=(VN,VT,P,S)，若P中的每一個(gè)產(chǎn)生式都是A→aB或A→a，A,B都是非終結(jié)符，a是終結(jié)符，則G是正規(guī)文法。例：下列文法是正規(guī)文法S→0|0A|1B（2）A→0S|0A|1B（3）B→0|1|1B5、對(duì)比：0型文法：左部至少含有一個(gè)非終結(jié)符1型文法：左部比右部短（不長(zhǎng)于右部）2型文法：左部只有一個(gè)（非終結(jié)符）3型文法：右部只有一個(gè)或兩個(gè)（a或aB）例：通過(guò)分別給出下列語(yǔ)言的文法來(lái)證明這些語(yǔ)言是上下無(wú)關(guān)的：(1)L1={anb2ncm|n,m≥0} (2)L2={anbmc2m|n,m≥0}(1)S→ABA→|aAbbB→|cB (2)S→ABA→|aAB→|bBcc第五節(jié)上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）的定義：給定文法G=(VN,VT,P,S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)，須滿足條件：（1）每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)。（2）根的標(biāo)記是S。（3）若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則A肯定在VN中。（4）如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)n1,n2,…,nK，其標(biāo)記分別為A1,A2,…,AK，那么 AA1A2…AK一定是P中的一個(gè)產(chǎn)生式。例1、給定下列文法：(1)SaAS(2)ASbA(3)ASS(4)Sa(5)Aba請(qǐng)構(gòu)造aabbaa的語(yǔ)法樹(shù)。SaASaSbASaSbAaaabAaaabbaa語(yǔ)法樹(shù)的理解：語(yǔ)法樹(shù)表示了在推導(dǎo)過(guò)程中用到什么樣的產(chǎn)生式和用到哪些非終結(jié)符，并沒(méi)有表明采用的順序。它只表示推導(dǎo)的結(jié)果，不表示推導(dǎo)的過(guò)程。最左推導(dǎo)（或最右推導(dǎo)）：若在推導(dǎo)中的任何一步β（、β是句型），都是對(duì)中的最左（最右）非終結(jié)符進(jìn)行替換，則稱為最左（最右）推導(dǎo)。最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。例2、給定下列文法：(1)SaAS(2)ASbA(3)ASS(4)Sa(5)Aba請(qǐng)構(gòu)造aabbaa的語(yǔ)法樹(shù)1）每次替換最右邊非終結(jié)符 SaASaAaaSbAaaSbbaaaabbaa2）每次替換最左邊非終結(jié)符 SaASaSbASaabASaabbaSaabbaa3）無(wú)固定的推導(dǎo)方向 SaASaSbASaSbAaaabAaaabbaa一棵語(yǔ)法樹(shù)表示了一個(gè)句型的種種可能的不同推導(dǎo)過(guò)程，包括最左(最右)推導(dǎo)。但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢?一個(gè)句型是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?文法的二義性的定義：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則說(shuō)這個(gè)文法是二義的；若一個(gè)文法中存在某個(gè)句子，它有兩個(gè)不同的最左（最右）推導(dǎo)，則這個(gè)文法是二義的。如果一個(gè)語(yǔ)言的每一個(gè)文法都是二義的，那么這個(gè)語(yǔ)言是二義的例3、證明下列文法是二義的：(1)Ei(2)EE+E(3)EE*E(4)E(E)。推導(dǎo)1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推導(dǎo)2：EE*Ei*Ei*E+Ei*i+Ei*i+i產(chǎn)生兩個(gè)不同的語(yǔ)法樹(shù)：如果規(guī)定“*”和“+”的優(yōu)先性，并服從左結(jié)合，上式就可以構(gòu)出無(wú)二義性。（1）ET|E+T （2）TF|T*F （3）F(E)|i例4、證明下列文法是二義的：(1)EEOF|(E)|v|d(2)O+|*第六節(jié)句型的分析1、判斷給定的符號(hào)串是否某文法的句子。例如：給定C語(yǔ)言的文法規(guī)則，對(duì)于一個(gè)源程序，要求編譯系統(tǒng)判斷該源程序是否合法。句型分析是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是整個(gè)推導(dǎo)的構(gòu)造過(guò)程。（為一個(gè)符號(hào)串構(gòu)造一個(gè)語(yǔ)法樹(shù)/推導(dǎo)樹(shù)）。即識(shí)別輸入符號(hào)串是否為語(yǔ)法上是否正確的過(guò)程。分析程序（識(shí)別程序）是完成句型分析的程序。分析算法：（1）自上而下分析法：從文法開(kāi)始符號(hào)出發(fā)，反復(fù)使用規(guī)則，尋找匹配符號(hào)串（推導(dǎo)）（2）自下而上分析法：從輸入符號(hào)開(kāi)始，逐步進(jìn)行“規(guī)約”，直至文法的開(kāi)始符號(hào)（歸約）例1、給定下列文法：（1）ScAd （2）Aab （3）Aa輸入串cabd是否為該文法的句子？自上而下分析法自下而上分析法2、句型分析的2個(gè)問(wèn)題(討論)：（1）在自上而下分析中，被代換的最左部非終結(jié)符號(hào)在右部有多個(gè)終結(jié)符時(shí)，如何確定？假定要被代換的最左非終結(jié)符號(hào)是B，且有n條規(guī)則：B→A1|A2|…|An，那么如何確定用哪個(gè)右部去替代B？采取回溯法（在第5章介紹）（2）自下而上的分析中，如何確定可歸約串呢？尋找句柄。3、短語(yǔ)：設(shè)有文法G，S是文法的開(kāi)始符號(hào)，設(shè)是G的一個(gè)句型（S*），若有S*A且A+，則稱是句型關(guān)于非終結(jié)符A的短語(yǔ)。例2、ab、bb、Ab、aAcBe、abbcde是短語(yǔ)嗎？ab不是短語(yǔ)；bb、Ab是短語(yǔ)；aAcBe是短語(yǔ)；abbcde是短語(yǔ) 六、句型的分析3、直接短語(yǔ)：如果：S+、S*A、A，則稱是句型關(guān)于規(guī)則A的直接短語(yǔ)。4、句柄：一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。規(guī)范推導(dǎo)：最右推導(dǎo)。規(guī)范歸約：最左歸約，即對(duì)句柄進(jìn)行的歸約。由規(guī)范歸約構(gòu)成的分析樹(shù)和推導(dǎo)樹(shù)完全相同。例3、給定文法：(1)EE+T|T(2)TT*F|F(3)F(E)|I，給定句型：i1*i2+i3。（1）E*F*i2+i3且Fi1，則稱i1是句型i1*i2+i3的相對(duì)非終結(jié)符F的短語(yǔ)，是相對(duì)規(guī)則Fi的直接短語(yǔ)。（2）E*i1*F+i3且Fi2，則稱i2是句型i1*i2+i3的相對(duì)非終結(jié)符F的短語(yǔ)，是相對(duì)規(guī)則Fi的直接短語(yǔ)。（3）E*i1*i2+F且Fi3，則稱i3是句型i1*i2+i3的相對(duì)非終結(jié)符F的短語(yǔ)，是相對(duì)規(guī)則Fi的直接短語(yǔ)。（4）E*T*i2+i3且Ti1，則i1是句型i1*i2+i3的相對(duì)于T的短語(yǔ)。（5）E*i1*i2+T且T+i3，則i3是句型i1*i2+i3的相對(duì)于T的短語(yǔ)（6）E*T+i3且T+i1*i2，則i1*i2是句型i1*i2+i3相對(duì)于T的短語(yǔ)。（7）E*E+i3且E+i1*i2，則i1*i2是句型i1*i2+i3相對(duì)于E的短語(yǔ)。（8）E*E且Ei1*i2+i3，則i1*i2+i3是句型i1*i2+i3相對(duì)于E的短語(yǔ)。（9）i2+i3是句型i1+i2+i3的短語(yǔ)嗎？（10）句柄=i1，還有沒(méi)有別的句柄？例4、給定文法：(1)SaAS(2)ASbA(3)ASS(4)Sa(5)Aba給定句型：a1a2b1b2a3a4，直接短語(yǔ)有：a2、b2a3、a4，短語(yǔ)有a2、b2a3、a4、a2b1b2a3，句柄=a2。SbA是不是短語(yǔ)？a1為什么不是句柄？解題方法：畫(huà)出句型對(duì)應(yīng)的語(yǔ)法樹(shù)；以某非終結(jié)符為根的兩代以上的子樹(shù)的所有末端結(jié)點(diǎn)從左到右排列就是該非終結(jié)符的一個(gè)短語(yǔ)；如果子樹(shù)只有兩代，則該短語(yǔ)就是直接短語(yǔ)；最左的兩代子樹(shù)的所有末端結(jié)點(diǎn)從左到右排列就是該句型的句柄第七節(jié)有關(guān)文法的一些限制文法中不含有有害規(guī)則和多余規(guī)則，有害規(guī)則：形如U→U的產(chǎn)生式。會(huì)引起文法的二義性。多余規(guī)則：指文法中任何句子的推導(dǎo)都不會(huì)用到的規(guī)則。多余規(guī)則也可表示為：文法中不含有不可到達(dá)和不可終止的非終結(jié)符，分以下兩種情況：（1）文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，該非終結(jié)符稱為不可到達(dá)。（2）文法中某些非終結(jié)符，由它不能推出終結(jié)符號(hào)串，該非終結(jié)符稱為不可終止。例1、（1）SBe（2）BCe|Af（3）AAe|e（4）CCf（5）Df文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)；文法中某些非終結(jié)符，由它不能推出終結(jié)符號(hào)串。D為不可到達(dá)，C為不可終止。產(chǎn)生式2），6），7）為多余規(guī)則應(yīng)去掉。本章小結(jié)本章出現(xiàn)的概念較多,應(yīng)重點(diǎn)理解文法,推導(dǎo),句型句子及語(yǔ)言的定義等概念.語(yǔ)法分析有關(guān)內(nèi)容在后面章節(jié)會(huì)詳細(xì)討論.文法作為程序語(yǔ)言的語(yǔ)法的描述工具,它用規(guī)則只能陳述的是:語(yǔ)言的所有句子以什麼樣的符號(hào)串能出現(xiàn).請(qǐng)記住文法和語(yǔ)言的形式定義中的“形式”的含義—只涉及語(yǔ)言的語(yǔ)法不涉及語(yǔ)言的語(yǔ)義.本章內(nèi)容是形式語(yǔ)言理論的一部分.形式語(yǔ)言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究。是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的基礎(chǔ)。

第四章詞法分析一、說(shuō)明：1、教學(xué)目的與要求：熟練掌握正規(guī)式與有窮自動(dòng)機(jī)和正規(guī)文法與有窮自動(dòng)機(jī)關(guān)系。掌握詞法分析程序的設(shè)計(jì)原理與構(gòu)造方法。2、主要內(nèi)容：詞法分析程序的設(shè)計(jì)、單詞的描述工具、有窮自動(dòng)機(jī)、正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性、正規(guī)文法和有窮自動(dòng)機(jī)間的轉(zhuǎn)換、詞法分析程序的自動(dòng)構(gòu)造工具。自動(dòng)識(shí)別單詞的方法：（1）單詞結(jié)構(gòu)的描述--正規(guī)文法和正規(guī)式；（2）把正規(guī)式轉(zhuǎn)換為一個(gè)NFA；（3）把NFA轉(zhuǎn)換為相應(yīng)的DFA；（4）基于DFA構(gòu)造詞法分析程序。3、教學(xué)重點(diǎn)：?jiǎn)卧~的描述技術(shù)；正規(guī)文法和正規(guī)式；單詞的識(shí)別機(jī)制：確定有窮自動(dòng)機(jī)、不確定有窮自動(dòng)機(jī)；詞法分析程序的自動(dòng)構(gòu)造。4、教學(xué)難點(diǎn)：正規(guī)式等價(jià)變換為NFA、NFA等價(jià)變換為正規(guī)式、DFA的最小化。二、教學(xué)內(nèi)容第一節(jié)掃描器的設(shè)計(jì)方法1、詞法分析程序也叫詞法分析器或掃描器。其功能是輸入源程序,輸出單詞符號(hào)。單詞符號(hào)：是語(yǔ)言中具有獨(dú)立意義的最小單位，包括保留字、標(biāo)識(shí)符、運(yùn)算符、標(biāo)點(diǎn)符號(hào)和常量等。輸出形式為二元組。主要任務(wù)：從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描,產(chǎn)生一個(gè)個(gè)單詞符號(hào),把字符串形式的源程序改造成為單詞符號(hào)串形式的中間程序。其他任務(wù)：濾掉空格、跳過(guò)注釋、追蹤換行標(biāo)志、宏展開(kāi)、查填符號(hào)表、發(fā)現(xiàn)并定位詞法錯(cuò)誤、……。單詞符號(hào)分類：?jiǎn)卧~符號(hào)是程序語(yǔ)言的基本語(yǔ)法單位。通常分為五種：(1)保留字： 如if、while(2)標(biāo)識(shí)符： 標(biāo)記常量、變量、函數(shù)等的名字(3)常數(shù)： 如實(shí)型0.618、布爾型TRUE(4)運(yùn)算符： 如+、-、*、/、>、<(5)界符： 分界符，如,、;、(、)注意：保留字、運(yùn)算符和界符的個(gè)數(shù)確定，標(biāo)識(shí)符和常數(shù)的個(gè)數(shù)不確定。單詞符號(hào)的輸出形式：(單詞種別,單詞自身的值)單詞種別:單詞種別表示單詞的種類。一個(gè)語(yǔ)言的單詞符號(hào)如何分類、分為幾類、如何編碼主要取決于處理上的方便。通常，每種單詞對(duì)應(yīng)一個(gè)整數(shù)碼。保留字：可全體視為一種，也可一字一種；標(biāo)識(shí)符：統(tǒng)歸為一種；常數(shù)：統(tǒng)歸為一種,或按整、實(shí)、布爾等再分；運(yùn)算符和界符：一符一種，或統(tǒng)歸為一種。單詞自身的值：?jiǎn)卧~自身的值是編譯其它階段需要的信息。對(duì)于單詞符號(hào),若一個(gè)種別只含一個(gè)單詞,則其種別編碼就代表它自身的值。若一個(gè)種別含多個(gè)單詞,則除種別編碼外,還應(yīng)給出單詞自身的值,以便把同一種類的單詞區(qū)別開(kāi)來(lái)。注意：標(biāo)識(shí)符自身的值是標(biāo)識(shí)符自身的字符串,常數(shù)自身的值是常數(shù)本身的二進(jìn)制數(shù)值。此外,也可用指向某類表格中一特定項(xiàng)目的指針來(lái)區(qū)分同類中的不同單詞。例如,對(duì)于標(biāo)識(shí)符,可用它在符號(hào)表的入口指針作為自身的值;常數(shù)可用它在常數(shù)表的入口指針作為自身的值。如：while (WHILE, _)( (SLP, _)* (FETCH， _)pointer (IDN， 符號(hào)表入口指針)!= (RELOP， NE)'\0' (CONST， 0)) (SRP， _){ (LP， _)pointer (IDN， 符號(hào)表入口指針)++ (INC， _); (SEMI， _)} (RP， _)詞法分析和語(yǔ)法分析的接口關(guān)系：主程序、子程序。詞法分析從語(yǔ)法分析中獨(dú)立出來(lái)的原因：簡(jiǎn)化設(shè)計(jì)；改進(jìn)編譯效率；增加編譯系統(tǒng)的可移植性主程序：詞法分析是編譯過(guò)程中的一個(gè)階段，在語(yǔ)法分析前進(jìn)行。將詞法分析作為獨(dú)立的一遍來(lái)完成。子程序：詞法分析和語(yǔ)法分析結(jié)合在一起作為一遍，進(jìn)行語(yǔ)法分析時(shí),每當(dāng)需要一個(gè)單詞時(shí)便調(diào)用詞法分析程序。第二節(jié)單詞的描述工具某種程序設(shè)計(jì)語(yǔ)言中的所有單詞構(gòu)成一種語(yǔ)言。該語(yǔ)言的語(yǔ)法都能用正規(guī)文法表示。正規(guī)文法是描述單詞的一種工具。正規(guī)文法：文法G=(VN,VT,P,S)，P中每一規(guī)則有A→aB或A→a的形式，A,BVN，aVT*，稱G(S)是正規(guī)文法。正規(guī)集：由正規(guī)文法產(chǎn)生的語(yǔ)言L(G)。正規(guī)式（正則表達(dá)式）：表示正規(guī)集的工具，也是用以描述單詞符號(hào)的方便工具。正規(guī)式與正規(guī)集：設(shè)字母表為Σ，輔助字母表Σ'={,,|,·,*,(,)}；(1)和都是Σ上的正規(guī)式，表示的正規(guī)集分別為{}和；(2)任何aΣ,a是Σ上的一個(gè)正規(guī)式，表示的正規(guī)集為{a}；(3)假定e1和e2都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2),則(e1),e1|e2,e1·e2和e1*也都是正規(guī)式，所表示的正規(guī)集分別為:L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))*。僅由有限次使用上述三步驟定義的表達(dá)式才是Σ上的正規(guī)式，僅由這些正規(guī)式所表示的集合才是Σ上的正規(guī)集。說(shuō)明：（1）Σ上的一個(gè)字指的是由Σ中字符構(gòu)成的一個(gè)有窮序列;不包含任何字符的序列稱為空字。Σ*表示Σ上所有字的全體,包括空字。例如,若Σ={a,b}，則Σ={,a,b,aa,ab,ba,bb,aaa,…}（2）Ф表示不含任何元素的空集{}。注意：、{}和{}的區(qū)別：表示不包含任何字符的序列,它是正規(guī)集中的一個(gè)元素；{}表示不含任何字的集合,它是一個(gè)空的正規(guī)集；{}表示由空字組成的集合。（3）使用括號(hào)可改變運(yùn)算符的運(yùn)算次序。若規(guī)定*優(yōu)先于·,·優(yōu)先于|,則在不混淆情況下,可省去括號(hào)。（4）Σ*的正規(guī)式R和S的連接可形式化為RS={|∈R&∈S}。例如,R={a,b}，S={1,2}，RS={a1,a2,b1,b2}。（5）R自身的n次連接記為：Rn=RR…R（6）R0={},R*=R0∪R1∪R2∪R3∪…,R*為R的閉包。R+=RR*,稱R+是R的正閉包。閉包R*中的每個(gè)字都是由R中的字經(jīng)過(guò)有限次連接而成的。對(duì)于正規(guī)式R和S,若它們表示的正規(guī)集L(R)=L(S),則稱R和S等價(jià),記為R=S。（7）正規(guī)式服從代數(shù)規(guī)律：設(shè)r、s、t為正規(guī)式，1、r|s＝s|r 交換律2、r|(s|t)＝(r|s)|t 結(jié)合律3、(rs)t=r(st) 結(jié)合律4.r(s|t)=rs|rt 分配律(s|t)r=sr|tr 分配律5.r=r 零一律r=r 零一律例1、＝{a,b}，上的正規(guī)式和相應(yīng)的正規(guī)集例2、令={d,,e,+,-}，則上的正規(guī)式d*(.dd*|)(e(+|-|)dd*|)表示的是所有無(wú)符號(hào)數(shù)。 其中d為0～9中的數(shù)字。比如：2,12.59,3.6e2,471.88e-1等都是正規(guī)式表示集合中的元素。例3：判斷下述正規(guī)式之間是否等價(jià)：(1)(a|b)*與a*|b* (2)(ab)*與a*b* (3)(a|b)*與(a*b*)*(1)(a|b)*對(duì)應(yīng)的正規(guī)集其a,b可任意交替出現(xiàn),如abbaaab…,而(a*|b*)對(duì)應(yīng)的正規(guī)集只可出現(xiàn)任意個(gè)a或任意個(gè)b,因此兩者不等價(jià)。(2)(ab)*對(duì)應(yīng)的正規(guī)集以任意個(gè)ab對(duì)出現(xiàn)，即ababab…,而a*b*對(duì)應(yīng)的正規(guī)集則是任意個(gè)a后接任意個(gè)b,即a…ab…b,因此兩者不等價(jià)。(3)(a|b)*對(duì)應(yīng)的正規(guī)集其a,b可任意交替出現(xiàn),如aababbb,而(a*b*)*可采用如下方法得到相應(yīng)的字:(a*b*)*(a*b*)(a*b*)(a2b1)(a1b3)aababbb。反之,(a*b*)*產(chǎn)生的任意字也可由(a|b)*得到,因此兩者等價(jià)。例4、程序設(shè)計(jì)語(yǔ)言中的單詞既能用正規(guī)文法表示，又能用正規(guī)式來(lái)表示。正規(guī)文法：<字母>::=a|b|c…|z<字母數(shù)字>→l|d|l<字母數(shù)字>|d<字母數(shù)字><標(biāo)識(shí)符>::=<字母>|<字母><字母數(shù)字>正規(guī)式： 標(biāo)識(shí)符=字母(字母|數(shù)字)*二、單詞的描述工具例5、證明:若L(a+)={a}*-{},則a+=aa*證:L(a+)={a}*-{}={,a,a2,a3,…}-{}={a,a2,a3,…}={a}·{,a,a2…}={a}{a}*=L(a)L(a*)=L(aa*)一個(gè)正規(guī)語(yǔ)言可以由正規(guī)文法定義，也可以用正規(guī)式定義。有些語(yǔ)言容易用文法表示，有些語(yǔ)言容易用正規(guī)式表示。正規(guī)文法和正規(guī)式的等價(jià)性,即正規(guī)式正規(guī)文法(1)對(duì)于任意一個(gè)正規(guī)文法，存在一個(gè)定義同一語(yǔ)言的正規(guī)式。(2)對(duì)于任意一個(gè)正規(guī)式，存在一個(gè)生成同一語(yǔ)言的正規(guī)文法。例6、將R＝a(a|d)*變換成正規(guī)文法（S是開(kāi)始符號(hào)）。S→a(a|d)*S→aA,A→(a|d)*A→(a|d)*A→(a|d)A,A→A→(a|d)AA→aA,A→dAS→aA,A→aA,A→dA,A→例7：設(shè)有文法G(S)： S→aA,S→a,A→aA,A→dA,A→a,A→d試將該文法變換成正規(guī)式。（不斷收縮產(chǎn)生式規(guī)則，直到剩下一個(gè)開(kāi)始符號(hào)定義的正規(guī)式）第三節(jié)單詞的識(shí)別機(jī)制1、有窮自動(dòng)機(jī)是一種自動(dòng)識(shí)別裝置，能正確識(shí)別正規(guī)