编译原理语义分析实验报告 免费

编译原理综合训练语义分析实验报告 指导老师： 班级：学生：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; else word.readNext(); cout定义语句 null|,iSDTbool SDT() deal(word.normal); bool ret = true; if(word.type!=$comma)return true; word.readNext(); deal(word.normal); if(word.type!=$flag) error(语法错误); return false; else word.readNext(); deal(word.normal); return SDT();/SA-i:=Ebool SA() deal(word.normal); string result; if(word.type!= $flag )error(语法错误);return false; else result = word.att; deal(word.readNext(); deal(word.normal); if(word.type!= $copy )error(语法错误);return false; cout赋值语句if B then S SELSEbool SIF(Sstruct &ss) deal(word.normal); bool ret = true; if(word.type!= $if ) ret =false; error(缺少if); else word.readNext(); deal(word.normal); Bstruct bs; if(!B(bs)return false; if( word.type != $then ) ret = false; error(缺少then); else word.readNext(); deal(word.normal); coutif-then语句嵌套; Mstruct m1; m1.quad = quad; Sstruct ss1; if(!S(ss1)return false; deal(word.normal); if(word.type!=$else) ss.nextlist = merge(bs.falselist,ss1.nextlist); backpatch(bs.truelist,m1.quad); return ret; else Nstruct ns; ns.nextlist = Nextquad(); RSSns.nextlist.setop(j); RSSns.nextlist.setjump(0); Mstruct m2; m2.quad = quad; Sstruct ss2; if(!SEL