第一章介绍综合性跨越,渗透程序设计语言与算法计算理论与软件工程体系结构与操作系统组成部分环境软件工具编译器要做哪些事情?position:=initial+rate*60MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR1,R2MOVFR1,id1词法分析——分词position:=initial+rate*60id1:=id2+id3*60语法分析语法树id1:=id2+id3*60:=id1id2id3+*60语义分析——类型检查&转换:=id1id2id3+*60:=id1id2id3+*inttoreal60中间代码生成虚拟机程序:=id1id2id3+*inttoreal60temp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3代码优化——机器无关的temp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3temp1:=id3*60.0id1:=id2+temp1目标代码生成——汇编码temp1:=id3*60.0id1:=id2+temp1MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR1,R2MOVFR1,id1“编译器”要做哪些事情?h1今天天气真好!/h1词法分析h1今天天气真好!/h1LTheader1_begGTSTRLTheader1_endGT语法分析LTH1ENDheader1_endGTLTH1BEGheader1_begGTSTRH1LTheader1_begGTSTRLTheader1_endGT语义分析LTH1ENDheader1_endGTLTH1BEGheader1_begGTSTRH1LTH1ENDheader1_endGTLTH1BEGheader1_begGTSTRH1浏览器绘制渲染LTH1ENDheader1_endGTLTH1BEGheader1_begGTSTRH1“编译器”要做哪些事情?Model=“Civic”ANDYear=“2001”ID#ModelYearColorDealerPrice6734Civic2001WhiteOR$17,0004395Civic2001RedCA$17,000词法分析Model=“Civic”ANDYear=“2001”Field_name=STRANDField_name=STR语法分析Field_name=STRANDField_name=STRField_name=STRANDField_name=STR语义分析Field_name=STRANDField_name=STRField_name=STRANDField_name=STR数据库管理程序执行查询ID#ModelYearColorDealerPrice6734Civic2001WhiteOR$17,0004395Civic2001RedCA$17,000Field_name=STRANDField_name=STR1.1编译器CompilerSourceprogramTargetProgramErrormessagesDiverse&Varied分类都可划分为相同的基本任务采取相似的基本技术SinglePassMultiplePassLoad&GoConstructionDebuggingOptimizingFunctional1.1.1分析-综合模型两个基本组成部分分析:将源程序分解为基本组成部分,生成中间表示形式综合:从中间表示形式构建目标程序中间表示形式中间表示形式——树节点——操作,孩子——参数position:=initial+rate*60positioninitialrate:=+*60中间表示形式中间表示形式——树节点——操作,孩子——参数position:=initial+rate*60positioninitialrate:=+*60使用编译技术的软件工具处理源码、进行分析工作的辅助工具格式化编辑器强制文本符合语法,符合标准格式关键字自动完成、括号匹配格式化打印标准格式输出程序,清晰、美观字体、空格、缩进SourceFormatX软件工具静态检查“简单”、“快速”的编译,检查可能的语义错误,甚至逻辑错误PC-LINT:不会执行的程序段、判断非负整数是否大于等于0静态检查例子charfirstChar1(char*s){return*s;}可能为空!静态检查例子(续)int*glob;int*f(int**x){intsa[2]={0,1};intloc=3;glob=&loc;*x=&sa[0];return&loc;}voidh(void){unsignedinti;if(i=0)printf(=0\n);elseprintf(0);}Splint工具检查此程序的输出返回局部变量!i为无符号整数!软件工具解释器不产生目标程序,边分析边执行Shell语言,早期BASIC、Java、Python其它应用排版软件普通文本,命令格式、图表、公式LATEX,TROFF硅编译器源程序电路设计,变量——逻辑信号文本/图形模式数据库查询数据查询语言输入—数据查询语句底层数据库访问操作数据压缩压缩:初始数据上下文无关文法压缩文法解压:解压文法文法推导出唯一串初始数据滑铁卢大学杨恩辉教授,已应用于黑莓手机1.2源程序分析三个阶段线性分析/词法分析由左至右扫描源程序字符序列token,单词(记号)——具有组合意义的字符序列层次分析/语法分析单词序列有意义的集合,语法单位语义分析检查程序各部分是否正确符合语义1.2.1词法分析线性分析,词法分析,扫描忽略空格、回车等,将字符组合为单词ForExample:AllaretokensPosition:=initial+rate*60;______________________标识符——position、initial和rate赋值符——:=加法、乘法算符——+、*操作数——601.2.2语法分析层次分析,分析(parsing),语法分析将词法分析产生的单词组合为语法短语identifieridentifierexpressionidentifierexpressionnumberexpressionexpressionexpressionassignmentstatementposition:=+*60initialrate简化的语法分析树表示仅保存单词内部结点——运算符,叶结点——运算对象positioninitialrate:=+*60语法分析树(parsetree)identifieridentifierexpressionidentifierexpressionnumberexpressionexpressionexpressionassignmentstatementposition:=+*60initialrate语法结构的递归定义表达式1.标识符是表达式2.数是表达式3.若expression1和expression2是表达式,则expression1+expression2expression1*expression2(expression1)也是表达式1、2——基本规则,3——递归定义文法(grammar)语句(statement)定义1.若identifier1是一个标识符,expression2是一个表达式,则identifier1:=expression2是一个语句2.若expression1是一个表达式,statement2是一个语句,则while(expression1)dostatement2和if(expression1)thenstatement2也是语句文法:处理token相互关系和结构的一组规则词法分析和语法分析的划分是否需要递归词法分析扫描输入流,识别单个“单词”——token线性动作,无需递归语法分析表达式、语句分析,括号匹配…需要层次化结构——语法分析树递归1.2.3语义分析确定语法结构无歧义的唯一的含义检查不合语义的错误为代码生成收集信息最重要的工作:类型检查,2+‘a’例1.1类型转换intrealpositioninitialrate:=+*inttoreal60ConversionAction1.2.4排版软件中的分析LATEXLATEX文件:普通文本+命令命令的分析和执行——词法分析、语法分析、语义分析\begin{proof}\end{proof}\noindent\section{Introduction}$A_i$$A_{i_j}$Embeddedinastreamoftext,i.e.,aFILEbeginsinglenoindentsectionLanguageCommands编译结果1.3编译器的多个阶段SourceProgramLexicalAnalyzer1SyntaxAnalyzer2SemanticAnalyzer3IntermediateCodeGenerator4CodeOptimizer5CodeGenerator6TargetProgramSymbol-tableManagerErrorHandler1.3.1符号表创建/管理记录标识符属性信息变量的存储分配、类型、作用域(对函数、过程)参数数目、参数类型、参数传递方式、返回类型符号表的数据结构——记录表每个记录:一个标识符及其属性词法分析时创建后续阶段修改/使用属性varposition,initial,rate:real;1.3.2错误检测和报告各阶段均会遇到错误处理方式:报告错误,应继续编译大部分错误在语法分析、语义分析阶段检测出来词法分析:字符无法构成合法单词语法分析:单词流违反语法结构规则语义分析:语法结构正确,但无实际意义一个语句的完整翻译过程position:=initial+rate*60lexicalanalyzersyntaxanalyzersemanticanalyzerintermediatecodegeneratorid1:=id2+id3*60:=id1id2id3+*60:=id1id2id3+*inttoreal60SymbolTableposition....initial….rate….ErrorsErrorsintermediatecodegeneratorcodeoptimizerfinalcodegeneratortemp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3temp1:=id3*60.0id1:=id2+temp1MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR1,R2MOVFR1,id1position....initial….rate….SymbolTable3addresscode1.3.3分析阶段词法分析单词,词素,词法值符号表id1:=id2+id3*60语法分析语法分析树id1:=id2id3+*601.3.4中间代码生成虚拟机程序——不依赖实际体系结构应有两个重要特性容易生成容易翻译为目标程序三地址码temp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp31.3.5代码优化生成运行速度更快的机器码简单直接的优化:temp1:=id3*60.0id1:=id2+temp1“优化编译器”存在简单但非常有效的优化方法——不会大幅减慢编译速度代码优化intmain(intargc,char*argv[]){inti;doublesum=0.0;
本文标题:编译原理第一章介绍
链接地址:https://www.777doc.com/doc-2068959 .html