编译原理实验三-自下而上语法分析及语义分析.x.doc
优质文本上海电力学院编译原理课程实验报告 实验名称： 实验三 自下而上语法分析及语义分析 院系： 计算机科学与技术学院 专业年级： 学生姓名： 学号： 指导老师： 实验日期： 实验三自上而下的语法分析 一、实验目的： 通过本实验掌握LR分析器的构造过程，并根据语法制导翻译，掌握属性文法的自下而上计算的过程。 二、实验学时： 4学时。 三、实验内容 根据给出的简单表达式的语法构成规那么见五，编制LR分析程序，要求能对用给定的语法规那么书写的源程序进行语法分析和语义分析。对于正确的表达式，给出表达式的值。对于错误的表达式，给出出错位置。四、实验方法 采用LR分析法。首先给出S-属性文法的定义为简便起见，每个文法符号只设置一个综合属性，即该文法符号所代表的表达式的值。属性文法的定义可参照书137页表6.1，并将其改造成用LR分析实现时的语义分析动作可参照书145页表6.5。接下来给出LR分析表。然后程序的具体实现： l LR分析表可用二维数组或其他实现。l 添加一个val栈作为语义分析实现的工具。l 编写总控程序，实现语法分析和语义分析的过程。注：对于整数的识别可以借助实验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动作GOTO转换i+-*/()#ETF0S5S41231S6S12acc2R3R3S7S13R3R33R6R6R6R6R6R64S5S48235R8R8R8R8R8R86S5S4937S5S4108S6R12S119R1R1S7S13R1R110R4R4R4R4R4R411R7R7R7R7R7R712S5S414313S5S41514R2R2S7S13R2R215R5R5R5R5R5R5五、 处理程序例和处理结果例 例如1：2*(+3191)+ 3191#六、源代码【cifa.h】/cifa.h#include<string>using namespace std;/单词结构定义struct WordTypeint code;string pro;/函数声明WordType get_w();void getch();void getBC();bool isLetter();bool isDigit();void retract();int Reserve(string str);string concat(string str);【Table.action.h】/table_action.hclass Table_actionint row_num,line_num;int lineName8;string tableData168;public:Table_action()row_num=16;line_num=8;lineName0=30;lineName1=7;lineName2=13;lineName3=8;lineName4=14;lineName5=1;lineName6=2;lineName7=15;lineName8=0;for(int m=0;m<row_num;m+)for(int n=0;n<line_num;n+)tableDatamn=""tableData00="S5"tableData05="S4"tableData11="S6"tableData12="S12"tableData17="acc"tableData21="R3"tableData22="R3"tableData23="S7"tableData24="S13"tableData26="R3"tableData27="R3"tableData31="R6"tableData32="R6"tableData33="R6"tableData34="R6"tableData36="R6"tableData37="R6"tableData40="S5"tableData45="S4"tableData51="R8"tableData52="R8"tableData53="R8"tableData54="R8"tableData56="R8"tableData57="R8"tableData60="S5"tableData65="S4"tableData70="S5"tableData75="S4"tableData81="S6"tableData82="S12"tableData86="S11"tableData91="R1"tableData92="R1"tableData93="S7"tableData94="S13"tableData96="R1"tableData97="R1"tableData101="R4"tableData102="R4"tableData103="R4"tableData104="R4"tableData106="R4"tableData107="R4"tableData111="R7"tableData112="R7"tableData113="R7"tableData114="R7"tableData116="R7"tableData117="R7"tableData120="S5"tableData125="S4"tableData130="S5"tableData135="S4"tableData141="R2"tableData142="R2"tableData143="S7"tableData144="S13"tableData146="R2"tableData147="R2"tableData151="R5"tableData152="R5"tableData153="R5"tableData154="R5"tableData155="R5"tableData156="R5"tableData157="R5"string getCell(int rowN,int lineN)int row=rowN;int line=getLineNumber(lineN);if(row>=0&&row<row_num&&line>=0&&line<=line_num)return tableDatarowline;else return""int getLineNumber(int lineN)for(int i=0;i<line_num;i+)if(lineNamei=lineN)return i;return -1;【Table_go.h】/table_go.hclass Table_goint row_num,line_num;/行数、列数string lineName3;int tableData163;public:Table_go()row_num=16;line_num=3;lineName0="E"lineName1="T"lineName2="F"for(int m=0;m<row_num;m+)for(int n=0;n<line_num;n+)tableDatamn=0;tableData00=1;tableData01=2;tableData02=3;tableData40=8;tableData41=2;tableData42=3;tableData61=9;tableData62=3;tableData72=10;tableData121=14;tableData122=3;tableData132=15;int getCell(int rowN,string lineNa)int row=rowN;int line=getLineNumber(lineNa);if(row>=0&&row<row_num&&line<=line_num)return tableDatarowline;elsereturn -1;int getLineNumber(string lineNa)for(int i=0;i<line_num;i+)if(lineNamei=lineNa)return i;return -1;【Stack_num.h】class Stack_numint i; /栈顶标记int *data; /栈结构public:Stack_num() /构造函数 data=new int100;i=-1;int push(int m) /进栈操作 i+;datai=m;return i;int pop() /出栈操作i-;return datai+1;int getTop() /返回栈顶return datai;Stack_num() /析构函数delete data;int topNumber()return i;void outStack()for(int m=0;m<=i;m+)cout<<datam;【Stack_str.h】class Stack_strint i; /栈顶标记string *data; /栈结构public:Stack_str() /构造函数 data=new string50;i=-1;int push(string m) /进栈操作 i+;datai=m;return i;int pop() /出栈操作datai=""i-;return i;string getTop() /返回栈顶return datai;Stack_str() /析构函数delete data;int topNumber()return i;void outStack()for(int m=0;m<=i;m+)cout<<datam;【cifa.cpp】/cifa.cpp#include<iostream>#include<string>#include"cifa.h"using namespace std;/关键字表和对应的编码string codestring10="main","int","if","then","else","return","void","cout","endl"int codebook10=26,21,22,23,24,25,27,28,29;/全局变量char ch;int flag=0;/*/主函数int main()WordType word;cout<<"请输入源程序序列:"word=get_w(); while(word.pro!="#")/#为自己设置的结束标志cout<<"("<<word.code<<"，"<<"“"<<word.pro<<""<<")"<<endl;word=get_w();return 0;*/WordType get_w()string str=""int code;WordType wordtmp;getch();/读一个字符getBC();/去掉空白符if(isLetter() /以字母开头while(isLetter()|isDigit()str=concat(str);getch();retract();code=Reserve(str);if(code=-1)wordtmp.code=0;wordtmp.pro=str;/不是关键字elsewordtmp.code=code;wordtmp.pro=str;/是关键字else if(isDigit() /以数字开头while(isDigit()str=concat(str);getch();retract();wordtmp.code=30;wordtmp.pro=str;else if(ch='(') wordtmp.code=1;wordtmp.pro="("else if(ch=')') wordtmp.code=2;wordtmp.pro=")"else if(ch='') wordtmp.code=3;wordtmp.pro=""else if(ch='') wordtmp.code=4;wordtmp.pro=""else if(ch='') wordtmp.code=5;wordtmp.pro=""else if(ch='=') wordtmp.code=6;wordtmp.pro="="else if(ch='+') wordtmp.code=7;wordtmp.pro="+"else if(ch='*') wordtmp.code=8;wordtmp.pro="*"else if(ch='>') wordtmp.code=9;wordtmp.pro=">"else if(ch='<') wordtmp.code=10;wordtmp.pro="<"else if(ch=',') wordtmp.code=11;wordtmp.pro=","else if(ch=''') wordtmp.code=12;wordtmp.pro="'"else if(ch='-') wordtmp.code=13;wordtmp.pro="-" else if(ch='/') wordtmp.code=14;wordtmp.pro="/"else if(ch='#') wordtmp.code=15;wordtmp.pro="#"else if(ch='|') wordtmp.code=16;wordtmp.pro="|"else wordtmp.code=100;wordtmp.pro=ch;return wordtmp;void getch()if(flag=0) /没有回退的字符ch=getchar();else /有回退字符，用回退字符，并设置标志flag=0;void getBC()while(ch=' '|ch='t'|ch='n')ch=getchar();bool isLetter()if(ch>='a'&&ch<='z'|ch>='A'&&ch<='Z')return true;else return false;bool isDigit()if(ch>='0'&&ch<='9')return true;else return false;string concat(string str)return str+ch;void retract()flag=1;int Reserve(string str)int i;for(i=0;i<=8;i+)if(codestringi=str) /是某个关键字，返回对应的编码return codebooki;if(i=9) /不是关键字return -1;【LR.cpp】#include<iostream>#include<string>#include<cstdlib>#include"cifa.h"#include"stack_num.h"#include"stack_str.h"#include"table_action.h"#include"table_go.h"using namespace std;void process()int stepNum=1;int topStat;Stack_num statusSTK; /状态栈 Stack_str symbolSTK; /符号栈Stack_num valueSTK; /值栈 WordType word;Table_action actionTAB; /行为表 Table_go goTAB; /转向表cout<<"请输入源程序，以#结束："word=get_w();/总控程序初始化操作 symbolSTK.push("#");statusSTK.push(0);valueSTK.push(0);cout<<"步骤t状态栈t符号栈t值栈t当前词t动作t转向"<<endl;/分析while(1)topStat=statusSTK.getTop(); /当前状态栈顶string act=actionTAB.getCell(topStat,word.code);/根据状态栈顶和当前单词查到的动作/输出cout<<stepNum+<<"t"statusSTK.outStack(); cout<<"t"symbolSTK.outStack(); cout<<"t"valueSTK.outStack(); cout<<"t"cout<<word.pro<<"t"/行为为“acc，且当前处理的单词为#，且状态栈里就两个状态/说明正常分析结束if(act="acc"&&word.pro="#"&&statusSTK.topNumber()=1)cout<<act<<endl;cout<<"分析成功！"<<endl;cout<<"结果为："<<valueSTK.getTop()<<endl;return;/读到act表里标记为错误的单元格else if(act="")cout<<endl<<"不是文法的句子！"<<endl;cout<<"错误的位置为单词"<<word.pro<<"附近。"return;/移进动作else if(act0='S')int newstat=atoi(act.substr(1).c_str();statusSTK.push(newstat);symbolSTK.push(word.pro);if(word.code=30)/整数，压入其值valueSTK.push(atoi(word.pro.c_str();else /其他单词，压入0占位valueSTK.push(0);/输出word=get_w();cout<<act<<endl;/规约动作else if(act0='R')cout<<act<<'t'string sn=act.substr(1);/产生式编号/根据规约使用的产生式更新各个栈if(sn="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.pop();int new_value=left_digit+right_digit;valueSTK.push(new_value);else if(sn="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=valueSTK.pop();int new_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 new_value=left_digit*right_digit;valueSTK.push(new_value);else if(sn="5")/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 new_value=left_digit/right_digit;valueSTK.push(new_value);else if(sn="3")/E->TstatusSTK.pop();symbolSTK.pop();symbolSTK.push("E");else if(sn="6")/T->FstatusSTK.pop();symbolSTK.pop();symbolSTK.push("T");else if(sn="7")/F->(E)statusSTK.pop();statusSTK.pop();statusSTK.pop();symbolSTK.pop();symbolSTK.pop();symbolSTK.pop();symbolSTK.push("F");valueSTK.pop();int digit_val=valueSTK.pop();valueSTK.pop();valueSTK.push(digit_val);else if(sn="8")/F->istatusSTK.pop();symbolSTK.pop();symbolSTK.push("F");elsecout<<"分析程序出错！"<<endl;return;/实施go表中的动作int next_status=goTAB.getCell(statusSTK.getTop(),symbolSTK.getTop();statusSTK.push(next_status);/输出cout<<next_status<<endl;elsecout<<"分析程序出错。"return ;int main()char ch;dosystem("cls");process();cout<<endl<<endl<<"继续新的语法分析按y，其它字符退出:"cin.clear();cin.sync();cin>>ch;while(ch='y');return 0;17 / 17
