编译原理试验三自下而上语法分析及语义分析x

1、海电力学院编译原理课程实验报告15 / 17实验名称:院 系:实验三自下而上语法分析及语义分析计算机科学与技术学院专业年级:学号:学生姓名: 指导老师: 实验日期:实验三自上而下的语法分析、实验目的:通过本实验掌握LR 分析器的构造过程，并根据语法制导翻译，掌握属性文法的自下而上计算的过程。二、实验学时:4学时。、实验内容根据给出的简单表达式的语法构成规则（见五），编制LR 分析程序，要求能对用给定的语法规则书写的源程序进行 语法分析和语义分析。对于正确的表达式，给出表达式的值。对于错误的表达式，给出出错位置。四、实验方法米用LR分析法。首先给出S-属性文法的定义（为简便起见，每个文法符号只设

2、置一个综合属性，即该文法符号所代表的表达式的值。属性文法的定义可参照书137页表6.1 ），并将其改造成用LR分析实现时的语义分析动作（可参照书145页表6.5 ）。接下来给出LR分析表。然后程序的具体实现:LR分析表可用二维数组（或其他）实现。添加一个val栈作为语义分析实现的工具。编写总控程序，实现语法分析和语义分析的过程。注：对于整数的识别可以借助实验1。五、文法定义简单的表达式文法如下: (1)E->E+T (2)E->E-T E->T(4) T->T*F(5) T->T/F(6) T->F(7) F->(E)(8) F->i状态ACTI

3、ON (动作)GOTO （转换）i+-*/()#ETF0S5S41231S6S12acc2R3R3S7S13R3R33R6R6R6R6R6R64S5S48235R8R8R8R8R8R86S5S4937S5S4108S6R12S119R1R1S7S13R1R110R4R4R4R4R4R411R7R7R7R7R7R712S5S414313S5S41514R2R2S7S13R2R215R5R5R5R5R5R5五、处理程序例和处理结果例示例 1: 20133191*(20133191+3191)+ 3191#20133191*(20133191+3191)+3191tt步骤12345678910111

4、213141516171S1920状态栈00503 02 027 0274 02745 02743 02742 02748 027486 0274865 0274863 0274859 02748 0274811 02710 02010160165 0163 016901符号栈值栈# 0S20133191020133191当前词动作20133191 020133191#T*(m(20133191 #T*(F 灯+(T#T*(E(E+020133191 020133191002013319100转向S5*R6S7S4RS2201331910201331910020133191+020133191

