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、符：字母/數(shù)字串以開頭：整常數(shù)：數(shù)字開頭的數(shù)字串實常數(shù)：整數(shù).整數(shù)：+，-，*，/，(，)，:，:=，;，.：enter2.2 Micro2.2 Micro語言的詞法分析（單詞的分析）語言的詞法分析（單詞的分析）. . 特點：特點： 不依賴于語法分析，只依賴于單詞的文法定義. . 任務：任務： 程序的字符串序列Token序列（單詞的內部表示）保留字：$begin, $end, $var, $read, $write, $int, $real標識符：($id，標識符)整常數(shù)：($intC，整常數(shù))實常數(shù)：($reaC，實常數(shù))符號詞：$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是數(shù)字，則取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、常數(shù)實常數(shù)Constant(class,C)：從輸入流讀到當前常數(shù)，并在：從輸入流讀到當前常數(shù)，并在class中給出常數(shù)的中給出常數(shù)的類型類型標志，標志，C中給出常數(shù)的二中給出常數(shù)的二進制進制數(shù)值數(shù)值。調用時當前字符定是數(shù)字（在。調用時當前字符定是數(shù)字（在ch中）中）整數(shù)整數(shù)(小數(shù)點左部小數(shù)點左部)整數(shù)整數(shù)(小小數(shù)點右部數(shù)點右部)Micro語言的詞法分析程序的相關子程序相關子程序(3)(3)讀整常數(shù)讀整常數(shù)IntConst(N,L):從輸入流讀當前整常數(shù)，并在從輸入流讀當前整常數(shù)，并在N中給中給出所讀常數(shù)的二出所讀常數(shù)的二(十十)進制值，在進制值，在L中給出整常數(shù)的中給出整常數(shù)的位數(shù)。調用時當

10、前字符應是數(shù)字。位數(shù)。調用時當前字符應是數(shù)字。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):表示數(shù)字字符表示數(shù)字字符ch對應的二對應的二(十十)進制值。進制值。3.語法分析程序思路語法分析程序思路：聲明檢查：begin var id: real; (聲明的位置) 賦值語句 標識符單詞 輸入語句 表達式 整/實常數(shù)語句檢查： 輸出語句 左括號 后繼符（語句末符號）(；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*表示變量名（或常數(shù)）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 # 產(chǎn)生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送入送入代碼區(qū)代碼區(qū)賦值的左邊賦值的左邊賦值的右邊賦值的右邊 $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判斷優(yōu)先級判斷優(yōu)先級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