实验三算符优先分析算法的设计与实现
实验三 算符优先分析算法的设计与实现
（8学时）
一、 实验目的
根据算符优先分析法，对表达式进行语法分析，使其能够判断一个表达式是否正确。通过算符优先分析方法的实现，加深对自下而上语法分析方法的理解。
二、 实验要求
1、输入文法。可以是如下算术表达式的文法（你可以根据需要适当改变）： E→E+T|E-T|T
T→T*F|T/F|F F→（E）|i
2、对给定表达式进行分析，输出表达式正确与否的判断。 程序输入/输出示例： 输入：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 firstvt[N][N],lastvt[N][N],table[N][N];
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 F[P,a] then begin
F[P,a] = true; //(P,a)进栈 end;
Procedure FirstVT; Begin
for 对每个非终结符 P和终结符 a do F[P,a] = false for 对每个形如 P Insert(P,a) while stack 非空 begin
栈顶项出栈，记为(Q,a)
for 对每条形如 P→Q…的产生式 do insert(P,a) end; end.
同理，可构造计算LASTVT的算法。 3、构造算符优先分析表
依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。 算法描述如下：
for 每个形如 P->X1X2…Xn的产生式 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 < a ;
if Xi为非终结符, Xi+1为终结符 then for LastVT 中的每个元素 a do a > Xi+1 ; end
4、构造总控程序 算法描述如下： stack S;
k = 1; //符号栈S的使用深度 S[k] = ‘#’ REPEAT
a…或 P→Qa…的产生式 do
实验三算符优先分析算法的设计与实现
把下一个输入符号读进a中；
If S[k] ? VT then j = k else j = k-1; While S[j] > a do Begin Repeat
Q = S[j];
if S[j-1] ? VT then j = j-1 else j = j-2 until S[j] < Q;
把S[j+1]…S[k]归约为某个N，并输出归约为哪个符号； K = j+1; S[k] = N; end of while
if S[j] < a or S[j] = a then
begin k = k+1; S[k] = a end else error //调用出错诊察程序 until a = ‘#’
5、对给定的表达式，给出准确与否的分析过程 6、给出表达式的计算结果。（本步骤可选作）
四、实验报告要求
1.写出编程思路、源代码（或流程图）；
2.写出上机调试时发现的问题，以及解决的过程； 3.写出你所使用的测试数据及结果； 4.谈谈你的体会。
5.上机8小时，完成实验报告2小时。
五、源代码 #include
#include
typedef struct {
char R; char r; int flag; }array;
typedef struct {
char E; char e; }charLode;