/*LL(1)分析法源程序,只能在VC++中运行 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<dos.h>
char A[20]; /*分析栈*/
char B[20]; /*剩余串*/
char v1[20]={'x','y','z','#'}; /*终结符 */
char v2[20]={'S','P','Q'}; /*非终结符 */
int j=0,b=0,top=0,l; /*L为输入串长度 */
typedef struct type /*产生式类型定义 */
{
char origin; /*大写字符 */
char array[5]; /*产生式右边字符 */
int length; /*字符个数 */
}type;
type s,s1,p,p1,q,q1; /*结构体变量 */
type C[4][3]; /*预测分析表 */
/*--------------------------------*/
/*输出分析栈 */
void print()
{
int a; /*指针*/
for(a=0;a<=top+1;a++)
printf("%c",A[a]);
printf("\t\t");
}
/*--------------------------------*/
/*输出剩余串*/
void print1()
{
int j;
for(j=0;j<b;j++) /*输出对齐符*/
printf(" ");
for(j=b;j<=l;j++)
printf("%c",B[j]);
printf("\t\t\t");
}
/*--------------------------------*/
void main()
{
int m,n,k=0,flag=0,finish=0;
char ch,x;
type cha;/*用来接受C[m][n]*/
/*把文法产生式赋值结构体*/
s.origin='S'; strcpy(s.array,"xQz"); s.length=3;
s1.origin='S'; strcpy(s1.array,"yPQ"); s1.length=3;
p.origin='P'; strcpy(p.array,"xPy"); p.length=3;
p1.origin='P'; strcpy(p1.array,"y"); p1.length=1;
q.origin='Q'; strcpy(q.array,"y"); q.length=1;
q1.origin='Q'; q1.array[0]='^'; q1.length=1;
/*初始化分析表*/
for(m=0;m<=4;m++)
for(n=0;n<=3;n++)
C[m][n].origin='N';/*全部赋为空*/
/*填充分析表*/
C[0][0]=s; C[0][1]=s1;
C[1][0]=p; C[1][1]=p1;
C[2][1]=q; C[2][3]=q1; C[2][4]=q1;
printf("提示:本程序只能对由'x','y','z'构成的以'#'结束的字符串进行分析,\n");
printf("请输入要分析的字符串:");
do/*读入分析串*/
{
scanf("%c",&ch);
if ((ch!='x') &&(ch!='y') &&(ch!='z')&&(ch!='#'))
{
printf("输入串中有非法字符\n");
exit(1);
}
B[j]=ch;
j++;
}while(ch!='#');
l=j; /*分析串长度*/
ch=B[0]; /*当前分析字符*/
A[top]='#'; A[++top]='S'; /*'#','E'进栈*/
printf("步骤\t\t分析栈 \t\t剩余字符 \t\t所用产生式 \n");
do
{
x=A[top--];/*x为当前栈顶字符*/
printf("%d",k++);
printf("\t\t");
for(j=0;j<=3;j++)/*判断是否为终结符*/
if(x==v1[j])
{
flag=1;
break;
}
if(flag==1)/*如果是终结符*/
{
if(x=='#')
{
finish=1; /*结束标记*/
printf("acc!\n"); /*接受 */
getchar();
exit(1);
}
if(x==ch)
{
print();
print1();
printf("%c匹配\n",ch);
ch=B[++b]; /*下一个输入字符*/
flag=0; /*恢复标记*/
}
else
{ /*出错处理*/
print();
print1();
printf("%c出错\n",ch);/*输出出错终结符*/
exit(1);
}
}
else
{ /*非终结符处理*/
for(j=0;j<=4;j++)
if(x==v2[j])
{
m=j; /* m: 分析表行号*/
break;
}
for(j=0;j<=3;j++)
if(ch==v1[j])
{
n=j; /*n: 分析表列号*/
break;
}
cha=C[m][n];
if(cha.origin!='N')/*判断是否为空*/
{
print();
print1();
printf("%c-",cha.origin); /*输出产生式*/
for(j=0;j<cha.length;j++)
printf("%c",cha.array[j]);
printf("\n");
for(j=(cha.length-1);j>=0;j--) /*产生式逆序入栈*/
A[++top]=cha.array[j];
if(A[top]=='^') /*为空则不进栈*/
top--;
}
else/*出错处理*/
{
print();
print1();
printf("%c出错\n",x);/*输出出错非终结符*/
exit(1);
}
}/*else*/
}while(finish==0);
}