compiler2_一个微小编译器

1、第二章第二章 一个微小编译器一个微小编译器2.1 Micro2.1 Micro语言描述语言描述2.2 Micro2.2 Micro语言的词法分析语言的词法分析2.3 Micro2.3 Micro语言的语法分析语言的语法分析2.4 Micro2.4 Micro语言的语义分析语言的语义分析2.5 Micro2.5 Micro语言的目标代码语言的目标代码第二章第二章 一个微小编译器一个微小编译器2.1 Micro2.1 Micro语言描述语言描述 MicroMicro语言语言（称Micro,Pascal语言的子集）以开头：保留字：begin,end,var,read,write,int,real标识

2、符：字母/数字串以开头：整常数：数字开头的数字串实常数：整数.整数：+，-，*，/，(，)，:，:=，;，.：enter2.2 Micro2.2 Micro语言的词法分析（单词的分析）语言的词法分析（单词的分析）. . 特点：特点： 不依赖于语法分析，只依赖于单词的文法定义. . 任务：任务： 程序的字符串序列Token序列（单词的内部表示）保留字：$begin, $end, $var, $read, $write, $int, $real标识符：($id，标识符)整常数：($intC，整常数)实常数：($reaC，实常数)符号词：$plus,$sub,$mult,$div,$Lparen,$

3、Rparen,$colon,$assig,$semi,$line,$stop(+，-，*，/，(，)，:，:=，;，enter，.)输入输出例：begin var x1:real;var z1:real;x1:=0.5;z1:=x1+56;write(z1+2.3);read(x1)end.$begin$var($id,x1)$colon$real$semi$line$var($id,z1)$colon$real$semi$line($id,x1)$assig($reaC,0.5)$semi$line($id,z1)$assig($id,x1)$plus($intC,56)$semi$line

4、$write$Lparen($id,z1)$plus($reaC,2.3)$Rparen$semi$line$read$Lparen($id,x1)$Rparen$line$end$stop# 程序的字符串序列Token序列3.Micro3.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”

5、 GenToken($var); “int” GenToken($int); “real” GenToken($real); “read” GenToken($read); “write” GenToken($write); other GenToken($id,name); end ; Noblank(ch):跳过空格符串将第一个非空格字符读到ch中（删除空格符）例：例：begin var x1:real;var z1:real;x1:=0.5;z1:=x1+56;write(z1+2.3);read(x1)end. 0.9 Constant(class,C); GenToken(Class

6、,C); ( GenToken($Lparen); Read(ch); ) GenToken($Rparen); Read(ch); + GenToken($plus); Read(ch); * GenToken($mult); Read(ch); ; GenToken($semi); Read(ch); : Read(ch); if ch= then GenToken($assig); Read(ch) else GenToken($colon) . GenToken($stop); Read(ch); enter GenToken($line); Read(ch); other Lexic

7、alError(ch) end end 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)(1)读读标识符，保留字（关键字）Identifier(name)：从输入流把当前标识符名读到name中（它可能是保留字）。在调用时，当前字符一定是字母，且已被读到ch中。isLetter(ch):如果ch是字母，

8、则取true，否则取false。isDigit(ch):如果ch是数字，则取true，否则取false。Procedure Constant(class:classType,C:ConsstType);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:=N1End Micro语言的词法分析程序的相关子程序相关子程序(2)(2)读整读整/ /实

9、常数实常数Constant(class,C)：从输入流读到当前常数，并在：从输入流读到当前常数，并在class中给出常数的中给出常数的类型类型标志，标志，C中给出常数的二中给出常数的二进制进制数值数值。调用时当前字符定是数字（在。调用时当前字符定是数字（在ch中）中）整数整数(小数点左部小数点左部)整数整数(小小数点右部数点右部)Micro语言的词法分析程序的相关子程序相关子程序(3)(3)读整常数读整常数IntConst(N,L):从输入流读当前整常数，并在从输入流读当前整常数，并在N中给中给出所读常数的二出所读常数的二(十十)进制值，在进制值，在L中给出整常数的中给出整常数的位数。调用时当

10、前字符应是数字。位数。调用时当前字符应是数字。Procedure IntConst(N,L);Begin N:=Num(ch); L:=1; Read(ch); while isDigit(ch) do N:=N*10+Num(ch); L:=L+1; Read(ch) End Num(ch):表示数字字符表示数字字符ch对应的二对应的二(十十)进制值。进制值。3.语法分析程序思路语法分析程序思路：声明检查：begin var id: real; (声明的位置) 赋值语句 标识符单词 输入语句 表达式 整/实常数语句检查： 输出语句 左括号 后继符（语句末符号）(；enter end)2.2.

11、 MicroMicro语言的语法分析语言的语法分析 1.1.任务：任务： 检查程序是否有语法（语法结构）上的错误 2.输入输入：词法分析后得到的Token表输出输出：具体语法错误提示和语法全部正确提示位置的正确性位置的正确性4.Micro4.Micro语言的语法分析程序语言的语法分析程序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 toke

