编译原理综合训练-语义分析实验报告.docx

编译原理综合训练语义分析实验报告 指导老师： 班级：学生：zeadom学号：学生： 学号： 2011/6/29目录语言文法的形式化描述3语义规则3运行环境介绍5关键算法的流程图及文字解释51、本编译器的总框架52、在语义分析中的主要函数介绍53、产生布尔表达式74、while-do语句的语义分析85、词法、语法和语义分析的衔接8测试报告8附录12语言文法的形式化描述（bnf范式） 程序开始p-program i;sdn sc;定义语句sdn-sdsdn|nullsd-var int isdtsdt - null|,isdt复合语句sc-begin sn endsn-s;sn|null单个语句s-sd|sa|sif|sw|sc赋值语句sa-i:=e算术表达式e-cet|iet|(e)etet-ae|ce|de|null;c-+|-|*|/;布尔表达式b-eaebt|not b|(b)bt bt-db|nulla-|=|=|d-and|orif语句sif-if b then s selseselse-null|else s2while语句sw-while b do s语义规则（属性文法）产生式语 义 规 则i:=e gen(:=, e.place , ，entry(i) ee1+e2 e.place = newtemp; gen(+ , e1.place, e2.place , e.place ) ee1*e2 e.place = newtemp; gen(* , e1.place, e2.place , e.place ) e e1 e.place = newtemp; gen( , e1.place, , e.place ) e (e1) e.place = e1.place ei e.place = entry(i) 产生式语 义 规 则ei e.truelist:=makelist(nextquad); e.falselist:=makelist(nextquad+1); gen( jnz，entry(i)， ，0 )； gen( j ， ， ，0 ) ei1 r i2 e.truelist:=makelist(nextquad); e.falselist:=makelist(nextquad+1); gen( jr，entry(i1)，entry(i2)，0 )； gen( j ， ， ，0 ) e e1 e.truelist:= e1.falselist ; e.falselist:= e1.truelist ; e ( e1 ) e.truelist:= e1.truelist ; e.falselist:= e1.falselist ; m m.quad := nextquad ; ee1me2 backpatch(e1.truelist, m.quad ); e.truelist:=e2.truelist; e.falselist:=merge(e1.falselist,e2. falselist)ee1me2 backpatch(e1. falselist, m.quad ); e.truelist:= merge(e1. truelist, e2. truelist); e.falselist:= e2. falselist ee1me2backpatch(e1.truelist, m.quad );e.truelist:= e2.truelist;e.falselist:=merge(e1.falselist, e2.falselist) 产生式语 义 规 则sif e then m s1 backpatch(e.truelist, m.quad );s.nextlist:=merge(e.falselist, s1.nextlist) m m.quad := nextquad ; n n.nextlist:=makelist(nextquad);gen( j , , , 0 ) sif e then m1 s1 n else m2 s2 backpatch(e.truelist, m1.quad );backpatch(e.falselist, m2.quad );s.nextlist:=merge(s1.nextlist, n.nextlist, s2.nextlist) swhile m1 e do m2 s1 backpatch(s1.nextlist, m1.quad ); gen( j , , , m1.quad ); backpatch(e.truelist, m2.quad ); s.nextlist:= e.falselist s begin l end s.nextlist:=l.nextlist s a s.nextlist:= makelist() /*空链*/ l s l.nextlist:=s.nextlist ll1； m s backpatch(l1.nextlist, m.quad );l.nextlist:=s.nextlist 运行环境介绍运行环境是devc+dev-c+是一个c&c+开发工具，它是一款自由软件，遵守gpl协议。它集合了gcc、mingw32等众多自由软件，并且可以取得最新版本的各种工具支持，而这一切工作都是来自全球的狂热者所做的工作，并且你拥有对这一切工具自由使用的权利，包括取得源代码等，前提是你也必须遵守gnu协议。dev-c+每一天都在进步着，因为它是一个自由软件。 dev-c+是一个非常实用的编程软件，多款著名软件均由它编写而成，它在c的基础上，增强了逻辑性关键算法的流程图及文字解释1、本编译器的总框架2、在语义分析中的主要函数介绍backpatch(int list,int quad)代码：void backpatch(int list,int patch) int tmp; while(list) tmp = list; list = rsstmp.jump; rsstmp.jump = patch; merge (int list1,int list2)代码：int merge(int list1, int list2) int tmp = list2; if(list2=0)list2 = list1; else while(rsstmp.jump) tmp = rsstmp.jump; rsstmp.jump = list1; return list2;3、产生布尔表达式4、while-do语句的语义分析5、词法、语法和语义分析的衔接1、词法分析是分析输入代码产生词法三元式的程序。读入代码，并将代码中的单词分解成词法三元式。2、语法分析读入词法三元式，并根据词法三元式对句子进行语法分析。3、语义分析嵌入在语法分析中。根据语法分析中得到的句子类型和语义四元式产生规则，产生四元式测试报告（测试用例，测试结果）测试用例输入程序（文件input.txt）：program example;var int j,m,n; begin /*there is a comment*/ j:=6; m:=3; /there is a comment n:=j+m; if n=3 and n10 then j:=j*4; while a=,8)(16,3,8)(12,and,8)(15,n,8)(23,10)(16,10,10)(7,then,10)(15,j,10)(26,:=,10)(15,j,10)(28,*,10)(16,4,10)(24,;,10)(10,while,11)(15,a,11)(23,=,n,3,106)105(j,-,-,111)106(j,n,10,113)112(j,-,-,115)113(*,j,4,t3)114(:=,t3,-,j)115(j:22, :23,;:24,:25,:=:26,:27, *:28,/:29,.:30,=:32,:33 def isletter(): global ch if ch=none: return false else: return ch.isalpha()def isdigit(): global ch if ch=none: return false else: return ch.isdigit()def concat(): global code global ch code = code+chdef getchar(l,i): if len(l)=i or i0: return none else: return lidef getstr():global codeglobal key_wordsglobal lltype = 0state = nonestr = ;if code=none:str = u(0,+code+,%d)%llelif code in key_words:if(key_wordscode=25):str = error code in line %dn%llstr = str + error code :else:str= u(+key_wordscode+u,+code+,%d)%llelif code.isdigit():str= (16,+code+,%d)%llelse:str= (15,+code+,%d)%llreturn strll = 0flag = ;if _name_=_main_: src = rinput.txt outfile = routput.txt if not os.path.exists(src): print cannot open file,src else:inputf = open(src,r)outputf = open(outfile,w)annotation = 0ll = 0for line in inputf:ll=ll+1i = 0l = len(line)while i=len(line):breakcode = ch = getchar(line,i)i = i+1if annotation=1:if ch=* and getchar(line,i)!=none and getchar(line,i)=/:str = annotation end in line %dn%lloutputf.write(str)annotation = 0i=i+1continueif ch=/ and getchar(line,i)!=none and getchar(line,i)=/:outputf.write(line annotation in line %dn%ll)i = i+1breakif ch=none:breakelif ch=/ and getchar(line,i)!=none and getchar(line,i)=*:str = annotation start in line %dn%lloutputf.write(str)i=i+1annotation = 1elif ch= or ch=n or ch=t:continueelif isletter():while isletter() or isdigit():concat()ch = getchar(line,i)i=i+1i=i-1str = getstr()str = str+noutputf.write(str)continueelif isdigit():while isdigit():concat()ch = getchar(line,i)i=i+1i=i-1str = getstr()str = str+noutputf.write(str)continueelif ch in key_words:concat()ch = getchar(line,i)i=i+1if ch!=none and (code+ch) in key_words:concat()str = getstr()str = str+noutputf.write(str)else:i=i-1str = getstr()str = str+noutputf.write(str)else:str = error in line %dn%lloutputf.write(str)outputf.write(error code +ch+n);*资源文件（resource.h）*#ifndef resource_h_zeadom#define resource_h_zeadom#define $program 1#define $begin 2#define $end 3#define $var 4#define $integer 5#define $if 6#define $then 7#define $else 8#define $do 9#define $while 10#define $int 11#define $and 12#define $or 13#define $not 14#define $flag 15#define $num 16#define $add 17#define $sub 18#define $left 19#define $right 20#define $eq 21#define $gt 22#define $lt 23#define $ 24#define $copy 26#define $comma 27#define $mul 28#define $div 29#define $point 30#define $loe 31#define $goe 32#define $ne 33#endif*语义分析头文件（semantic.h）*#ifndef zeadom_semantic_h#define zeadom_semantic_h#include stringusing namespace std;#includeiostream#include fstream#include sstreamint quad,vart;int nextquad() return quad+;string nextt() vart+; string temp = t; stringstream ss; ssvart; temp = temp+ ss.str(); return temp;void semantic_init() vart=0; quad=100;struct siyuanshi string op,par1,par2,result; bool hasop,haspar1,haspar2,hasresult; bool isjump; int jump; siyuanshi() op = par1 = par2 = result = ; hasop = haspar1 = haspar2 = hasresult = false; jump = 0; isjump=false; void setop(string arg) op = arg; hasop = true; void setpar1(string arg) par1 = arg; haspar1 = true; void setpar2(string arg) par2 = arg; haspar2 = true; void setresult(string arg) result = arg; hasresult = true; void setjump(int arg) jump = arg; isjump = true; void output(ofstream &s) s (op,; if(haspar1) spar1,; else s-,; if(haspar2) spar2,; else s-,; if(isjump) sjump)endl; else if(hasresult) sresult)endl; else s-)endl; ;siyuanshi rss10000;struct estruct string lexval; estruct()lexval=;struct bstruct int truelist; int falselist; bstruct()truelist=falselist=0;struct mstruct int quad; mstruct()quad=0;void backpatch(int list,int patch) int tmp; while(list) tmp = list; list = rsstmp.jump; rsstmp.jump = patch; int merge(int list1, int list2) int tmp = list2; if(list2=0)list2 = list1; else while(rsstmp.jump) tmp = rsstmp.jump; rsstmp.jump = list1; return list2;void semantic_output() ofstream out(semantic.out); for(int i=100;iquad;i+) outi; rssi.output(out); out.close();struct sstruct int nextlist; sstruct()nextlist=0;struct nstruct int nextlist; nstruct()nextlist=0;#endif*语法和语义分析程序（main.cpp）*#include iostreamusing namespace std;#include string.h#include string#include stdlib.h#include stdio.h#include resource.h#include semantic.h#define deal(s) if(!(s)return false;#define pdeal(s) if(!(s)cout没有找到文件结尾（程序是否未完成？）line; if(!cin)cin.clear();normal = false;return false; while(line0!=() cinline; att=; int i,j=0; int l = line.length(); i=3; if(line2=0&line2=9) type = (line1-0)*10+(line2-0); i=4; else type = line1-0; for(;linei!=,;i+) att.push_back(linei); for(i=0;i=0&linei=9) pos = pos*10 + (linei-0); i+; return true; word;/定义函数 bool error(string s);bool p();bool sn(sstruct &ss);bool s(sstruct &ss);bool sdn();bool sd();bool sdt();bool sa();bool sif(sstruct &ss);bool selse(sstruct &ss);bool sw(sstruct &ss);bool sc(sstruct &ss);bool b(bstruct &bs);bool bt(bstruct &bs);bool e(estruct &es);bool et(estruct &es);bool a();bool c();bool d();/函数实现 bool error(string s) printf(语法错误：在第%d行n,word.pos); coutsprogram i;sdn sc;bool p() pdeal(word.normal); bool ret = true; sstruct ss; if(word.type!= $program )error(缺少程序定义语句);ret = false; else pdeal(word.readnext(); if(word.type!=$flag)error(缺少程序名);ret = false; else pdeal(word.readnext(); if(word.type!=$)error(缺少语句结束标志); ret = false; else pdeal(word.readnext(); if(!sdn()ret = false; pdeal(word.normal); if(!sc(ss)ret = false; pdeal(word.normal); if(word.type!=$)error(缺少程序结束标志); ret = false; cout程序s;sn|nullbool sn(sstruct &ss) deal(word.normal); bool ret = true; while(word.type!=$if&word.type!=$flag&word.type!=$var&word.type!=$while&word.type!=$begin) if(word.type=$end) return ret; error(语法错误); ret = false; deal(word.readnext(); if(!s(ss)ret = false; backpatch(ss.nextlist,quad); deal(word.normal); if(word.type!=$)ret = false; error(缺少行终止符); else deal(word.readnext(); if(!sn(ss)ret = false; deal(word.normal); return ret;/s-sd|sa|sif|sw|scbool s(sstruct &ss) deal(word.normal); bool ret = true; switch(word.type) case $if:return sif(ss); case $var: ss.nextlist=0; return sd(); case $flag: ss.nextlist=0; return sa(); case $while:return sw(ss); case $begin:return sc(ss); default: error(语法错误); /sdn-sd;sdn|nullbool sdn() deal(word.normal); if(word.type=$begin) return true; bool ret = true; while(true) while(word.type!=$begin&word.type!=$var) error(语法错误); deal(word.readnext(); if(word.type=$var) if(!sd() while(true) if(word.type=$|word.type=$begin)break; deal(word.readnext(); else if(word.type!=$) error(缺少行终止符); ret = false; else deal(word.readnext(); if(word.type=$begin)break; return ret;/sd-var int isdtbool sd() deal(word.normal); bool ret = true; if(word.type!=$var) error(语法错误); return false; else word.readnext(); deal(word.normal); if(word.type!= $int ) error(语法错误); return false; else word.readnext(); deal(word.normal); if(word.type!=$flag) error(语法错误); return false;