程序设计语言与编译原理-第五章编译概述课件.ppt

1、程序设计语言与编译 主要内容主要内容1.1.编译的一些基本概念编译的一些基本概念2.2.编译步骤编译步骤1 1程序设计语言与编译 第一节第一节 不同语言的翻译不同语言的翻译:将一种语言编写的程序转换成完全等效的另一种语言编写的程序的过程称为（translate）；在计算机中，翻译由一个程序来实现，称为(translator)；源程序源程序翻译程序翻译程序目标程序目标程序一一.基本概念基本概念编译程序编译程序:高级语言低级语言汇编程序汇编程序:汇编语言机器语言2 2程序设计语言与编译 :编写编译程序的语言称为；源语言、目标语言、宿主语言通常是不同的语言；：运行翻译程序的机器编译程序能生成可供其宿

2、主机执行的机器代码编译程序是用源语言写的:编译程序生成的不是宿主机的机器代码，而是别的机器代码3 3程序设计语言与编译 二二.两种运行方式两种运行方式源程序源程序编译程序编译程序目标程序目标程序初始数据初始数据目标程序目标程序运行库运行库结果结果 源程序源程序 目标程序目标程序 计算结果计算结果 汇编语言程序汇编语言程序 目标程序目标程序编译编译编译编译运行运行汇编程序汇编程序初始数据初始数据4 4程序设计语言与编译 :不将源程序翻译成目标程序，而是一边分析，一边执行，这种翻译方法称为 实现解释的程序，称为。1.特别适合于动态语言和交互式环境，便于人机对话2.解释器边解释边执行，重复执行的程序

3、需要重复翻译，比编译执行花费更多时间，执行效率低；源程序源程序解释程序解释程序计算结果计算结果初始数据初始数据5 5程序设计语言与编译1.:输入字符串，根据词法规词法规则则识别出单词符号。2.:根据语法规则，将单词符号构成各类语法单位，并进行语法检查。3.:根据语义规则,进行初步编译。第二节第二节 编译步骤编译步骤6 6程序设计语言与编译4.:对中间代码进行等价变换,以使代码更有效。5.:生成机器语言程序或汇编语言程序。说明：说明：（1 1）实用的编译程序不一定总是分成）实用的编译程序不一定总是分成5 5个阶段个阶段（2 2）目标程序不一定能立即执行，可能还要经过连接、装入等阶段）目标程序不一

4、定能立即执行，可能还要经过连接、装入等阶段（3 3）编译的各阶段均需要和符号表管理程序、出错处理程序打交道）编译的各阶段均需要和符号表管理程序、出错处理程序打交道7 7程序设计语言与编译8 8自然语言翻译过程：自然语言翻译过程：编译程序工作过程：编译程序工作过程：识别单词识别单词分析句法分析句法初步翻译初步翻译译文润饰译文润饰正式翻译正式翻译词法分析词法分析语法分析语法分析语义分析与中间代码产生语义分析与中间代码产生代码优化代码优化目标代码生成目标代码生成程序设计语言与编译9 91.词法分析词法分析l任务：输入源程序，对字符串扫描分解、识别出任务：输入源程序，对字符串扫描分解、识别出单词单词(

5、或单词符号、或简称符号或单词符号、或简称符号)。l单词是高级语言中有实在意义的最小语法单位，单词是高级语言中有实在意义的最小语法单位，一般分为一般分为5类：类：保留字保留字（begin、end、if、for、while等）、等）、标识符标识符、常数常数、运算符运算符和和分界符分界符（标（标点符号、括号、注释符号等点符号、括号、注释符号等 依循原则：语言的词法规则依循原则：语言的词法规则(或构词规则或构词规则)描述工具：正规式和有限自动机描述工具：正规式和有限自动机程序设计语言与编译1010程序设计语言与编译11112.语法分析语法分析l任务：在词法分析的基础上，根据语言的任务：在词法分析的基础