12、n=$line then ReadToken(token); if token=$var then goto LD;Match(kind,n)：读当前Token，并检查Token.LH=kind？若不等，则打出错误编号n。Token.LH：Token的左半部。Token.RH：Token的右半部。ReadToken(token):把当前Token读到token中声声明明 LS:case token of $write Match($Lparen,7); Expr(); Match($Rparen,8); $read Match($Lparen,9); Match($id,10); Match(

13、$Rparen,11); $id Match($assig,12); Expr(); other error(13) end; ReadToken(token); /读语句的后继符 语句单单词词后继符后继符 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 endMicro语

14、言的语法分析子程序子程序表达式的语法检查表达式的语法检查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 goto LF; Other BackToken Ende

15、ndTokenToken指针指针回溯一步回溯一步Error 1 程序头不是beginError 2 变量声明头不是varError 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语言的具体语法错误：Error 11 “read (id”后 不是”）” Error 12 赋值语句左部 不是“:=”Error 13 语

16、句头单词错Error 14 程序结束符错Error 15 语句后继符错Error 16 缺“(E)”中的 闭括号Error 17 运算分量的 后继符错2.4 Micro2.4 Micro语言的语义分析语言的语义分析1.1.任务：任务：语法分析：只检查位置的正确性不检查他本身(语义)的正确性语义分析：主要是类型匹配问题 将Token序列中的标识符转换为（$id,entry） (entry：变量的属性表（符号表属性表（符号表）地址)X1*:X1Realx1AddrZ1*:Z1 Realz1Addr（X*表示变量名（或常数）X的符号表地址）.Micro.Micro语言的语义分析程序语言的语义分析程序

17、Procedure Semantic(); begin Creat; /建空符号表 ReadToken(); /读$begin LD: ReadToken(token); case token.LH of $var ReadToken(token); 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 SetAttr

18、ibute(entry,newAddr,realType) end; ReadToken(); goto LD; /；Enter(name,Entry,s):将将name填入符号表，并在填入符号表，并在entry中给出其表项地址中给出其表项地址。若已有同名项，则。若已有同名项，则s取取true值，否则取值，否则取false。SetAttribute(entry,Addr,Type)：将标识符的：将标识符的地址和类型填地址和类型填入符号表的入符号表的entry项内项内 $other while token!=$stop do if token.LH=$id then Find(token.RH,

19、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地址2.5 Micro2.5 Micro语言的目标代码语言的目标代码1.采用三地址形式三地址形式的目标语言，其指令如下：add d1 d2 d3 (d3)=(d1)+(d2) mul d1 d2 d3 (d3)=(

20、d1)*(d2) sto d1 d2 (d2)=(d1) inp d1 输入d1 out d1 输出d1例：表达式 a*b+c*d 的目标代码信息栈余下表达式动作说明目标代码#a*b+c*d # Push(a)#a*b+c*d # Push(*)#a*b+c*d # Push(b)#a*b+c*d # 产生mul代码；pop(3); push(t1)Mul a b t1#t1+c*d # Push(+)#t1+c*d # Push(c).2. Micro2. Micro语言的目标代码生成程序语言的目标代码生成程序Procedure GenCodeS(); begin LS: ReadNewTo

21、ken(tk); case LH(tk) of $id Search(RH(tk),vAddr,vType)； ReadNewToken(); /:= GenCodeE(); eAddr:=SemanStack(top).addr; eType:=SemanStack(top).Type; if Equ(vType,eType) then Error(1); Sendcode(STO,eAddr,vAddr); POP;Search(RH(tk),vAddr,vType):用用符号表的某项地址符号表的某项地址entry求变求变量的地址和类型。量的地址和类型。SemanStack(top):表示

22、表示SemanStack的顶元素的顶元素Sendcode(code):把代码把代码code送入送入代码区代码区赋值的左边赋值的左边赋值的右边赋值的右边 $write ReadNewToken()； /读 ( GenCodeE(); eAddr:=SemanStack(top).addr; Sendcode(OUT,eAddr); POP; ReadNewToken()；/读 ) $read ReadNewToken(tk)； Search(RH(tk),vAddr,vType);/求变量地址 Sendcode(INP,vAddr); end; ReadNewToken(tk)； if tk=$

23、semi then goto LS else SendCode(STOP)end无括号表达式的目标代码生成程序无括号表达式的目标代码生成程序Procedure GenCodeE();begin L0: ReadNewToken(tk); L1: case tk 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 t

24、op1 & SemanStack(top-1)1 then ProduceCode; goto L1end判断优先级判断优先级ProduceCode ：用语义栈：用语义栈SemanStack的内容生成代码的内容生成代码Procedure ProduceCode;begin if Equa(typ1,typ2) then Error() else temp:=NewAddr; SendCode(OP,Addr1,Addr1,temp); Pop(3);push(temp,typ1) endProduceCode ：用语义栈：用语义栈SemanStack的内容生成代码的内容生成代码带括号表达式的目标代码生成程序带括号表达式的目标代码生成程序P