编译原理实验三

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

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

3、动作)GOTO (转换)i+-*/()#ETF0S5S41231S6S12acc2R3R3S7S13R3R33R6R6R6R6R6R64S5S48235R8R8R8R8R8R86S5S4937S5S4108S6R12S119R1R1S7S13R1R110R4R4R4R4R4R411R7R7R7R7R7R712S5S414313S5S41514R2R2S7S13R2R215R5R5R5R5R5R5五、处理程序例和处理结果例示例 1: 20133191*(20133191+3191)+ 3191#0133191(20133191+3191)+3191A狀态栈符号栈值栈当前词动作转向10fl0201

4、33191S51105#20133191020133191辛RS3J03020133191+R&2102#T020133191半S750270201331910(S4n0274#T*(0201231Q1002013311S5(02745#T*4-R83*02743#T*(F十R62902742#T*(T+R3£100274=8#T*(B+筋11027436#T+ (E+3191S5120274865)RS3130274863#TM=(E+F)R&g140274869#T*(E+T)R18150274S#T*(E)S11160274=811#T*(E)+R7W17027

5、10#T*F+R42IS02#T0-92S149070十R3119010-923149070+S&2l0160-92814907002191£5210165#E3191#R83220163R&g230169#E+-TR1124010-923145879#盘X分析成功i!结果为：-928145879六、源代码【cifa.h】/cifa.h#in cludevstri ng> using n amespace std;单词结构定义struct WordType int code;stri ng pro;函数声明WordType get_w(); void getch

6、();void getBC();bool isLetter();bool isDigit();void retract();int Reserve(stri ng str);stri ng con cat(stri ng str);【Table.actio nHtable_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、=7; lin eName2=13; lin eName3=8; lin eName4=14; lin eName5=1; lin eName 6=2; lin eName7=15; lin eName8=0; for(i nt m=0;m<row_num ;m+) for(int n=0;n<line_num;n+) tableDatam n="" tableData00="S5" tableData05="S4" tableData11="S6" tableData12="S12"

8、; tableData17="acc" tableData21="R3" tableData22="R3" tableData23="S7" tableData24="S13" tableData2 6="R3" tableData27="R3" tableData31="R6" tableData32="R6" tableData33="R6" tableData34="R6"

9、; tableData3 6="R6"tableData37="R6" tableData40="S5" tableData45="S4" tableData 5 1="R8" tableData 52="R8" tableData 5 3="R8" tableData 5 4="R8" tableData 56="R8" tableData 5 7="R8" tableData60="

10、S5" tableData65="S4" tableData70="S5" tableData75="S4" tableData81="S6" tableData82="S12" tableData86="S11" tableData91="R1" tableData92="R1" tableData93="S7" tableData94="S13" tableData9 6="

11、;R1" tableData97="R1" tableData101="R4" tableData102="R4" tableData103="R4" tableData104="R4" tableData106="R4" tableData107="R4" tableData111="R7" tableData112="R7" tableData113="R7" tableData11

12、4="R7" tableData116="R7" tableData117="R7" tableData120="S5" tableData125="S4" tableData130="S5" tableData135="S4" tableData141="R2" tableData142="R2" tableData143="S7" tableData144="S13" ta

13、bleData146="R2" tableData147="R2"tableData151="R5"tableData152="R5"tableData153="R5"tableData154="R5"tableData15 5="R5"tableData156="R5"tableData157="R5"string getCell(int rowN,int lineN)int row=rowN;in t li ne

14、=getLi neNumber(li neN);if(row>=0&&row<row_ num&&li ne>=0&&li ne<=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_

15、go _int row_nu m,li ne_num; 行数、列数stri ng lin eName3; int tableData163; public:Table_go() row_num=16; line_num=3;lin eName0="E"lin eName1="T"lin eName2="F"for(i nt m=0;m<row_num ;m+) for(int n=0;n<line_num;n+) tableDatam n=0;tableData00=1; tableData01=2;tableData02

16、=3;tableData40=8;tableData41=2;tableData42=3;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 ne<=li ne_num) retur n ta

