1、(1)若是终结符号,则和向前看符号对照,若匹配则向前进一个符号;否则出错。(2)若是非终结符号,则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现, 具体为:(1)对于每个非终结符号U-u1|u2|un处理的方法如下 U( ) ch=当前符号; if(ch可能是u1字的开头) 处理u1的程序部分; else if(ch可能是u2字的开头)处理u2的程序部分; . else error();(2)对于每个右部u1-x1x2xn的处理架构如下: 处理x1的程序; 处理x2的程序; 处理xn的程序;(3)如果非终结符U有空产生式:U ,则还需考虑ch属于Follow(U)的情况
2、。F程序要求:对算术表达式文法,用递归下降分析法(或预测分析方法、算符优先分析方法等)对任意输入的符号串进行分析,如合法给出相应信息,如果不合法,最好能给出发生错误的位置。算术表达式至少包含+、-、*、/、()。例如:32 + 123 * ( 34 - 58 / 2 )原理(算法流程)自顶向下语法分析法指从文法开始符号出发 ,企图推导出与输入单词串完全相匹配的句子旺其宗旨在于对任何输入单词串用一切可能的办法 ,从文法开始符号出发自上而下从左到右为输入串建立分析树,若输入串是给定文法的句子 ,则必能建立。其本质是一种试探过程,反复使用不同的产生式谋求与输入 串匹配的过程。算法的关键在于利用堆栈先
3、进后 出的功能保留程序正在处理文法规则节点的位置信息,借助于递归算法的递归功能进行穷举试探 ,使处理流程在进入某条文法规则之后发现该文法规则不符合 ,可以退出到上一次的情况,对后续的文法规则进行处理。序界面效果图输入S-a:输出:代码#includestring.hstdio.htypedef struct char R; char r; int flag;array;typedef struct char E; char e;charLode; charLode *base; int top;charstack;char str8080,arr8080,brr8080;array F20;i
4、nt m,kk,p,ppp,FF=1;char r10;int crr2020,FLAG=0;char ccrr1120,ccrr2201;void Initstack(charstack &s)/定义栈 s.base=new charLode20; s.top=-1;void push(charstack &s,charLode w) /入栈 s.top+; s.bases.top.E=w.E; s.bases.top.e=w.e;void pop(charstack &s,charLode &w) /出栈 w.E=s.bases.top.E; w.e=s.bases.top.e; s.to
5、p-;int IsEmpty(charstack s) /判断是否到栈顶 if(s.top=-1) return 1; else return 0;int IsLetter(char ch) /判断是不是大写字母(非终结符) if(ch=A&chZ/judge1是判断是否是算符文法:若产生式中含有两个相继的非终结符则不是算符文法int judge1(int n) int j=3,flag=0; for(int i=0;i=n;i+) while(strij!0 char a=strij; char b=strij+1; if(IsLetter(a)&IsLetter(b) /两个非终结符相连,
6、不是算符文法 flag=1; break; j+; if(flag=1) /根据flag设定返回值 else/judge2是判断文法G是否为算符优先文法:若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法void judge2(int n) if(stri3=|FLAG=1)/代表空 coutn)文法G是算符优先文法!/search1是查看存放终结符的数组r中是否含有重复的终结符int search1(char r,int kk,char a)kk; if(ri=a) if(i=kk) /createF函数是用F数组存放每个终结符与非终结符和组合,并且值每队的标志位为0;F
7、数组是一个结构体void createF(int n) int k=0,i=1;char g; char t10;/t数组用来存放非终结符 t0=str00; while(i=n) if(tk!=stri0) k+; tk=stri0; g=tk; i+; else i+; kk=0; char c; for(i=0; int j=3; c=strij; if(IsLetter(c)=0) if(!search1(r,kk,c) rkk=c; kk+;/r数组用来存放终结符 m=0;k; for(int j=0;jkk-1;j+) Fm.R=ti; Fm.r=rj; Fm.flag=0; m+
8、;/search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1void search(charLode w)m; if(Fi.R=w.E&Fi.r=w.e) Fi.flag=1;break;void FirstVT(int n)/求FirstVT charstack sta; charLode w; int i=0; Initstack(sta); int k=3; w.E=stri0; char a=strik; char b=strik+1;IsLetter(a) /产生式的后选式的第一个字符就是终结符的情况 w.e=a; push(sta,w); search(w); els
9、e if(IsLetter(a)&b!IsLetter(b) /产生式的后选式的第一个字符是非终结符的情况 w.e=b; charLode ww; while(!IsEmpty(sta) pop(sta,ww); if(stri3=ww.E&stri4= w.e=ww.e; p=0;int k=1;i=1;m) if(Fi-1.flag=1) arrp0=Fi-1.R; arrpk=Fi-1.r; while(Fi.flag=0& if(Fi.flag=1) if(Fi.R=arrp0) else arrpk+1=;p+;k=1; void LastVT(int n)/求LastVT Fi.f
10、lag=0; i=0; int k=strlen(stri); char a=strik-1; char b=strik-2;IsLetter(a)IsLetter(b) charLode ee; pop(sta,ee); if(stri3=ee.E& w.e=ee.e; int k=1; ppp=0; brrppp0=Fi-1.R; brrpppk=Fi-1.r; if(Fi.R=arrppp0) else brrpppk+1=ppp+;void createYXB(int n)/构造优先表 int i,j; for(j=1;=kk; ccrr10j=rj-1; for( i=1; ccrr
11、2i0=ri-1; for(i=1; crrij=0; int I=0,J=3; while(I if(strIJ+1=) /扫描右部 I+; J=3; while(strIJ+1! char aa=strIJ; char bb=strIJ+1;IsLetter(aa)&IsLetter(bb)/优先及等于的情况,用1值表示等于 if(ccrr2i0=aa) if(ccrr10j=bb) if(crrij=0) crrij=1; else FLAG=1; I=n+1; J+;IsLetter(bb)&strIJ+2!IsLetter(strIJ+2)/优先及等于的情况 for(int j=1;
12、 if(ccrr10j=strIJ+2)IsLetter(bb)/优先及小于的情况,用2值表示小于 if(aa=ccrr2i0) for(j=0;=p; if(bb=arrj0) for(int mm=1;arrjmm!mm+) for(int pp=1;pppp+) if(ccrr10pp=arrjmm) if(crripp=0) crripp=2;I=n+1; if(IsLetter(aa)&IsLetter(bb)/优先及大于的情况,用3值表示大于 if(ccrr10i=bb)=ppp; if(aa=brrj0)brrjmm! if(ccrr2pp0=brrjmm) if(crrppi=
13、0) crrppi=3; else FLAG=1;/judge3是用来返回在归约过程中两个非终结符相比较的值int judge3(char s,char a) int i=1,j=1; while(ccrr2i0!=s) while(ccrr10j!=a) if(crrij=3) return 3; if(crrij=2) return 2; if(crrij=1)void print(char s,char STR20,int q,int u,int ii,int k)/打印归约的过程u =k;si; for(i=q;=ii;STR0i;void process(char STR20,int
14、 ii)/对输入的字符串进行归约的过程 步骤符号栈输入串动作 int k=0,q=0,u=0,b,i,j; char s40,a; sk=# print(s,STR,q,u,ii,k);预备 u+; sk=STR0q; q+;移进 while(q=ii) a=STR0q;IsLetter(sk) j=k; else j=k-1; b=judge3(sj,a); if(b=3)/大于的情况进行归约 while(IsLetter(sj-1) j-; for(i=j; si= k=j;N归约 else if(b=2|b=1)/小于或等于的情况移进 sk=a; if(s0=s1=s2=接受 else
15、coutn;请输入文法产生式: gets(stri); j=strlen(stri); strij= stri0=Q /最末行添加扩展 stri1=- stri2= stri3= stri4=str00; stri5=你定义的产生式如下: stri6=stri if(judge1(n)=0) /判断文法G是否为算符文法文法G不是算符文法! if(judge1(n)=1)文法G是算符文法! createF(n); FirstVT(n); LastVT(n); createYXB(n);i+)/打印FirstVTFirstVT(arri0)= for(int l=1;arril+1!l+)arril,FirstVT(Q)=#i+)/打印LastVTLastVT(brril+1!brrilLastVT(Q)=#优先表如下:i+)/打印优先关系表ccrr10i;ccrr2i0 else if(crrij=1)= else if(crrij=2) else if(crrij=3) judge2(n);/判断文
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2