编译原理PPT课件.ppt

1、编译原理 概论 词法分析 语法分析 语义分析 中间代码生成 优化 目标代码生成一. 概论1.1 翻译程序 汇编程序：源语言为汇编语言，目标语言为 机器语言 编译程序：源语言为高级语言，目标语言为 某台计算机上的汇编语言或机器 语言 解释程序：能够按源程序的动态顺序逐句进 行分析解释，根据语句功能翻译 成与该语句相应的机器指令序 列，并立即执行，直至结束。翻译程序源程序目标程序翻译程序1.2 源程序执行的途径（编译途径、解释途径） 编译途径即是将一份源程序从头至尾翻译成某台计算机上的机器语言表示的目标程序，然后执行该目标程序得到运行结果，并允许重复执行若干次。 编译的转换过程两阶段转换：编译运行

2、源程序编译程序目标代码编译时初始数据运行子程序目标代码计算结果运行时1.2 源程序执行的途径（编译途径、解释途径） 解释途径即是对于源程序的一个语句，把它翻译成相应的机器语言，并让计算机立即执行。如果需要数据时，则提示用户输入初始数据，并立即进行处理。解释途径就是边解释边执行，直至源程序动态处理完毕为止。 当用高级语言编写的源程序输入计算机后，键入运行程序命令，则解释程序就对源程序逐条翻译，翻译一条立即执行一条。该途径不产生目标代码程序，故占用内存较少，但执行速度要慢些。解释程序源程序结果初始数据1.4 编译程序的结构词法分析器语法分析器语义分析器中间代码生成优化目标代码生成源程序目标代码表格

3、管理出错处理二.词法分析2.1 任务输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词及其有关属性，并转换成属性字，这也就是词法分析的输出。2.2 单词是高级语言中有实在意义的最小语法单位，它由字符构成。2.3 属性字 指单词的一种机内表示单词类别单词属性值 2.4 词法分析程序与语法分析程序的接口方式词法分析程序是编译第一阶段的工作。词法分析工作可以是独立的一遍，把字符流的源程序变为单词序列，输出在一个中间文件上，这个文件做为语法分析程序的输入而继续编译过程。而更一般的情况，常将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。词法程序每得到一次调

4、用，便从源程序文件中赌徒一些字符，直到识别出一个单词，或者直到下一单词的第一个字符为止。这中设计方案中，词法分析程序和语法分析程序放在同一遍里，而省掉了中间文件。字符串表示的源程序词法分析器字符单词符号取下一个单词符号语法分析器0 1020 34567891011121416131517l非ldl |d非d非dd/非非和非 ;其它:2.2.语法分析语法分析2.1 2.1 任务：任务：在词法分析的基础上，根据语言的语法规则，逐一分析词法分析时得到的属性字，检查语法错误，若没有错误，则给出正确的语法结构（如短语、子句、句子、程序段、程序等）。2.2 2.2 语法规则：语法规则：语言的规则，又称为文

5、法；规定单词如何构成短语、语句、过程和程序。2.3 2.3 语法分析的方法语法分析的方法2.3.12.3.1自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E Ei+ +* *EiiEEEE2.3.2

