编译原理piler一个微小编译器

例一个微小编译器Micro语言描述Micro语言的词法分析Micro语言的语法分析Micro语言的语义分析Micro语言的目标代码化工大学信息科学与技术学院计算机系22020/11/1例一个微小编译器0.1

Micro语言描述Micro语言（称Micro,Pascal语言的子集）beginvar

x1:real;var

z1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.Main(){

float

x1;float

z1;x1=0.5;z1=x1+56;scanf(“%f”,&x1);printf(“%f”,z1+2.3);}PascalC化工大学信息科学与技术学院计算机系32020/11/1Pascal与C语言区别PascalCBegin…end{…}int

x;

//变量var x1:

int;Float,doublerealX=0.5; //赋值=

<>

//判等，判不等Read(…)X:=0.5;==

!=Scanf(…)/

getchar()Write(…)Printf(…)语句以分号分隔，但end前的语句没有符号语句以分号分隔程序结束.无.ProcedureFunctionVoid

function_name(…)Int/floatfunction_name(…)If(…)…else…If

(…)

then…else…While(…)…While(…)

do

………beginvar

x1:real;var

z1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.例一个微小编译器0.1

Micro语言描述Micro语言（称Micro,Pascal语言的子集）程序组成性语句使用性语句赋值语句输入语句输出语句beginvar

x1:real;var

z1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.化工大学信息科学与技术学院计算机系52020/11/10.2

Micro语言的词法分析（单词的分析）１.特点：不依赖于语法分析，只依赖于单词的文法定义Micro的有用单词的种类：以字母开头：保留字：begin,end,var,read,write,int,real标识符：字母/数字串以数字开头：整常数：数字开头的数字串实常数：整数.整数符号词：+，-，*，/，(，)，:，:=，;，.控制词：enter化工大学信息科学与技术学院计算机系62020/11/1保留字：$begin,$end,$var,$read,$write,$int,

$real标识符：($id，标识符)

整常数：($intC，整常数)实常数：($reaC，实常数)符号词：$plus,$sub,$mult,$div,$Lparen,$Rparen,$colon,$assig,$semi,$line,$stop(+，-，*，/，(，)，:，:=，;，enter，.)输入输出程序的字符串序列Token序列（单词的

表示）２.任务：化工大学信息科学与技术学院计算机系72020/11/1程序的字符串序列例：beginvar

x1:real;var

z1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.$begin$line$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$read$Lparen($id,x1)$Rparen$semi$line$write$Lparen($id,z1)$plus($reaC,2.3)$Rparen$line$end$stop#Token序列化工大学信息科学与技术学院计算机系88/11/13.Micro语言的词法分析程序Procedure

scanner();begin

while

~Eof

do

{Noblank(ch);case

ch

of{Identifier(name);‘A’..’Z’|’a’..’z’case

name

of“begin”“end”GenToken($begin);GenToken($end);GenToken($var);GenToken($int);GenToken($real);GenToken($read);GenToken($write);“var”“int”“real”“read”“write”otherGenToken($id,name); end

};Noblank(ch):跳过空格符串将第一个非空格字符读到ch中（删除空格符）例：beginvar

x1:real;var

z1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.化工大学信息科学与技术学院计算机系99/11/1‘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);

Read(ch);‘:’

{Read(ch);if

ch=‘=’

then

{GenToken($assig);

Read(ch)}else

GenToken($colon)}GenToken($stop);

Read(ch);GenToken($line);

Read(ch);LexicalError(ch)‘.’‘enter’‘other’end}end化工大学信息科学与技术学院计算机系102020/11/1Procedure

Identifier(name:string);Beginname:=“

”;Append(name,ch);Read(ch);while isLetter(ch)

or

isDigit(ch)do{

Append(name,ch);Read(ch);}EndIdentifier(name)：从输入流把当前标识符名读到name中（它可能是保留字）。在调用时，当前字符一定是字母，且已被读到ch中。isLetter(ch):如果ch是字母，则取true，否则取false。isDigit(ch):如果ch是数字，则取true，否则取false。Micro语言的词法分析程序的相关子程序(1)——读标识符，保留字（关键字）化工大学信息科学与技术学院计算机系112020/11/1BeginIntConst(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}EndConstant(class,C)：从输入流读到当前常数，并在class中给出常数的类型标志，C中给出常数的二进制数值。调用时当前字符定是数字（在ch中）整数(小数点左部)整数(小数点右部)Micro语言的词法分析程序的相关子程序(2)——读整/实常数Procedure

Constant(class:classType,C:ConsstType);化工大学信息科学与技术学院计算机系122020/11/1IntConst(N,L):从输入流读当前整常数，并在N中给出所读常数的二(十)进制值，在L中给出整常数的位数。调用时当前字符应是数字。Num(ch):表示数字字符ch对应的二(十)进制值。Micro语言的词法分析程序的相关子程序(3)——读整常数Procedure

IntConst(N,L);BeginN:=Num(ch);

L:=1;

Read(ch);while isDigit(ch)

do{N:=N*10+Num(ch);L:=L+1;

Read(ch)

}End化工大学信息科学与技术学院计算机系132020/11/11.任务：位置的正确性0.３Micro语言的语法分析检查程序是否有语法（语法结构）上的错误输入：词法分析后得到的Token表输出：具体语法错误提示和语法全部正确提示语法分析程序思路：检查：begin

var id:

real;

(

的位置)赋值语句

标识符单词

输入语句

表达式

整/实常数语句检查：

输出语句

左括号后继符（语句末符号）(；enter

end)化工大学信息科学与技术学院计算机系142020/11/1LD:

Match($id,3);Match($colon,4);Match($intC/$reaC,5);Match($semi,6);ReadToken(token);if

