编译原理-算符优先分析程序设计

1、编译原理课程设计报告 评分： 签字：编译原理课程设计二算符优先分析程序设计实验目的了解掌握算符优先分析的基本方法、内容；学会科学思考并解决问题，提高程序设计能力。实验内容与要求 用算符优先分析方法设计一个分析解释程序，对输入的赋值语句、输出语句、清除语句进行词法分析、语法分析、表达式求值并存储于指定变量中；若存在错误，提示错误相关信息。文法表示： Sv=E|E?|clear EE+T|E-T|T TT*F|T/F|F F (E)|v|c 单词种别码设计： = 1 ？ 2 + 3 - 4 * 5 / 6 （ 7 ） 8 v 9 c 10 clear 11 # 12 N 13 实验环境系统环境为w

2、indows系统，编译环境为VS2015,编程语言为C+。实验过程过程一：构建firstVT()和lastVT()算法分析：对于firstVT()构建，对于每个非终结符F的产生式，第一个终结符或者|后的第一个终结符应该在其firstVT()集合内，且若非终结符T能推出非终结符F则firstVT(T)包含first（F）。lastVT()的构造类似，对于每个非终结符F的产生式，非终结符后的第一个终结符都属于lastVT（F）, 且若非终结符T能推出非终结符F则lastVT(T)包含first（F）。算法实现主要函数：void get_firstVT()/求firstVT();void get_l

3、astVT()/求lastVT();结果：FirstVT(S)=,?,l,+,-,*,/,(,v,c,FirstVT(E)+,-,*,/,(,v,c,FirstVT(T)*,/,(,v,c,FirstVT(F)(,v,c,LastVT(S)=,?,l,+,-,*,/,),v,c,LastVT(E)+,-,*,/,),v,c,LastVT(T)*,/,),v,c,LastVT(F),v,c,过程二：构建优先符号表算法分析:（1） 在产生式中两个相邻的终结符优先顺序相等（2） 对于小于关系，首先扫描终结符a标记flag=1，再扫描到非终结符Q，此时判断若flag=1，则对所有bFristVTQ，a

4、a.算法结果： =?+-*/()vcl#=-2-2-1-1-1-1-1-2-1-1-21?-2-2-2-2-2-2-2-2-2-2-21+-2111-1-1-11-1-1-21-2111-1-1-11-1-1-21*-211111-11-1-1-21/-211111-11-1-1-21(-2-2-1-1-1-1-10-1-1-21)-211111-21-2-2-21v011111-21-2-2-21c-211111-21-2-2-21l-2-2-2-2-2-2-2-2-2-2-21#-1-1-1-1-1-1-1-1-1-1-10其中-2表示不会出现，1表示,-1表示,0表示=.字母l表示cle

5、ar.过程三：词法分析算法分析：详见课程设计一算法主要函数：int letter()/判断是否为字母int digit()/判断是否为数字int str_to_num()/数字字符串转化为整数int reserve(char *k)/处理保留字int sysmbol(identifier *id)/处理标识符，查找符号表并存放位置若没有则添加int constant(constnumber *con)/存入常数表，并返回它在常数表中的位置void WordAnalyze( constnumber *con, identifier *id, char sentence,int &point,in

6、t &syn,int &sym_point)/词法分析void Insert_to_symboltbl(int syn, int value, int &point)/把二元组加入symbol表算法结果：得到语句的所有单词二元组 symbolTBL表,存放种别码syn及其值val，其中对于种别码为9的变量val为标志符的入口标志，对于种别码为10的的常量val为存放的值。以及标志符表。过程四：算符优先分析算法分析：1) 置栈底及输入串尾为 # ,并设 # #; 栈顶终结符为 ,输入字为 a ; 2) 若 a, 则在栈中寻找最左素短语, 归约为 N ,并记录N的值重复 2); 若=a=#, 且栈

7、中为 #N, 则分析成功;否则,输入串为非法字串.数据结构设计：构造堆栈结构存储分析句子typedef struct SymbolTbl *elem;int n;int top;Stack;堆栈相关操作int CreateStack(Stack &s, int n)/初始化void clearStack(Stack &s)/清空int empty(Stack &s)/判断是否为空void push(Stack &s,SymbolTbl t)/入栈void pop(Stack &s)/出栈主要函数：void Clear_Symbol_Tbl()/清空符号表void print_(Stack &s

