chapter03文法和语言.ppt

北京化工大学 信息科学与技术学院计算机系 赵瑞莲 rlzhao@,,,编译原理,,,2019/1/28,北京化工大学信息科学与技术学院计算机系,2,,0.1 Micro语言描述,Micro语言的定义,P  begin VDL;SL end. VDL  VD | VD ; VDL VD  var id : T SL  S | S ; SL S  id:= E | write(E) | read(id) T  int | real E  id | num | E + E | E * E |(E),2019/1/28,北京化工大学信息科学与技术学院计算机系,3,,0.1 Micro语言描述,Micro语言（称Micro,Pascal语言的子集）,2019/1/28,北京化工大学信息科学与技术学院计算机系,4,,,● Micro语言中单词的种类：,0.2 Micro语言的词法分析,１. 特点： 不依赖于语言的语法定义 ，只依赖于单词的文法定义2019/1/28,北京化工大学信息科学与技术学院计算机系,5,,程序的字符串序列 Token序列 （单词的内部表示）,Token定义： 二元组（单词种类，单词自身值） 标识符: ($id,标识符）如($id,x) 整常数: ($intC,整常数）如（$intC,5) 实常数: ($realC,实常数）如($realC,0.5) 保留字: ($begin,-), ($end,-), ($var,-) … 符号词: ($plus,-), ($mult,-), ($LParen,-), ($Rparen, -), ($colon,-),($assig,-),($semi,-) 换行符: ($line,-), ($stop,-),2019/1/28,北京化工大学信息科学与技术学院计算机系,6,Micro的词法分析,读当前字符流，直至文件结束。

如果是： (1)标识符时判断是保留字还是变量标识 符，构造Token表示； (2)数字时判断是整型还是实型，构造 Token表示； (3)构造其它合法的符号的Token表示； (4)遇到非法符号则报错0.2 Micro语言的词法分析,3. 词法分析过程,2019/1/28,北京化工大学信息科学与技术学院计算机系,7,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); “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); 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; read(x1); write(z1+2.3) end.,2019/1/28,北京化工大学信息科学与技术学院计算机系,8,,,,1.任务： 检查程序是否有语法（语法结构）上的错误。

2.输入：词法分析后得到的Token表 输出：具体语法错误提示和语法全部正确提示0.３ Micro语言的语法分析,说明：语法分析只用到单词的Token表示， 并不改变单词的Token表示2019/1/28,北京化工大学信息科学与技术学院计算机系,9,,,声明检查：begin var id: real; (声明的位置) 赋值语句 标识符 单词 输入语句 表达式 整/实常数 语句检查： 输出语句 左括号 后继符（语句末符号）(； ， end),0.３ Micro语言的语法分析,3.语法分析程序思路：,2019/1/28,北京化工大学信息科学与技术学院计算机系,10,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; 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); 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,2019/1/28,北京化工大学信息科学与技术学院计算机系,11,,,0.4 Micro语言的语义分析,1.任务： 语法分析：只检查语法结构的正确性 不检查他本身(语义)的正确性,语义分析： 检查语义错误：没有声明；重复声明；类型不相容 将Token序列中的标识符转换为（$id, entry） (entry表示标识符在符号表中的地址),2019/1/28,北京化工大学信息科学与技术学院计算机系,12,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); // 重复声明错 ReadToken(); ReadToken(token);//: $int/$real case token.LH of $int SetAttribute(entry,newAddr,intType); $real SetAttribute(entry,newAddr,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,2019/1/28,北京化工大学信息科学与技术学院计算机系,13,,,0.5 Micro语言的目标代码,1.采用三地址形式的目标语言，其指令如下： add d1 d2 d3 (d3)=(d1)+(d2) mul d1 d2 d3 (d3)=(d1)*(d2) sto d1 d2 (d2)=(d1) inp d1 输入d1 out d1 输出d1,2019/1/28,北京化工大学信息科学与技术学院计算机系,14,,例：表达式 a*b+c*d 的目标代码,2019/1/28,北京化工大学信息科学与技术学院计算机系,15,,● Micro语言的目标代码生成程序,Procedure GenCodeS(); begin LS: ReadNewToken(tk); case LH(tk) of $id {Search(RH(tk), vAddr,vType)； ReadNewToken(); //:= GenCodeE(); 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),2019/1/28,北京化工大学信息科学与技术学院计算机系,16,$write {ReadNewToken()； //读 ( GenCodeE(); pAddr:=SemanStack(top).addr; Sendcode(OUT,pAddr); 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,2019/1/28,北京化工大学信息科学与技术学院计算机系,17,,● 无括号表达式的目标代码生成程序,Procedure GenCodeE(); begin L0: ReadNewToken(tok); L1: case 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 。