6、上，根据语言的语法语法规则规则，从单词符号串中识别出各类语法单元，从单词符号串中识别出各类语法单元(如：如：表达式、语句、程序段、程序等）并进行语法表达式、语句、程序段、程序等）并进行语法检查，即检查各种语法单位在语法结构上的正检查，即检查各种语法单位在语法结构上的正确性。通过语法分析，确定整个输入串是否构确性。通过语法分析，确定整个输入串是否构成语法上正确的成语法上正确的“程序程序”。依循原则：语言的语法规则依循原则：语言的语法规则描述方法：上下文无关文法描述方法：上下文无关文法程序设计语言与编译1212词法分析词法分析 线性分析线性分析语法分析语法分析 层次结构分析层次结构分析u识别标识符

7、，因为标识符的结构是字母打头的字母和数字串，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符 u不能用于识别递归定义的语法成分，比如就无法仅用线性扫描去匹配表达式中的括号 程序设计语言与编译1313词法分析词法分析 线性分析线性分析语法分析语法分析 层次结构分析层次结构分析u把源程序的单词序列依照语法结构按层次分组，形成各类语法单元，组成语法短语(表示成语法树)uid1=id2+id3*10Id1 id2 id3是变量单词序列id2+id3*10是表达式id1=id2+id3*10是 赋值语句 程序设计语言与编译1414u语法分析所依

8、据的是语言的语法规则，语语法分析所依据的是语言的语法规则，语言的语法规则通常是由递归规则来定义言的语法规则通常是由递归规则来定义u如表达式和赋值语句可由下述递归规则来如表达式和赋值语句可由下述递归规则来定义：定义：(1)任何标识符是表达式；任何标识符是表达式；(2)任何常数是表达式；任何常数是表达式；(3)若表达式若表达式1和表达式和表达式2都是表达式，则表达式都是表达式，则表达式1+表达式表达式2，表达式，表达式1*表达式表达式2都是表达式；都是表达式；(4)赋值语句就可以用规则：标识符赋值语句就可以用规则：标识符=表达式表达式；来定义。；来定义。程序设计语言与编译1515程序设计语言与编译

9、16163.语义分析与中间代码产生语义分析与中间代码产生任务任务：对语法分析所识别的各类语法范畴，：对语法分析所识别的各类语法范畴，分析其含义分析其含义，并进行，并进行初步翻译初步翻译(产生中产生中间代码间代码)。静态语义检查：变量是否定义，类型是静态语义检查：变量是否定义，类型是否正确等。否正确等。若语义正确，则进行中间代码的翻译。若语义正确，则进行中间代码的翻译。通常包括两方面工作：通常包括两方面工作：程序设计语言与编译1717依循原则：依循原则：语言的语义规则语言的语义规则描述方法：描述方法：属性文法属性文法中间代码：中间代码：一种含义明确，便于处理的记号系统，一种含义明确，便于处理的记

10、号系统，通常独立于具体的硬件，或者与现代计算通常独立于具体的硬件，或者与现代计算机的指令形式机的指令形式接近接近或者或者容易变换容易变换成现代计成现代计算机的机器指令。算机的机器指令。从这个阶段起，翻译工作开始从这个阶段起，翻译工作开始程序设计语言与编译1818例：例：“四元式四元式”三地址中间代码三地址中间代码算符算符左操作数左操作数右操作数右操作数结果结果对语句对语句 Z=(X+0.418)Y/W序号序号左操作数左操作数右操作数右操作数结果结果算符算符123+/XT1T20.418YWT1T2Z还有三元式、间接三元式、逆波兰记号还有三元式、间接三元式、逆波兰记号和树形表示等。和树形表示等。

11、程序设计语言与编译19194.优化优化任务任务：对中间代码加工变换，以期产生更：对中间代码加工变换，以期产生更为高效为高效(时间、空间时间、空间)的目标代码，的目标代码，公共子表达式的提取、循环优化、公共子表达式的提取、循环优化、删除无用代码等。删除无用代码等。依循原则：依循原则：程序的等价变换规则。程序的等价变换规则。程序设计语言与编译2020例：例：for(k=1;k=100;k+)M=I+10 k;N=J+10 k;程序设计语言与编译2121需需300次加次加和和200次乘次乘中间代码为：中间代码为：序号OP ARG1 ARG2 结果注 解(1)=1K K=1(2)j100K(9)若10

12、0K转至第(9)个四元式(3)*10KT1 T1=10*K；T1为临时变量为临时变量(4)+IT1M M=I+T1(5)*10KT2 T2=10*K；T2为临时变量为临时变量(6)+JT2N N=J+T2(7)+K1K K=K+1(8)j(2)转至第(2)个四元式(9)程序设计语言与编译2222仅仅300次加次加转换后的等价代码为：转换后的等价代码为：序号 OP ARG1 ARG2 结果注 解(1)=IM M=I(2)=JN N=J(3)=1K K=1(4)j100K(9)若100K转至第(9)个四元式(5)+M10M M=M+10(6)+N10N N=N+10(7)+K1K K=K+1(8)

13、j(2)转至第(4)个四元式(9)程序设计语言与编译23235.目标代码生成目标代码生成任务任务：把中间代码：把中间代码(或优化后或优化后)变换成变换成特定特定机器机器上的上的低级低级语言代码。语言代码。非常复杂：非常复杂：最后的翻译，有赖于硬件系最后的翻译，有赖于硬件系统结构和机器指令含义，涉及到硬件功能部统结构和机器指令含义，涉及到硬件功能部件的运用，机器指令的选择，各种类型变量件的运用，机器指令的选择，各种类型变量的空间分配，以及寄存器和后援寄存器的调的空间分配，以及寄存器和后援寄存器的调度等。如何产生出足以发挥硬件效率的目标度等。如何产生出足以发挥硬件效率的目标代码是一件非常不容易的事

14、情。代码是一件非常不容易的事情。程序设计语言与编译2424绝对指令代码绝对指令代码 可立即执行可立即执行可重定位指令代码可重定位指令代码 借助连接装配程序把借助连接装配程序把各目标模块连接在一起，确定程序变各目标模块连接在一起，确定程序变量量(或常数或常数)在主存中的位置，装入内在主存中的位置，装入内存中指定的起始地址，使之成为绝对存中指定的起始地址，使之成为绝对指令代码指令代码(大多数编译程序采用大多数编译程序采用)。汇编指令代码汇编指令代码 汇编器汇编之后运行汇编器汇编之后运行目目标标代代码码形形式式程序设计语言与编译2525某些情况下，为加速编译速度，某些某些情况下，为加速编译速度，某些

15、阶段可省，某些阶段也可合并，但多数实阶段可省，某些阶段也可合并，但多数实用编译程序的工作过程大致都像这五个阶用编译程序的工作过程大致都像这五个阶段。段。程序设计语言与编译26262.表格与表格管理表格与表格管理常见的表格常见的表格:符号名表，常数表，标号表，入符号名表，常数表，标号表，入口名表，过程引用表。口名表，过程引用表。格式格式:名字名字信息信息一个名字一个名字常量名常量名 值值变量名变量名 类型、内存大小、地址类型、内存大小、地址过程名过程名 地址、参数地址、参数处理定义时处理定义时 登记登记处理引用时处理引用时 查证查证程序设计语言与编译2727void INCWAP(int M，i

16、nt N)int K;START:K=M+1;M=N+4;N=K;表表 0.1 0.1 符号名表符号名表 SNTSNT NAMENAME INFORMATIONINFORMATION M M 形式参数形式参数，整整型型，值参数值参数 N N 形式参数形式参数，整整型型，值参数值参数 K K 整型整型，变量变量 表表 0.2 0.2 常数表常数表 CTCT 值值(VALUE)(VALUE)(1)(1)1 1 (2)(2)4 4 程序设计语言与编译2828表表0 0.3 3 入入口口名名表表E EN NT T N NA AM ME E I IN NF FO OR RM MA AT TI IO ON

17、 N (1 1)I IN NC CW WA AP P 二二目目子子程程序序,入入口口四四元元式式:1 1 表表0 0.4 4 标标号号表表L LT T N NA AM ME E I IN NF FO OR RM MA AT TI IO ON N (1 1)S ST TA AR RT T 四四元元式式:(4 4)void INCWAP(int Mvoid INCWAP(int M，int N)int N)int K;int K;START:START:K=M+1;K=M+1;M=N+4;M=N+4;N=K;N=K;程序设计语言与编译2929 表表 0 0.5 5 四四元元式式表表 Q QT T

18、O OP PR R O OP PN N1 1 O OP PN N2 2 R RE ES SU UL LT T (1 1)l li in nk k (2 2)p pa ar r I IN NC CW WA AP P 1 1 M M (3 3)p pa ar r I IN NC CW WA AP P 2 2 N N (4 4)+M M 1 1 K K (5 5)+N N 4 4 M M (6 6):=K K N N (7 7)r re et tu ur rn n 程序设计语言与编译30303.出错处理出错处理l出错处理程序：发现源程序中的错误，把出错处理程序：发现源程序中的错误，把有关错误信息报告

19、给用户有关错误信息报告给用户最大限度发现各种错误，准确指出其性质最大限度发现各种错误，准确指出其性质及地点，并将其影响限制在尽可能小的范围，及地点，并将其影响限制在尽可能小的范围，使源程序其它部分能继续被编译，以进一步发使源程序其它部分能继续被编译，以进一步发现其它可能的错误。现其它可能的错误。程序设计语言与编译3131语法错：语法错：不符合词法规则不符合词法规则(“非法字符非法字符”，5X，256.)、或不符合语法规则、或不符合语法规则(“括号括号不匹配不匹配”，x=(a+(b*c)-1、“缺少；缺少；”等等)。语义错：语义错：不符合语义规则，语义分析时检不符合语义规则，语义分析时检测出来测出来(静态语义静态语义)，有时要到运行时，有时要到运行时才能检测出来才能检测出来(动态语义动态语义)。如：说明。如：说明错误、作用域错误、类型不一致等。错误、作用域错误、类型不一致等。绝大多数错误可在编译的前三阶段检测出来：绝大多数错误可在编译的前三阶段检测出来：程序设计语言与编译源程序字符串源程序字符串词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器代码优化器代码优化器目标代码生成器目标代码生成器单词流单词流语法树语法树中间代码序列中间代码序列中间代码序列中间代码序列目标程序目标程序符符 号号 表表 管管 理理 程程 序序出出 错错 处处 理理 程程 序序3232