6、 自上而下分析法自上而下分析法(Top-down)(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序F优点：直观、简单和宜于手工实现。 自上而下分析面临的问题 要消除文法的左递归性 克服回溯例：下列文法含有直接左递归：SSaS b所能产生的语言L = | n 0 ，对输入串baaaa#是该语言的句子，但用自顶向下分析时可看出当输入符为b时，为与b匹配应选用Sb来推导，这样就推不出后面部分，若用SSa

7、则无法确定到什么时候才用Sb替换。nnba左递归的消除左递归的消除 对上例的直接左递归可改写为右递归，如对上例的文法可改写为：改写后的文法和原文法产生的语言相同。SbS|SaS回溯的消除回溯的消除 为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。 提取公共左因子提取公共左因子: 假定关于A的规则是 A 1 | 2 | | n | 1 | 2 | | m (其中，每个 不以开头) 那么，可以把这些规则改写成AA | 1 | 2 | | mA 1 | 2 | | n 经过反复提取左因

8、子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。2.4 LL(1)文法的判断 当需要选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST,FOLLOW,SELECT集合，进而判别文法是否为LL(1)文法。实质:对于文法GS,其每个非终结符号的不同规则具有不相交的可选集Select,则称该文法为LL(1)文法.AX1 X2 Xn Select(AXi)Select(AXj)=(空集)(ij)FIRST集合定义 令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为：.,|=)(*TVaa

9、aFIRST 特别是，若 ，则规定FIRST()。* 如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选 i和 jFIRST(i)FIRST( j) 当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。FOLLOW集合定义 假定S是文法G的开始符号，对于G的任何非终结符A，我们定义.,.|)(*TVaAaSaAFOLLOWAS*特别是，若 ，则规定 FOLLOW(A)可选集可选集 SelectSelect设文法GS,并有规则A（为符号串）则该规则的可选集为 定义Select（）=Follow(A) Fir

10、st()， 当为空符号串First()，当不为空符号串例：例：文法文法GE EE+TGE EE+TT T TT TT* *F FF F F F（E E）iSellectSellect（ETET）= First= First（T T）= =（，（，i iSellectSellect（FF（E E）= First= First（E E）= =（SellectSellect（EE+TEE+T）= First= First（E+TE+T）= =（，（，i iSellectSellect（TTTT* *F F）= First= First（T T* *F F）= =（，（，i iSellectSelle

11、ct（TFTF）= First= First（F F）= =（，（，i i构造预测分析表 对每个终结符或#号用a表示。若 则把 放入MA,a中。把所有无定义的MA,a标上出错标记。()aSELECT AA 例：例： 对于文法对于文法G(E)ETE E +TE | TFT T *FT | F(E) | i 输入串为输入串为i1*i2+i3，利用分析表进行，利用分析表进行预测分析：预测分析：i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E) 步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式 0#Ei1*i2+i3# 1#E Ti

12、1*i2+i3# ETE 2#E T Fi1*i2+i3# TFT 3#E T ii1*i2+i3# Fii+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E) 步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式 3#E T ii1*i2+i3# Fi 4#E T *i2+i3# 5#E T F*i2+i3# T *FT 6#E T F i2+i3# 7#E T ii2+i3# Fii+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)i+*()#EETE ETE E

13、E +TE E E TTFT TFT T T T *FT T T FFiF (E)步骤步骤符号栈符号栈输入串输入串所用产生所用产生7#E T ii2+i3# Fi 8#E T +i3#9#E +i3# T 10#E T+i3# E +TE 11#E Ti3#i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)步骤步骤符号栈符号栈输入串输入串所用产生所用产生11#E Ti3#12#E T F i3# TFT 13#E T ii3# Fi14#E T #15#E # T 16# E 3.语义分析 任务 对语法分析识别出的各类语法范畴，

14、分析其含义，进行和初步翻译，产生介于源代码和目标代码之间的一种代码。 分为两阶段工作对每种语法范畴进行静态语义检查若语义正确，就进行中间代码的翻译 中间代码形式四元式、三元式、逆波兰式 “中间代码”是一种结构简单、含义明确的记号 系统。这种记号系统或者与现代计算机的指令形式 有某种程度的接近，或者能够比较容易地把它变换 成现代计算机的机器指令。“翻译”工作仅仅在这里才开始涉及到。常用的中间代码如：三元式、四元式、逆波兰式 算 符左操作数右操作数 结 果例如x = 2 * a + b三元式(*,2,a) (2) (+,(1),b)(3) (=,(2),x)四元式(*,2,a,t1) (2) (+

15、,t1,b,t2)(3) (=,t2,/,x) 如上述源程序经语义分析得到下列中间代码程序Void jisuan() float r, s,c; s=3.14*r*r; c=2*3.14*r; （1） （*，3.14，r）（2） （*，（1），r）（3） （：=，（2），s）（4） （*，2，3.14）（5） （*，（4），r）（6） （：=，（5），c） 如上述源程序经代码优化得到下列中间代码程序Void jisuan() float r, s,c; s=3.14*r*r; c=2*3.14*r; （1） （*，3.14，r）（2） （*，（1），r）（3） （：=，（2），s）（4） （*

16、，2，3.14）（5） （*，（4），r）（6） （：=，（5），c）（1） （*，3.14，r）（2） （*，（1），r）（3） （：=，（2），s）（4） （*，2，（1）（5） （ ：=， （4），c）4.优化 任务 对前面产生的中间代码进行加工变换，以期在最后阶段能产生更为高效的目标代码。 原则：等价变换 主要方面 公共子表达式的提取、合并已知量、删除无用语句、循环优化等。4.1合并常量运算当运算分量为常量时，立即计算出运算结果，而不生成目标代码。i:=10; j:=2*i+5;k:=2*i+j 优化前(:=,10,i)(2) (*,2,i) (3)(+,5,(2) (4)(:=,(3

17、),j) (5) (*,2,i) (6)(+,(5),(4)(7)(:=,(6),k)优化后(1) (:=,10,i)(2)(:=,25,j)(3)(:=,45,k)4.2 外提循环中的不变表达式指该表达式中的所有运算分量是常量或者是关于该循环的区域常量。for i:=1 to 100 dobegin a:=(x+y)*i;b:=(x-y)*i;s:=a*b; end t1:=x+y; t2:=x-y; for i:=1 to 100 dobegin a:=t1*i;b:=t2*i; s:=a*b; end x+y和x-y是不变表达式，被重复执行100次 4.3 削减运算强度把强度大的运算改为

18、强度小的运算如* /改为+ -for i:=1 to 100 do s:=i*b; 执行100次*s:=0; for i:=1 to 100 do s:=s+b; 执行100次+5.目标代码生成 任务 把经过优化的中间代码转化成特定机器上的低级语言代码 目标代码的形式绝对指令代码:可立即执行的目标代码。汇编指令代码：汇编语言程序，需要通过汇编程序汇编后才能运行。可重定位指令代码：先将各目标模块连接起来，确定变量、常数在主存中的位置，装入主存后才能成为可以运行的绝对指令代码。一个实例 通过设计和实现能够正确对IF-THEN- ELSE的语句进行词法，语法及语义分析的程序，加深对整个编译过程的理解

19、。（1）词法分析1.1. 词法分析器的输入和输出输入：所给文法的源程序字符串输出：二元组（单词种别，单词符号属性值）构成的序列。1.2. 待分析单词的词法模拟程序语言的单词符号分为以下五种关键字： , , if, else,then, while, 运算符：+, -, *, /,= 界 符: 逗号，分号，左圆括号，右圆括号 常 数: 这里我们只涉及int型常数 其它单词是标识符（ID）和整型常数(NUM),可以通过一下 正规式定义: ID = letter(letter|digit)* NUM = digit digit* 制表符，换行符，空格在词法分析阶段就会过滤掉。1.3. 各种单词的种别

20、码单词符号种别码单词符号种别码*/if=else,then;while()+letter(letter|digit)*-digit digit*（2）语法分析2.1根据需求设计如下文法：G = (VN,VT,S,P) ,VN = S,E,B,N,VT = if,then,else,a,b,x,P有下列产生式组成:S- if E then B1 else B2E- id1 N id2B- id1 N numN- 此文法中a,b,x指的是程序中的变量 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best, Failure Is Great, So DonT Give Up, Stick To The End谢谢大家荣幸这一路，与你同行ItS An Honor To Walk With You All The Way演讲人：XXXXXX 时 间：XX年XX月XX日