实验三_算符优先分析算法的设计与实现
实验三算符优先分析算法的设计与实现
（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 a…或 P→Qa…的产生式 do
Insert(P,a)
while stack 非空
begin
栈顶项出栈，记为(Q,a)
for 对每条形如 P→Q…的产生式 do
insert(P,a)
end;
end.
同理，可构造计算LASTVT的算法。
3、构造算符优先分析表
依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。
算法描述如下：
for 每个形如 P->X1X2…X n的产生式 do
for i =1 to n-1 do
begin
if X i和X i+1都是终结符 then
X i = X i+1
if i<= n-2, X i和X i+2 是终结符, 但X i+1 为非终结符 then X i = X i+2
if X i为终结符, X i+1为非终结符 then
for FirstVT 中的每个元素 a do
X i < a ;
if X i为非终结符, X i+1为终结符 then
for LastVT 中的每个元素 a do
a > X i+1 ;
end
4、构造总控程序
算法描述如下：
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 = ‘#’
5、对给定的表达式，给出准确与否的分析过程
6、给出表达式的计算结果。（本步骤可选作）
四、实验报告要求
1.写出编程思路、源代码（或流程图）；
2.写出上机调试时发现的问题，以及解决的过程；
3.写出你所使用的测试数据及结果；
4.谈谈你的体会。
5.上机8小时，完成实验报告2小时。
五、源代码
#include
#include
#include
typedef struct
{
char R;
char r;
int flag;
}array;
typedef struct
{
char E;
char e;
}charLode;
typedef struct
{
charLode *base;
int top;
}charstack;
char str[80][80],arr[80][80],brr[80][80];
array F[20];
int m,kk,p,ppp,FF=1;
char r[10];
int crr[20][20],FLAG=0;
char ccrr1[1][20],ccrr2[20][1];
void Initstack(charstack &s)//定义栈
{
s.base=new charLode[20];
s.top=-1;
}
void push(charstack &s,charLode w) //入栈
{
s.top++;
s.base[s.top].E=w.E;
s.base[s.top].e=w.e;
}
void pop(charstack &s,charLode &w) //出栈
{
w.E=s.base[s.top].E;
w.e=s.base[s.top].e;
s.top--;
}
int IsEmpty(charstack s) //判断是否到栈顶
{
if(s.top==-1)
return 1;
else
return 0;
}
int IsLetter(char ch) //判断是不是大写字母（非终结符）
if(ch>='A'&&ch<='Z')
return 1;
else
return 0;
}
//judge1是判断是否是算符文法：若产生式中含有两个相继的非终结符则不是算符文法int judge1(int n)
{
int j=3,flag=0;
for(int i=0;i<=n;i++)
while(str[i][j]!='\0')
{
char a=str[i][j];
char b=str[i][j+1];
if(IsLetter(a)&&IsLetter(b)) //两个非终结符相连，不是算符文法
{
flag=1;
break;
}
else
j++;
}
if(flag==1) //根据flag设定返回值
return 0;
else
return 1;
}
//judge2是判断文法G是否为算符优先文法：若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法
void judge2(int n)
{
for(int i=0;i<=n;i++)
if(str[i][3]=='~'||FLAG==1)//'~'代表空
{
cout<<"文法G不是算符优先文法!"< FF=0; break; } if(i>n) cout<<"文法G是算符优先文法!"< } //search1是查看存放终结符的数组r中是否含有重复的终结符 int search1(char r[],int kk,char a) { for(int i=0;i if(r[i]==a) break; if(i==kk) return 0; else return 1; } //createF函数是用F数组存放每个终结符与非终结符和组合，并且值每队的标志位为0;F 数组是一个结构体 void createF(int n) { int k=0,i=1;char g; char t[10];//t数组用来存放非终结符 t[0]=str[0][0]; while(i<=n) { if(t[k]!=str[i][0]) { k++; t[k]=str[i][0]; g=t[k]; i++; } else i++; } kk=0; char c; for(i=0;i<=n;i++) { int j=3; while(str[i][j]!='\0') { c=str[i][j]; if(IsLetter(c)==0) { if(!search1(r,kk,c)) r[kk]=c; kk++;//r数组用来存放终结符 } j++; } } m=0; for(i=0;i for(int j=0;j { F[m].R=t[i]; F[m].r=r[j]; F[m].flag=0; m++; } } //search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1 void search(charLode w) { for(int i=0;i if(F[i].R==w.E&&F[i].r==w.e) { F[i].flag=1;break; } } void FirstVT(int n)//求FirstVT { charstack sta; charLode w; int i=0; Initstack(sta); while(i<=n) { int k=3; w.E=str[i][0]; char a=str[i][k]; char b=str[i][k+1]; if(!IsLetter(a)) //产生式的后选式的第一个字符就是终结符的情况 { w.e=a; push(sta,w); search(w); i++; } else if(IsLetter(a)&&b!='\0'&&!IsLetter(b)) //产生式的后选式的第一个字符是非终结符的情况 { w.e=b; push(sta,w); search(w); i++; } else i++; } charLode ww; while(!IsEmpty(sta)) { pop(sta,ww); for(i=0;i<=n;i++) { w.E=str[i][0]; if(str[i][3]==ww.E&&str[i][4]=='\0') { w.e=ww.e; push(sta,w); search(w); break; } } } p=0;int k=1;i=1; while(i { if(F[i-1].flag==1) { arr[p][0]=F[i-1].R; arr[p][k]=F[i-1].r; } while(F[i].flag==0&&i i++; if(F[i].flag==1) { if(F[i].R==arr[p][0]) k++; else {arr[p][k+1]='\0';p++;k=1;} i++; } } } void LastVT(int n)//求LastVT { charstack sta; charLode w; for(int i=0;i F[i].flag=0; i=0; Initstack(sta); while(i<=n) { int k=strlen(str[i]); w.E=str[i][0]; char a=str[i][k-1]; char b=str[i][k-2]; if(!IsLetter(a)) { w.e=a; push(sta,w); search(w); i++; } else if(IsLetter(a)&&!IsLetter(b)) { w.e=b; push(sta,w); search(w); i++; } else i++; } charLode ee; while(!IsEmpty(sta)) { pop(sta,ee); for(i=0;i<=n;i++) { w.E=str[i][0]; if(str[i][3]==ee.E&&str[i][4]=='\0') { w.e=ee.e; push(sta,w); search(w); } } } int k=1;i=1; ppp=0; while(i { if(F[i-1].flag==1) { brr[ppp][0]=F[i-1].R; brr[ppp][k]=F[i-1].r; } while(F[i].flag==0&&i i++; if(F[i].flag==1) { if(F[i].R==arr[ppp][0]) k++; else {brr[ppp][k+1]='\0';ppp++;k=1;} i++; } } } void createYXB(int n)//构造优先表 { int i,j; for(j=1;j<=kk;j++) ccrr1[0][j]=r[j-1]; for( i=1;i<=kk;i++) ccrr2[i][0]=r[i-1]; for(i=1;i<=kk;i++) for(j=1;j<=kk;j++) crr[i][j]=0; int I=0,J=3; while(I<=n) { if(str[I][J+1]=='\0') //扫描右部 { I++; J=3; } else { while(str[I][J+1]!='\0') { char aa=str[I][J]; char bb=str[I][J+1]; if(!IsLetter(aa)&&!IsLetter(bb))//优先及等于的情况，用1值表示等于 { for(i=1;i<=kk;i++) { if(ccrr2[i][0]==aa) break; } for(j=1;j<=kk;j++) { if(ccrr1[0][j]==bb) break; } if(crr[i][j]==0) crr[i][j]=1; else { FLAG=1; I=n+1; } J++; } if(!IsLetter(aa)&&IsLetter(bb)&&str[I][J+2]!='\0'&&!IsLetter(str [I][J+2]))//优先及等于的情况 { for(i=1;i<=kk;i++) { if(ccrr2[i][0]==aa) break; } for(int j=1;j<=kk;j++) { if(ccrr1[0][j]==str[I][J+2]) break; } if(crr[i][j]==0) crr[i][j]=1; else { FLAG=1; I=n+1; } } if(!IsLetter(aa)&&IsLetter(bb))//优先及小于的情况，用2值表示小于 { for(i=1;i<=kk;i++) { if(aa==ccrr2[i][0]) break; } for(j=0;j<=p;j++) { if(bb==arr[j][0]) break; } for(int mm=1;arr[j][mm]!='\0';mm++) { for(int pp=1;pp<=kk;pp++) { if(ccrr1[0][pp]==arr[j][mm]) break; } if(crr[i][pp]==0) crr[i][pp]=2; else { FLAG=1;I=n+1; } } J++; } if(IsLetter(aa)&&!IsLetter(bb))//优先及大于的情况，用3值表示大于 { for(i=1;i<=kk;i++) { if(ccrr1[0][i]==bb) break; } for(j=0;j<=ppp;j++) { if(aa==brr[j][0]) break; } for(int mm=1;brr[j][mm]!='\0';mm++) { for(int pp=1;pp<=kk;pp++) { if(ccrr2[pp][0]==brr[j][mm]) break; } if(crr[pp][i]==0) crr[pp][i]=3; else {FLAG=1;I=n+1;} } J++; } } } } } //judge3是用来返回在归约过程中两个非终结符相比较的值 int judge3(char s,char a) { int i=1,j=1; while(ccrr2[i][0]!=s) i++; while(ccrr1[0][j]!=a) j++; if(crr[i][j]==3) return 3; else if(crr[i][j]==2) return 2; else if(crr[i][j]==1) return 1; else return 0; } void print(char s[],char STR[][20],int q,int u,int ii,int k)//打印归约的过程{ cout< for(int i=0;i<=k;i++) cout< cout<<" "; for(i=q;i<=ii;i++) cout< cout<<" "; } void process(char STR[][20],int ii)//对输入的字符串进行归约的过程 { cout<<"步骤"<<" "<<"符号栈"<<" "<<"输入串"<<" "<<"动作"< int k=0,q=0,u=0,b,i,j; char s[40],a; s[k]='#'; print(s,STR,q,u,ii,k); cout<<"预备"< k++; u++; s[k]=STR[0][q]; q++; print(s,STR,q,u,ii,k); cout<<"移进"< while(q<=ii) { a=STR[0][q]; if(!IsLetter(s[k])) j=k; else j=k-1; b=judge3(s[j],a); if(b==3)//大于的情况进行归约 { while(IsLetter(s[j-1])) j--; for(i=j;i<=k;i++) s[i]='\0'; k=j; s[k]='N'; u++; print(s,STR,q,u,ii,k); cout<<"归约"< } else if(b==2||b==1)//小于或等于的情况移进 { k++; s[k]=a; u++; q++; print(s,STR,q,u,ii,k); if(s[0]=='#'&&s[1]=='N'&&s[2]=='#') cout<<"接受"< else cout<<"移进"< } else { cout<<"出错"< break; } } if(s[0]=='#'&&s[1]=='N'&&s[2]=='#') cout<<"归约成功"< else cout<<"归约失败"< } void main() { int n,i,j; cout<<"请输入你要定义的文法G的产生式的个数n:"; cin>>n; cout<<"请输入文法产生式："< for(i=0;i { gets(str[i]); j=strlen(str[i]); str[i][j]='\0'; } str[i][0]='Q'; //最末行添加扩展 str[i][1]='-'; str[i][2]='>'; str[i][3]='#'; str[i][4]=str[0][0]; str[i][5]='#'; cout<<"你定义的产生式如下:"< str[i][6]='\0'; for(i=0;i<=n;i++) cout< if(judge1(n)==0) //判断文法G是否为算符文法 cout<<"文法G不是算符文法!"< if(judge1(n)==1) { cout<<"文法G是算符文法!"< } createF(n); FirstVT(n); LastVT(n); createYXB(n); for(i=0;i<=p;i++)//打印FirstVT { cout<<"FirstVT("< cout< cout< } cout<<"FirstVT(Q)={#}"< for(i=0;i<=ppp;i++)//打印LastVT { cout<<"LastVT("< cout< cout< } cout<<"LastVT(Q)={#}"< cout<<"优先表如下:"< for(i=1;i { cout<<" "; cout< } cout< for(i=1;i { cout< for(j=1;j { if(crr[i][j]==0) cout<<" "; else if(crr[i][j]==1) cout<<"="; else if(crr[i][j]==2) cout<<"<"; else if(crr[i][j]==3) cout<<">"; cout<<" "; } cout< } judge2(n);//判断文法G是否为算符优先文法 if(FF==1) { char STR[1][20]; cout<<"请输入要规约的字符串:"< int ii=strlen(STR[0]); STR[0][ii]='#'; cout<<"下面是规约的过程:"< process(STR,ii); } } 编译原理实验报告 题目： 算符优先分析法分析器 学 院 计算机科学与技术 专 业 xxxxxxxxxxxxxxxx 学 号 xxxxxxxxxxxx 姓 名 宁剑 指导教师 xxxx 2015年xx 月xx 日 算符优先分析法分析器 装 订 线 一、实验目的 1.理解自底向上优先分析，比较和自顶向下优先分析的不同。 2.理解算符优先分析的特点，体会其和简单优先分析方法的不同。 3.加深对编译器语法分析的理解。 二、实验原理 1.自底向上优先分析方法，也称移进-归约分析，粗略地说它的思想是对输入符号串自左向右进行扫描，并将输入符号逐个移入一个后进先出栈，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可归约串时，就将该产生式的左部非终极符代替相应的右边文法符号串。 2.算符优先分析法的基本思想 首先确定算符（确切地说是终结符）之间的优先关系和结合性质，然后借助这种关系，比较相邻算符之间的优先级来确定句型的可归约串，并进行归约。 注意：算符优先分析过程是自下而上的归约过程，但它的可归约串未必是句柄，也就是说，算符优先分析过程不是一种规归约。 3.终结符号间优先关系的确定，用FIRSTVT和LASTVT计算。 4.最左素短语 所谓素短语是指这样一个短语，它至少含有一个终结符，并且除它自身之外不再含有其它素短语。最左素短语是指处于句型最左边的那个素短语。最左素短语是算符优先分析算法的可归约串。 5.计算得到所给文法的算符优先矩阵 6.算符优先分析的基本过程 三、实验要求 使用算符优先分析算法分析下面的文法： E’→#E# E→E+T|T T→T*F|F F→P^F|P 编译原理课程设计报告_算符优先分析法 编译原理课程设计报告 选题名称: 算符优先分析法 系（院）: 计算机工程学院 专业: 计算机科学与技术 班级: 姓名: 学号: 指导教师: 学年学期: 7>2012 ~ 2013 学年第 1 学期 2012年 12 月 04 日 设计任务书 课题名称算符优先分析法 设计 目的 通过一周的课程设计，对算符优先分析法有深刻的理解，达到巩固理论知识、锻炼实践能力、构建合理知识结构的目的。实验环境Windows2000以上操作系统，Visual C++6.0编译环境 任务要求 1.判断文法是否为算符优先文法，对相应文法字符串进行算符优先分析； 2.编写代码，实现算符优先文法判断和相应文法字符串的算符优先分析； 3.撰写课程设计报告； 4提交报告。工作进度计划序号起止日期工作内容 1 理论辅导，搜集资料 2 ～编写代码，上机调试 3 撰写课程设计报告 4 提交报告 指导教师（签章）： 年月日 摘要： 编译原理是计算机专业重要的一门专业基础课程，内容庞大，涉及面广，知识点多。本次课程设计的目的正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。我们这次课程设计的主要任务是编程实现对输入合法的算符优先文法的相应的字符串进行算符优先分析，并输出算符优先分析的过程。算符优先分析法特别有利于表达式的处理，宜于手工实现。算符优先分析过程是自下而上的归约过程，但这种归约未必是严格的规范归约。而在整个归约过程中，起决定作用的是相继连个终结符之间的优先关系。因此，所谓算符优先分析法就是定义算符之间的某种优先关系，并借助这种关系寻找句型的最左素短语进行归约。通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷。 关键字：编译原理；归约；算符优先分析；最左素短语； 目录 1 课题综述 1 1.1 课题来源 1 1.2课题意义 1 1.3 预期目标 1 1.4 面对的问题 1 2 系统分析 2 实验名称： 实验任务： 对下述描述算符表达式的算符优先文法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的使用深度 编译原理实验3 算符优先分析 一、实验目的 通过设计编制调试构造FIRSTVT集、LASTVT集和构造算符优先表、对给定符号串进行分析的程序，了解构造算符优先分析表的步骤，对文法的要求，生成算符优先关系表的算法，对给定的符号串进行分析的方法。 二、实验内容 1. 给定一文法G，输出G的每个非终结符的FIRSTVT集和LASTVT集。 2. 构造算符优先表。 3. 对给定的符号串进行分析，包含符号栈，符号栈栈顶符号和输入串当前符号的优先级，最左素短语和使用的产生式和采取的动作。 三、程序思路 在文法框内输入待判断文法产生式，格式E->a|S,注意左部和右部之间是“->”，每个产生式一行，ENTER键换行。文法结束再输入一行G->#E# 1. 先做文法判断，即可判断文法情况。 2. 若是算符优先文法，则在优先表栏显示优先表。 3. 写入要分析的句子，按回车即可。 4. 在分析过程栏，可以看到整个归约过程情况 四、实验结果 FunctorFirst.h #include #define rightlength 20 #define product_num 20 // 产生式最多个数 #define num_noterminal 26 // 非终结符最多个数 #define num_terminal 26 // 终结符最多个数 struct Production { char Left; char Right[rightlength]; int num; }; struct VT { bool vt[num_noterminal][num_terminal]; }; struct Stack { char P; char a; }; class CMyDlg { public:CMyDlg(); void InputRule(); CString showLastVT(); CString showFirstVT(); CString shownoTerminal(char G[]); CString showTerminal(char g[]); CString showLeftS(char S[], int j, int k); void InitAll(); CString showSentence(CString sen, int start); CString showStack(char S[], int n); void Initarry(char arry[], int n); CString ProdtoCStr(Production prod); int selectProd(int i, int j, char S[]); void preFunctor(CString sen); void insertFirstVT(Stack S[], int&sp, char P, char a); void insertLastVT(Stack S[], int&sp, char P, char a); void ShowPreTable(); void createPreTable(); 实验三分治算法（2） 一、实验目的与要求 1、熟悉合并排序算法（掌握分治算法） 二、实验题 1、问题陈述: 对所给元素存储于数组中和存储于链表中两中情况，写出自然合并排序算法. 2、解题思路: 将待排序元素分成大小大相同的两个集合,分别对两个集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合.自然排序是通过一次扫描待排元素中自然排好序的子数组,再进行子数组的合并排序. 三、实验步骤 程序代码: #include int target[N],head[N],tail[N]; int i=0,n,m; for(; i 编译原理实验 一实验目的 设计、编制并调试一个算符优先分析算法，加深对此分析法的理解 二实验过程 先在算符栈置“＄”，然后开始顺序扫描表达式，若读来的单词符号是操作数，这直接进操作数栈，然后继续读下一个单词符号。分析过程从头开始，并重复进行；若读来的是运算符θ2则将当前处于运算符栈顶的运算符θ1的入栈优先数f与θ2的比较优先函数g进行比较。 2.2 各种单词符号对应的种别码 2.3 算符优先程序的功能 完成一个交互式面向对象的算符优先分析程序，而一个交互式面向对象的算符优先分析程序基本功能是： （1）输入文法规则 （2）对文法进行转换 （3）生成每个非终结符的FirstVT和LastVT （4）生成算符优先分析表 （5）再输入文法符号 （6）生成移进规约步骤 三设计源码 算符优先分析器 #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; int m,n,N; //转化后文法规则个数 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 南华大学 实验名称：算符优先分析程序 学院：计算机学院 专业班级：本2010 电气信息类03班 学号：20104030342 姓名：谢志兴 指导教师：吴取劲 日期：2012 年 6 月12 日 实验二算符优先分析程序 一、实验目的 调试并完成一个算符优先分析程序，加深对算符优先分析原理的理解。 二、实验要求 算符优先分析程序的功能： 输入：所给文法的源程序字符串、待匹配字符串。 输出：转化后的文法、每个非终结符的FIRSTVT集和LASTVT集、算符优先分析表、规约过程。 三、源程序代码： #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 实验任务： 对下述描述算符表达式的算符优先文法G[E],给出算符优先分析的实验结果。 E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 说明： 优先关系矩阵的构造过程： （1）= 关系 由产生式F->(E) 知‘（’=‘）’ FIRSTVT集 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)优先关系矩阵 + - * / ( ) i # + > > < < < > < > - > > < < < > < > * > > > > < > < > / > > > > < > < > ( < < < < < = < ) > > > > > > i > > > > > > # < < < < < < = 终结符之间的优先关系是唯一的，所以该文法是算符优先文法。 程序的功能描述： 程序由文件读入字符串（以#结束），然后进行算符优先分析， 实验5 语法分析程序的设计（2） 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。 二、实验内容 设计一个文法的算法优先分析程序，判断特定表达式的正确性。 三、实验要求 1、给出文法如下： G[E] E->T|E+T; T->F|T*F; F->i|(E); + * ( ) i + * ( ) i 2、计算机中表示上述优先关系，优先关系的机内存放方式有两种1）直接存放，2）为 优先关系建立优先函数，这里由学生自己选择一种方式； 1、给出算符优先分析算法如下： k:=1; S[k]:=‘#’; REPEAT 把下一个输入符号读进a中； IF S[k]∈V T THEN j:=k ELSE j:=k-1; WHILE S[j] a DO BEGIN REPEAT Q:=S[j]; IF S[j-1]∈V T 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=‘#’ 1、 根据给出算法，利用适当的数据结构实现算符优先分析程序； 2、 利用算符优先分析程序完成下列功能： 1） 手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束； 2） 读入文本文件中的表达式； 3） 调用实验2中的词法分析程序搜索单词； 4） 把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语 言），若错误，应给出错误信息； 5） 完成上述功能，有余力的同学可以对正确的表达式计算出结果。 四、实验环境 PC 微机 DOS 操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、 分析文法中终结符号的优先关系； 2、 存放优先关系或构造优先函数； 3、利用算符优先分析的算法编写分析程序； 4、写测试程序，包括表达式的读入和结果的输出； 5、程序运行效果，测试数据可以参考下列给出的数据。 六、测试数据 输入数据： 编辑一个文本文文件expression.txt ，在文件中输入 如下内容： 正确 结果： （1）10; 输出：正确 （2）1+2; 输出：正确 （3）(1+2)*3+(5+6*7); 输出：正确 （4）((1+2)*3+4 10; 1+2; (1+2)*3+(5+6*7); ((1+2)*3+4; 1+2+3+(*4+5); (a+b)*(c+d); ((ab3+de4)**5)+1; 一、实验目的与任务 算术表达式和赋值语句的文法可以是（你可以根据需要适当改变）： S→i=E E→E+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,r1) (=,b,r2,-) （3）输出：(+,r1,1,2) (/,r2,r1,3) (/,r3,6,7) (+,r4,5,r3,) (+,r5,r2,4) (-,r6,r5,r4) (=,c,r6,-) 五、实验有关附件（如程序、附图、参考资料，等） ... ... h == '#') o][Peek(n0).No]; if(r == '<') h == 'E'&& Peek(1).ch == '#' && Token[ipToken].ch == '#') return TRUE; else return FALSE; } h) { k = TRUE; h == 'E') { n ++; } return n; } 词结束（遇到“#”号），无法移进，需要规约，返回：1 词没有结束，需判断是否可以移进 栈单词<=单词：移进后返回：2 栈单词>单词：不能移进，需要规约，返回：1 单词没有优先关系：出错，返回：-1 int MoveIn() { SToken s,t; h = '#'; 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生：俞梦真 指导教师：郝晓丽 2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 编译原理实验报告 实验名称：编写语法分析分析器实验类型： 指导教师： 专业班级： 学号： 电子邮件： 实验地点： 实验成绩： 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。 1、选择最有代表性的语法分析方法，如LL(1) 语法分析程序、算符优先分析程序和LR分析分析程序，至少选一题。 2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 二、实验过程 编写算符优先分析器。要求： （a）根据算符优先分析算法，编写一个分析对象的语法分析程序。读者可根据自己的能力选择以下三项(由易到难)之一作为分析算法中的输入： Ⅰ：通过构造算符优先关系表，设计编制并调试一个算法优先分析程序Ⅱ：输入FIRSTVT，LASTVT集合，由程序自动生成该文法的算符优先关系矩阵。 Ⅲ：输入已知文法，由程序自动生成该文法的算符优先关系矩阵。（b）程序具有通用性，即所编制的语法分析程序能够使用于不同文法以及各种输入单词串，并能判断该文法是否为算符文法和算符优先文法。 （c）有运行实例。对于输入的一个文法和一个单词串，所编制的语法分析程序应能正确地判断，此单词串是否为该文法的句子，并要求输出分析过程。 三、实验结果 算符优先分析器： 测试数据：E->E+T|T T->T*F|F F->(E)|i 实验结果：(输入串为i+i*i+i) 四、讨论与分析 自下而上分析技术－算符优先分析法： 算符文法：一个上下无关文法G，如果没有且没有P→..QR...(P ,Q ,R属于非终结符)，则G是一个算符文法。 FIRSTVT集构造 1、若有产生式P →a...或P →Qa...，则a∈FIRSTVT(P)。 2、若有产生式P→...，则FIRSTVT(R)包含在FIRSTVT(P)中。由优先性低于的定义和firstVT集合的定义可以得出：若存在某个产生式：…P…，则对所有：b∈firstVT(P)都有：a≦b。 构造优先关系表： 1、如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。 2、若产生式右部有...aP...的形式，则对于每个b∈FIRSTVT(P)都有 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i; 华北水利水电学院编译原理实验报告 一、实验题目：语法分析（算符优先分析程序） （1）选择最有代表性的语法分析方法算符优先法； （2）选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 二、实验内容 （1）根据给定文法，先求出FirstVt和LastVt集合，构造算符优先关系表（要求算符优先关系表输出到屏幕或者输出到文件）； （2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程） （3）给定表达式文法为： G(E’): E’→#E# E→E+T | T T→T*F |F F→(E)|i (4) 分析的句子为: (i+i)*i和i+i)*i 三、程序源代 #include 算法设计与分析课程实验项目目录 学生：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的： S END +MORE MONEY . 这里有两个前提假设： 第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 该算法程序代码如下： #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l #include 算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4．实现具体的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9) 三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i 实验三算符优先分析算法的设计与实现 （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 a…或 P→Qa…的产生式 do Insert(P,a) while stack 非空 begin 栈顶项出栈，记为(Q,a) for 对每条形如 P→Q…的产生式 do insert(P,a) end; end. 同理，可构造计算LASTVT的算法。 3、构造算符优先分析表 依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。 算法描述如下： for 每个形如 P->X1X2…X n的产生式 do for i =1 to n-1 do begin if X i和X i+1都是终结符 then X i = X i+1 if i<= n-2, X i和X i+2 是终结符, 但X i+1 为非终结符 then X i = X i+2 if X i为终结符, X i+1为非终结符 then for FirstVT 中的每个元素 a do X i < a ; if X i为非终结符, X i+1为终结符 then for LastVT 中的每个元素 a do a > X i+1 ; end 4、构造总控程序 算法描述如下： stack S; k = 1; //符号栈S的使用深度 S[k] = ‘#’ REPEAT算符优先分析器设计实验报告--宁剑
编译原理课程设计报告_算符优先分析法
实验4 算符优先分析法.
编译原理 实验3 算符优先分析
算法设计与分析实验三
算符优先分析算法(c语言).(优选)
算符优先分析程序
算符优先报告及代码
编译原理实验报告5-语法分析程序的设计(2)
编译原理实验4算符优先算法
算法设计与分析实验报告
编译原理-语法分析-算符优先文法分析器
《算法设计与分析》递归算法典型例题
编译原理_实验报告实验二__语法分析(算符优先) 2
《算法设计与分析》实验报告
c语言实现算符优先语法分析
算法设计与分析实验报告 统计数字问题
实验3 算符优先分析算法的设计与实现