《编译原理实验4算符优先算法》由会员分享，可在线阅读，更多相关《编译原理实验4算符优先算法（16页珍藏版）》请在金锄头文库上搜索。
1、一、实验目的与任务算术表达式和赋值语句的文法可以是（你可以根据需要适当改变）：Si=EEE+E|E-E|E*E|E/E|（E）|i根据算符优先分析法，将赋值语句进行语法分析，翻译成等价的一组基本操作，每一基本操作用四元式表示。二、实验涉及的相关知识点算符的优先顺序。三、实验内容与过程如参考 C 语言的运算符。输入如下表达式（以分号为结束）：（1）a = 10;（2）b = a + 20;注：此例可以进行优化后输出（不作要求）：(+,b,a,20)（3）c=(1+2)/3+4-(5+6/7);四、实验结果及分析（1）输出：(=, a,10,-)（2）输出：(=,r1,20,-) (+,r2,a,
2、r1)(=,b,r2,-)（3）输出：(+,r1,1,2) (/,r2,r1,3) (/,r3,6,7) (+,r4,5,r3,) (+,r5,r2,4) (-,r6,r5,r4) (=,c,r6,-)五、实验有关附件（如程序、附图、参考资料，等）/程序功能：/根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确。/文法：EE+E|E-E|E*E|E/E|(E)|i/ 其中 i 为无符号整数/例：/输入：10;/输出：正确/输入：1+2;/输出：正确/输入：(1+2)/3+4-(5+6/7);/输出：正确/输入：(1-2)/3+4;/输出：错误/输入测试数据保存在同目录的文本文件
3、testin.txt 中，保存格式：/ 表达式行;/ 表达式行;/ ./预期的输出保存在同目录的文本文件 testout.txt 中，保存格式：/ 表达式行;/ 正确/错误/ 表达式行;/ 正确/错误/ ./#include stdio.h#include stdlib.h#define TRUE 1#define FALSE 0/文件信息：#define TESTIN_FILENAME testin.txt#define TESTOUT_FILENAME testout.txtFILE * fTestIn;FILE * fTestOut; /打开文件后的柄/运算符定义：#define O_N
4、UMBER 8 /运算符个数，+-*/()i#define O_PLUS 0 / 加+#define O_MINUS 1/ 减-#define O_TIMES 2/ 乘*#define O_SLASH 3/ 除/#define O_L_PAREN 4 /左括号(parenthesis)#define O_R_PAREN 5 /右括号#define O_IDENT 6/标识符#define O_NUL 7 /语法界符#/表达式缓冲区：由专门函数操作（ReadFormula(),GetChar()）#define BUFFER_SIZE 1000 /表达式缓冲区大小char BufferBUFFE
5、R_SIZE; /表达式缓冲区，以0表示结束int ipBuffer = 0; /表达式缓冲区当前位置序号/算符优先关系表：char O_TableO_NUMBERO_NUMBER = ,-,-,-,-, 2) /出错（多个非终结符相邻）return -1;r = O_TablePeek(n).NoPeek(n0).No;if(r = 或没有关系）return -1;/判断规约是否全部完成/返回：TRUE 全部完成；FALSE 没有完成bool IsOK()/if(Peek(1) = NULL) return FALSE;if(Peek(0).ch = E& Peek(1).ch = # &
6、TokenipToken.ch = #)return TRUE;elsereturn FALSE;/返回：TRUE 成功，FALSE 失败bool GuiYueN(int n) /将堆栈中 0n 单词规约int i,j;bool k;for(i=0;i=0;j-)if(OGin-j != Peek(j).ch)k = TRUE; /TRUE 表示规约串和文法右部不符，break;if(k) continue; /k=FALSE 表示规约串判断完成if(OGin+1=0) /文法也判断完成，匹配成功PopUp(n + 1); /弹出规约串PushToken(E,O_IDENT); /压入左部“E
7、”return TRUE;return FALSE;/在堆栈中，从 Begin 开始，查找前一个终结符位置/如果从开始找，让 Begin = -1int FindPriorOp(int Begin)int n;n = Begin + 1;while(Peek(n).ch = E)n +;return n;/移进，并判断是否需要规约/返回：-1 出错，1 需要规约，2 可继续移进/ 1.单词结束（遇到“#”号），无法移进，需要规约，返回：1/ 2.单词没有结束，需判断是否可以移进/ 2-1.堆栈单词单词：不能移进，需要规约，返回：1/ 2-3.两单词没有优先关系：出错，返回：-1int Move
8、In()SToken s,t; /分别存堆栈顶单词和单词序列的第一个单词char r; /存放优先关系s = Peek(FindPriorOp(-1); /取得堆栈中第一个终结符位置t = TokenipToken;r = O_Tables.Not.No;if(t.ch = #) /单词结束，无法移进，需要规约return 1;else /单词没有结束，需判断是否可以移进if(r = ) /不能移进，需要规约return 1;else /没有优先关系，出错MakeErr(移进时出现两个没有优先关系的相邻单词。);return -1;/（利用算符优先关系表判断单词序列是否正确）判断前的初始化/由
9、于多个表达式需要依次判断，因此对每个表达式判断前都需要初始化void JudgeInit()ipStack = 0; /堆栈初始化（如果有专门的 StackClear()函数则更好）ipToken = 0; /指向首个单词/窥视堆栈/参数：n 相对栈顶的位置（0 开始）/成功返回：返回单词/不成功返回：NULLSToken Peek(int n)SToken Token;if(n 0 | n ipStack - 1) n = ipStack - 1;ipStack -= n;return TRUE;/压栈（以字符形式）/参数：ch 是要压栈的字符（+-*/()i#E 之一），O_No 运算符序
10、号/调用：Push()void PushToken(char ch, int O_No)SToken Token;Token.ch = ch;Token.No = O_No;Push(Token);/压栈/参数：Token 是要压栈的 SToken 结构体类型的单词/缺点：没有判断堆栈是否满void Push(SToken Token)StackipStack + = Token;/全局初始化/成功：返回 TRUE；失败：返回 FALSEbool Init()/if(fTestIn = fopen(TESTIN_FILENAME, r) = NULL) return ! MakeErr(不能打
11、开测试文件！);/if(fTestOut = fopen(TESTOUT_FILENAME, w) = NULL) return ! MakeErr(不能打开结果输出文件！);fTestIn = fopen(TESTIN_FILENAME, r);fTestOut = fopen(TESTOUT_FILENAME, w);return TRUE;/程序退出前作善后处理/主要是关闭文件等void End()fclose(fTestIn);fclose(fTestOut);/将结果输出到文件/要求文件事先以追加方式打开，文件指针为 fTestOut/参数：Formula 表达式内容，Result
12、判断结果void OutPut(char * Formula, char * Result)fprintf(fTestOut,%sn%sn,Formula,Result);/从文件中读出一个表达式存于表达式缓冲区 Buffer中，以0结束，并置ipBuffer=0；/需要先打开文件，文件指针存于 fTestIn/读出非空表达式：返回 TRUE；文件结束：返回 FALSEbool ReadFormula() int n = 0;bool k = FALSE; /当 k=TRUE 时表示文件结束，否则文件没有结束while(TRUE)if(Buffern = fgetc(fTestIn) != E
13、OF) /读出一个字符成功if(Buffern = ;) break;n +;else /文件结束k = TRUE;break;Buffern = 0;/最后一个字符用结束标记0代替ipBuffer = 0; /初始化缓冲区指针if(n 0) /读出的数据非空，返回成功return TRUE;else /读出的数据为空，需要判断文件结束，还是只有;的空表达式if(k) /文件结束return FALSE;else /空表达式，文件没有结束，让它继续读下一个表达式return ReadFormula();/将表达式分割成单词序列/结果：单词序列存于 SToken Token中，单词个数存于 To
14、kenNumber 中/这是一个大模块，其中要调用一些子函数/本函数只识别：运算符+-*/、括号()、无符号整数 i，并在末尾添加#号/ 遇到其它任何字符都返回错误信息/返回：TRUE 表示成功；FALSE 表示失败，同时将错误信息存于全局变量 ErrMsg 中/使用到的其他全局变量：ch（取一个字符）、AToken（取到的单词）bool ChangeToTokens()TokenNumber = 0;if(GetFirstChar() = 0) return ! MakeErr(表达式为空。);while(TRUE) /对缓冲区进行循环读if(ch 0) GetFirstChar(); /滤去空格switch(ch) /对单词的第一个进行判断，在下面一次处理整个单词case 0:TokenTokenNumber.ch = #;TokenTokenNumber.No = O_NUL;return TRUE; /处理结束case +:TokenTokenNumber.ch = +;TokenTokenNumber.No = O_PLUS;GetChar();break;case
