編譯原理教案

PAGEPAGE1編譯原理教案說明：一、參考書：1、陳意云、張昱：《編譯原理》，高等教育出版社，2003年。2、陳意云、張昱：《編譯原理習(xí)題精選》，中國科技大學(xué)出版社，2003年。3、呂映芝、張素琴、蔣維杜：《編譯原理》，清華大學(xué)出版社，1998年第二版。4、王生原、呂映芝、張素琴：《編譯原理課程輔導(dǎo)》，清華大學(xué)出版社，2007年。5、伍春香：《編譯原理習(xí)題與解析》，清華大學(xué)出版社，2001年。6、AndrewW.Appel：《現(xiàn)代編譯原理—C語言描述》，人民郵電出版社，2005年。7、NoamNison等：《計算機(jī)系統(tǒng)要素》，電子工業(yè)出版社，2007年。8、RandallHyde：《編程卓越之道（第二卷）》，電子工業(yè)出版社，2007年。二、教學(xué)目的：通過學(xué)習(xí)形式語言與自動機(jī)理論、詞法分析、語法分析、語義分析、代碼優(yōu)化和生成等內(nèi)容使學(xué)生掌握構(gòu)造編譯程序的基本原理和基本方法，并通過上機(jī)實(shí)習(xí)使學(xué)生進(jìn)一步掌握開發(fā)應(yīng)用程序的基本方法，為深入理解計算機(jī)系統(tǒng)、程序設(shè)計語言與開發(fā)大型應(yīng)用程序打下良好的基礎(chǔ)。三、教學(xué)時數(shù)：課堂教學(xué)51學(xué)時，上機(jī)實(shí)驗(yàn)30學(xué)時。四、授課內(nèi)容：第一章編譯程序概述第二章PL/0編譯程序的實(shí)現(xiàn)第三章文法和語言第四章詞法分析第五章自頂向下語法分析方法第六章自底向上優(yōu)先分析方法第七章LR分析方法第八章語法制導(dǎo)翻譯和中間代碼生成第九章符號表第一○章目標(biāo)程序運(yùn)行時的存儲組織第一一章代碼優(yōu)化第一二章代碼生成第一章概述一、說明：1、教學(xué)目的與要求：了解編譯程序的概念、結(jié)構(gòu)以及工作流程。2、主要內(nèi)容：什么是編譯程序、編譯過程概述、編譯程序的結(jié)構(gòu)、編譯階段的組合、編譯技術(shù)和軟件工具以及實(shí)例分析。3、教學(xué)重點(diǎn)：編譯程序的結(jié)構(gòu)以及每一階段的任務(wù)。4、教學(xué)難點(diǎn)：理解編譯程序各模塊的判錯功能、編譯方式和解釋方式執(zhí)行速度上的不同。二、教學(xué)內(nèi)容第一節(jié)編譯程序1、機(jī)器語言：直接用計算機(jī)能夠識別的二進(jìn)制代碼指令來編寫程序的語言。由二進(jìn)制的指令代碼組成。1+3表示為100000010000000100000011。是最底層的計算機(jī)語言，不需要翻譯就可以直接被計算機(jī)硬件識別。對應(yīng)不同的計算機(jī)硬件有不同的機(jī)器語言。特點(diǎn)：執(zhí)行速度快，但編寫程序的難度大，修改、調(diào)試不方便，直觀性差，不易移植。2、匯編語言：又稱為符號語言。與機(jī)器語言一一對應(yīng)，采用能幫助記憶的英文縮寫符號（指令助記符）來代替機(jī)器語言指令中的操作碼，用地址符號來代替地址碼。用指令助記符及地址符號書寫的指令稱為匯編指令，用匯編指令編寫的程序稱為匯編語言源程序。將X、Y中的內(nèi)容相加表示為ADDXY。機(jī)器不能直接識別匯編語言程序，必須把它翻譯為機(jī)器語言程序才能執(zhí)行。特點(diǎn)：比機(jī)器語言直觀，容易理解和記憶，比高級語言的執(zhí)行效率高，但通用性和移植性較差。3、高級語言：與具體的計算機(jī)硬件無關(guān)，是面向問題的程序設(shè)計語言，其表達(dá)方式接近于自然語言和數(shù)學(xué)語言，易于人們接受和掌握。采用類似于數(shù)學(xué)公式的書寫方式：x=1+3。特點(diǎn)：獨(dú)立于具體的計算機(jī)硬件，程序的編制和調(diào)試方便，通用性和可移植性好。在計算機(jī)執(zhí)行之前，需要通過編譯程序翻譯成目標(biāo)語言程序，或需要通過解釋程序邊解釋，邊執(zhí)行。時間與空間效率比較低。目前比較流行的高級語言有：C++,VisualBasic,Java，Pascal，4、什么是編譯程序：編譯程序把高級語言程序翻譯成等價的低級語言程序：源程序編譯程序目標(biāo)程序。編譯程序是現(xiàn)代計算機(jī)系統(tǒng)的基本組成部分。從功能上看，一個編譯程序就是一個語言翻譯程序，它把一種語言(稱作源語言)書寫的程序翻譯成另一種語言(稱作目標(biāo)語言)的等價的程序。高級語言源程序的執(zhí)行通常分兩個階段:源程序源程序(高級語言)編譯程序計算機(jī)目標(biāo)程序(機(jī)器語言)編譯階段初始數(shù)據(jù)目標(biāo)程序計算機(jī)運(yùn)行系統(tǒng)計算結(jié)果運(yùn)行階段若編譯生成的目標(biāo)程序是匯編語言形式,則在編譯與運(yùn)行階段之間還要添加一個匯編階段。高級語言源程序也可通過解釋程序來執(zhí)行,如BASIC。解釋程序與編譯程序的主要區(qū)別是：編譯程序?qū)⒄麄€源程序全部翻譯成目標(biāo)程序后再執(zhí)行該目標(biāo)程序；解釋程序則逐條讀出源程序中的語句并解釋執(zhí)行，在解釋程序執(zhí)行過程中并不產(chǎn)生目標(biāo)程序。源程序源程序(高級語言)初始數(shù)據(jù)解釋程序計算機(jī)計算結(jié)果第二節(jié)編譯程序結(jié)構(gòu)編譯程序的工作過程是指從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟恼麄€過程。編譯程序內(nèi)部包括了許多步驟或稱為階段，它們執(zhí)行不同的邏輯操作。將這些階段設(shè)想為編譯程序中一個個單獨(dú)的片斷是很有用的，盡管在應(yīng)用中它們是經(jīng)常組合在一起的，但它們確實(shí)是作為單獨(dú)的代碼操作來編寫的。編譯工作的基本過程是：詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成等6個階段。每個階段都有表格管理和出錯處理部分。1、詞法分析：像翻譯英文句子一樣，先要分析單詞，弄清各單詞的意義和句中的作用，才能對句子進(jìn)行翻譯。主要任務(wù)：從左到右一個字符一個字符地讀入源程序，對構(gòu)成源程序的字符流進(jìn)行掃描和分解，從而識別出一個個單詞。單詞包括：保留字、標(biāo)識符、運(yùn)算符、分界符等。例：position:=initial+rate*60;單詞類型 單詞值標(biāo)識符(id1) position算符(賦值) :=標(biāo)識符(id2) initial算符(加) +標(biāo)識符(id3) rate算符(乘) *整數(shù) 60界符 ；有關(guān)術(shù)語：lexicalanalysisorscanning--Thestreamofcharactersmakingupasourceprogramisreadfromlefttorightandgroupedintotokens,whicharesequencesofcharactersthathaveacollectivemeaning.單詞token保留字reservedword標(biāo)識符identifier(user-definedname)如一個C源程序片斷：inta;a=a+2;詞法分析后可能返回:單詞類型 單詞值保留字 int標(biāo)識符(變量名) a界符 ;標(biāo)識符(變量名) a算符(賦值) =標(biāo)識符(變量名) a算符(加) +整數(shù) 2界符 ；2、語法分析：語法分析程序與自然語言中句子的語法分析類似。語法分析定義了程序的結(jié)構(gòu)元素及其關(guān)系。通常將語法分析的結(jié)果表示為分析樹或語法樹。主要任務(wù)：在詞法分析的基礎(chǔ)上，將單詞分解成各類語法短語。一般語法短語可表示成語法樹。功能：據(jù)源程序的語法規(guī)則把源程序的單詞序列組成語法短語(表示成語法樹).<賦值語句>::=<標(biāo)識符>“:=”<表達(dá)式><表達(dá)式>::=<表達(dá)式>“+”<表達(dá)式>|<表達(dá)式>::=<表達(dá)式>“*”<表達(dá)式><表達(dá)式>::=“(”<表達(dá)式>“)”|<標(biāo)識符>|<整數(shù)>|<實(shí)數(shù)>有關(guān)術(shù)語：syntaxanalysisorparsing--Thepurposeofsyntaxanalysisistodeterminethesourceprogram’sphrasestructure.Thisprocessisalsocalledparsing.Thesourceprogramisparsedtocheckwhetheritconformstothesourcelanguage’ssyntax,andtoconstructasuitablerepresentationofitsphrasestructure.如：id1:=id2+id3*N的分析結(jié)果為：3、語義分析：按照語法樹的層次關(guān)系和先后次序，逐個語句地進(jìn)行語義處理。主要任務(wù)：進(jìn)行類型審查，審查每個算符是否符合語言規(guī)范，不符合時應(yīng)報告錯誤。例： programp(); varrate:real; procedureinitial; … position:=initial+rate*60/*error*//*error*//*warning*/; …有關(guān)術(shù)語：semanticanalysis--Theparsedprogramisfurtheranalyzedtodeterminewhetheritconformstothesourcelanguage’scontextualconstraints:scoperules,typerulese.g.Torelateeachappliedoccurrenceofanidentifierinthesourceprogramtothecorrespondingdeclaration.4、中間代碼生成：語法分析和語義分析之后，有時將源程序變成一種內(nèi)部表示形式，這種內(nèi)部表示形式叫中間代碼，該代碼是一種簡單的記號系統(tǒng)。三元式、四元式等。四元式的形式為：(算符，運(yùn)算對象1，運(yùn)算對象2，結(jié)果)。如下列語句的生成序列： sum:=first+count*10： (inttoreal,10,_,t1) (*, id3,t1,t2) (+,id2,t2,t3) (:=,t3,-,id1)有關(guān)術(shù)語：intermediatecodegeneration--Thisiswheretheintermediaterepresentationofthesourceprogramiscreated.Wewantthisrepresentationtobeeasytogenerate,andeasytotranslateintothetargetprogram.Therepresentationcanhaveavarietyofforms,butacommononeiscalledthree-addresscodeor4-tuplecode.5、代碼優(yōu)化：對中間代碼進(jìn)行變換，使目標(biāo)代碼更為高效。（節(jié)省時間和空間），如：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ù)語：codeoptimization--Intermediatecodeoptimization.Theoptimizeracceptsinputintheintermediaterepresentationandoutputaversionstillintheintermediaterepresentation.Inthisphase,thecompilerattemptstoproducethesmallest,fastestandmostefficientrunningresultbyapplyingvarioustechniques.6、目標(biāo)代碼生成：將中間代碼變換成特定機(jī)器上的絕對指令代碼或可重定位的匯編指令代碼。主要與硬件系統(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、符號表管理：記錄源程序中使用的名字；收集每個名字的各種屬性信息類型、作用域、分配存儲信息。有關(guān)術(shù)語：Symboltableisadatastructurewhichisemployedtoassociateidentifierswiththeirattributes.Anidentifier’sattributeconsistsofinformationrelevanttocontextualanalysis,andisobtainedfromtheidentifier’sdeclaration.8、出錯處理：編譯程序在各個階段應(yīng)診斷和報告源程序中的錯誤，包括詞法錯誤，語法錯誤，語義錯誤；編譯程序應(yīng)報告出錯地點(diǎn)，并給出簡明準(zhǔn)確的提示信息。有關(guān)術(shù)語：errorhandling(errorreportinganderrorrecovery)--Thecompilershouldreportthelocationofeacherror,togetherwithsomeexplanation.Themajorcategoriesofcompile-timeerror:syntaxerror,scopeerror,typeerror.Afterdetectingandreportinganerror,thecompilershouldattempterrorrecovery,meansthatthecompilershouldtrytogetitselfintoastatewhereanalysisofthesourceprogramcancontinueasnormallyaspossible.9、有關(guān)概念：前端和后端：前端后端：源程序中間代碼目標(biāo)代碼僅依賴源程序僅依賴目標(biāo)計算機(jī)遍(PASS)：對輸入文件（源程序或其等價的中間形式）從頭到尾掃視，完成預(yù)定的處理。編譯過程可分為一遍、兩遍或多遍完成，每一遍完成所規(guī)定的任務(wù)。例如，第一遍只完成詞法分析的任務(wù)，第二遍完成語法分析和語義加工并生成中間代碼，第三遍實(shí)現(xiàn)代碼優(yōu)化和目標(biāo)代碼生成。一個編譯程序應(yīng)分成幾遍、如何劃分？和源程序語言結(jié)構(gòu)及目標(biāo)機(jī)器的特征有關(guān)。分多遍完成編譯過程可使整個編譯程序的邏輯結(jié)構(gòu)更清晰，但多遍會增加讀寫中間文件的次數(shù)，從而消耗過多的時間。10、用到編譯原理與技術(shù)的常見軟件工具：（1）語言的結(jié)構(gòu)化編輯器：提供關(guān)鍵字及其匹配的關(guān)鍵字?？蓽p少語法錯誤，加快源程序調(diào)試。（2）語言程序的調(diào)試工具：提供判定程序的算法與功能是否正確。（3）程序格式化工具：使程序呈現(xiàn)清晰的結(jié)構(gòu)（4）語言程序的測試工具：Junit（5）高級語言之間的轉(zhuǎn)換工具：一種高級語言轉(zhuǎn)化成另一種高級語言。11、編譯程序的開發(fā)：編譯程序的開發(fā)通常采用自編譯、交叉編譯、自展、移植等技術(shù)來實(shí)現(xiàn)。目前已經(jīng)出現(xiàn)了一些編譯程序的自動生成系統(tǒng)，如UNIX操作系統(tǒng)下的軟件工具LEX和YACC等。（1）自編譯：用某種高級語言書寫自己的編譯程序稱為自編譯。例如,假定A機(jī)器上已有一個PASCAL語言編譯程序,則可用PASCAL語言編寫一個功能更強(qiáng)的PASCAL語言編譯程序，然后借助于原有的編譯程序?qū)π戮帉懙腜ASCAL編譯程序進(jìn)行編譯,從而得到一個能在A機(jī)器上運(yùn)行的功能更強(qiáng)的PASCAL編譯程序。（2）交叉編譯：用A機(jī)器上的編譯程序來產(chǎn)生可在B機(jī)器上運(yùn)行的目標(biāo)代碼稱為交叉編譯。例如,若A機(jī)器上已有C語言編譯程序,則可用A機(jī)器中的C語言書寫一個編譯程序,該編譯程序的源程序是C語言程序,而產(chǎn)生的目標(biāo)程序則是基于B機(jī)器的,即產(chǎn)生在B機(jī)器上執(zhí)行的低級語言程序。上述兩種方法假定已有一個編譯程序,若沒有,則可采用自展或移植法。（3）自展：首先確定一個非常簡單的核心語言L0，然后用機(jī)器語言或匯編語言書寫出其編譯程序T0；再把語言L0擴(kuò)充到L1，L0L1，并用L0編寫L1的編譯程序T1(自編譯)；然后再把語言L1擴(kuò)充為L2，L1L2，并用L1編寫L2的編譯程序T2；……這樣不斷擴(kuò)展，直到完成所要求的編譯程序?yàn)橹?。?）移植：移植是指A機(jī)器上的某種高級語言的編譯程序稍加改動后能在B機(jī)器上運(yùn)行。一個程序若能較容易地從A機(jī)器移到B機(jī)器上運(yùn)行,則稱該程序是可移植的。用系統(tǒng)已有的程序設(shè)計語言來書寫編譯程序雖縮短了開發(fā)周期,但實(shí)現(xiàn)的自動化程序不高。編譯程序示例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)一、說明：1、教學(xué)目的與要求：以PL/0為實(shí)例（編譯程序示例2）,了解語言的描述、編譯程序的結(jié)構(gòu)以及工作流程、解釋程序。2、主要內(nèi)容：PL/0語言、PL/0編譯程序、PL/0解釋程序。3、教學(xué)重點(diǎn)：編譯程序的結(jié)構(gòu)以及每一階段的任務(wù)。4、教學(xué)難點(diǎn)：源代碼分析。二、教學(xué)內(nèi)容PL/0語言描述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表示<程序>::=<分程序><分程序>::=[<常量說明>][<變量說明>][<過程說明>]<語句><常量說明>::=const<常量定義>{,<常量定義>}<常量定義>::=<標(biāo)識符>=<無符號整數(shù)><標(biāo)識符>::=<字母>|{<字母>|<數(shù)字>}<字母>::=a|b|c...x|y|z<無符號整數(shù)>::=<數(shù)字>{<數(shù)字>}<數(shù)字>::=0|1|2|3|4|5|6|7|8|9<變量說明>::=var<標(biāo)識符>{,<標(biāo)識符>}<過程說明>::=<過程首部><分程序>{,<過程說明>}<過程首部>::=procedure<標(biāo)識符>;<語句>::=<賦值語句>|<條件語句>|<當(dāng)循環(huán)語句>|<過程調(diào)用語句>|<復(fù)合語句>|<讀語句> |<寫語句>|<空><賦值語句>::=<標(biāo)識符>:=<表達(dá)式><表達(dá)式>::=[+|-]<項(xiàng){<加法運(yùn)算符><項(xiàng)>}<項(xiàng)>::=<因子>{<乘法運(yùn)算符><因子>}<因子>::=<標(biāo)識符>|<無符號整數(shù)>|'('<表達(dá)式>')'<加法運(yùn)算符>::=+|-<乘法運(yùn)算符>::=*|/<條件語句>::=if<條件>then<語句><條件>::=<表達(dá)式><關(guān)系運(yùn)算符><表達(dá)式>|odd<表達(dá)式><關(guān)系運(yùn)算符>::=<|<=|>|>=|<>|=<當(dāng)循環(huán)語句>::=while<條件>do<語句><過程調(diào)用語句>::=call<標(biāo)識符><復(fù)合語句>::=begin<語句>{;<語句>}<讀語句>::=read'('<標(biāo)識符>{,<標(biāo)識符>}')'<寫語句>::=write'('<表達(dá)式>{,<表達(dá)式>}')'3、單詞的種類基本字：也可稱為保留字或關(guān)鍵字，如BEGIN，END，IF，THEN等。運(yùn)算符：如：+、-、*、／、∶=、#、＞=、＜=等。標(biāo)識符：用戶定義的變量名、常數(shù)名、過程名。常數(shù)：如：10，25，100等整數(shù)。界符：如：‘;’、‘(’、‘)’等。

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

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

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