编译原理教案

PAGEPAGE1编译原理教案说明：一、参考书：1、陈意云、张昱：《编译原理》，高等教育出版社，2003年。2、陈意云、张昱：《编译原理习题精选》，中国科技大学出版社，2003年。3、吕映芝、张素琴、蒋维杜：《编译原理》，清华大学出版社，1998年第二版。4、王生原、吕映芝、张素琴：《编译原理课程辅导》，清华大学出版社，2007年。5、伍春香：《编译原理习题与解析》，清华大学出版社，2001年。6、AndrewW.Appel：《现代编译原理—C语言描述》，人民邮电出版社，2005年。7、NoamNison等：《计算机系统要素》，电子工业出版社，2007年。8、RandallHyde：《编程卓越之道（第二卷）》，电子工业出版社，2007年。二、教学目的：通过学习形式语言与自动机理论、词法分析、语法分析、语义分析、代码优化和生成等内容使学生掌握构造编译程序的基本原理和基本方法，并通过上机实习使学生进一步掌握开发应用程序的基本方法，为深入理解计算机系统、程序设计语言与开发大型应用程序打下良好的基础。三、教学时数：课堂教学51学时，上机实验30学时。四、授课内容：第一章编译程序概述第二章PL/0编译程序的实现第三章文法和语言第四章词法分析第五章自顶向下语法分析方法第六章自底向上优先分析方法第七章LR分析方法第八章语法制导翻译和中间代码生成第九章符号表第一○章目标程序运行时的存储组织第一一章代码优化第一二章代码生成第一章概述一、说明：1、教学目的与要求：了解编译程序的概念、结构以及工作流程。2、主要内容：什么是编译程序、编译过程概述、编译程序的结构、编译阶段的组合、编译技术和软件工具以及实例分析。3、教学重点：编译程序的结构以及每一阶段的任务。4、教学难点：理解编译程序各模块的判错功能、编译方式和解释方式执行速度上的不同。二、教学内容第一节编译程序1、机器语言：直接用计算机能够识别的二进制代码指令来编写程序的语言。由二进制的指令代码组成。1+3表示为100000010000000100000011。是最底层的计算机语言，不需要翻译就可以直接被计算机硬件识别。对应不同的计算机硬件有不同的机器语言。特点：执行速度快，但编写程序的难度大，修改、调试不方便，直观性差，不易移植。2、汇编语言：又称为符号语言。与机器语言一一对应，采用能帮助记忆的英文缩写符号（指令助记符）来代替机器语言指令中的操作码，用地址符号来代替地址码。用指令助记符及地址符号书写的指令称为汇编指令，用汇编指令编写的程序称为汇编语言源程序。将X、Y中的内容相加表示为ADDXY。机器不能直接识别汇编语言程序，必须把它翻译为机器语言程序才能执行。特点：比机器语言直观，容易理解和记忆，比高级语言的执行效率高，但通用性和移植性较差。3、高级语言：与具体的计算机硬件无关，是面向问题的程序设计语言，其表达方式接近于自然语言和数学语言，易于人们接受和掌握。采用类似于数学公式的书写方式：x=1+3。特点：独立于具体的计算机硬件，程序的编制和调试方便，通用性和可移植性好。在计算机执行之前，需要通过编译程序翻译成目标语言程序，或需要通过解释程序边解释，边执行。时间与空间效率比较低。目前比较流行的高级语言有：C++,VisualBasic,Java，Pascal，4、什么是编译程序：编译程序把高级语言程序翻译成等价的低级语言程序：源程序编译程序目标程序。编译程序是现代计算机系统的基本组成部分。从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。高级语言源程序的执行通常分两个阶段:源程序源程序(高级语言)编译程序计算机目标程序(机器语言)编译阶段初始数据目标程序计算机运行系统计算结果运行阶段若编译生成的目标程序是汇编语言形式,则在编译与运行阶段之间还要添加一个汇编阶段。高级语言源程序也可通过解释程序来执行,如BASIC。解释程序与编译程序的主要区别是：编译程序将整个源程序全部翻译成目标程序后再执行该目标程序；解释程序则逐条读出源程序中的语句并解释执行，在解释程序执行过程中并不产生目标程序。源程序源程序(高级语言)初始数据解释程序计算机计算结果第二节编译程序结构编译程序的工作过程是指从输入源程序开始到输出目标程序为止的整个过程。编译程序内部包括了许多步骤或称为阶段，它们执行不同的逻辑操作。将这些阶段设想为编译程序中一个个单独的片断是很有用的，尽管在应用中它们是经常组合在一起的，但它们确实是作为单独的代码操作来编写的。编译工作的基本过程是：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等6个阶段。每个阶段都有表格管理和出错处理部分。1、词法分析：像翻译英文句子一样，先要分析单词，弄清各单词的意义和句中的作用，才能对句子进行翻译。主要任务：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。单词包括：保留字、标识符、运算符、分界符等。例：position:=initial+rate*60;单词类型 单词值标识符(id1) position算符(赋值) :=标识符(id2) initial算符(加) +标识符(id3) rate算符(乘) *整数 60界符 ；有关术语：lexicalanalysisorscanning--Thestreamofcharactersmakingupasourceprogramisreadfromlefttorightandgroupedintotokens,whicharesequencesofcharactersthathaveacollectivemeaning.单词token保留字reservedword标识符identifier(user-definedname)如一个C源程序片断：inta;a=a+2;词法分析后可能返回:单词类型 单词值保留字 int标识符(变量名) a界符 ;标识符(变量名) a算符(赋值) =标识符(变量名) a算符(加) +整数 2界符 ；2、语法分析：语法分析程序与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树或语法树。主要任务：在词法分析的基础上，将单词分解成各类语法短语。一般语法短语可表示成语法树。功能：据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树).<赋值语句>::=<标识符>“:=”<表达式><表达式>::=<表达式>“+”<表达式>|<表达式>::=<表达式>“*”<表达式><表达式>::=“(”<表达式>“)”|<标识符>|<整数>|<实数>有关术语：syntaxanalysisorparsing--Thepurposeofsyntaxanalysisistodeterminethesourceprogram’sphrasestructure.Thisprocessisalsocalledparsing.Thesourceprogramisparsedtocheckwhetheritconformstothesourcelanguage’ssyntax,andtoconstructasuitablerepresentationofitsphrasestructure.如：id1:=id2+id3*N的分析结果为：3、语义分析：按照语法树的层次关系和先后次序，逐个语句地进行语义处理。主要任务：进行类型审查，审查每个算符是否符合语言规范，不符合时应报告错误。例： programp(); varrate:real; procedureinitial; … position:=initial+rate*60/*error*//*error*//*warning*/; …有关术语：semanticanalysis--Theparsedprogramisfurtheranalyzedtodeterminewhetheritconformstothesourcelanguage’scontextualconstraints:scoperules,typerulese.g.Torelateeachappliedoccurrenceofanidentifierinthesourceprogramtothecorrespondingdeclaration.4、中间代码生成：语法分析和语义分析之后，有时将源程序变成一种内部表示形式，这种内部表示形式叫中间代码，该代码是一种简单的记号系统。三元式、四元式等。四元式的形式为：(算符，运算对象1，运算对象2，结果)。如下列语句的生成序列： sum:=first+count*10： (inttoreal,10,_,t1) (*, id3,t1,t2) (+,id2,t2,t3) (:=,t3,-,id1)有关术语：intermediatecodegeneration--Thisiswheretheintermediaterepresentationofthesourceprogramiscreated.Wewantthisrepresentationtobeeasytogenerate,andeasytotranslateintothetargetprogram.Therepresentationcanhaveavarietyofforms,butacommononeiscalledthree-addresscodeor4-tuplecode.5、代码优化：对中间代码进行变换，使目标代码更为高效。（节省时间和空间），如：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)有关术语：codeoptimization--Intermediatecodeoptimization.Theoptimizeracceptsinputintheintermediaterepresentationandoutputaversionstillintheintermediaterepresentation.Inthisphase,thecompilerattemptstoproducethesmallest,fastestandmostefficientrunningresultbyapplyingvarioustechniques.6、目标代码生成：将中间代码变换成特定机器上的绝对指令代码或可重定位的汇编指令代码。主要与硬件系统结构和指令含义有关。如：(*,id3,60.0,t1)(+,id2,t1,id1)MOV id3,R2MUL #60.0,R2MOV id2,R1ADD R2,R1MOV R1,id17、符号表管理：记录源程序中使用的名字；收集每个名字的各种属性信息类型、作用域、分配存储信息。有关术语：Symboltableisadatastructurewhichisemployedtoassociateidentifierswiththeirattributes.Anidentifier’sattributeconsistsofinformationrelevanttocontextualanalysis,andisobtainedfromtheidentifier’sdeclaration.8、出错处理：编译程序在各个阶段应诊断和报告源程序中的错误，包括词法错误，语法错误，语义错误；编译程序应报告出错地点，并给出简明准确的提示信息。有关术语：errorhandling(errorreportinganderrorrecovery)--Thecompilershouldreportthelocationofeacherror,togetherwithsomeexplanation.Themajorcategoriesofcompile-timeerror:syntaxerror,scopeerror,typeerror.Afterdetectingandreportinganerror,thecompilershouldattempterrorrecovery,meansthatthecompilershouldtrytogetitselfintoastatewhereanalysisofthesourceprogramcancontinueasnormallyaspossible.9、有关概念：前端和后端：前端后端：源程序中间代码目标代码仅依赖源程序仅依赖目标计算机遍(PASS)：对输入文件（源程序或其等价的中间形式）从头到尾扫视，完成预定的处理。编译过程可分为一遍、两遍或多遍完成，每一遍完成所规定的任务。例如，第一遍只完成词法分析的任务，第二遍完成语法分析和语义加工并生成中间代码，第三遍实现代码优化和目标代码生成。一个编译程序应分成几遍、如何划分？和源程序语言结构及目标机器的特征有关。分多遍完成编译过程可使整个编译程序的逻辑结构更清晰，但多遍会增加读写中间文件的次数，从而消耗过多的时间。10、用到编译原理与技术的常见软件工具：（1）语言的结构化编辑器：提供关键字及其匹配的关键字。可减少语法错误，加快源程序调试。（2）语言程序的调试工具：提供判定程序的算法与功能是否正确。（3）程序格式化工具：使程序呈现清晰的结构（4）语言程序的测试工具：Junit（5）高级语言之间的转换工具：一种高级语言转化成另一种高级语言。11、编译程序的开发：编译程序的开发通常采用自编译、交叉编译、自展、移植等技术来实现。目前已经出现了一些编译程序的自动生成系统，如UNIX操作系统下的软件工具LEX和YACC等。（1）自编译：用某种高级语言书写自己的编译程序称为自编译。例如,假定A机器上已有一个PASCAL语言编译程序,则可用PASCAL语言编写一个功能更强的PASCAL语言编译程序，然后借助于原有的编译程序对新编写的PASCAL编译程序进行编译,从而得到一个能在A机器上运行的功能更强的PASCAL编译程序。（2）交叉编译：用A机器上的编译程序来产生可在B机器上运行的目标代码称为交叉编译。例如,若A机器上已有C语言编译程序,则可用A机器中的C语言书写一个编译程序,该编译程序的源程序是C语言程序,而产生的目标程序则是基于B机器的,即产生在B机器上执行的低级语言程序。上述两种方法假定已有一个编译程序,若没有,则可采用自展或移植法。（3）自展：首先确定一个非常简单的核心语言L0，然后用机器语言或汇编语言书写出其编译程序T0；再把语言L0扩充到L1，L0L1，并用L0编写L1的编译程序T1(自编译)；然后再把语言L1扩充为L2，L1L2，并用L1编写L2的编译程序T2；……这样不断扩展，直到完成所要求的编译程序为止。（4）移植：移植是指A机器上的某种高级语言的编译程序稍加改动后能在B机器上运行。一个程序若能较容易地从A机器移到B机器上运行,则称该程序是可移植的。用系统已有的程序设计语言来书写编译程序虽缩短了开发周期,但实现的自动化程序不高。编译程序示例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编译程序的实现一、说明：1、教学目的与要求：以PL/0为实例（编译程序示例2）,了解语言的描述、编译程序的结构以及工作流程、解释程序。2、主要内容：PL/0语言、PL/0编译程序、PL/0解释程序。3、教学重点：编译程序的结构以及每一阶段的任务。4、教学难点：源代码分析。二、教学内容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<常量定义>{,<常量定义>}<常量定义>::=<标识符>=<无符号整数><标识符>::=<字母>|{<字母>|<数字>}<字母>::=a|b|c...x|y|z<无符号整数>::=<数字>{<数字>}<数字>::=0|1|2|3|4|5|6|7|8|9<变量说明>::=var<标识符>{,<标识符>}<过程说明>::=<过程首部><分程序>{,<过程说明>}<过程首部>::=procedure<标识符>;<语句>::=<赋值语句>|<条件语句>|<当循环语句>|<过程调用语句>|<复合语句>|<读语句> |<写语句>|<空><赋值语句>::=<标识符>:=<表达式><表达式>::=[+|-]<项{<加法运算符><项>}<项>::=<因子>{<乘法运算符><因子>}<因子>::=<标识符>|<无符号整数>|'('<表达式>')'<加法运算符>::=+|-<乘法运算符>::=*|/<条件语句>::=if<条件>then<语句><条件>::=<表达式><关系运算符><表达式>|odd<表达式><关系运算符>::=<|<=|>|>=|<>|=<当循环语句>::=while<条件>do<语句><过程调用语句>::=call<标识符><复合语句>::=begin<语句>{;<语句>}<读语句>::=read'('<标识符>{,<标识符>}')'<写语句>::=write'('<表达式>{,<表达式>}')'3、单词的种类基本字：也可称为保留字或关键字，如BEGIN，END，IF，THEN等。运算符：如：+、-、*、／、∶=、#、＞=、＜=等。标识符：用户定义的变量名、常数名、过程名。常数：如：10，25，100等整数。界符：如：‘;’、‘(’、‘)’等。

