编译原理第二章：一个微小编译器.ppt

资源描述

《编译原理第二章：一个微小编译器.ppt》由会员分享，可在线阅读，更多相关《编译原理第二章：一个微小编译器.ppt（54页珍藏版）》请在三一文库上搜索。

1、,编译原理,2021/2/23,北京化工大学信息科学与技术学院计算机系,2,2021/2/23,北京化工大学信息科学与技术学院计算机系,2,第 1 章编译简介,1.1 编译器 1.2 源程序的结构 1.3 编译器的实例 1.4 与编译相关的数据结构 1.5 编译器各阶段的分组,2021/2/23,北京化工大学信息科学与技术学院计算机系,3,2021/2/23,北京化工大学信息科学与技术学院计算机系,3,1.1 编译器,2021/2/23,北京化工大学信息科学与技术学院计算机系,4,2021/2/23,北京化工大学信息科学与技术学院计算机系,4, The phase of a compiler

2、编译程序的结构,词法分析Scanner,语法分析Parser,语义分析Semantic Analyzer,代码优化Code Optimizer,中间代码生成 Intermediate Code Generator, The phase of a compiler 编译程序的结构,目标代码生成 Target Code Generator,源程序 Source Code,目标程序 Target Code,2021/2/23,北京化工大学信息科学与技术学院计算机系,5,5,编译器的分析/综合模式,编译器基础架构（Infrastructure）,2021/2/23,北京化工大学信息科学与技术学院计

3、算机系,6,Q and A,Java程序编译执行过程,Java 语言能够跨平台执行，在不同平台上有不同的 Java 虚拟机，可以使 Java 的执行代码即统一的中间代码与平台无关。,2021/2/23,北京化工大学信息科学与技术学院计算机系,7,7,例1. Pascal源程序语句如下： var x, y, z : real; x := y + z * 60;,（记号流）(id,1),(:=),(id,2),(+),(id,3),(*) ,(60),依据源程序的语法规则把源程序的单词序列组成语法短语 (表示成语法树).,1.3 编译器的实例,2021/2/23,北京化工大学信息科学与技术学院计算

4、机系,8,2021/2/23,北京化工大学信息科学与技术学院计算机系,8,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,:=,表达式,*,x := y + z * 60;,2021/2/23,北京化工大学信息科学与技术学院计算机系,9,9,中间代码的形式与作用： (序号) (op， arg1, arg2, result) result := arg1 op arg2,(1) (itr, 60, , T1) (2) (*, id3, T1, T2) (3) (+, id2, T2, T3) (4) (:=, T3, , id1),x := y + z * 60;,2

5、021/2/23,北京化工大学信息科学与技术学院计算机系,10,10,(1) (itr, 60, , T1) (2) (*, id3, T1, T2) (3) (+, id2, T2, T3) (4) (:=, T3, , id1),(1) (*, id3, 60, T1) (2) (+, id2, T1, id1),MOVF R2, id3 MULF R2, #60 MOVF R1, id2 ADDF R1, R2 MOVF id1, R1,x := y + z * 60;,2021/2/23,北京化工大学信息科学与技术学院计算机系,11,11,编译器各阶段工作的归纳, 词法分析：识别单词，

6、至少分以下几大类：关键字（保留字）、标识符、特殊符号；语法分析：得到语言结构并以树的形式表示；语义分析：考察结构正确的句子是否语义合法，可修改树结构；中间代码生成（可选）：生成一种既接近目标语言，又与具体机器无关的表示，便于优化与代码生成；, 中间代码优化（可选）：局部优化、循环优化、全局优化等；优化实际上是一个等价变换，变换前后的指令序列完成同样的功能，但是，在占用的空间上和程序执行的时间上都更省、更有效。目标代码生成：不同形式的目标代码汇编、可重定位、内存形式; 符号表管理：合理组织符号，便于各阶段查找、填写等；出错处理：错误的种类词法错、语法错、静态语义错、动态语义错。,202

7、1/2/23,北京化工大学信息科学与技术学院计算机系,12,第2章一个微小编译器,2.1 Micro语言描述 2.2 Micro语言的词法分析 2.3 Micro语言的语法分析 2.4 Micro语言的语义分析 2.5 Micro语言的目标代码,2021/2/23,北京化工大学信息科学与技术学院计算机系,13,2.1 Micro语言描述,Micro语言（称Micro, Pascal语言的子集）,begin var x1:real; var z1:real; x1:=0.5; z1:=x1+56; write(z1+2.3); read(x1) end.,Main() float x1; fl

