实验名称:
实验任务:
对下述描述算符表达式的算符优先文法 G[E],给出算符优先分析的实
验结果。
实验内容:
有上下无关文法如下:
E->E+T|E-T|T
T->T*F|T/F|F
F->(E)|i
说明: 优先关系矩阵的构造过程:
(1) = 关系 由产生式 F->(E) 知 ‘(’=‘)’
FIRSTVT 集 及 LASTVT 集
FIRSTVT(E)={ +,-,*,/,(,i }
FIRSTVT(F)={ (,i }
FIRSTVT(T)={ *,/,(,i }
LASTVT(E)={ +,-,*,/,),i }
LASTVT(F)={ ),i }
LASTVT(T)={ *,/,),i }
(2) < 关系
+T 则有:+ < FIRSTVT(T)
-T 则有:- < FIRSTVT(T)
*F 则有:* < FIRSTVT(F)
/F 则有:/ < FIRSTVT(F)
(E 则有:( < FIRSTVT(E)
(3) > 关系
E+ 则有: LASTVT(E) > +
E- 则有: LASTVT(E) > -
T* 则有: LASTVT(T) > *
T/ 则有: LASTVT(T) > /
E) 则有: LASTVT(E) > )
(4)请大家画出优先关系矩阵
终结符之间的优先关系是唯一的,所以该文法是算符优先文法。 程
序的功能描述: 程序由文件读入字符串(以#结束),然后进行算符
优先分析,分析过程中如有错误,则终止程序并报告错误位置,最终
向屏幕输出移近——规约过程。
(5)依据文法和求出的相应 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
(6)构造总控程序
算法描述如下:
stack S; k = 1; //符号栈 S 的使用深度
S[k] = ‘#’
REPEAT
把下一个输入符号读进 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 = ‘#’
(7)代码如下:
#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
char data[20][20]; //算符优先关系
char s[100]; //模拟符号栈 s
char lable[20]; //文法终极符集
char input[100]; //文法输入符号串
char string[20][10]; //用于输入串的分析
int k;
char a;
int j;
char q;
int r; //文法规则个数
int r1; //转化后文法规则个数
char st[10][30]; //用来存储文法规则
char first[10][10]; //文法非终结符 FIRSTVT 集
char last[10][10]; //文法非终结符 LASTVT 集
int fflag[10]={0}; //标志第 i 个非终结符的 FIRSTVT 集是否已求出
int lflag[10]={0}; //标志第 i 个非终结符的 LASTVT 集是否已求出
int deal(); //对输入串的分析
int zhongjie(char c); //判断字符 c 是否是终极符
int xiabiao(char c); //求字符 c 在算符优先关系表中的下标
void out(int j,int k,char *s); //打印 s 栈
void firstvt(char c); //求非终结符 c 的 FIRSTVT 集
void lastvt(char c); //求非终结符 c 的 LASTVT 集
void table(); //创建文法优先关系表
void main()
{
int i,j,k=0;
printf("请输入文法规则数:");
scanf("%d",&r);
printf("请输入文法规则:\n");
for(i=0;i<r;i++)
{
scanf("%s",st[i]); //存储文法规则,初始化 FIRSTVT 集和 LASTVT 集*/
first[i][0]=0; /*first[i][0]和 last[i][0]分别表示 st[i][0]非终极
符的 FIRSTVT 集和 LASTVT 集中元素的个数*/
评论12