基本字、运算符、界符称为语言固有的单词。标识符、常数称为用户定义的单词。对语言固有的单词只给出类别存放在SYM中，而对用户定义的单词既给类别又给值，其类别放在SYM中，值放在ID或NUM中4、变量作用域规则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代码指令的结构PL/0编译程序所产生的目标代码是一个假想栈式计算机的汇编语言，可称为类PCODE指令代码，它不依赖任何具体计算机，其格式如下：aalf其中f代表功能码，l表示层次差，也就是变量或过程被引用的分程序与说明该变量或过程的分程序之间的层次差。a的含意对不同的指令有所区别，对存取指令表示位移量，而对其它的指令则分别有不同的含义。6、类pcode指令LIT：将常量值取到运行栈顶。a域为常数值。LOD：将变量放到栈顶。a域为变量在所说明层中的相对位置,l为调用层与说明层的层差值。STO：将栈顶的内容送入某变量单元中。a,l域的含意同LOD指令。CAL：调用过程的指令。a为被调用过程的目标程序入口地址，l为层差。INT：为被调用的过程(或主程序)在运行栈中开辟数据区。a域为开辟的单元个数。JMP：无条件转移指令，a为转向地址。JPC：条件转移指令，当栈顶的布尔值为0时，转向a域的地址，否则顺序执行。LIT：将常量值取到运行栈顶。a域为常数值。LOD：将变量放到栈顶。a域为变量在所说明层中的相对位置,l为调用层与说明层的层差值。STO：将栈顶的内容送入某变量单元中。a,l域的含意同LOD指令。CAL：调用过程的指令。a为被调用过程的目标程序入口地址，l为层差。INT：为被调用的过程(或主程序)在运行栈中开辟数据区。a域为开辟的单元个数。JMP：无条件转移指令，a为转向地址。JPC：条件转移指令，当栈顶的布尔值为0时，转向a域的地址，否则顺序执行。OPR：关系运算和算术运算指令等。具体操作由a域值给出。OPR00：过程调用结束后,返回调用点并退栈OPR01：栈顶元素取反OPR02：次栈顶与栈顶相加，退两个栈元素， 结果值进栈OPR03：次栈顶减去栈顶，退两个栈元素， 结果值进栈OPR04：次栈顶乘以栈顶，退两个栈元素， 结果值进栈OPR05：次栈顶除以栈顶，退两个栈元素， 结果值进栈OPR06：栈顶元素的奇偶判断，结果值在栈顶OPR08：次栈顶与栈顶是否相等，退两个栈元素，结果进栈OPR09：次栈顶与栈顶是否不等，退两个栈元素，结果进栈OPR010：次栈顶是否小于栈顶，并退栈，结果值进栈OPR011：次栈顶是否大于等于栈顶，退两个栈元素，结果进栈OPR012：次栈顶是否大于栈顶，退两个栈元素，结果进栈OPR013：次栈顶是否小于等于栈顶，退两个栈元素，结果进栈OPR014：栈顶值输出至屏幕OPR015：屏幕输出换行OPR016：从命令行读入一个输入置于栈顶7、PL/0语言的出错信息表1：常数说明中的“=”写成“∶=”。2：常数说明中的“=”后应是数字。3：常数说明中的标识符后应是“=”。4：const,var,procedure后应为标识符。5：漏掉了‘，’或‘；’。6：过程说明后的符号不正确(应是语句开始符，或过程定义符)。7：应是语句开始符。8：程序体内语句部分的后跟符不正确。9：程序结尾丢了句号‘.’。10：语句之间漏了‘；’。11：标识符未说明。12：赋值语句中，赋值号左部标识符属性应是变量。13：赋值语句左部标识符后应是赋值号‘∶=’。14：call后应为标识符。15：call后标识符属性应为过程。16：条件语句中丢了‘then’。17：丢了‘end“或’；‘。18：while型循环语句中丢了‘do’。19：语句后的符号不正确。20：应为关系运算符。21：表达式内标识符属性不能是过程。22：表达式中漏掉右括号‘)’。23：因子后的非法符号。24：表达式的开始符不能是此符号。31：数越界。32：read语句括号中的标识符不是变量。8、PL/0语言的实现9、程序的数据栈：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、程序的编译和运行