8、,int &point)/打印出堆栈和符号表的情况void suanfu_main()/算符优先分析测试分析测试用例a=5 b=a+10 测试结果#a=5#标识符表：1 a -1二元组表: 0 12 -1 1 9 1 2 1 -1 3 10 5 4 12 -1当前堆栈情况：(12,-1) 当前符号表情况：(9,1) (1,-1) (10,5)这里是小于等于关系，入栈当前堆栈情况：(12,-1) (9,1)当前符号表情况：(1,-1) (10,5)这里是小于等于关系，入栈当前堆栈情况：(12,-1) (9,1) (1,-1)当前符号表情况：(10,5)这里是小于等于关系，入栈当前堆栈情况：(12

9、,-1) (9,1) (1,-1) (10,5)当前符号表情况：此处将常量归约为N当前堆栈情况：(12,-1) (9,1) (1,-1) (13,5)当前符号表情况：此处将v=c归约为N当前堆栈情况：(12,-1) (13,5)当前符号表情况：当前堆栈情况：(12,-1) (13,5)当前符号表情况：归约成功结果为5coninue ? y or n y请输入句子,以#开始并且以#结束#b=a+10#标识符表：1 a 52 b -1 二元组表: 0 12 -1 1 9 2 2 1 -1 3 9 1 4 3 -1 5 10 10 6 12 -1当前堆栈情况：(12,-1)当前符号表情况：(9,2)

10、 (1,-1) (9,1) (3,-1) (10,10)这里是小于等于关系，入栈当前堆栈情况：(12,-1) (9,2)当前符号表情况：(1,-1) (9,1) (3,-1) (10,10)这里是小于等于关系，入栈当前堆栈情况：(12,-1) (9,2) (1,-1)当前符号表情况：(9,1) (3,-1) (10,10)这里是小于等于关系，入栈当前堆栈情况：(12,-1) (9,2) (1,-1) (9,1)当前符号表情况：(3,-1) (10,10)此处将变量归约为N当前堆栈情况：(12,-1) (9,2) (1,-1) (13,5)当前符号表情况：(3,-1) (10,10)这里是小于等

11、于关系，入栈当前堆栈情况：(12,-1) (9,2) (1,-1) (13,5) (3,-1)当前符号表情况：(10,10)这里是小于等于关系，入栈当前堆栈情况：(12,-1) (9,2) (1,-1) (13,5) (3,-1) (10,10)当前符号表情况：此处将常量归约为N当前堆栈情况：(12,-1) (9,2) (1,-1) (13,5) (3,-1) (13,10)当前符号表情况：此处将N+N归约为N当前堆栈情况：(12,-1) (9,2) (1,-1) (13,15)当前符号表情况：此处将v=c归约为N当前堆栈情况：(12,-1) (13,15)当前符号表情况：归约成功结果为15c

12、oninue ? y or n结论 符合预期结果该赋值语句解释程序符合要求感想与收获赋值语句的词法分析包括了众多过程与步骤，通过完整的完成本次课程设计，我对构建算符优先表以及语法分析过程有了更深的理解与掌握。同时在用代码实现的过程中我程序设计、程序优化、调试程序的能力也有较大提升。代码#include#include using namespace std;/单词种别码int zb_c(char a)switch (a) case =:return 1;case ?:return 2;case +:return 3;case -:return 4;case *:return 5;case /:

13、return 6;case (:return 7;case ):return 8;case v:return 9;case c:return 10;case l:return 11;case #:return 12;case N:return 13;default:return 0;char zbc12 = =,?,+,-,*,/,(,),v,c,l,# ;/是否为终结符int ISzj_code(char ch)if (ch = 97 & ch = 0;i-)int k = 0,flag = 1;for ( j = 2;wenfaij != 0;j+)if (ISzj_code(wenfai

