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

1、编译原理综合训练语义分析实验报告指导老师：班级：学生：zeadom学号：学生：学号：2011/6/29目录语言文法的形式化描述 3语义规则 3运行环境介绍 5关键算法的流程图及文字解释 51、本编译器的总框架 52、在语义分析中的主要函数介绍 63、产生布尔表达式 74、While-do 语句的语义分析 85、词法、语法和语义分析的衔接 8测试报告 8附录 12语言文法的形式化描述（BNF式）程序开始P->program i;SD n SC;定义语句SDn->SDSD n|n ullSD->var int iSDTSDT -> nu ll|,iSDT复合语句SC->

2、;begin Sn endSn->S;S n| 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| null A->>|<|=|>=|<=|<> D->AND|ORif语句SIF->if B then S SELSESELSE-> null|else S2while语句SW->while B

3、 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 E i E.PLACE = En try(i) 产生式语义规则E i E.true

4、list:=makelist( nextquad);E.falselist:=makelist (n extquad+1);Gen( jnz, entry(i) , , 0 );Gen( j ,，, 0 ) E i1 R i2 E.truelist:=makelist( nextquad);E.falselist:=makelist (n extquad+1);Gen( jR, entry(i1) , entry(i2) , 0 );Gen( j ，, , 0 )E n E1 E.truelist:= E1.falselist ;E.falselist:= E1.truelist ;E ( E

5、1 ) E.truelist:= E1.truelist ;E.falselist:= E1.falselist ; M£ M.quad := n extquad ;EE1AME2 backpatch(E1.truelist, M.quad );E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2. Falselist)EE1VME2 backpatch(E1. falselist, M.quad );E.truelist:= merge(E1. truelist, E2. truelist);E.falselist:=

6、 E2. Falselist EE1AME2backpatch(E1.truelist, M.quad );E.truelist:= E2.truelist;E.falselist:=merge(E1.falselist, E2.Falselist) 产生式语义规则S if E then M S1 backpatch(E.truelist, M.quad );S. nextlist:=merge(E.falselist,S1. nextlist) M£ M.quad := n extquad ;N£ N.n extlist:=makelist( nextquad); Ge

7、n( j , , , 0 )S if E the n M1 S1N else M2 S2 backpatch(E.truelist, M1.quad ); backpatch(E.falselist, M2.quad );S.n extlist:=merge(S1. nextlist,N.n extlist, S2. nextlist) S while M1 E do M2 S1 backpatch(S1.nextlist, M1.quad ); Gen( j ,，, M1.quad ); backpatch(E.truelist, M2.quad ); S.nextlist:= E.fals

8、elist S beg in L end S.n extlist:=L. nextlistS A S.nextlist:= makelist() /* 空链 */ LS L.n extlist:=S. nextlistL L1； MS backpatch(L1. nextlist, M.quad );L.n extlist:=S .n extlist运行环境介绍运行环境是DEVC+Dev-C+是一个C&C+研发工具，它是一款自由软件，遵守GPL协议。它集合了 GCC MinGW32 等众多自由软件，并且可以取得最新版本的各种工具支持，而这一切工作都是来自全球的狂热者所做的工作，并且你拥

9、有对这一切工具自由使用的权利，包括取得源代码等， 前提是你也必须遵守GNU协议。Dev-C+每一天都在进步着，因为它是一个自由软件。Dev-C+是一个非常实用的编程软件，多款著名软件均由它编写而成，它在C的基础上，增强了逻辑性关键算法的流程图及文字解释1、本编译器的总框架词法分RJ词法三1L兀式1【语法分L2_Ji语义分iFj四元式2、在语义分析中的主要函数介绍Backpatch(i nt list,i nt quad)代码：void backpatch(i nt list,i nt patch) int tmp;while(list)tmp = list;list = RSStmp.jump

10、;RSStmp.jump = patch; 写目标謔申四元琲 中第四项的值Merge (int list1,i nt list2)代码：int merge(i nt list1, int list2)int tmp = list2; if(list2=0)list2 = list1; elsewhile(RSStmp.jump)tmp = RSStmp.jump; RSStmp.jump = list1; return list2;若|处2为则返回listl的值若Itt2不为0则将 链list 1接到Iist2末尾 ,返回Ii5t2的值3、产生布尔表达式对第一个表达式规约记粥作符&达式