17、bleDatarowli ne;elsereturn -1;int getL in eNumber(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_numHclass Stack_ num _int i;/栈顶标记int *data;/ 栈结构public:Stack_num() / 构造函数 _data=new int100;i=-1;in t push( int m)进栈操作i+; datai=m; return i;in t pop()/出栈操作

18、i-;return datai+1;in t getTop()返回栈顶return datai;Stack_num()/ 析构函数 _delete data;int topNumber() return i;void outStack()for(i nt m=0;m<=i;m+) cout<<datam;【Stack_str.Rclass Stack_strint i;/栈顶标记stri ng *data; / 栈结构 public:Stack_str()/ 构造函数 _data=new stri ng50; i=-1;in t push(stri ng m)进栈操作i+;d

19、atai=m; return i;in t pop()/出栈操作datai=""I-; return I;stri ng getTop()返回栈顶return datai;Stack_str()/ 析构函数 _delete data;int topNumber()return i;void outStack()for(i nt m=0;m<=i;m+)cout<<datam;【cifa.cpp】/cifa.cpp#in clude<iostream>#in clude<stri ng>#i nclude"cifa.h&qu

20、ot;using n amespace std;/关键字表和对应的编码stri ng codestri ng10="mai n","i nt","if","the n" ,"else","return","void","cout","e ndl"in t codebook10=26,21,22,23,24,25,27,28,29;/全局变量char ch;int flag=0;/*/主函数int main()Word

21、Type word;cout«"请输入源程序序列:"word=get_w();while(!="#")#为自己设置的结束标志cout<v"("vvword.codevv"，"<<" “"<<<<" ” "vv")"vvendl; word=get_w();return 0;*/WordType get_w() _stri ng str=""int cod

22、e;WordType wordtmp;getch();读一个字符getBC();去掉空白符 if(isLetter()/ 以字母开头while(isLetter()|isDigit() str=co ncat(str); getch();retract();code=Reserve(str);if(code=-1)wordtmp.code=0;=str; 不是关键字 elsewordtmp.code=code;=str; 是 关键字else if(isDigit() / 以数字开头 while(isDigit() str=co ncat(str);

23、getch();retract();wordtmp.code=30; =str;else if(ch='(') wordtmp.code=1;="("else if(ch=')') wordtmp.code=2;=")"else if(ch='') wordtmp.code=3;=""else if(ch='') wordtmp.code=4;="&qu

24、ot;else if(ch='') wordtmp.code=5;=""else if(ch='=') wordtmp.code=6;="="else if(ch='+') wordtmp.code=7;="+"else if(ch='*') wordtmp.code=8;="*"else if(ch='>') wordtmp.code=9;w

25、=">"else if(ch='<') wordtmp.code=10;="<"else if(ch=',') wordtmp.code=11;=","else if(ch='”) wordtmp.code=12;="'"else if(ch='-') wordtmp.code=13;="-"else if(

26、ch='/') wordtmp.code=14;="/"else if(ch='#') wordtmp.code=15;="#"else if(ch=T) wordtmp.code=16;=T;elsewordtmp.code=100;=ch;return wordtmp;void getch() if(flag=0)没有回退的字符ch=getchar();else有回退字符，用回退字符，并设置标志flag=0;void getBC()

27、while(ch=' '|ch='t'|ch='n')ch=getchar();bool isLetter()if(ch>='a'&&ch<='z'|ch>='A '&&ch<='Z')return true;elsereturn false;bool isDigit()if(ch>='0'&&ch<=9)return true;elsereturn false;stri ng con

28、 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) /是某个关键字，返回对应的编码 retur n codebooki;if(i=9)不是关键字return -1;【LR.cpp】#in clude<iostream>#in clude<stri ng>#i nclude<cstdlib>#i nclude"cifa.h"#i nclude"

29、stack_ nu m.h"#i nclude"stack_str.h"#i nclude"table_actio n.h"#i nclude"table_go.h"using n amespace std;void process()int stepNum=1;状态栈/符号栈/值栈int topStat;Stack_num statusSTK;Stack_str symbolSTK;Stack_num valueSTK;行为表/转向表H.WordType word;Table_act ion action TAB;Tabl

30、e_go goTAB;coutvv"请输入源程序，以#结束：word=get_w();总控程序初始化操作symbolSTK.push("#");statusSTK.push(O);valueSTK.push(O);coutvv"步骤t状态栈t符号栈t值栈t当前词t动作t转向"<<endl;分析while(1) topStat=statusSTK.getTop(); / 当前状态栈顶 stri ng act=actio nTAB.getCell(topStat,word.code);/根据状态栈顶和当前单 词查到的动作输出cout&#

31、171;"t" cout«"t" cout<<"t"cout<vstepNum+vv"t" statusSTK.outStack(); symbolSTK.outStack();valueSTK.outStack(); cout<<vv"t"行为为“ acc”，且当前处理的单词为#，且状态栈里就两个状态 说明正常分析结束if(act="acc"&&="#"&&a

32、mp;statusSTK.topNumber()=1)coutvvactvve ndl;coutvv"分析成功！ "<<e ndl;coutvv"结果为："vvvalueSTK.getTop()v<e ndl; return;读到act表里标记为错误的单元格else if(act="")cout«e ndlvv"不是文法的句子！ "<<e ndl;cout«"错误的位置为单词"vv"附近。" return;

33、/移进动作else if(actO='S')int n ewstat=atoi(act.substr(1).c_str(); statusSTK.push( newstat);symbolSTK.push();if(word.code=30) 整数，压入其值 valueSTK.push(atoi(.c_str();else 其他单词，压入0占位valueSTK.push(0);输出word=get_w(); cout<<act<<e ndl;/规约动作else if(act0='R')cout<<

34、;act<<'t'stri ng sn=act.substr(1);/产生式编号/根据规约使用的产生式更新各个栈if(s n="1")/E->E+TstatusSTK.pop();statusSTK.pop();statusSTK.pop(); symbolSTK.pop();symbolSTK.pop();symbolSTK.pop(); symbolSTK.push("E");int right_digit=valueSTK.pop();valueSTK.pop();int left_digit=valueSTK.p

35、op();int n ew_value=left_digit+right_digit; valueSTK.push( new_value);else if(s n="2")/E->E-TstatusSTK.pop();statusSTK.pop();statusSTK.pop(); symbolSTK.pop();symbolSTK.pop();symbolSTK.pop(); symbolSTK.push("E");int right_digit=valueSTK.pop();valueSTK.pop();int left_digit=value

36、STK.pop();int n ew_value=left_digit-right_digit; valueSTK.push( new_value); _else if(sn="4")/T->T*FstatusSTK.pop();statusSTK.pop();statusSTK.pop(); symbolSTK.pop();symbolSTK.pop();symbolSTK.pop(); symbolSTK.push("T");int right_digit=valueSTK.pop();valueSTK.pop();int left_digit=valueSTK.pop();int n ew_value=left_digit*right_digit;valueSTK.push( new_value); _else if(sn="5")/T->T/FstatusSTK.pop();s