14、j) & flag = 1)if (i = 0 & j = 3);elseFirst_VTik+ = wenfaij;flag = 0;if (wenfaij = |)flag = 1;if (i!=3)j = 0;while (First_VTi + 1j != 0)First_VTik+ = First_VTi + 1j+;First_VTik = 0;void get_lastVT()int i, j;for ( i = 3;i = 0;i-)int k = 0, flag = 0;for ( j = 3;wenfaij != 0;j+)if (ISzj_code(wenfaij) &

15、flag = 1)Last_VTik+ = wenfaij;flag = 0;if (!ISzj_code(wenfaij)flag = 1;if (i!=3)j = 0;while (Last_VTi+1j != 0)Last_VTik+ =Last_VTi + 1j+;/打印fistVT与lastVT结果void printFistlast()get_firstVT();for (int i = 0;i 4;i+)cout FirstVT( chci );int j = 0;while (First_VTij != 0)cout First_VTij+ ,;cout endl;get_la

16、stVT();for (int i = 0;i 4;i+)cout LastVT( chci );int j = 0;while (Last_VTij != 0)cout Last_VTij+ ,;cout endl;/优先关系表int priority1313 ;void prior() int i, j,flag,p;for (i = 0;i 13;i+)for (j = 0;j 13;j+)priorityij = -2;char ch1, ch2;/求等号for (i = 0;i 4;i+) flag = 0;for (j = 3;wenfaij != 0;j+)if (ISzj_co

17、de(wenfaij)flag+;if (flag = 1)ch1 = wenfaij;if (flag = 2)ch2 = wenfaij;priorityzb_c(ch1)zb_c(ch2) = 0;flag = 0;if (wenfaij = |)flag = 0;/求小于for (i = 0;i 4;i+) flag = 0;for (j = 3;wenfaij != 0;j+)if (ISzj_code(wenfaij)flag = 1;ch1 = wenfaij;if (!ISzj_code(wenfaij) & flag = 1)ch2 = wenfaij;if(ch2=S|ch

18、2=T|ch2=F|ch2=E)int temp = Fzj(ch2);for ( p = 0;First_VTtempp != 0;p+)priorityzb_c(ch1)zb_c(First_VTtempp) = -1;flag = 0;if (wenfaij = |)flag = 0;/求大于for (i = 0;i 4;i+)flag = 0;for (j = 3;wenfaij != 0;j+)if (wenfaij = S | wenfaij = T | wenfaij = F | wenfaij = E)flag = 1;ch1 = wenfaij;if (ISzj_code(w

19、enfaij) & flag = 1)ch2 = wenfaij;int temp = Fzj(ch1);for (p = 0;Last_VTtempp != 0;p+)priorityzb_c(Last_VTtempp)zb_c(ch2) = 1;flag = 0;if (wenfaij = |)flag = 0;for (i = 0;i = 12;i+)priorityi12 = 1;priority12i = -1;priority1212 = 0;void print_prior()int i;cout setw(10);for (i = 0;i 12;i+)cout zbci;cou

20、t setw(5);cout endl;for (int i = 1;i = 12;i+)cout zbci - 1setw(5) ;for (int j = 1;j = 12;j+)cout priorityij setw(5);cout endl;typedef structint syn;/种别码int value;/数值或者标识符入口指针SymbolTbl;#define LENGTH 10char ch;char *CODE = identifier,constant,keyword/*保留字*/,+,-,*,/,=,!=,=,=,(,),:,;, ;char *k = for,wh

21、ile,do,else,if,static,int,sizeof,break,continue ;/保留字char token16;/存放处理后的字符串/标识符结构体typedef structchar I30;int value;identifier;/变量表typedef structint cont300;int len;constnumber;/词法分析器void contacat()/连接字符char * cht = &(ch);strcat_s(token, cht);int letter()/判断是否为字母returnisalpha(ch);int digit()/判断是否为数字

22、return isdigit(ch);int reserve(char *k)/处理保留字int i;for (i = 0;i LENGTH;i+)if (strcmp(token, ki) = 0)return (i + 1);return 0;identifier id256;/标志符表int idscan = 1;int sysmbol(identifier *id)/处理标识符，查找符号表并存放位置若没有则添加int i;for (i = 1;i contcon-len = str_to_num();con-len+;return con-contcon-len-1;SymbolTbl

23、 symbol100;void Insert_to_symboltbl(int syn, int value, int &point)/把二元组加入symbol表symbolpoint.syn = syn;symbolpoint.value = value;point+;void WordAnalyze( constnumber *con, identifier *id, char sentence,int &point,int &syn,int &sym_point)/词法分析int entry,val;strcpy_s(token, );/初始化为空字符串ch = sentencepoin

24、t;if (ch = #&point = 0)point+;ch = sentencepoint;if (ch = A&ch = a&ch len = 0;char sentence100 = 0;int syn = -1,scan_point=0;int sym_point = 0;printf(请输入句子,以#开始并且以#结束n); cinsentence;Insert_to_symboltbl(12, -1, sym_point);while (syn != 12)WordAnalyze(con, id, sentence, scan_point, syn,sym_point);for

25、(int m1 = 1;m1 idscan;m1+)cout m1 ;printf(%s , idm1.I);cout idm1.value endl;for (int m2 = 0;m2sym_point;m2+) /符号表 printf(t%d %d %dn, m2, symbolm2.syn, symbolm2.value); /算符优先分析typedef struct SymbolTbl *elem;int n;int top;Stack;int CreateStack(Stack &s, int n)/初始化if (n 0) return 0;s.n = n;s.top = -1;s

26、.elem = (SymbolTbl*)malloc(sizeof(SymbolTbl)*n);if (!s.elem)return 0;return 1;void clearStack(Stack &s)/清空s.top = -1;int empty(Stack &s)/判断是否为空return s.top = -1;void push(Stack &s,SymbolTbl t)/入栈s.elem+s.top = t;void pop(Stack &s)/出栈SymbolTbl t;t = s.elems.top-;void Clear_Symbol_Tbl()/清空符号表/将符号表的syn

27、全部设置为0for (int i = 0;i100;i+)symboli.syn = 0;/代表没定义symboli.value = -1;/指定为-1void print_(Stack &s,int &point)/打印出堆栈和符号表的情况cout endl;cout 当前堆栈情况：;for (int i = 0;i = s.top;i+)cout ( s.elemi.syn , s.elemi.value ) ;cout endl;cout 当前符号表情况：;for(int j=point;symbolj.syn!=12;j+)cout ( symbolj.syn , symbolj.va

28、lue ) ;cout endl;void error()cout 程序有错误;exit(0);void suanfu_main()/算符优先分析int symbol_scan=1;/符号表扫描指针，从1开始int stack_scan;/初始化一个堆栈Stack s;CreateStack(s, 50);SymbolTbl temp;temp.syn = 12;temp.value = -1;push(s, temp);print_(s, symbol_scan);stack_scan = s.top;int prior_stack, prior_symbol;while (1)prior_

29、stack = s.elemstack_scan.syn;prior_symbol = symbolsymbol_scan.syn;int prio = priorityprior_stackprior_symbol;if (prio = -1 | (prio = 0 & prior_symbol != 12)push(s, symbolsymbol_scan);symbol_scan+;stack_scan = s.top;cout 这里是小于等于关系，入栈;print_(s, symbol_scan);else if (prio = 0 & s.elems.top.syn = 13 & p

30、rior_symbol = 12 & s.elems.top - 1.syn = 12)cout 归约成功 endl;cout 结果为 s.elems.top.value endl;break;else if (prio = 1)stack_scan = s.top;while (prio = 1)int judge = s.elemstack_scan.syn;if (judge = 9)/栈顶元素为变量if (ids.elemstack_scan.value - 1.value = -1);else if (s.elemstack_scan.value 0)cout 该变量未定义;exit

31、(0);elsetemp.syn = 13;temp.value = ids.elemstack_scan.value.value;pop(s);push(s, temp);stack_scan = s.top - 1;if (stack_scan 0)error();prior_stack = s.elemstack_scan.syn;prio = priorityprior_stackprior_symbol;cout 此处将变量归约为N endl;print_(s, symbol_scan);else if (judge = 10)/常量temp.syn = 13;temp.value

32、= s.elemstack_scan.value;pop(s);push(s, temp);stack_scan = s.top - 1;if (stack_scan 0)error();prior_stack = s.elemstack_scan.syn;prio = priorityprior_stackprior_symbol;cout 此处将常量归约为N endl;print_(s, symbol_scan);else if (judge = 1)/=if (s.elemstack_scan - 1.syn = 9)ids.elemstack_scan - 1.value.value

33、= s.elems.top.value;temp.syn = 13;temp.value = s.elems.top.value;pop(s);pop(s);pop(s);push(s, temp);stack_scan = s.top - 1;if (stack_scan 0)error();prior_stack = s.elemstack_scan.syn;prio = priorityprior_stackprior_symbol;cout 此处将v=c归约为N endl;print_(s, symbol_scan);elseerror();else if (judge = 3)/+i

34、f (s.elemstack_scan - 1.syn = 13 & s.elems.top.syn = 13)temp.syn = 13;temp.value = s.elemstack_scan - 1.value + s.elems.top.value;pop(s);pop(s);pop(s);push(s, temp);stack_scan = s.top - 1;if (stack_scan 0)error();prior_stack = s.elemstack_scan.syn;prio = priorityprior_stackprior_symbol;cout 此处将N+N归约

35、为N endl;print_(s, symbol_scan);elseerror( );else if(judge=4)/-if (s.elemstack_scan - 1.syn = 13 & s.elems.top.syn = 13)temp.syn = 13;temp.value = s.elemstack_scan - 1.value - s.elems.top.value;pop(s);pop(s);pop(s);push(s, temp);stack_scan = s.top - 1;if (stack_scan 0)error();prior_stack = s.elemstack_scan.syn;prio = priorityprior_stackprior_symbol;cout 此处将N-N归约为N endl;print_(s, symbol_scan);elseerror( );else if (judge = 5)/*if (s.elemstack_scan - 1.syn = 13 & s.elems.top.syn = 13)temp.syn = 13;temp.value = s.elemstack_scan - 1.value * s.elems.top.value;pop(s);pop(s);pop(s);push(s, temp);sta