11、逬行规约逬行相应的b孔kpmtch和mmrga操作4、While-do语句的语义分析5、词法、语法和语义分析的衔接1、词法分析是分析输入代码产生词法三元式的程序。读入代码，并将代码中的单词分解 成词法三元式。2、语法分析读入词法三元式，并根据词法三元式对句子进行语法分析。3、 语义分析嵌入在语法分析中。根据语法分析中得到的句子类型和语义四元式产生规则, 产生四元式测试报告（测试用例，测试结果）测试用例输入程序（文件input.txt）:program example;var int j,m, n;begi n/*there is a comme nt*/j:=6;m:=3; /there is

12、 a comme ntn:=j+m;if n>=3 and n<5the n j:=j-1j:=j*4;output.txt )：else if n>10 then while a<b do j:=j+1; end;词法分析产生的词法三元式文件( (1,program,2) (15,example,2)(24,;,2) (4,var,3) (11,int,3) (15,j,3) (27,3) (15,m,3) (27,3) (15,n,3) (24,;,3) (2,begin,4) annotation start in line 4 annotation end in

13、 line 4 (15,j,5) (26,:=,5) (16,6,5) (24,;,5) (15,m,6) (26,:=,6) (16,3,6) (24,;,6) line annotation in line 6 (15,n,7) (26,:=,7) (15,j,7) (17,+,7) (15,m,7) (24,;,7) (6,if,8) (15,n,8) (32,>=,8)(16,3,8) (12,and,8) (15,n,8) (23,<,8)(16,5,8) (7,then,9) (15,j,9)(26,:=,9)(15,j,9)(18,-,9)(16,1,9) (8,el

14、se,10)(6,if,10)(15,n,10)(22,>,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,<,11)(15,b,11)(9,do,11)(15,j,11) (26,:=,11)(15,j,11)(17,+,11)(16,1,11) (24,;,11)(3,end,12)(24,;,12)语法分析产生的文件( Grammar.out )：定义语句赋值语句赋值语句赋值语句if-then 语句嵌套赋值语句i

15、f-then-else 语句嵌套 if-then 语句嵌套赋值语句 循环语句赋值语句复合语句 程序 语义分析产生的语义四元式文件( Semantic.out )： 100(:=,6,-,j) 101(:=,3,-,m) 102(+,j,m,T1) 103(:=,T1,-,n) 104(j>=,n,3,106) 105(j,-,-,111) 106(j<,n,5,108) 107(j,-,-,111) 108(-,j,1,T2) 109(:=,T2,-,j) 110(j,-,-,115) 111(j>,n,10,113) 112(j,-,-,115) 113(*,j,4,T3)

16、 114(:=,T3,-,j) 115(j<,a,b,117) 116(j,-,-,120) 117(+,j,1,T4) 118(:=,T4,-,j) 119(j,-,-,115)经测试，该语义分析程序正确执行，并产生了正确的四元式中间代码。附录程序源代码：词法分析器代码 (wordAnalyze.py )*#!C:Python27python#FileName:wordAnalyze.py'''author: zeadomdate: 2011-03-30 import os import os.path ch = "" code = &quo

17、t;" key_words="program":"1","begin":"2","end":"3","var":"4","integer":"5","if":"6","then":"7","else":"8","do":"9",&

18、quot;while":"10", "int":"11","and":"12","or":"13","not":"14", "+":"17","-":"18","(":"19",")":"20","=":"21"

19、;,">":"22", "<":"23","":"24",":":"25",":=":"26",",":"27", "*":"28","/":"29",".":"30","<=":"31&qu

20、ot;,">=":"32","<>":"33"def isLetter():global ch if ch=None: return False else:return ch.isalpha()def isDigit():global chif ch=None: return False else:return ch.isdigit()def concat(): global code global ch code = code+chdef getchar(l,i):if len(l)<=i

21、 or i<0: return Noneelse:return lidef getstr():global code global key_words global ll type = 0 state = None str = ""if code=None:str = u"(0,"+code+",%d)"%llelif code in key_words: if(key_wordscode=25): str = "error code in line %dn"%ll str = str + "err

22、or code :" else:str= u"("+key_wordscode+u","+code+",%d)"%ll elif code.isdigit():str= "(16,"+code+",%d)"%llelse:str= "(15,"+code+",%d)"%llreturn str ll = 0 flag = ;if _name_="_mainsrc = r"input.txt"outfile = r&q

23、uot;output.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<l:if i>=len(line):breakcode = ""ch = getchar(line,

24、i)i = i+1if annotation=1:if ch="*" and getchar(line,i)!=None and getchar(line,i)='/': str = "annotation end in line %dn"%ll outputf.write(str) annotation = 0 i=i+1continueif ch='/' and getchar(line,i)!=None and getchar(line,i)='/': outputf.write("line

25、 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

26、isLetter():while isLetter() or isDigit():concat()ch = getchar(line,i) i=i+1i=i-1str = getstr()str = str+"n"outputf.write(str)continueelif isDigit():while isDigit():concat()ch = getchar(line,i) i=i+1i=i-1str = getstr()str = str+"n"outputf.write(str)continueelif ch in key_words:con

27、cat()ch = getchar(line,i)i=i+1if ch!=None and (code+ch) in key_words: concat() str = getstr() str = str+"n" outputf.write(str)else:i=i-1str = getstr()str = str+"n"outputf.write(str)else:str = "error in line %dn"%ll outputf.write(str) outputf.write("error code "

28、;+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 $no

29、t 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.

30、h )*#ifndef ZEADOM_SEMANTIC_H #define ZEADOM_SEMANTIC_H #include "string" using namespace std; #include"iostream" #include "fstream" #include "sstream" int quad,varT;int Nextquad()return quad+;string NextT()varT+; string temp = "T" stringstream ss; s

31、s<<varT;temp = temp+ ss.str(); return temp;void semantic_init()varT=0; quad=100;struct siyuanshistring 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

32、=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<< &

33、quot;("<<op<<","if(haspar1)s<<par1<<","elses<<"-"<<","if(haspar2) s<<par2<<","elses<<"-"<<","if(isjump) s<<jump<<")"<<endl; else if(hasre

34、sult) s<<result<<")"<<endl; else s<<"-"<<")"<<endl;siyuanshi RSS10000;struct Estructstring lexval;Estruct()lexval="" ;struct Bstructint truelist;int falselist;Bstruct()truelist=falselist=0; ;struct Mstructint quad;Mstruct()q

35、uad=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(

36、"Semantic.out"); for(int i=100;i<quad;i+) out<<i;RSSi.output(out); out.close();struct Sstructint nextlist;Sstruct()nextlist=0; ;struct Nstructint nextlist;Nstruct()nextlist=0; ;#endif*#include "iostream" using namespace std;#include "string.h"#include "str

37、ing"#include "stdlib.h"#include "stdio.h"#include "resource.h" #include "semantic.h"语法和语义分析程序（main.cpp )*#define deal(s) if(!(s)return false;#define pdeal(s) if(!(s)cout<<" 没有找到文件结尾(程序是否未完成？)"<<endl;return false;/ 定义读入元素用的结构体及变量 stru

38、ct WORDint type;int pos;bool normal;string att;string line;WORD()normal=true;bool readNext()cin>>line;if(!cin)cin.clear();normal = false;return false; while(line0!='(')cin>>line;att=""int i,j=0;int l = line.length();i=3;if(line2>='0'&&line2<='9

39、')type = (line1-'0')*10+(line2-'0'); i=4;elsetype = line1-'0'for(;linei!=','i+)att.push_back(linei);for(i=0;i<l;i+)if(linei=',')j+;if(j=2)break;i+;pos = 0;while(linei>='0'&&linei<='9')pos = pos*10 + (linei-'0');i+;r

40、eturn 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); bo

41、ol E(Estruct &es);bool ET(Estruct &es); bool A();bool C();bool D();/ 函数实现bool error(string s)printf(” 语法错误：在第 d行n",word.pos); cout<<s<<endl;/P->program i;SDn SC;bool P()pdeal(word.normal);bool ret = true;Sstruct ss;if(word.type!= $program )error(" 缺少程序定义语句 ");re

42、t = 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(wo

43、rd.type!=$)error(" 缺少程序结束标志 "); ret = false; cout<<" 程序 "<<endl;return ret;/Sn->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

44、!=$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

45、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;

46、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(); els

47、e 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!=

48、$int )error(" 语法错误 ");return false;else word.readNext(); deal(word.normal);if(word.type!=$flag)error(" 语法错误 "); return false;else word.readNext();cout<<" 定义语句 "<<endl; deal(word.normal);return SDT();/SDT -> null|,iSDTbool SDT()deal(word.normal); bool ret

49、= 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 fa

50、lse; elseresult = word.att; deal(word.readNext(); deal(word.normal);if(word.type!= $copy )error(" 语法错误 ");return false;cout<<" 赋值语句 "<<endl; word.readNext();deal(word.normal);Estruct es; if(!E(es)return false;int quad = Nextquad();RSSquad.setop(":="); RSSqua

51、d.setpar1(es.lexval); RSSquad.setresult(result);return true;/SIF->if B then S SELSE bool 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 )r

52、et = false;error(" 缺少 then");else word.readNext();deal(word.normal);cout<<"if-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

53、ret;elseNstruct ns;ns.nextlist = Nextquad();RSSns.nextlist.setop("j");RSSns.nextlist.setjump(0);Mstruct m2; m2.quad = quad;Sstruct ss2; if(!SELSE(ss2)ret =false; deal(word.normal);backpatch(bs.truelist,m1.quad); backpatch(bs.falselist,m2.quad);ss.nextlist = merge(merge(ss1.nextlist,ns.next

54、list),ss2.nextlist); return ret;/SELSE->null|else S2bool SELSE(Sstruct &ss) deal(word.normal); bool ret = true;if(word.type!=$else)return true; word.readNext();deal(word.normal);cout<<"if-then-else 语句嵌套 " return S(ss);/SW->while B do Sbool SW(Sstruct &ss)cout<<&qu

55、ot; 循环语句 "<<endl; deal(word.normal);bool ret = true; if(word.type!=$while) error(" 缺少 while"); ret = false;else word.readNext(); deal(word.normal);Mstruct m1; m1.quad = quad; Bstruct bs;if(!B(bs)return false;if(word.type!=$do)error(" 缺少 do");ret = false;else word.readN

56、ext(); deal(word.normal);Mstruct m2;m2.quad = quad;if(!S(ss)return false;deal(word.normal);int swquad = Nextquad();RSSswquad.setop("j"); RSSswquad.setjump(m1.quad);backpatch(bs.truelist,m2.quad); backpatch(ss.nextlist,m1.quad); ss.nextlist = bs.falselist;return ret;/SC->begin Sn endbool

57、 SC(Sstruct &ss) deal(word.normal);bool ret = true;if(word.type!=$begin)error(" 复合语句缺少 begin");ret = false; else word.readNext();deal(word.normal);if(!Sn(ss)ret = false;deal(word.normal);if(word.type!=$end)error(" 复合语句缺少 end");ret = false; else word.readNext();cout<<&qu

58、ot; 复合语句 "<<endl;deal(word.normal); return ret;/B->EAEBT|NOT B|(B)BT bool B(Bstruct &bs) deal(word.normal);bool ret = true; if(word.type= $left ) word.readNext(); deal(word.normal);if(!B(bs)return false;if(word.type!= $right )error(" 缺少括号 ");ret = false;else word.readNext

59、(); deal(word.normal);if(!BT(bs)ret = false;deal(word.normal);else if(word.type= $not)word.readNext(); deal(word.normal); Bstruct bsa; if(!B(bsa)return false;bs.falselist = bsa.truelist; bs.truelist = bsa.falselist;else if(word.type=$flag|word.type=$num)Estruct es1;if(!E(es1)return false;if(!A()return false;string op = word.att;op = "j"+op;word.readNext();Estruct es2; if(!E(es2)return false;int quad = Nextquad(); bs.truelist = quad;RSSquad.setjump(0);RSSquad.setpar1(es1.lexval);RSSquad.setpar2(es2.lexval);RSSquad.setop(op);quad = Nextqua