5、00201331910201331910020133191020133191002013319102013319100201331910+319155+R35635RS28222324 介析成功！m(E+3191 #T*(E+F#T*(E m(E)AT*?#E+#E+3191紙+T020133191002013319103191020133191002013319103191020133191002013319103191020133191002013638202013319100201363S200201331910201363820-92S1490700-92S1490700-928149

6、07000-928149070031910-92S149070031910-92S149070031910-92S145879#+3191+R3S6S5#accsnR7民4RSR6R1结果为：-928145879六、源代码【cifa.h】/cifa.h#in cludevstri ng> using n ames pace std;单词结构定义 struct WordT ypeint code; stri ng pro;；函数声明R6R1102R898WordT ype get_w();void getch();void getBC();bool isLetterO;bool isDig

7、it();void retract();int Reserve(stri ng str);stri ng con cat(stri ng str);【Table.actio nH/table_act ion.hclass Table_act ion "int row_nu m,li ne_num;int lin eName8;stri ng tableData168;public:Table_act ion()row_num=16; line_num=8; lin eName0=30; lin eName1=7; lin eName2=13; lin eName3=8; lin eN

8、ame4=14;lin eName5=1;lin eName 6=2;lin eName7=15;lin eName8=0;for(i nt m=0;mvrow_num ;m+)for(i nt n=0;n vli ne_num;n+)tableDatam n=""tableData00="S5"tableData05="S4"tableData11="S6" tableData12="S12" tableData17="acc"tableData21="R3&qu

9、ot;tableData22="R3" tableData23="S7" tableData24="S13"tableData2 6="R3"tableData27="R3"tableData31="R6"tableData32="R6" tableData33="R6" tableData34="R6" tableData3 6="R6" tableData37="R6" t

10、ableData40="S5" tableData4 5="S4" tableData 5 1="R8" tableData 5 2="R8" tableData 5 3="R8" tableData 5 4="R8" tableData 56="R8" tableData 5 7="R8" tableData60="S5" tableData6 5="S4" tableData70="

11、S5" tableData7 5="S4" tableData81="S6" tableData82="S12" tableData86="S11" tableData91="R1" tableData92="R1" tableData93="S7" tableData94="S13" tableData9 6="R1" tableData97="R1" tableData101=&qu

12、ot;R4" tableData102="R4" tableData103="R4" tableData104="R4" tableData106="R4" tableData107="R4" tableData111="R7" tableData112="R7" tableData113="R7" tableData114="R7" tableData116="R7" tableDat

13、a117="R7" tableData120="S5" tableData125="S4" tableData130="S5" tableData135="S4" tableData141="R2" tableData142="R2" tableData143="S7" tableData144="S13" tableData146="R2" tableData147="R2"

14、 tableData151="R5" tableData152="R5" tableData153="R5" tableData154="R5" tableData155="R5" tableData156="R5" tableData157="R5"stri ng getCell(i nt rowN,i nt lin eN)int row=rowN;in t li ne=getLi neNumber(li neN);if(row>=0&&a

15、mp;row<row_ num&&li ne>=0&&li nev=li ne_num) retur n tableDatarowli ne;elsereturn""int getL in eNumber(i nt li neN)for(i nt i=0;i<li ne_nu m;i+) if(li neNamei=li neN) return i;return -1;【Table_goH/table_go.hclass Table_go "int row_nu m,li ne_num;/行数、列数 stri ng

16、 lin eName3;int tableData163;public:Table_go() row_num=16; line_num=3;lin eNameO="E" lin eName1="T"lin eName2="F"for(i nt m=0;mvrow_num ;m+) for(i nt n=0;n vli ne_num;n+) tableDatam n=0;tableData00=1;tableData01=2;tableData02=3;tableData40=8;tableData41=2;tableData42=3;

17、tableData61=9;tableData62=3;tableData72=10; tableData121=14;tableData122=3;tableData132=15;in t getCell(i nt rowN,stri ng lin eNa)int row=rowN;in t li ne=getLi neNumber(li neNa);if(row>=0&&row<row_ num&&li nev=li ne_num) retur n tableDatarowli ne;elsereturn -1;int getL in eNumb

18、er(stri ng lin eNa) for(i nt i=0;i<li ne_nu m;i+) if(li neNamei=li neNa) return i;return -1;/栈顶标记/栈结构/构造函数【Stack_numH class Stack_ num "int i;int *data;public:Stack_num() "data=new in t100;i=-1;int p ush(i nt m)进栈操作i+;datai=m; return i;int pop()/出栈操作return datai+1;in t getTo p()返回栈顶retu

19、rn datai;Stack_num() / 析构函数delete data;int topNu mber() return i;void outStack()for(i nt m=0;m<=i;m+) cout<<datam;【Stack_str.fl class Stack_str " int i; stri ng *data; public:Stack_str()data=new stri ng50; i=-1;int p ush(stri ng m)进栈操作/栈顶标记/栈结构/构造函数i+;datai=m; return i;/出栈操作int pop() d

20、atai=""i-; return i;stri ng getTo p()返回栈顶return datai;Stack_str()/ 析构函数delete data;int topNu mber() return i;void outStack()for(i nt m=0;m<=i;m+) cout<<datam;；【cifa.c pp】/cifa.c pp#in cludeviostream>#in clude<stri ng>#i nclude"cifa.h" using n ames pace std;/关键字表

21、和对应的编码stri ng codestri ng10="mai rr,"i nt","ifVthe rr,"else","retum","void","cout","e ndl" in t codebook10=26,21,22,23,24,25,27,28,29;/全局变量 char ch;int flag=O;/*/主函数int main()WordT ype word;coutvv"请输入源程序序列："；word=get_w()

22、;while(!="#")/#为自己设置的结束标志coutvv"("vvword.codevv" , "<<" “"<<w" ” "vv")"vvendl; word=get_w();return 0;*/WordT ype get_w()stri ng str=""int code;WordT ype wordt mp;getch();/读一个字符 getBCO;/去掉空白符 if(isLetter

23、()/ 以字母开头while(isLetter()|isDigit()str=co ncat(str); getch();retract();code=Reserve(str);if(code=-1)wordtmp.code=0;=str;/ 不是关键字 elsewordt mp .code=code;wordt =str;/是 关键字else if(isDigit()/ 以数字开头while(isDigit()str=co ncat(str); getch();retract();wordt mp .code=30;wordt mp.p ro=str;els

24、e if(ch='(') wordtm p. code=1;wordt mp.p ro="("else if(ch=')') wordt mp .code=2;wordt mp.p ro=")"else if(ch='') wordt mp .code=3;wordt =""elseelse if(ch='') wordt mp .code=4;wordt mp.p ro="" else if(ch='') wordt mp

25、 .code=5;wordt ="" else if(ch='=') wordt mp .code=6;wordt ="=" else if(ch='+') wordt mp .code=7;wordt ="+" else if(ch='*') wordt mp. code=8;wordt ="*" else if(ch='>') wordt mp .code=9;wordt =&quo

26、t;>" else if(ch='<') wordt mp .code=10;wordt ="<" else if(ch=',') wordt mp .code=11;wordt mp.p ro="," else if(ch=''') wordt mp .code=12;wordt mp.p ro="'" else if(ch='-') wordt mp .code=13;wordt mp.p ro="-&

27、quot; else if(ch='/') wordtm p. code=14;wordtm p.p ro-7" else if(ch='#') wordt mp .code=15;wordt ="#" else if(ch=T) wordtm p. code=16;wordt mp.p ro="|"wordtm p. code=100;wordt mp.p ro=ch;return wordt mp;void getch()if(flag=0)没有回退的字符ch=getchar();else有回退字

28、符，用回退字符，并设置标志flag=0;void getBC()while(ch=' '|ch='t'|ch='n') ch=getchar();bool isLetter()if(ch>='a'&&chv='z'|ch>='A '&&ch<='Z') return true;elsereturn false;bool isDigit() if(ch>='0'&&ch<='9'

29、;) return true;elsereturn false;stri ng con cat(stri ng str) return st叶ch;void retract()flag=1;int Reserve(stri ng str)int i;for(i=0;i<=8;i+)if(codestri ngi=str)/是某个关键字，返回对应的编码retu rn codebooki;if(i=9)不是关键字return -1;【LR.c pp】#in clude<iostream>#in clude<stri ng> #i ncludevcstdlib>

30、#i nclude"cifa.h" #i nclude"stack_ nu m.h" #i nclude"stack_str.h" #i nclude"table_actio n.h” #i nclude"table_go.h" using n ames pace std;void P rocess()int ste pNu m=1;int top Stat;状态栈/符号栈/值栈行为表/转向表Stack_num statusSTK;Stack_str symbolSTK;Stack_num valueST

31、K;WordT ype word;Table_act ion action TAB;Table_go goTAB;coutvv"请输入源程序，以#结束：" word=get_w();总控程序初始化操作 symbolSTK .p ush(' "#"); statusSTK. push(O); valueSTK. push(0);coutvv"步骤t状态栈t符号栈t值栈t当前词t动作t转向"<<endl;分析while(1)top Stat=statusSTK.getT op ();/ 当前状态栈顶stri ng ac

32、t=actio nTAB.getCell(to pStat,word.code);/根据状态栈顶和当前单 词查到的动作输出coutvv"t" coutvv"t" cout<<"t"coutvvste pNu m+vv"t" statusSTK.outStack(); symbolSTK.outStack(); valueSTK.outStack(); coutvvword. provv"t"行为为“ acc”，且当前处理的单词为#，且状态栈里就两个状态 说明正常分析结束if(act=

33、"acc"&&word. pro="#"&&statusSTK.t opNu mber()=1) cout<<act<<e ndl;coutvv"分析成功！ "<<e ndl;coutvv"结果为："vvvalueSTK.getTo p()vve ndl; return;读到act表里标记为错误的单元格else if(act="")coutvve ndlw"不是文法的句子！"<<e ndl;cou

34、tvv"错误的位置为单词"w"附近。" return;/移进动作else if(actO='S')int n ewstat=atoi(act.substr(1).c_str(); statusSTK .p ush( newstat); symbolSTK. pu sh(word. pro); if(word.code=30)/ 整数，压入其值 valueSTK .p ush(atoi(word. pro.c_str();else 其他单词，压入0占位valueSTK. push(O);输出word=get_w(); c

35、outvvactvve ndl;/规约动作else if(actO='R')coutvvactvv't'stri ng sn=act.substr(l);/产生式编号/根据规约使用的产生式更新各个栈17 / 17if(sn="1")/E->E+TstatusSTK. pop ();statusSTK. pop( );statusSTK. pop(); symbolSTK .pop ();symbolSTK. pop ();symbolSTK .pop(); symbolSTK. pu sh("E");int nght

36、_digit=valueSTK .pop();valueSTK .pop ();int left_digit=valueSTK .pop();int n ew_value=left_digit+right_digit; valueSTK .p ush( new_value); "else if(sn="2")/E->E-TstatusSTK. pop ();statusSTK. pop( );statusSTK. pop(); symbolSTK .pop ();symbolSTK. pop ();symbolSTK .pop(); symbolSTK. p

37、u sh("E");int right_digit=valueSTK .pop();valueSTK .pop ();int left_digit=valueSTK .pop();int n ew_value=left_digit-right_digit; valueSTK .p ush( new_value); "else if(sn="4")/T->T*FstatusSTK. pop ();statusSTK. pop( );statusSTK. pop(); symbolSTK .pop ();symbolSTK. pop ();symbolSTK .pop(); symbolSTK .p ush("T");int right_digit=valueSTK .pop();valueSTK .pop ();int left_digit=valueSTK .pop();int n ew_value=left_digit*right_digit; valueSTK .p ush( new_value); "else if(sn="5")/T->T/FstatusSTK. pop ();statusSTK. pop( );st