?? ll1.c
字號:
/**
20031401008 褚超
實驗三 LL(1)語法分析
編寫為某一任意上下文無關文法構造的LL(1)語法分析程序，并對任給的一個輸入串進行語法分析檢查。
程序要求為該文法構造預測分析表，并按照預測分析算法對輸入串進行語法分析，判別程序是否符合已
知的語法規則，如果不符合（編譯出錯），則輸出錯誤信息。
注意:本程序不具備判斷輸入的文法是否為LL1文法的功能,所以在進行測試時請確保輸入的文法是LL1文法
在輸入文法過程中請按提示進行操作
程序測試示例文法:
E->aH
H->aMd
H->d
M->Ab
M->^
A->aM
A->e
程序測試數據:aaebd
(可以選用任何LL1文法以及符合該文法的輸入串進行測試)
**/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
/*產生式類型定義*/
typedef struct type
{
char origin; /*大寫字符*/
char array[5]; /*產生式右邊字符*/
int length; /*字符個數*/
}type;
/*各個非終結符的信息*/
typedef struct info
{
int isNull; /*能否推出"空"? 1是 0否*/
char firstSet[10];
char followSet[10];
}info;
int n1; /*文法中產生式的個數*/
int numOfVn,numOfVt; /*記錄VN和VT的個數*/
char VN[10],VT[10]; /*非終結符和終結符表*/
char select[10][10]; /*各個產生試的SELECT集*/
type table[10][10]; /*預測分析表*/
int j=0,b=0,top=0,l; /*L為輸入串長度*/
char A[20]; /*分析棧*/
char B[20]; /*剩余串*/
/* 獲取由用戶輸入的文法的產生式,保存到所定義的數據結構中,在此過程中可以順便搜集非終結符列表 */
void getLL1(type ll1[]);
void print() /*輸出分析棧*/
{
int a; /*指針*/
for(a=0;a<=top+1;a++)
printf("%c",A[a]);
printf("\t\t");
} /*print*/
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");
}/*print1*/
/*返回某一非終結符在表中的序號*/
int inVN(char c)
{
int i;
for (i=0;i<numOfVn;i++)
{
if (c==VN[i])
{
return i;
}
}
return -1;
}
/*返回某一終結符在表中的序號*/
int inVT(char c)
{
int i;
for (i=0;i<numOfVt;i++)
{
if (c==VT[i])
{
return i;
}
}
return -1;
}
/*輔助函數:若字符c不在s中，則將c加入s*/
void addIn1(char s[],char c,int *flag)
{
int i,len,tag=1;
len=strlen(s);
for (i=0;i<len;i++)
{
if (s[i]==c)
{
tag=0;
break;
}
}
if (tag)
{
s[len]=c;
s[len+1]='\0';
*flag=1;
}
}
/*輔助函數:將s2中不存在與s1中的字符加入到s1中*/
void addIn2(char s1[],char s2[],int *flag)
{
int i,len;
len=strlen(s2);
for (i=0;i<len;i++)
{
addIn1(s1,s2[i],flag);
}
}
/* 掃描每條產生式,求出能推出"空的" VN ,在此過程中可以順便搜集終結符列表 */
void getNULL(type ll1[],info infoVn[]);
/* 計算各非終結符的First集 */
void getFirst(type ll1[],info infoVn[]);
/* 計算各非終結符的Follow集 */
void getFollow(type ll1[],info infoVn[]);
/* 根據計算出來的First,Follow集求解各個產生式的SELECT
構造LL1的預測分析表
*/
void setTable(type ll1[],info infoVn[]);
/* 對輸入的文法串進行分析掃描的主控程序 */
void doScan();
void main()
{
int i,m,n;
type ll1[15];
info infoVn[10];
getLL1(ll1);
getNULL(ll1,infoVn);
getFirst(ll1,infoVn);
getFollow(ll1,infoVn);
for(m=0;m<numOfVn;m++) /*初始化分析表*/
for(n=0;n<numOfVt;n++)
table[m][n].origin='N'; /*全部賦為空*/
setTable(ll1,infoVn);
printf("能推出空的非終結符有:");
for (i=0;i<numOfVn;i++)
{
if (infoVn[i].isNull==1)
{
printf("%3c",VN[i]);
}
}
printf("\n");
for (i=0;i<numOfVn;i++)
{
printf("FIRST(%c)=%s\n",VN[i],infoVn[i].firstSet);
}
printf("\n");
for (i=0;i<numOfVn;i++)
{
printf("FOLLOW(%c)=%s\n",VN[i],infoVn[i].followSet);
}
printf("\n");
doScan();
}
/* 獲取由用戶輸入的文法的產生式,保存到所定義的數據結構中 */
void getLL1(type ll1[])
{
int n,i,k=0,flag=0;
char l,r[10];
printf("請輸入文法的產生式個數:\n");
scanf("%d",&n);
getchar();
n1=n;
for (i=0;i<n;i++)
{
flag=0;
printf("輸入第%d條產生式的左部:\n",i+1);
scanf("%c",&l);
getchar();
ll1[i].origin=l;
printf("輸入第%d條產生式的右部(默認不超過10個字符):\n",i+1);
scanf("%s",r);
getchar();
strcpy(ll1[i].array,r);
ll1[i].length=strlen(ll1[i].array);
addIn1(VN,l,&flag);
}
numOfVn=strlen(VN);
printf("您所輸入的文法為:\n");
for (i=0;i<n;i++)
{
printf("%c->%s\n",ll1[i].origin,ll1[i].array);
}
}
/* 掃描每條產生式,求出能推出"空的" VN ,在此過程中可以順便搜集終結符列表 */
void getNULL(type ll1[],info infoVn[])
{
int i,j,m,flag[10],flag1=0,flag2=1,flag3=1,k=0,len;
int isModified[10];
for (i=0;i<10;i++)
{
flag[i]=1;
}
/*將每一非終結符能否推出"空"的標記置為未定*/
for (i=0;i<numOfVn;i++)
{
infoVn[i].isNull=-1;
}
/*第一遍掃描，刪除所有右部含有終結符的產生式，若這使得以某一非終結符為左部的產生式都被刪除，則該非終結符不能推出空*/
/*在此過程中可以搜集終結符表*/
for (i=0;i<n1;i++)
{
/*產生式右部為空的非終結符當然可以推出空*/
if( ll1[i].array[0]=='^' )
{
infoVn[inVN(ll1[i].origin)].isNull=1;
/*刪除該非終結符的所有產生式*/
for (m=0;m<n1;m++)
{
if (ll1[i].origin == ll1[m].origin)
{
flag[m]=0;
}
}
}
for(j=0;j<ll1[i].length;j++)
{
flag1=0;
if ( (!isupper(ll1[i].array[j])) && ll1[i].array[j]!='^' )
{
flag[i]=0; /*刪除所有右部含有終結符的產生式,將對應的標志置0*/
infoVn[inVN(ll1[i].origin)].isNull=0;
/*搜集終結符*/
addIn1(VT,ll1[i].array[j],&flag1);
}
}
}
addIn1(VT,'#',&flag1);
numOfVt=strlen(VT);
for (i=0;i<numOfVn;i++)
{
isModified[i]=infoVn[i].isNull;
}
/*flag3用來標記是否停止掃描(到非終結符對應的特征沒有變化為止)*/
while(flag3)
{
/*掃描產生式右部的每一符號*/
flag3=0;
for (i=0;i<n1;i++)
{
len=ll1[i].length;
for (j=0;j<ll1[i].length;j++)
{
if (isupper(ll1[i].array[j]))
{
if (infoVn[inVN(ll1[i].array[j])].isNull==1)
{
len--;
}
else if (infoVn[inVN(ll1[i].array[j])].isNull==0)
{
flag[i]=0;
for (k=0;k<n1;k++)
{
/*某一VN的產生式在掃描過程中是否都被刪除?*/
if ( inVN(ll1[i].array[j]) == inVN(ll1[k].origin) )
{
if(flag[k]==1)
flag2=0;
}
}
if (flag2)
{
infoVn[inVN(ll1[i].array[j])].isNull=0;
}
}
}
}
/*某項產生式長度能減為0?*/
if (len==0)
{
infoVn[inVN(ll1[i].origin)].isNull=1;
/*刪除該非終結符的所有產生式*/
for (m=0;m<n1;m++)
{
if (ll1[i].origin == ll1[m].origin)
{
flag[m]=0;
}
}
}
}
for (i=0;i<numOfVn;i++)
{
if ( isModified[i]!=infoVn[i].isNull )
{
flag3=1;
isModified[i]=infoVn[i].isNull;
//break;
}
}
}
}
/* 計算各非終結符的First集 */
void getFirst(type ll1[],info infoVn[])
{
int i,j,k,l,m,length,flag1=1;
/*將各非終結符的FIRST集合初始化為空串*/
for (i=0;i<numOfVn;i++)
{
infoVn[i].firstSet[0]='\0';
}
while (flag1)
{
flag1=0;
for (i=0;i<n1;i++)
{
for (j=0;j<ll1[i].length;j++)
{
if ( !isupper(ll1[i].array[j]) )
{
break;
}
}
/*某條產生式的第一個字符是非VT或為空*/
if (j==0)
{
addIn1(infoVn[inVN(ll1[i].origin)].firstSet,ll1[i].array[0],&flag1);
}
/*如果產生式右部以VN開頭,則定位到不能推出空的VN*/
else
{
for (k=0;k<j;k++)
{
if (infoVn[inVN(ll1[i].array[k])].isNull != 1)
{
break;
}
}
/*處理書中算法所列的情況⑤*/
if (k==ll1[i].length)
{
for (l=0;l<k;l++)
{
addIn2(infoVn[inVN(ll1[i].origin)].firstSet,infoVn[inVN(ll1[i].array[l])].firstSet,&flag1);
}
}
/*處理書中算法所列的情況④*/
else
{
for (l=0;l<k;l++)
{
length=strlen(infoVn[inVN(ll1[i].array[l])].firstSet);
for (m=0;m<length; m++)
{
if (infoVn[inVN(ll1[i].array[l])].firstSet[m] != '^')
{
addIn1(infoVn[inVN(ll1[i].origin)].firstSet,infoVn[inVN(ll1[i].array[l])].firstSet[m],&flag1);
}
}
}
addIn2(infoVn[inVN(ll1[i].origin)].firstSet,infoVn[inVN(ll1[i].array[k])].firstSet,&flag1);
}
}
}
}
}
/* 計算各非終結符的Follow集 */
void getFollow(type ll1[],info infoVn[])
{
int i,j,k,l,m,n,length,flag;
char ch;
/*將各非終結符的FOLLOW集合初始化為空串*/
for (i=0;i<numOfVn;i++)
{
infoVn[i].followSet[0]='\0';
}
addIn1(infoVn[0].followSet,'#',&flag);
while (flag)
{
flag=0;
for (i=0;i<n1;i++)
/*掃描每條產生式*/
{
for (j=0;j<ll1[i].length;j++)
{
/*找到該VN后第一個不能推出空的字符*/
if (isupper(ll1[i].array[j]))
{
for (k=j+1;k<ll1[i].length;k++)
{
if ( !isupper(ll1[i].array[k]) )
{
break;
}
}
/*緊跟某VN后的是一個VT*/
if (k==j+1 && k<ll1[i].length)
{
addIn1(infoVn[inVN(ll1[i].array[j])].followSet,ll1[i].array[k],&flag);
//continue;
}
else
{
for (l=j+1;l<k;l++)
{
if (infoVn[inVN(ll1[i].array[l])].isNull!=1)
{
break;
}
}
/*P82 算法的②中第2點*/
if (l == ll1[i].length)
{
addIn2(infoVn[inVN(ll1[i].array[j])].followSet,infoVn[inVN(ll1[i].origin)].followSet,&flag);
for (m=j+1;m<l;m++)
{
length=strlen(infoVn[inVN(ll1[i].array[m])].firstSet);
for (n=0;n<length;n++)
{
if ( (ch=infoVn[inVN(ll1[i].array[m])].firstSet[n])!='^' )
{
addIn1(infoVn[inVN(ll1[i].array[j])].followSet,ch,&flag);
}
}
}
}
else
{
for (m=j+1;m<=l;m++)
{
length=strlen(infoVn[inVN(ll1[i].array[m])].firstSet);
for (n=0;n<length;n++)
{
if ( (ch=infoVn[inVN(ll1[i].array[m])].firstSet[n])!='^' )
{
addIn1(infoVn[inVN(ll1[i].array[j])].followSet,ch,&flag);
}
}
}
}
}
}
}
}
}
}
/*
根據計算出來的First,Follow集求解各個產生式的SELECT
構造LL1的預測分析表
*/
void setTable(type ll1[],info infoVn[])
{
int i,j,k,l,m,n,flag,flag1=0,flag2=0,length;
char ch;
for (i=0;i<n1;i++)
{
/*掃描各產生式,計算SELECT集*/
if (!isupper(ll1[i].array[0]))
{
/*對 A->^ 類型的產生式的處理*/
if (ll1[i].array[0]=='^')
{
addIn2(select[i],infoVn[inVN(ll1[i].origin)].followSet,&flag);
}
/*產生式第一個字符是VT*/
else
addIn1(select[i],ll1[i].array[0],&flag);
}
else
{
for (j=0;j<ll1[i].length;j++)
{
if (isupper(ll1[i].array[j]))
{
length=strlen(infoVn[inVN(ll1[i].array[j])].firstSet);
for (k=0;k<length;k++)
{
if ( (ch=infoVn[inVN(ll1[i].array[j])].firstSet[k])!='^' )
{
addIn1(select[i],ch,&flag);
}
}
if (infoVn[inVN(ll1[i].array[j])].isNull != 1)
{
flag1=1;
break;
}
}
else
{
flag2=1;
break;
}
}
/*處理像E->ABaβ的產生式的情況,游標j掃描到a時停止*/
if ((!flag1) && flag2)
{
addIn1(select[i],ll1[i].array[j],&flag);
}
/*處理像E->β的產生式的情況,其中β可以推出空*/
if (j==ll1[i].length)
{
addIn2(select[i],infoVn[inVN(ll1[i].origin)].followSet,&flag);
}
}
}
for (i=0;i<n1;i++)
{
length=strlen(select[i]);
for (j=0;j<length;j++)
{
table[inVN(ll1[i].origin)][inVT(select[i][j])]=ll1[i];
}
}
}
/* 對輸入的文法串進行分析掃描的主控程序 */
void doScan()
{
char ch,x;
int m,n,k=0,flag=0,finish=0;
type cha;
printf("\n請輸入要分析的字符串(以'#'結束):");
do/*讀入分析串*/
{
scanf("%c",&ch);
if (inVT(ch)==-1)
{
printf("輸入串中有非法字符\n");
exit(1);
}
B[j]=ch;
j++;
}while(ch!='#');
l=j; /*分析串長度*/
ch=B[0]; /*當前分析字符*/
//printf("\n%c\n",ch);
A[top]='#'; A[++top]='E'; /*'#','E'進棧*/
printf("步驟\t\t分析棧 \t\t剩余字符 \t\t所用產生式 \n");
do
{
x=A[top--]; /*x為當前棧頂字符*/
printf("%d",k++);
printf("\t\t");
for(j=0;j<numOfVt;j++) /*判斷是否為終結符*/
{
if(x==VT[j])
{
flag=1;
break;
}
}
if(flag==1) /*如果是終結符*/
{
if(x=='#')
{
finish=1; /*結束標記*/
printf("acc!\n"); /*接受*/
getchar();
getchar();
exit(1);
}/*if*/
else if(x==ch)
{
print();
print1();
printf("%c匹配\n",ch);
ch=B[++b]; /*下一個輸入字符*/
flag=0; /*恢復標記*/
} /*if*/
else /*出錯處理*/
{
print();
print1();
printf("%c出錯\n",ch);/*輸出出錯終結符*/
exit(1);
}/*else*/
}/*if*/
else /*非終結符處理*/
{
for(j=0;j<numOfVn;j++)
{
if(x==VN[j])
{
m=j; /*行號*/
break;
}
}
for(j=0;j<numOfVt;j++)
{
if(ch==VT[j])
{
n=j; /*列號*/
break;
}
}
cha=table[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--;
}/*if*/
else /*出錯處理*/
{
print();
print1();
printf("%c出錯\n",x); /*輸出出錯非終結符*/
exit(1);
}/*else*/
}/*else*/
}while(finish!=1);
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -