算符优先算法实验报告.doc
文本预览下载声明
算符优先算法实验报告
实验3 算符优先分析算法的设计与实现
实验三 算符优先分析算法的设计与实现
（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] ? VTthen 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 elsej = 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] = aend
else error //调用出错诊察程序
until a = ‘#’
5、对给定的表达式，给出准确与否的分析过程
6、给出表达式的计算结果。（本步骤可选作）
四、实验报告要求
1.写出编程思路、源代码（或流程图）；
2.写出上机调试时发现的问题，以及解决的过程；
3.写出你所使用的测试数据及结果；
4.谈谈你的体会。
5.上机8小时，完成实验报告2小时。
程序代码:
#includestdio.h
#include stdlib.h
#include iostream.h
char data[20][20]; //算符优先关系
char s[100]; //模拟符号栈s
显示全部