语法分析Word文件下载.docx
《语法分析Word文件下载.docx》由会员分享，可在线阅读，更多相关《语法分析Word文件下载.docx（25页珍藏版）》请在冰点文库上搜索。
（1）若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；
否则出错。
（2）若是非终结符号，则调用与此非终结符对应的过程。
当A的右部有多个产生式时,可用选择结构实现,具体为：
（1）对于每个非终结符号U->
u1|u2|…|un处理的方法如下
U（）
{
ch=当前符号;
if（ch可能是u1字的开头）处理u1的程序部分；
elseif（ch可能是u2字的开头）处理u2的程序部分；
…..
elseerror（）;
}
（2）对于每个右部u1->
x1x2…xn的处理架构如下：
处理x1的程序；
处理x2的程序；
……
处理xn的程序；
（3）如果非终结符U有空产生式：
Uε，则还需考虑ch属于Follow（U）的情况。
F程序要求：
对算术表达式文法，用递归下降分析法（或预测分析方法、算符优先分析方法等）对任意输入的符号串进行分析，如合法给出相应信息，如果不合法，最好能给出发生错误的位置。
算术表达式至少包含+、-、*、/、（）。
例如：
32+123*（34-58/2）
原
理
（
算
法
流
程
）
自顶向下语法分析法指从文法开始符号出发，企图推导出与输入单词串完全相匹配的句子旺其宗旨在于对任何输入单词串用一切可能的办法，从文法开始符号出发自上而下从左到右为输入串建立分析树，若输入串是给定文法的句子，则必能建立。
其本质是一种试探过程，反复使用不同的产生式谋求与输入串匹配的过程。
算法的关键在于利用堆栈先进后出的功能保留程序正在处理文法规则节点的位置信息，借助于递归算法的递归功能进行穷举试探，使处理流程在进入某条文法规则之后发现该文法规则不符合，可以退出到上一次的情况，对后续的文法规则进行处理。
序
界
面
效
果
图
输入S->
a：
输出：
代
码
#include<
iostream.h>
string.h>
stdio.h>
typedefstruct
{
charR;
charr;
intflag;
}array;
typedefstruct
charE;
chare;
}charLode;
charLode*base;
inttop;
}charstack;
charstr[80][80],arr[80][80],brr[80][80];
arrayF[20];
intm,kk,p,ppp,FF=1;
charr[10];
intcrr[20][20],FLAG=0;
charccrr1[1][20],ccrr2[20][1];
voidInitstack（charstack&
s）//定义栈
s.base=newcharLode[20];
s.top=-1;
voidpush（charstack&
s,charLodew）//入栈
s.top++;
s.base[s.top].E=w.E;
s.base[s.top].e=w.e;
voidpop（charstack&
s,charLode&
w）//出栈
w.E=s.base[s.top].E;
w.e=s.base[s.top].e;
s.top--;
intIsEmpty（charstacks）//判断是否到栈顶
if（s.top==-1）
return1;
else
return0;
intIsLetter（charch）//判断是不是大写字母（非终结符）
if（ch>
='
A'
&
ch<
Z'
//judge1是判断是否是算符文法：
若产生式中含有两个相继的非终结符则不是算符文法
intjudge1（intn）
intj=3,flag=0;
for（inti=0;
i<
=n;
i++）
while（str[i][j]!
\0'
chara=str[i][j];
charb=str[i][j+1];
if（IsLetter（a）&
IsLetter（b））//两个非终结符相连，不是算符文法
flag=1;
break;
}
j++;
if（flag==1）//根据flag设定返回值
else
//judge2是判断文法G是否为算符优先文法：
若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法
voidjudge2（intn）
if（str[i][3]=='
~'
||FLAG==1）//'
代表空
cout<
<
"
文法G不是算符优先文法!
endl;
FF=0;
if（i>
n）
文法G是算符优先文法!
//search1是查看存放终结符的数组r中是否含有重复的终结符
intsearch1（charr[],intkk,chara）
kk;
if（r[i]==a）
if（i==kk）
//createF函数是用F数组存放每个终结符与非终结符和组合，并且值每队的标志位为0;
F数组是一个结构体
voidcreateF（intn）
intk=0,i=1;
charg;
chart[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++;
elsei++;
kk=0;
charc;
for（i=0;
{
intj=3;
c=str[i][j];
if（IsLetter（c）==0）
if（!
search1（r,kk,c））
r[kk]=c;
kk++;
//r数组用来存放终结符
m=0;
k;
for（intj=0;
j<
kk-1;
j++）
F[m].R=t[i];
F[m].r=r[j];
F[m].flag=0;
m++;
//search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1
voidsearch（charLodew）
m;
if（F[i].R==w.E&
F[i].r==w.e）
F[i].flag=1;
break;
voidFirstVT（intn）//求FirstVT
charstacksta;
charLodew;
inti=0;
Initstack（sta）;
intk=3;
w.E=str[i][0];
chara=str[i][k];
charb=str[i][k+1];
IsLetter（a））//产生式的后选式的第一个字符就是终结符的情况
w.e=a;
push（sta,w）;
search（w）;
elseif（IsLetter（a）&
b!
!
IsLetter（b））//产生式的后选式的第一个字符是非终结符的情况
w.e=b;
charLodeww;
while（!
IsEmpty（sta））
pop（sta,ww）;
if（str[i][3]==ww.E&
str[i][4]=='
w.e=ww.e;
p=0;
intk=1;
i=1;
m）
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&
if（F[i].flag==1）
if（F[i].R==arr[p][0]）
else{arr[p][k+1]='
;
p++;
k=1;
}
voidLastVT（intn）//求LastVT
F[i].flag=0;
i=0;
intk=strlen（str[i]）;
chara=str[i][k-1];
charb=str[i][k-2];
IsLetter（a））
IsLetter（b））
charLodeee;
pop（sta,ee）;
if（str[i][3]==ee.E&
w.e=ee.e;
intk=1;
ppp=0;
brr[ppp][0]=F[i-1].R;
brr[ppp][k]=F[i-1].r;
if（F[i].R==arr[ppp][0]）
else{brr[ppp][k+1]='
ppp++;
voidcreateYXB（intn）//构造优先表
inti,j;
for（j=1;
=kk;
ccrr1[0][j]=r[j-1];
for（i=1;
ccrr2[i][0]=r[i-1];
for（i=1;
crr[i][j]=0;
intI=0,J=3;
while（I<
if（str[I][J+1]=='
）//扫描右部
I++;
J=3;
while（str[I][J+1]!
charaa=str[I][J];
charbb=str[I][J+1];
IsLetter（aa）&
IsLetter（bb））//优先及等于的情况，用1值表示等于
if（ccrr2[i][0]==aa）
if（ccrr1[0][j]==bb）
if（crr[i][j]==0）
crr[i][j]=1;
else{
FLAG=1;
I=n+1;
J++;
IsLetter（bb）&
str[I][J+2]!
IsLetter（str[I][J+2]））//优先及等于的情况
for（intj=1;
if（ccrr1[0][j]==str[I][J+2]）
IsLetter（bb））//优先及小于的情况，用2值表示小于
if（aa==ccrr2[i][0]）
for（j=0;
=p;
if（bb==arr[j][0]）
for（intmm=1;
arr[j][mm]!
mm++）
for（intpp=1;
pp<
pp++）
if（ccrr1[0][pp]==arr[j][mm]）
if（crr[i][pp]==0）
crr[i][pp]=2;
I=n+1;
if（IsLetter（aa）&
IsLetter（bb））//优先及大于的情况，用3值表示大于
if（ccrr1[0][i]==bb）
=ppp;
if（aa==brr[j][0]）
brr[j][mm]!
if（ccrr2[pp][0]==brr[j][mm]）
if（crr[pp][i]==0）
crr[pp][i]=3;
else{FLAG=1;
//judge3是用来返回在归约过程中两个非终结符相比较的值
intjudge3（chars,chara）
inti=1,j=1;
while（ccrr2[i][0]!
=s）
while（ccrr1[0][j]!
=a）
if（crr[i][j]==3）
return3;
if（crr[i][j]==2）
return2;
if（crr[i][j]==1）
voidprint（chars[],charSTR[][20],intq,intu,intii,intk）//打印归约的过程
u<
"
=k;
s[i];
for（i=q;
=ii;
STR[0][i];
voidprocess（charSTR[][20],intii）//对输入的字符串进行归约的过程
{
步骤"
符号栈"
输入串"
动作"
intk=0,q=0,u=0,b,i,j;
chars[40],a;
s[k]='
#'
print（s,STR,q,u,ii,k）;
预备"
u++;
s[k]=STR[0][q];
q++;
移进"
while（q<
=ii）
a=STR[0][q];
IsLetter（s[k]））j=k;
elsej=k-1;
b=judge3（s[j],a）;
if（b==3）//大于的情况进行归约
while（IsLetter（s[j-1]））
j--;
for（i=j;
s[i]='
k=j;
N'
归约"
elseif（b==2||b==1）//小于或等于的情况移进
s[k]=a;
if（s[0]=='
s[1]=='
s[2]=='
接受"
elsecout<
出错"
归约成功"
归约失败"
voidmain（）
intn,i,j;
请输入你要定义的文法G的产生式的个数n:
cin>
>
n;
请输入文法产生式：
gets（str[i]）;
j=strlen（str[i]）;
str[i][j]='
str[i][0]='
Q'
//最末行添加扩展
str[i][1]='
-'
str[i][2]='
'
str[i][3]='
str[i][4]=str[0][0];
str[i][5]='
你定义的产生式如下:
str[i][6]='
str[i]<
if（judge1（n）==0）//判断文法G是否为算符文法
文法G不是算符文法!
if（judge1（n）==1）
文法G是算符文法!
createF（n）;
FirstVT（n）;
LastVT（n）;
createYXB（n）;
i++）//打印FirstVT
FirstVT（"
arr[i][0]<
）={"
for（intl=1;
arr[i][l+1]!
l++）
arr[i][l]<
"
}"
FirstVT（Q）={#}"
i++）//打印LastVT
LastVT（"
brr[i][l+1]!
brr[i][l]<
LastVT（Q）={#}"
优先表如下:
i++）//打印优先关系表
ccrr1[0][i];
ccrr2[i][0]<
elseif（crr[i][j]==1）
="
elseif（crr[i][j]==2）
elseif（crr[i][j]==3）
judge2（n）;
//判断文
升级会员 