实验三 算符优先分析算法的设计与实现.doc

实验三 算符优先分析算法的设计与实现（8学时）一、 实验目的根据算符优先分析法，对表达式进行语法分析，使其能够判断一个表达式是否正确。通过算符优先分析方法的实现，加深对自下而上语法分析方法的理解。二、 实验要求1、输入文法。可以是如下算术表达式的文法（你可以根据需要适当改变）： EE+T|E-T|TTT*F|T/F|FF（E）|i2、对给定表达式进行分析，输出表达式正确与否的判断。程序输入/输出示例：输入：1+2;输出：正确输入：(1+2)/3+4-(5+6/7);输出：正确输入：(1-2)/3+4输出：错误输入：1+2-3+(*4/5)输出：错误三、实验步骤1、参考数据结构char *VN=0,*VT=0;/非终结符和终结符数组char firstvtNN,lastvtNN,tableNN;typedef struct /符号对(P,a)char Vn;char Vt; VN_VT;typedef struct /栈 VN_VT *top; VN_VT *bollow; int size;stack;2、根据文法求FIRSTVT集和LASTVT集给定一个上下文无关文法，根据算法设计一个程序，求文法中每个非终结符的FirstVT 集和LastVT 集。算符描述如下：/*求 FirstVT 集的算法*/ PROCEDURE insert(P,a); IF not FP,a then begin FP,a = true; /(P,a)进栈 end; Procedure FirstVT; Begin for 对每个非终结符 P和终结符 a do FP,a = false for 对每个形如 Pa或 PQa的产生式 do Insert(P,a) while stack 非空 begin 栈顶项出栈，记为(Q,a) for 对每条形如 PQ的产生式 do insert(P,a) end; end.同理，可构造计算LASTVT的算法。3、构造算符优先分析表依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。算法描述如下：for 每个形如 P-X1X2Xn的产生式 do for i =1 to n-1 do begin if Xi和Xi+1都是终结符 then Xi = Xi+1 if i= n-2, Xi和Xi+2 是终结符, 但Xi+1 为非终结符 then Xi = Xi+2 if Xi为终结符, Xi+1为非终结符 then for FirstVT 中的每个元素 a do Xi Xi+1 ; end4、构造总控程序 算法描述如下： stack S; k = 1; /符号栈S的使用深度 Sk = # REPEAT 把下一个输入符号读进a中； If Sk VT then j = k else j = k-1; While Sj a do Begin Repeat Q = Sj; if Sj-1 VT then j = j-1 else j = j-2 until Sj Q; 把Sj+1Sk归约为某个N，并输出归约为哪个符号； K = j+1; Sk = N; end of while if Sj a or Sj = a then begin k = k+1; Sk = a end else error /调用出错诊察程序 until a = #5、对给定的表达式，给出准确与否的分析过程6、给出表达式的计算结果。（本步骤可选作）四、实验报告要求1.写出编程思路、源