第三章文法和语言一、说明：1、教学目的与要求：为语言的语法描述寻求工具。要求熟练掌握形式语言中基本概念及知识。2、主要内容：文法的直观概念、符号和符号串、文法与语言的形式定义、文法的分类、上下文无关文法及其语法树、句型的分析、有关文法实用中的一些说明。3、教学重点：与编译技术密切相关的一些术语和概念。4、教学难点：句型的分析。二、教学内容第一节文法的概念1、语法：是一组规则，定义符号如何排列，排列与符号含义无关。2、语义：研究语法的含义3、语言=语法+语义例：<句子>∷=<主语><谓语><主语>∷=<代词>|<名词><代词>∷=我|你|他<名词>∷=王明|大学生|教师|英语<谓语>∷=<动词><直接宾语><动词>∷=是|学习<直接宾语〉∷=<代词>|<名词>写出以下语言的文法“你是大学生” 对“我是教师” 对“我大学生是” 错“我学习大学生” 对<句子><主语><谓语><代词><谓语>我<谓语>我<动词><直接宾语>我是<名词>第二节符号和符号串PASCAL等程序设计语言是由所有C、PASCAL程序组成的集合。程序是由一些基本符号组成的。从字面上看，每个程序都是一个基本符号串。设有一个基本符号集，C、PASCAL等程序设计语言可看成是在这个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。母表—符号集：是字母的有穷非空集合。汉语字母表包括：汉字、数字、标点符号等Pascal语言字母表包括：字母、数字以及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。空符号串：用表示长度为0符号串。符号串x,都有x=x=x。符号串的运算：符号串的头和尾、固有头和固有尾、连接、方幂、集合、闭包、正闭包。(1)符号串的头和尾：若z=xy,则x是z的头，y是z的尾。例：设z=abc,z的头是：，a，ab，abcz的尾是：，c，bc，abc（2）符号串的固有头和固有尾：若z=xy符号串，x非空，则y是固有尾；若y非空，则x是固有头。例：设z=abc，z的固有头是：、、ab，z的固有尾是：、c、bc。（3）符号串的连接：设x，y是符号串，连接xy是y符号写在x符号后。例：x=ab,y=MN，则xy=abMN。（4）符号串的方幂：设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∪∑+，∑+＝∑∑*＝∑*∑。第三节文法和语言的定义1、规则（重写规则、产生式、生成式）形如→或::=， 是字母表V的正闭包V+的一个符号；是字母表V的闭包V*的一个符号；称规则的左部，称规则的右部。2、文法的定义（1）文法G定义为四元组（VN，VT，P，S）其中： VN——非终结符号集VT——终结符号集 P——产生式（规则）S——开始符号或称作识别号，它是一个非终结符，至少要在一条规则中作为左部出现。规定：（1）VN，VT，P是有穷非空集合；（2）VN∩VT＝（不含公共元素）例1：文法G=(VN,VT,P,S)，其中VN={S}，VT={0，1}，P={S→0S1，S→01}。非终结符集中只含一个元素S；终结符集由两个元素0和1组成；有两条产生式；开始符号是S。问：从终结符可推出哪些符号串？ S＝{01，0011，000111，00001111…}例2：文法G=(VN,VT,P,S)，其中VN={标识符,字母,数字}，VT={a,b,c,…,x,y,z,0,1,…,9}，P={<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→a|b|c…z<数字>→1|2|3…9}，S=<标识符>例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一般约定，第一条产生式的左部是识别符号；用尖括号括起来的是非终结符号，不用尖括号括起来的是终结符号，或者用大写字母表示非终结符号，小写字母表示终结符号。3、直接推导的定义：→是文法G=VN,VT，P，S）的规则，和是V*中的任意符号，若有符号串V，W满足：V=，W＝，则V是直接产生W或W是V的直接推导或W直接规约到V，记作VW。例4：G:S→0S1，S→01，V＝0S1，W=0011，W是否V的直接推导？V=S，W＝0S1，W是否V的直接推导？V=0S1，W=00S11，W是否V的直接推导？若存在直接推导的序列：V=W0W1W2…Wn=W(n>0)，则称V推导W（或W规约到V），记V+W。若有VW，或V=W，则记作V*W。如：V＝0S100S11000S11100001111＝W记作：0S1+00001111或0S1*000011114、句型的定义：设G[S]是文法，如果符号串x是从识别符号（开始符号）推导出来的（即Sx）,则称x是文法G[S]的句型。若x仅由终结符号组成（Sx，xVT*），则称x为G[S]的句子。例：S，0S1，000111都是文法G的句型，000111是G的句子。注意：句子一定是句型，句型不一定是句子。5、语言的定义：文法G产生的语言定义为G产生的句子的集合{x|Sx，S为文法开始符号，xVT*}，该集合为语言，用L(G)表示。从定义可知：x是句型且x是文法G的句子。例：设G:S→0S1|01，G定义的语言是什么？L(G)＝｛0n1nn1｝。例：设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第四节文法的类型语言学家Chomsky把文法分成以下四种类型：其中，正规文法一定也是上下文无关文法1、0型文法：设G=(VN,VT,P,S)，如果它的每一个产生式满足：(VN∪VT)*且至少包含一个非终结符，(VN∪VT)*，则G是0型文法。2、1型文法：设G=(VN,VT,P,S)，如果它的每一个产生式满足：||≥||，仅仅S除外，则文法G是1型文法。1型文法又称为上下文有关文法，它的每一个产生式也可描述为：1A212,其中1、2及都在(VN∪VT)*中,A在VN中。只有A出现在12的上下文中，才允许用取代A。3、2型文法：设G=(VN,VT,P,S)，如果它的每一个产生式满足：是一非终结符，(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型文法（正规文法）：设G=(VN,VT,P,S)，若P中的每一个产生式都是A→aB或A→a，A,B都是非终结符，a是终结符，则G是正规文法。例：下列文法是正规文法S→0|0A|1B（2）A→0S|0A|1B（3）B→0|1|1B5、对比：0型文法：左部至少含有一个非终结符1型文法：左部比右部短（不长于右部）2型文法：左部只有一个（非终结符）3型文法：右部只有一个或两个（a或aB）例：通过分别给出下列语言的文法来证明这些语言是上下无关的：(1)L1={anb2ncm|n,m≥0} (2)L2={anbmc2m|n,m≥0}(1)S→ABA→|aAbbB→|cB (2)S→ABA→|aAB→|bBcc第五节上下文无关文法及其语法树语法树（推导树）的定义：给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树，须满足条件：（1）每个结点都有一个标记，此标记是V的一个符号。（2）根的标记是S。（3）若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在VN中。（4）如果结点n的直接子孙，从左到右的次序是结点n1,n2,…,nK，其标记分别为A1,A2,…,AK，那么 AA1A2…AK一定是P中的一个产生式。例1、给定下列文法：(1)SaAS(2)ASbA(3)ASS(4)Sa(5)Aba请构造aabbaa的语法树。SaASaSbASaSbAaaabAaaabbaa语法树的理解：语法树表示了在推导过程中用到什么样的产生式和用到哪些非终结符，并没有表明采用的顺序。它只表示推导的结果，不表示推导的过程。最左推导（或最右推导）：若在推导中的任何一步β（、β是句型），都是对中的最左（最右）非终结符进行替换，则称为最左（最右）推导。最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。例2、给定下列文法：(1)SaAS(2)ASbA(3)ASS(4)Sa(5)Aba请构造aabbaa的语法树1）每次替换最右边非终结符 SaASaAaaSbAaaSbbaaaabbaa2）每次替换最左边非终结符 SaASaSbASaabASaabbaSaabbaa3）无固定的推导方向 SaASaSbASaSbAaaabAaaabbaa一棵语法树表示了一个句型的种种可能的不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?文法的二义性的定义：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的；若一个文法中存在某个句子，它有两个不同的最左（最右）推导，则这个文法是二义的。如果一个语言的每一个文法都是二义的，那么这个语言是二义的例3、证明下列文法是二义的：(1)Ei(2)EE+E(3)EE*E(4)E(E)。推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i产生两个不同的语法树：如果规定“*”和“+”的优先性，并服从左结合，上式就可以构出无二义性。（1）ET|E+T （2）TF|T*F （3）F(E)|i例4、证明下列文法是二义的：(1)EEOF|(E)|v|d(2)O+|*第六节句型的分析1、判断给定的符号串是否某文法的句子。例如：给定C语言的文法规则，对于一个源程序，要求编译系统判断该源程序是否合法。句型分析是识别一个符号串是否为某文法的句型，是整个推导的构造过程。（为一个符号串构造一个语法树/推导树）。即识别输入符号串是否为语法上是否正确的过程。分析程序（识别程序）是完成句型分析的程序。分析算法：（1）自上而下分析法：从文法开始符号出发，反复使用规则，寻找匹配符号串（推导）（2）自下而上分析法：从输入符号开始，逐步进行“规约”，直至文法的开始符号（归约）例1、给定下列文法：（1）ScAd （2）Aab （3）Aa输入串cabd是否为该文法的句子？自上而下分析法自下而上分析法2、句型分析的2个问题(讨论)：（1）在自上而下分析中，被代换的最左部非终结符号在右部有多个终结符时，如何确定？假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？采取回溯法（在第5章介绍）（2）自下而上的分析中，如何确定可归约串呢？寻找句柄。3、短语：设有文法G，S是文法的开始符号，设是G的一个句型（S*），若有S*A且A+，则称是句型关于非终结符A的短语。例2、ab、bb、Ab、aAcBe、abbcde是短语吗？ab不是短语；bb、Ab是短语；aAcBe是短语；abbcde是短语 六、句型的分析3、直接短语：如果：S+、S*A、A，则称是句型关于规则A的直接短语。4、句柄：一个句型的最左直接短语称为该句型的句柄。规范推导：最右推导。规范归约：最左归约，即对句柄进行的归约。由规范归约构成的分析树和推导树完全相同。例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的相对非终结符F的短语，是相对规则Fi的直接短语。（2）E*i1*F+i3且Fi2，则称i2是句型i1*i2+i3的相对非终结符F的短语，是相对规则Fi的直接短语。（3）E*i1*i2+F且Fi3，则称i3是句型i1*i2+i3的相对非终结符F的短语，是相对规则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为什么不是句柄？解题方法：画出句型对应的语法树；以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是该非终结符的一个短语；如果子树只有两代，则该短语就是直接短语；最左的两代子树的所有末端结点从左到右排列就是该句型的句柄第七节有关文法的一些限制文法中不含有有害规则和多余规则，有害规则：形如U→U的产生式。会引起文法的二义性。多余规则：指文法中任何句子的推导都不会用到的规则。多余规则也可表示为：文法中不含有不可到达和不可终止的非终结符，分以下两种情况：（1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。（2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。例1、（1）SBe（2）BCe|Af（3）AAe|e（4）CCf（5）Df文法中某些非终结符不在任何规则的右部出现；文法中某些非终结符，由它不能推出终结符号串。D为不可到达，C为不可终止。产生式2），6），7）为多余规则应去掉。本章小结本章出现的概念较多,应重点理解文法,推导,句型句子及语言的定义等概念.语法分析有关内容在后面章节会详细讨论.文法作为程序语言的语法的描述工具,它用规则只能陈述的是:语言的所有句子以什麽样的符号串能出现.请记住文法和语言的形式定义中的“形式”的含义—只涉及语言的语法不涉及语言的语义.本章内容是形式语言理论的一部分.形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。

第四章词法分析一、说明：1、教学目的与要求：熟练掌握正规式与有穷自动机和正规文法与有穷自动机关系。掌握词法分析程序的设计原理与构造方法。2、主要内容：词法分析程序的设计、单词的描述工具、有穷自动机、正规式和有穷自动机的等价性、正规文法和有穷自动机间的转换、词法分析程序的自动构造工具。自动识别单词的方法：（1）单词结构的描述--正规文法和正规式；（2）把正规式转换为一个NFA；（3）把NFA转换为相应的DFA；（4）基于DFA构造词法分析程序。3、教学重点：单词的描述技术；正规文法和正规式；单词的识别机制：确定有穷自动机、不确定有穷自动机；词法分析程序的自动构造。4、教学难点：正规式等价变换为NFA、NFA等价变换为正规式、DFA的最小化。二、教学内容第一节扫描器的设计方法1、词法分析程序也叫词法分析器或扫描器。其功能是输入源程序,输出单词符号。单词符号：是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。输出形式为二元组。主要任务：从左至右逐个字符地对源程序进行扫描,产生一个个单词符号,把字符串形式的源程序改造成为单词符号串形式的中间程序。其他任务：滤掉空格、跳过注释、追踪换行标志、宏展开、查填符号表、发现并定位词法错误、……。单词符号分类：单词符号是程序语言的基本语法单位。通常分为五种：(1)保留字： 如if、while(2)标识符： 标记常量、变量、函数等的名字(3)常数： 如实型0.618、布尔型TRUE(4)运算符： 如+、-、*、/、>、<(5)界符： 分界符，如,、;、(、)注意：保留字、运算符和界符的个数确定，标识符和常数的个数不确定。单词符号的输出形式：(单词种别,单词自身的值)单词种别:单词种别表示单词的种类。一个语言的单词符号如何分类、分为几类、如何编码主要取决于处理上的方便。通常，每种单词对应一个整数码。保留字：可全体视为一种，也可一字一种；标识符：统归为一种；常数：统归为一种,或按整、实、布尔等再分；运算符和界符：一符一种，或统归为一种。单词自身的值：单词自身的值是编译其它阶段需要的信息。对于单词符号,若一个种别只含一个单词,则其种别编码就代表它自身的值。若一个种别含多个单词,则除种别编码外,还应给出单词自身的值,以便把同一种类的单词区别开来。注意：标识符自身的值是标识符自身的字符串,常数自身的值是常数本身的二进制数值。此外,也可用指向某类表格中一特定项目的指针来区分同类中的不同单词。例如,对于标识符,可用它在符号表的入口指针作为自身的值;常数可用它在常数表的入口指针作为自身的值。如：while (WHILE, _)( (SLP, _)* (FETCH， _)pointer (IDN， 符号表入口指针)!= (RELOP， NE)'\0' (CONST， 0)) (SRP， _){ (LP， _)pointer (IDN， 符号表入口指针)++ (INC， _); (SEMI， _)} (RP， _)词法分析和语法分析的接口关系：主程序、子程序。词法分析从语法分析中独立出来的原因：简化设计；改进编译效率；增加编译系统的可移植性主程序：词法分析是编译过程中的一个阶段，在语法分析前进行。将词法分析作为独立的一遍来完成。子程序：词法分析和语法分析结合在一起作为一遍，进行语法分析时,每当需要一个单词时便调用词法分析程序。第二节单词的描述工具某种程序设计语言中的所有单词构成一种语言。该语言的语法都能用正规文法表示。正规文法是描述单词的一种工具。正规文法：文法G=(VN,VT,P,S)，P中每一规则有A→aB或A→a的形式，A,BVN，aVT*，称G(S)是正规文法。正规集：由正规文法产生的语言L(G)。正规式（正则表达式）：表示正规集的工具，也是用以描述单词符号的方便工具。正规式与正规集：设字母表为Σ，辅助字母表Σ'={,,|,·,*,(,)}；(1)和都是Σ上的正规式，表示的正规集分别为{}和；(2)任何aΣ,a是Σ上的一个正规式，表示的正规集为{a}；(3)假定e1和e2都是Σ上的正规式，它们所表示的正规集分别为L(e1)和L(e2),则(e1),e1|e2,e1·e2和e1*也都是正规式，所表示的正规集分别为:L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))*。仅由有限次使用上述三步骤定义的表达式才是Σ上的正规式，仅由这些正规式所表示的集合才是Σ上的正规集。说明：（1）Σ上的一个字指的是由Σ中字符构成的一个有穷序列;不包含任何字符的序列称为空字。Σ*表示Σ上所有字的全体,包括空字。例如,若Σ={a,b}，则Σ={,a,b,aa,ab,ba,bb,aaa,…}（2）Ф表示不含任何元素的空集{}。注意：、{}和{}的区别：表示不包含任何字符的序列,它是正规集中的一个元素；{}表示不含任何字的集合,它是一个空的正规集；{}表示由空字组成的集合。（3）使用括号可改变运算符的运算次序。若规定*优先于·,·优先于|,则在不混淆情况下,可省去括号。（4）Σ*的正规式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中的字经过有限次连接而成的。对于正规式R和S,若它们表示的正规集L(R)=L(S),则称R和S等价,记为R=S。（7）正规式服从代数规律：设r、s、t为正规式，1、r|s＝s|r 交换律2、r|(s|t)＝(r|s)|t 结合律3、(rs)t=r(st) 结合律4.r(s|t)=rs|rt 分配律(s|t)r=sr|tr 分配律5.r=r 零一律r=r 零一律例1、＝{a,b}，上的正规式和相应的正规集例2、令={d,,e,+,-}，则上的正规式d*(.dd*|)(e(+|-|)dd*|)表示的是所有无符号数。 其中d为0～9中的数字。比如：2,12.59,3.6e2,471.88e-1等都是正规式表示集合中的元素。例3：判断下述正规式之间是否等价：(1)(a|b)*与a*|b* (2)(ab)*与a*b* (3)(a|b)*与(a*b*)*(1)(a|b)*对应的正规集其a,b可任意交替出现,如abbaaab…,而(a*|b*)对应的正规集只可出现任意个a或任意个b,因此两者不等价。(2)(ab)*对应的正规集以任意个ab对出现，即ababab…,而a*b*对应的正规集则是任意个a后接任意个b,即a…ab…b,因此两者不等价。(3)(a|b)*对应的正规集其a,b可任意交替出现,如aababbb,而(a*b*)*可采用如下方法得到相应的字:(a*b*)*(a*b*)(a*b*)(a2b1)(a1b3)aababbb。反之,(a*b*)*产生的任意字也可由(a|b)*得到,因此两者等价。例4、程序设计语言中的单词既能用正规文法表示，又能用正规式来表示。正规文法：<字母>::=a|b|c…|z<字母数字>→l|d|l<字母数字>|d<字母数字><标识符>::=<字母>|<字母><字母数字>正规式： 标识符=字母(字母|数字)*二、单词的描述工具例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*)一个正规语言可以由正规文法定义，也可以用正规式定义。有些语言容易用文法表示，有些语言容易用正规式表示。正规文法和正规式的等价性,即正规式正规文法(1)对于任意一个正规文法，存在一个定义同一语言的正规式。(2)对于任意一个正规式，存在一个生成同一语言的正规文法。例6、将R＝a(a|d)*变换成正规文法（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：设有文法G(S)： S→aA,S→a,A→aA,A→dA,A→a,A→d试将该文法变换成正规式。（不断收缩产生式规则，直到剩下一个开始符号定义的正规式）第三节单词的识别机制1、有穷自动机是一种自动识别装置，能正确识别正规