token=$line

thenReadToken(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中4.Micro语言的语法分析程序Procedure

Parser();begin

Match($begin,1);Match($var,2);例：beginvar

x1:real;var

z1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.化工大学信息科学与技术学院计算机系152020/11/1LS:case

token

of$write

{Match($Lparen,7);Expr();

Match($Rparen,8)};$read

{Match($Lparen,9);

Match($id,10);Match($Rparen,11)};{Match($assig,12);

Expr()};{error(13)}$idotherend;ReadToken(token); //读语句的后继符语句单词后继符例：beginvar

x1:real;var

z1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.化工大学信息科学与技术学院计算机系162020/11/1casetokenof$semi$line$end{ReadToken(token);iftoken=$line

thenReadToken(token);goto

LS};Match($end);{ReadToken(token);if

token=$stopthenSTOPelseError(14)}other

{Error(15)}endend例：beginvar

x1:real;var

z1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.化工大学信息科学与技术学院计算机系172020/11/12020/11/1化工大学信息科学与技术学院计算机系Micro语言的语法分析子程序—表达式的语法检查Procedure

Expr();beginLF:ReadToken(token);case

token

ofskip;skip;skip;begin

Expr(); Match($Rparen,16)

end;error(17)($id,..)($intC,..)($reaC,..)$Lparenotherend;ReadToken(token); (接右)case token

of

(接左)$plus$multOtherEndendgoto

LF;goto

LF;BackTokenToken指针回溯一步例：beginvar

x1:real;var

z1:real;x1:=0.5;z1:=x1+56;read(x1);write(z1+2.3)end.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

语句头单词错Error

14

程序结束符错Error

15

语句后继符错Error

16

缺“(E)”中的闭括号Error

17

运算分量的后继符错化工大学信息科学与技术学院计算机系192020/11/1X1Realx1AddrZ1Realz1Addr0.4 Micro语言的语义分析1.任务：语法分析：只检查位置的正确性查他本身(语义)的正确性语义分析：主要是类型匹配问题将Token序列中的标识符转换为（$id,entry）(entry：变量的属性表（符号表）地址)X1*:Z1*:（X*表示变量名（或常数）X的符号表地址）化工大学信息科学与技术学院计算机系202020/11/1２.Micro语言的语义分析程序Procedure

Semantic();begin

Creat; //建空符号表ReadToken(); //读$beginLD:

ReadToken(token);casetoken.LH

of$var {ReadToken(token);

Enter(token.RH,Entry,s)；if

s=true

then

Error(1); //

重复

错ReadToken();

ReadToken(token);//:

$int/$realcase

token.LH

of$int

SetAttribute(entry,newAddr,intType);$real

SetAttribute(entry,newAddr,realType)end;ReadToken();

gotoLD};

//；Enter(name,Entry,s):将name填入符号表，并在entry中给出其表项地址。若已有同名项，则s取true值，否则取false。SetAttribute(entry,Addr,Type)：将标识符的地址和类型填入符号表的entry化工大学信息科学与技术学院计算机系212020/11/1$other

while token!=$stop

do

{if

token.LH=$id

thenFind(token.RH,entry,s)

;错ifs=false

then

Error(2);

//无ChangeToken(entry)}end;Find(name,entry,s):用name查找符号表，并在addr和type中给出其name的地址和类型。若已有同名项，则s取true值，否则取false。ChangeToken(entry):将被读token(标识符)的右半部改为entry地址化工大学信息科学与技术学院计算机系222020/11/10.5 Micro语言的目标代码1.采用三地址形式的目标语言，其指令如下：add

d1

d2d3(d3)=(d1)+(d2)mul

d1

d2d3(d3)=(d1)*(d2)sto

d1

d2inp

d1out

d1(d2)=(d1)输入d1输出d1化工大学信息科学与技术学院计算机系232020/11/1例：表达式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)...…………………化工大学信息科学与技术学院计算机系242020/11/12.

Micro语言的目标代码生成程序Procedure

GenCodeS();beginLS:ReadNewToken(tk);caseLH(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):表示SemanStack的顶元素Sendcode(code):把代码code送入代码区赋值的左边赋值的右边类型不相容错化工大学信息科学与技术学院计算机系252020/11/1$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=$semi

then

goto

LS

else

SendCode(STOP)end化工大学信息科学与技术学院计算机系262020/11/1化工大学信息科学与技术学院计算机系27无括号表达式的目标代码生成程序Procedure

GenCodeE();beginL0:ReadNewToken(tk);L1:

case

tk

of($id,entry){Search(entry,vAddr,vType);//求变量地址push(vAddr,vType); goto

L0

};{push(val,int); goto

L0

};{push(val,real); goto

L0

};($intC,val)($reaC,val)$plus|$multif top>1

&&

SemanStack(top-1)<<tokthen

push(tok);

gotoL0Else

ProduceCode;

gotoL1if

top>1then

{ ProduceCode;

goto

L1}Otherend2020/11/1判断优先级ProduceCode

：用语义栈SemanStack的内容生成代码Procedure

ProduceCode;beginif

~Equa(typ1,typ2) then

Error()else {

temp:=NewAddr;SendCode(OP,Addr1,Addr1,temp);Pop(3);push(temp,typ1)}endProduceCode

：用语义栈SemanStack的内容生成代码化工大学信息科学与技术学院计算机系282020/11/1带括号表达式的目标代码生成程序Procedure

GenCodeE();beginpushOperator(•);L0:

ReadNewToken(tk);L1:

case

tkof($id,entry)($intC,val){Search(entry,vAddr,vType)；pushOperand(vAddr,vType); goto

L0};{pushOperand(val,int); goto

L0

};($reaC,val) {pus