9、.5; z1:=x1+56; write(z1+2.3); read(x1) end.,2021/2/23,北京化工大学信息科学与技术学院计算机系,16, Micro语言中单词的种类：,2.2 Micro语言的词法分析,. 特点：不依赖于语言的语法定义，只依赖于单词的文法定义。,2021/2/23,北京化工大学信息科学与技术学院计算机系,17,输出,输入,输出,程序的字符串序列 Token序列（单词的内部表示）,Token定义：二元组（单词种类，单词自身值）标识符: ($id,标识符）如($id,x) 整常数: ($intC,整常数）如（$intC,5) 实常数: ($realC,实

10、常数）如($realC,0.5) 保留字: ($begin,-), ($end,-), ($var,-) 符号词: ($plus,-), ($mult,-), ($LParen,-), ($Rparen, -), ($colon,-),($assig,-),($semi,-) 换行符: ($line,-), ($stop,-),2021/2/23,北京化工大学信息科学与技术学院计算机系,18,Micro的词法分析,图源程序在文件中的表示,begin var x1:real; var z1:real; x1:=0.5; z1:=x1+56; write(z1+2.3); read(x1) en

11、d.,空格,2021/2/23,北京化工大学信息科学与技术学院计算机系,19,Micro的词法分析,begin var x1:real; var z1:real; x1:=0.5; z1:=x1+56; write(z1+2.3); read(x1) end.,图词法分析后的TOKEN表示,2021/2/23,北京化工大学信息科学与技术学院计算机系,20,Micro的词法分析,读当前字符流，直至文件结束。如果是： (1)标识符时判断是保留字还是变量标识符，构造Token表示； (2)数字时判断是整型还是实型，构造 Token表示； (3)构造其它合法的符号的Token表示； (4)遇到非

12、法符号则报错。,2.2 Micro语言的词法分析,3. 词法分析过程,2021/2/23,北京化工大学信息科学与技术学院计算机系,21, Micro语言的词法分析程序,Procedure scanner(); begin while Eof do Noblank(ch); case ch of A.Z|a.z Identifier(name); case name of “begin” GenToken($begin); “end” GenToken($end); “var” GenToken($var); “int” GenToken($int); “real” GenToken($real

13、); “read” GenToken($read); “write” GenToken($write); other GenToken($id,name); end ;,例： begin var x1:real; var z1:real; x1:=0.5; z1:=x1+56; write(z1+2.3); read(x1) end.,2021/2/23,北京化工大学信息科学与技术学院计算机系,22, Micro语言的词法分析程序,Procedure scanner(); begin while Eof do Noblank(ch); case ch of A.Z|a.z Identifier

14、(name); case name of “begin” GenToken($begin); “end” GenToken($end); “var” GenToken($var); “int” GenToken($int); “real” GenToken($real); “read” GenToken($read); “write” GenToken($write); other GenToken($id,name); end ;,GenToken(token)将token送入TOKEN区。,例： begin var x1:real; var z1:real; x1:=0.5; z1:=x1

15、+56; write(z1+2.3); read(x1) end.,2021/2/23,北京化工大学信息科学与技术学院计算机系,23,Procedure scanner(); begin while Eof do Noblank(ch); case ch of A.Z|a.z Identifier(name); 0.9 Constant(class,C); GenToken(Class,C); ( GenToken($Lparen); Read(ch); ) GenToken($Rparen); Read(ch); + GenToken($plus); Read(ch); * GenToken

16、($mult); Read(ch); ; GenToken($semi); Read(ch); : Read(ch); if ch= then GenToken($assig); Read(ch) else GenToken($colon) . GenToken($stop); Read(ch); GenToken($line); Read(ch); other LexicalError(ch) end end,Constant(class,C)：从输入流读到当前常数，并在class中给出常数的类型标志，C中给出常数的二进制数值。调用时当前字符定是数字（在ch中）。,词法错误,2021/2/2

17、3,北京化工大学信息科学与技术学院计算机系,24,Procedure scanner(); begin while Eof do Noblank(ch); case ch of A.Z|a.z Identifier(name);,Procedure Identifier(name:string); Begin name:=“ ”; Append(name,ch); Read(ch); while isLetter(ch) or isDigit(ch) do Append(name,ch); Read(ch); End, Micro语言的词法分析程序的相关子程序(1),Identifier(na

18、me)：从输入流把当前标识符名读到name中。在调用时，当前字符一定是字母，且已被读到ch中。,读标识符，保留字（关键字）,2021/2/23,北京化工大学信息科学与技术学院计算机系,25,Procedure Constant(class:classType, C:Const); Begin IntConst(N1,L1); if ch=. then Read(ch); if (IsDigit(ch) LexicalError(ch); IntConst(N2,L2); class:=$realC; C:=N1+N2*(1.0/10)L2 Else class:=$intC; C:=N1 E

19、nd, Micro语言的词法分析程序的相关子程序(2),Constant(class,C)：从输入流读到当前常数，并在class中给出常数的类型标志，C中给出常数的二进制数值。调用时当前字符定是数字（在ch中）。,整数(小数点左部),整数(小数点右部),读整/实常数,2021/2/23,北京化工大学信息科学与技术学院计算机系,26, Micro语言的词法分析程序的相关子程序(3),IntConst(N,L):从输入流读当前整常数，并在N中给出所读常数的二(十)进制值，在L中给出整常数的位数。调用时当前字符应是数字。,Procedure IntConst(N,L); Begin N:=Num(

20、ch); L:=1; Read(ch); while isDigit(ch) do N:=N*10+Num(ch); L:=L+1; Read(ch) End,读整常数,2021/2/23,北京化工大学信息科学与技术学院计算机系,27,Procedure scanner(); begin while Eof do Noblank(ch); case ch of A.Z|a.z Identifier(name); case name of “begin” GenToken($begin); “end” GenToken($end); “var” GenToken($var); “int” Gen

21、Token($int); “real” GenToken($real); “read” GenToken($read); “write” GenToken($write); other GenToken($id,name); end ; 0.9 Constant(class,C); GenToken(Class,C); ( GenToken($Lparen); Read(ch); ) GenToken($Rparen); Read(ch); + GenToken($plus); Read(ch); * GenToken($mult); Read(ch); ; GenToken($semi);

22、Read(ch); : Read(ch); if ch= then GenToken($assig); Read(ch) else GenToken($colon) . GenToken($stop); Read(ch); GenToken($line); Read(ch); other LexicalError(ch) end end,例： begin var x1:real; var z1:real; x1:=0.5; z1:=x1+56; write(z1+2.3); read(x1) end.,2021/2/23,北京化工大学信息科学与技术学院计算机系,28,输入,输出,程序的字符串序

23、列 Token序列（单词的内部表示）,2.2 Micro语言的词法分析,2021/2/23,北京化工大学信息科学与技术学院计算机系,29,1. 任务：检查程序是否有语法（语法结构）上的错误。 2. 输入：词法分析后得到的Token表输出：具体语法错误提示和语法全部正确提示。,2. Micro语言的语法分析,说明：语法分析只用到单词的Token表示，并不改变单词的Token表示。,2021/2/23,北京化工大学信息科学与技术学院计算机系,30,声明检查：begin var id: real; (声明的位置) 赋值语句标识符语句输入语句表达式整/实常数语句检查：输出语句左

24、括号后继符（语句末符号）(；， end),2. Micro语言的语法分析,3. 语法分析程序思路：,2021/2/23,北京化工大学信息科学与技术学院计算机系,31,Procedure Parser(); begin Match($begin,1); Match($var,2); LD: Match($id,3); Match($colon,4); Match($intC/$reaC,5); Match($semi,6); ReadToken(token); if token=$line then ReadToken(token); if token=$var then goto LD;,

25、Match(kind,n)：读当前Token，并检查Token.LH=kind？若不等，则打出错误编号n。 Token.LH：Token的左半部。 Token.RH：Token的右半部。,ReadToken(token): 把当前Token读到token中。, Micro语言的语法分析程序,声明列处理,2021/2/23,北京化工大学信息科学与技术学院计算机系,32,LS: case token of ($write,-）Match($Lparen,7); Expr(); Match($Rparen,8); ($read,-) Match($Lparen,9); Match($id,10);

26、 Match($Rparen,11); ($id,-) Match($assig,12); Expr(); other error(13) end; ReadToken(token); /读语句的后继符,单词,后继符,Expr():表达式的语法分析程序,Procedure Parser(); begin Match($begin,1); Match($var,2); LD: Match($id,3); Match($colon,4); Match($intC/$reaC,5); Match($semi,6); ReadToken(token); if token=$line then Read

27、Token(token); if token=$var then goto LD;,2021/2/23,北京化工大学信息科学与技术学院计算机系,33,case token of ($semi,-) ReadToken(token); if token=$line then ReadToken(token); goto LS; ($line,-) Match($end); ($end,-) ReadToken(token); if token=$stop then STOP else Error(14) other Error(15) end end,ReadToken(token); /读语句

28、的后继符,2021/2/23,北京化工大学信息科学与技术学院计算机系,34, Micro语言的语法分析子程序表达式的语法检查,Procedure Expr(); begin LF: ReadToken(token); case token of ($id,-) skip; ($intC,-) skip; ($reaC,-) skip; $Lparen begin Expr(); Match($Rparen,16) end; other error(17) end; ReadToken(token);,case token of (接左) ($plus,-) goto LF; ($mult,-)

29、 goto LF; Other BackToken End end,Token指针回溯一步,2021/2/23,北京化工大学信息科学与技术学院计算机系,35,Error 1 程序头不是begin Error 2 变量声明头不是var Error 3 var后不是标识符 Error 4 “var id”后不是“：” Error 5 “var id:”后不是类型符 Error 6 变量声明后不是“;” Error 7 write后不是“（” Error 8 “write(E”后不是“）” Error 9 read后不是“（” Error 10 “read (”后不是”id”, Micro语言的具体

30、语法错误,Error 11 “read (id”后不是”）” Error 12 赋值语句左部不是“:=” Error 13 语句头单词错 Error 14 程序结束符错 Error 15 语句后继符错 Error 16 缺“(E)”中的闭括号 Error 17 运算分量的后继符错,2021/2/23,北京化工大学信息科学与技术学院计算机系,36,Procedure Parser(); begin Match($begin,1); Match($var,2); LD: Match($id,3); Match($colon,4); Match($intC/$reaC,5); Match($sem

31、i,6); ReadToken(token); if token=$line then ReadToken(token); if token=$var then goto LD; LS: case token of ($write,-）Match($Lparen,7); Expr(); Match($Rparen,8); ($read,-) Match($Lparen,9); Match($id,10); Match($Rparen,11); ($id,-) Match($assig,12); Expr(); other error(13) end; ReadToken(token); cas

32、e token of ($semi,-) ReadToken(token); if token=$line then ReadToken(token); goto LS; ($line,-) Match($end); ($end,-) ReadToken(token); if token=$stop then STOP else Error(14) other Error(15) end end,2021/2/23,北京化工大学信息科学与技术学院计算机系,37,2.4 Micro语言的语义分析,1.任务：语法分析：只检查语法结构的正确性不检查他本身(语义)的正确性,语义分析：检查语义错误

33、：没有声明；重复声明；类型不相容将Token序列中的标识符转换为（$id, entry） (entry表示标识符在符号表中的地址),2021/2/23,北京化工大学信息科学与技术学院计算机系,38,2.4 Micro语言的语义分析,语义分析过程,读入Token 遇到标识符声明时，检查是否已声明，是则报错，否则构造标识符的符号表；遇到标识符定义和使用时，检查是否声明过。将变量的Token改为（$id,entry)形式。,2021/2/23,北京化工大学信息科学与技术学院计算机系,39, Micro语言的语义分析程序,Procedure Semantic(); begin Creat; /

34、建空符号表 ReadToken(); /读掉$begin LD: ReadToken(token);/读声明/语句头符 case token.LH of $var ReadToken(token); /（$id,name） Enter(token.RH, Entry, s)； if s=true then Error(1); / 重复声明错 ReadToken(); ReadToken(token);/: $int/$real case token.LH of $int SetAttribute(entry,newAddr,intType); $real SetAttribute(entry,

35、newAddr,realType) end; ReadToken(); goto LD; /；,2021/2/23,北京化工大学信息科学与技术学院计算机系,40, Micro语言的语义分析程序,Procedure Semantic(); begin Creat; /建空符号表 ReadToken(); /读掉$begin LD: ReadToken(token);/读声明/语句头符 case token.LH of $var ReadToken(token); /（$id,name） Enter(token.RH,Entry,s)； if s=true then Error(1); / 重复声

36、明错 ReadToken(); ReadToken(token);/: $int/$real case token.LH of $int SetAttribute(entry,newAddr,intType); $real SetAttribute(entry,newAddr,realType) end; ReadToken(); goto LD; /；,SetAttribute(entry,Addr,Type)：将标识符的地址和类型填入符号表的entry项内。,2021/2/23,北京化工大学信息科学与技术学院计算机系,41,$other while token!=$stop do if

37、token.LH=$id then Find(token.RH,entry,s); if s=false then Error(2); /无声明错 ChangeToken(entry) end,Find(name,entry,s):用name查找符号表，并在addr和type中给出其name的地址和类型。若已有同名项，则s取true值，否则取false。,ChangeToken(entry): 将被读token(标识符)的右半部改为entry地址.,2021/2/23,北京化工大学信息科学与技术学院计算机系,42,Procedure Semantic(); begin Creat; /建空符号

38、表 ReadToken(); /读掉$begin LD: ReadToken(token);/读声明/语句头符 case token.LH of $var ReadToken(token); /（$id,name） Enter(token.RH,Entry,s)； if s=true then Error(1); / 重复声明错 ReadToken(); ReadToken(token);/: $int/$real case token.LH of $int SetAttribute(entry,newAddr,intType); $real SetAttribute(entry,newAdd

39、r,realType) end; ReadToken(); goto LD; /； $other while token!=$stop do if token.LH=$id then Find(token.RH,entry,s) ; if s=false then Error(2); /无声明错 ChangeToken(entry) end,2021/2/23,北京化工大学信息科学与技术学院计算机系,43,2.5 Micro语言的目标代码,1.采用三地址形式的目标语言，其指令如下： add d1 d2 d3 (d3)=(d1)+(d2) mul d1 d2 d3 (d3)=(d1)*(d2)

40、sto d1 d2 (d2)=(d1) inp d1 输入d1 out d1 输出d1,2021/2/23,北京化工大学信息科学与技术学院计算机系,44,例：表达式 a*b+c*d 的目标代码,2021/2/23,北京化工大学信息科学与技术学院计算机系,45,Procedure GenCodeS(); begin LS: ReadNewToken(tk); case LH(tk) of $id Search(RH(tk), vAddr,vType)； ; $write ReadNewToken()； /读 ( GenCodeE(); ReadNewToken()； /读 ) $read Rea

41、dNewToken(tk)；/读变量 ; /生成输入代码 end; ReadNewToken(tk)；/读后续符 if tk=$semi then goto LS else SendCode(STOP) end, Micro语言的目标代码生成程序,2021/2/23,北京化工大学信息科学与技术学院计算机系,46, Micro语言的目标代码生成程序,Procedure GenCodeS(); begin LS: ReadNewToken(tk); case LH(tk) of $id Search(RH(tk), vAddr,vType)； ReadNewToken(); /:= GenCode

42、E(); pAddr:=SemanStack(top).addr; pType:=SemanStack(top).Type; if Equ(vType,pType) then Error(1); Sendcode(STO, pAddr, vAddr); POP;,赋值的左边,表达式代码生成程序,类型不相容错,Sendcode(code): 生成代码code送入代码区,sto d1 d2 (d2)=(d1),$write ReadNewToken()； /读 ( GenCodeE(); pAddr:=SemanStack(top).addr; Sendcode(OUT,pAddr); POP;

43、ReadNewToken()； /读 ) $read ReadNewToken(tk)；/读变量 Search(RH(tk),vAddr,vType); /求变量地址 Sendcode(INP,vAddr); /生成输入代码 end; ReadNewToken(tk)；/读后续符 if tk=$semi then goto LS else SendCode(STOP) end,2021/2/23,北京化工大学信息科学与技术学院计算机系,48, 无括号表达式的目标代码生成程序,Procedure GenCodeE(); begin L0: ReadNewToken(tok); L1: case

44、tok of ($id,entry) Search(entry,vAddr,vType) ; /求变量地址 push(vAddr,vType); goto L0 ; ($intC,val) push(val,int); goto L0 ; ($reaC,val) push(val,real); goto L0 ; $plus|$mult if top1 goto L1 end,判断优先级,2021/2/23,北京化工大学信息科学与技术学院计算机系,49,Procedure ProduceCode; begin if Equa(typ1,typ2) then Error() else temp:=NewAddr; SendCode(OP,Addr1,Addr1,temp); Pop(3); push(temp,typ1) end,ProduceCode ：用语义栈SemanStack的内容生成代码.,2021/2/23,北京化工大学信

展开阅读全文