語法分析器得設計 實驗報告 一、實驗內容 語法分析程序用 LL(1)語法分析方法。首先輸入定義好得文法書寫文件(所用得文法可以用 LL(1)分析),先求出所輸入得文法得每個非終結符就是否能推出空,再分別計算非終結符號得 FIRST 集合,每個非終結符號得 FOLLOW 集合,以及每個規則得 SELECT 集合,并判斷任意一個非終結符號得任意兩個規則得 SELECT 集得交集就是不就是都為空,如果就是,則輸入文法符合 LL(1)文法,可以進行分析。
對于文法: G[E]: E>E+T|T T>T*F|F F>i|(E) 分析句子 i+i*i 就是否符合文法 。
二、基本思想 1、語法分析器實現 語法分析就是編譯過程得核心部分,它得主要任務就是按照程序得語法規則,從由詞法分析輸出得源程序符號串中識別出各類語法成分,同時進行詞法檢查,為語義分析與代碼生成作準備。這里采用自頂向下得 LL(1)分析方法。
語法分析程序得流程圖如圖 54 所示。
該程序可分為如下幾步: (1)讀入文法
(2)判斷正誤
(3)若無誤,判斷就是否為 LL(1)文法
(4)若就是,構造分析表; (5)由句型判別算法判斷輸入符號串就是為該文法得句型。
三、核心思想 該分析程序有 15 部分組成: (1)首先定義各種需要用到得常量與變量; (2)判斷一個字符就是否在指定字符串中; 開始 讀入文法 有效？
判斷句型 報錯 結束 語法分析程序流程圖 就 是 LL(1) 文
(3)讀入一個文法; (4)將單個符號或符號串并入另一符號串; (5)求所有能直接推出&得符號; (6)求某一符號能否推出‘ & ’; (7)判斷讀入得文法就是否正確; (8)求單個符號得 FIRST; (9)求各產生式右部得 FIRST; (10)求各產生式左部得 FOLLOW; (11)判斷讀入文法就是否為一個 LL(1)文法; (12)構造分析表 M; (13)句型判別算法; (14)一個用戶調用函數; (15)主函數; 下面就是其中幾部分程序段得算法思想: 1、求能推出空得非終結符集 Ⅰ、 實例中求直接推出空得 empty 集得算法描述如下: void emp(char c){
參數 c 為空符號
char temp[10];定義臨時數組
int i;
for(i=0;i<=count1;i++)從文法得第一個產生式開始查找
{
if 產生式右部第一個符號就是空符號并且右部長度為 1, then 將該條產生式左部符號保存在臨時數組 temp 中 將臨時數組中得元素合并到記錄可推出&符號得數組 empty 中。
} Ⅱ、求某一符號能否推出"&" int _emp(char c) {
//若能推出&,返回 1;否則,返回 0
int i,j,k,result=1,mark=0;
char temp[20];
temp[0]=c;
temp[1]="\0";
存放到一個臨時數組 empt 里,標識此字符已查找其就是否可推出空字
如果 c 在可直接推出空字得 empty[]中,返回 1
for(i=0;;i++)
{
if(i==count)
return(0);
找一個左部為 c 得產生式
j=strlen(right[i]);
//j 為 c 所在產生式右部得長度
if 右部長度為 1 且右部第一個字符在 empty[]中、 then 返回 1(A>B,B 可推出空)
if 右部長度為 1 但第一個字符為終結符,then 返回 0(A>a,a 為終結符)
else
{
for(k=0;k<=j1;k++)
{
查找臨時數組 empt[]、并標記 mark=1(A>AB)
if 找到得字符與當前字符相同(A>AB)
結束本次循環
else(mark 等于 0) 查找右部符號就是否可推出空字,把返回值賦給 result
把當前符號加入到臨時數組 empt[]里、 }
if 當前字符不能推出空字且還沒搜索完全部得產生式 then 跳出本次循環繼續搜索下一條產生式
else if //當前字符可推出空字,返回 1 } } } 2、計算每個符號得 first 集: 實例中求單個符號得 FIRST 集得算法描述如下: void first2 (int i) {
參數 i 為符號在所有輸入符號中得序號
c 等于指示器 i 所指向得符號
在保存終結符元素得 termin[]數組查找 c if
c 為終結符(c∈V T ),then
FIRST(c)={c} 在保存終結符元素得 non_ter[]數組查找 c if
c 就是非終結符(c∈V N ) 在所有產生式中查找 c 所在得產生式 if
產生式右部第一個字符為終結符或空(即 c→a (a∈V T )或 c→&)
then 把 a 或&加進 FIRST(c) if
產生式右部第一個字符為非終結符 then if
產生式右部得第一個符號等于當前字符 then
跳到下一條產生式進行查找 求當前非終結符在所有字符集中得位置 if
當前非終結符還沒求其 FIRST 集 then
查找它得 FIRST 集并標識此符號已求其 FIRST 集
求得結果并入到 c 得 FIRST 集、 if
當前產生式右部符號可推出空字且當前字符不就是右部得最后一個字符
then 獲取右部符號下一個字符在所有字符集中得位置 if
此字符得 FIRST 集還未查找 then 找其 FIRST 集,并標其查找狀態為 1 把求得得 FIRST 集并入到 c 得 FIRST 集、 if 當前右部符號串可推出空且就是右部符號串得最后一個字符(即產生式為 c→Y 1 Y 2 …Y k ,若對一切 1<=i<=k,均有&∈FIRST(Y i ),則將&∈符號加進 FIRST(c) )
then 把空字加入到當前字符 c 得 FIRST 集、
else 不能推出空字則結束循環 標識當前字符 c 已查找其 FIRST 集、 } 3、 計算 FOLLOW 集 FOLLOW 集得構造可用如下方法來求: 對于文法中得符號 X ?V N ,其 FOLLOW(A)集合可反復應用下列規則計算,直到FOLLOW(A)集合不再增大為止。
(1)對于文法開始符號 S,因為 S S,故#?FOLLOW(S); (2)若 A→??B?,其中 B?V N ,??(V T ?V N ) * 、??(V T ?V N ) + ,則 FIRST(?){?}?FOLLOW(B); (3)若 A→??B 或 A→??B? (????),則 FOLLOW(A) ?FOLLOW(B)。
FOLLOW 集得算法描述如下:
void FOLLOW(int i)
X 為待求得非終結符 把當前字符放到一臨時數組 foll[]中,標識求已求其 FOLLOW 集、避免循環遞歸 if
X 為開始符號 then
#∈FOLLOW(X)
對全部得產生式找一個右部含有當前字符 X 得產生式 注:比如求 FOLLOW(B)則找 A→αX 或 A→?X?(?ε)得產生式 if
X 在產生式右部得最后(形如產生式 A→?X)
then 查找非終結符 A 就是否已經求過其 FOLLOW 集、避免循環遞歸 if
非終結符 A 已求過其 FOLLOW 集
then FOLLOW(A)∈FOLLOW(X) 繼續查下一條產生式就是否含有 X else 求 A 之 FOLLOW 集,并標識為 A 已求其 FOLLOW 集 else
if
X 不在產生式右部得最后(形如 A→?B?)
then if 右部 X 后面得符號串?能推出空字? then 查找?就是否已經求過其 FOLLOW 集、避免循環遞歸 if
已求過?得 FOLLOW 集 then
FOLLOW(A)∈FOLLOW(B) 結束本次循環 else
if ?不能推出空字 then
求 FIRST(?) 把 FIRST(?)中所有非空元素加入到 FOLLOW(B)中 標識當前要求得非終結符 X 得 FOLLOW 集已求過 4、計算 SELECT 集 SELECT 集得構造算法如下: 對所有得規則產生式 A→x: (1)若 x 不能推出空字?,則 SELECT(A→x) = FIRST(x); (2)若 x 可推出空字?,則 SELECT(A→x)=FIRST(x)–{?} ? FOLLOW(A)。
算法描述如下:
for(i=0;i<=產生式總數 1;i++) 先把當前產生式右部得 FIRST 集(一切非空元素,不包括 ε)放入到當前產生式得
SELECT(i);
if
產生式右部符號串可推出空字?
then 把 i 指向得當前產生式左部得非終結符號得 FOLLOW 集并入到 SELECT(i)中 5、判斷就是否 LL(1)文法 要判斷就是否為 LL(1)文法,需要輸入得文法 G 有如下要求: 具有相同左部得規則得 SELECT 集兩兩不相交,即: SELECT(A→?)∩ SELECT(A→?)= ? 如果輸入得文法都符合以上得要求,則該文法可以用 LL(1)方法分析。
算法描述如下:
把第一條產生式得 SELECT(0)集放到一個臨時數組 temp[]中
for(i=1;i<=產生式總數 1;i++)
求 temp 得長度 length
if
i 指向得當前產生式得左部等于上一條產生式得左部
then
把 SELECT(i)并入到 temp 數組中
If
temp 得長度小于 length 加上 SELECT (i)得長度
返回 0
else 把 temp 清空 把 SELECT (i)存放到 temp 中 結果返回 1; 四、算法 #include<stdlib、h> #include<stdio、h> #include<string、h> /*******************************************/ int
count=0;
//產生式得個數 int
number;
//所有終結符與非終結符得總數 char start;
//開始符號 char termin[50];
//終結符號 char non_ter[50];
//非終結符號 char v[50];
//所有符號 char left[50];
//左部 char right[50][50];
//右部 char first[50][50],follow[50][50];
//各產生式右部得 FIRST 與左部得 FOLLOW 集合 char first1[50][50];
//所有單個符號得 FIRST 集合 char select[50][50];
//各個產生式得 SELECT 集合 char firstflag[50],followflag[50];
//記錄各符號得 FIRST 與 FOLLOW 就是否已求過 char empty[20];
//記錄可推出&得符號 char nonempty[20];
//記錄不可推出&得符號 char empt[20];
//求_emp 時使用 char TEMP[50];
//求 FOLLOW 時存放某一符號串得 FIRST 集合 int
validity=1;
//表示輸入文法就是否有效 int
ll=1;
//表示輸入文法就是否為 LL(1)文法 int
M[20][20];
//分析表
char choose;
//用戶輸入時使用 char foll[20];
//求 FOLLOW 集合時使用 /******************************************* 判斷一個字符 c 就是否在指定字符串 p 中 ********************************************/ int in(char c,char *p) {
int i;
if(strlen(p)==0)
return(0);
for(i=0;;i++)
{
if(p[i]==c)
return(1);
//若在,返回 1
if(i==(int)strlen(p))
return(0);
//若不在,返回 0
} } /******************************************* 將單個符號或符號串并入另一符號串 ********************************************/ void merge(char *d,char *s,int type) {
//就是目標符號串,s 就是源串,type＝1,源串中得"&"一并并入目串;
//type＝2,源串中得"&"不并入目串
int i,j;
for(i=0;i<=(int)strlen(s)1;i++)
{
if(type==2&&s[i]=="&");
else
{
for(j=0;;j++)
{
if(j<(int)strlen(d)&&s[i]==d[j])
break;
//若已存在,則退出,繼續瞧下一個源串字符
if(j==(int)strlen(d))
//若不存在,則并入
{
d[j]=s[i];
d[j+1]="\0";
break;
}
}
}
} }
/******************************************* 讀入一個文法 ********************************************/ char grammer(char *t,char *n,char *left,char right[50][50]) {
char vn[50],vt[50];
char s;
char p[50][50];
int i,j;
printf("請輸入文法得非終結符號串:");
scanf("%s",vn);
getchar;
i=strlen(vn);
memcpy(n,vn,i);
n[i]="\0";
printf("請輸入文法得終結符號串:");
scanf("%s",vt);
getchar;
i=strlen(vt);
memcpy(t,vt,i);
t[i]="\0";
printf("請輸入文法得開始符號:");
scanf("%c",&s);
getchar;
printf("請輸入文法產生式得條數:");
scanf("%d",&i);
getchar;
count=i;
for(j=1;j<=i;j++)
{
printf("請輸入文法得第%d 條(共%d 條)產生式:",j,i);
scanf("%s",p[j1]);
getchar;
}
for(j=0;j<=i1;j++)
{
if(p[j][1]!=""||p[j][2]!=">") //檢測輸入錯誤
{
printf("\n 輸入錯誤!");
validity=0;
return("\0");
}
}
return(s);
} /******************************************* 判斷讀入得文法就是否正確 ********************************************/ int judge {
int i,j;
for(i=0;i<=count1;i++)
{
if(in(left[i],non_ter)==0)
{
//若左部不在非終結符中,報錯
printf("\n 文法左部出錯!");
validity=0;
return(0);
}
for(j=0;j<=(int)strlen(right[i])1;j++)
{
if(in(right[i][j],non_ter)==0&&in(right[i][j],termin)==0&&right[i][j]!="&")
{
//若右部某一符號不在非終結符、終結符中且不為"&",報錯
printf("\n 文法右部出錯!");
validity=0;
return(0);
}
}
}
return(1); } /******************************************* 求所有能直接推出&得符號 ********************************************/ void emp(char c) {
char temp[10];
int i;
for(i=0;i<=count1;i++)
{
if(right[i][0]==c&&strlen(right[i])==1)
{
temp[0]=left[i];
temp[1]="\0";
merge(empty,temp,1);//求所有能直接推出"&"得符號,結果保存到 empty[]中
emp(left[i]);
}
}
} /******************************************* 求某一符號能否推出"&" ********************************************/ int _emp(char c) {
//若能推出&,返回 1;否則,返回 0
int i,j,k,result=1,mark=0;
char temp[20];
temp[0]=c;
temp[1]="\0";
merge(empt,temp,1);//存放到一個臨時數組empt里,標識此字符已查找其就是否可推出空字
if(in(c,empty)==1)//如果 c 在可直接推出空字得 empty[]中,返回 1
return(1);
for(i=0;;i++)
{
if(i==count)
return(0);
if(left[i]==c)
//找一個左部為 c 得產生式
{
j=strlen(right[i]);
//j 為 c 所在產生式右部得長度
if(j==1&&in(right[i][0],empty)==1)//右部長度為 1 且右部第一個字符在 empty[]中、返回 1(A>B,B 可推出空)
return(1);
else if(j==1&&in(right[i][0],termin)==1)//右部長度為 1 但第一個字符為終結符,返回 0(A>a,a 為終結符)
continue;
else
{
for(k=0;k<=j1;k++)
{
if(in(right[i][k],empt)==1)//查找臨時數組 empt[]、(A>AB)
mark=1;
}
if(mark==1)
//找到得字符與當前字符相同(A>AB)
continue;
//結束本次循環
else
//(mark 等于 0)
{
for(k=0;k<=j1;k++)
{
result*=_emp(right[i][k]);//遞歸調用,查找右部符號就是否可推出空字,把返回值賦給 result
temp[0]=right[i][k];
temp[1]="\0";
merge(empt,temp,1);//把當前符號加入到臨時數組 empt[]里,標記已查找
}
}
}
if(result==0&&i<count)//如果當前字符不能推出空字且還沒搜索完全部得產生式,則跳出本次循環繼續搜索下一條產生式
continue;
else if(result==1&&i<count)//當前字符可推出空字,返回 1
return(1);
}
} } /******************************************* 求單個符號得 FIRST ********************************************/ void first2(int i) {
//i 為符號在所有輸入符號中得序號
char c,temp[20];
int j,k,m;
char ch="&";
c=v[i];
emp(ch);//求所有能直接推出空字得符號,結果保存到 empty[]中
if(in(c,termin)==1)
//若為終結符 c∈VT,則 FIRST(c)={c}
{
first1[i][0]=c;
first1[i][1]="\0";
}
else if(in(c,non_ter)==1)
//若為非終結符
{
for(j=0;j<=count1;j++) //j 為所有產生式中得序列
{
if(left[j]==c) //找一個左部為 c 得產生式
{
if(in(right[j][0],termin)==1||right[j][0]=="&")
{//若產生式右部第一個字符為終結符或空、產生式 X→a (a∈VT)或 X→&,則把 a 或&加進 FIRST(X)
temp[0]=right[j][0];
temp[1]="\0";
merge(first1[i],temp,1);
}
//X→Y1Y2…Yk 得產生式,若 Y1∈VN,則把 FIRST(Y1)中得一切非空符號加進FIRST(X)
else if(in(right[j][0],non_ter)==1)//產生式右部第一個字符為非終結符
{
if(right[j][0]==c)//產生式右部得第一個符號等于當前字符,則跳到下一條產生式進行查找
continue;
for(k=0;;k++)
{
if(v[k]==right[j][0])//求右部第一個字符在所有字符集中得位置 k
break;
}
if(firstflag[k]=="0")
{
first2(k);//求其 FIRST 集
firstflag[k]="1";//標識其為查找狀態
}
merge(first1[i],first1[k],2);//求得結果并入到 X 得 FIRST 集、
for(k=0;k<(int)strlen(right[j]);k++)
{
empt[0]="\0";//存放到一個臨時數組里,標識此字符已查找其就是否可推出空字
if(_emp(right[j][k])==1&&k<(int)strlen(right[j])1)
{//當前產生式右部符號可推出空字,且當前字符不就是右部得最后一個字符
for(m=0;;m++)
{
if(v[m]==right[j][k+1])//獲取右部符號下一個字符在所有字符集中得位置
break;
}
if(firstflag[m]=="0")//如果此字符得 FIRST 集還未查找,則找其 FIRST 集,并標其查找狀態為 1
{
first2(m);
firstflag[m]="1";
}
merge(first1[i],first1[m],2);//把求得結果并入到 X 得 FIRST集、
} //產生式為 X→Y1Y2…Yk,若對一切 1<=i<=k,均有&∈FIRST(Yi),則將&∈符號加進FIRST(X)
else if(_emp(right[j][k])==1&&k==(int)strlen(right[j])1)
{//當前右部符號串可推出空且就是右部符號串得最后一個字符
temp[0]="&";
temp[1]="\0";
merge(first1[i],temp,1);//把空字加入到當前字符 X 得 FIRST
集、
}
else
break;//不能推出空字則結束循環
}
}
}
}
}
firstflag[i]="1";//標識當前字符 c 已查找其 FIRST 集 } /******************************************* 求各產生式右部得 FIRST ********************************************/ void FIRST(int i,char *p) {
//指針 p 指向右部符號串
int length;//標識右部符號串得長度
int j,k,m;
char temp[20];
length=strlen(p);
if(length==1)
//如果右部為單個符號
{
if(p[0]=="&")//右部符號串字符為"&"空字
{
if(i>=0)//i 不為 1 時就是產生式得序號
{
first[i][0]="&"; //把"&"加入到當前符號串得 FIRST 集
first[i][1]="\0";
}
else//i為1時,表示求FOLLOW時用到得產生式右部得FIRST集,保存在TEMP[]中
{
TEMP[0]="&";
TEMP[1]="\0";
}
}
else//右部符號串字符不為"&"空字
{
for(j=0;;j++)
{
if(v[j]==p[0])//求右部符號得第一個字符 p[0]在所有字符集中得位置 j
break;
}
if(i>=0)
{
memcpy(first[i],first1[j],strlen(first1[j]));//把 j 所指向得單個符號得 FIRST集拷貝到該右部符號串得 FIRST 集
first[i][strlen(first1[j])]="\0";
}
else
{
memcpy(TEMP,first1[j],strlen(first1[j]));
TEMP[strlen(first1[j])]="\0";
}
}
}
else
//如果右部為符號串
{
for(j=0;;j++)
{
if(v[j]==p[0])//求右部符號得第一個字符 p[0]在所有字符集中得位置 j
break;
}
if(i>=0)
merge(first[i],first1[j],2);
else
merge(TEMP,first1[j],2);
for(k=0;k<=length1;k++)
{
empt[0]="\0";
if(_emp(p[k])==1&&k<length1)
{ //當前產生式右部符號可推出空字,且當前字符不就是右部得最后一個字符
for(m=0;;m++)
{
if(v[m]==right[i][k+1])
break;
}
if(i>=0)
merge(first[i],first1[m],2);
else
merge(TEMP,first1[m],2);
}
else if(_emp(p[k])==1&&k==length1)
{//當前右部符號串可推出空且就是右部符號串得最后一個字符
temp[0]="&";
temp[1]="\0";
if(i>=0)
merge(first[i],temp,1);
else
merge(TEMP,temp,1);
}
else if(_emp(p[k])==0)
break;
}
} } /******************************************* 求各產生式左部得 FOLLOW ********************************************/ void FOLLOW(int i) {
//參數 i 為該符號在非終結符中得位置
int j,k,m,n,result=1;
char c,temp[20];
c=non_ter[i];
//c 為待求得非終結符
temp[0]=c;
temp[1]="\0";
merge(foll,temp,1);//把當前字符放到一臨時數組 foll[]中,標識求已求其 FOLLOW 集、避免循環遞歸
if(c==start)
{
//若為開始符號開始符號 S,則#∈FOLLOW(S)
temp[0]="#";
temp[1]="\0";
merge(follow[i],temp,1);
}
for(j=0;j<=count1;j++)
{
if(in(c,right[j])==1)
//找一個右部含有當前字符 c 得產生式
{//比如求 FOLLOW(B)則找 A→αB 或 A→αBβ(β=>*&)得產生式
for(k=0;;k++)
{
if(right[j][k]==c)
break;
//k 為 c 在該產生式右部得序號,如 B 在產生式 A→αB中得位置
}
for(m=0;;m++)
{
if(v[m]==left[j])
break;
//m 為產生式左部非終結符在所有符號中得序號
} //如果 c 在產生式右部得最后,形如產生式 A→αB,則 FOLLOW(A)∈FOLLOW(B)
if(k==(int)strlen(right[j])1)
{
if(in(v[m],foll)==1)//查找該非終結符就是否已經求過其 FOLLOW 集、避免循環遞歸
{//就是則 FOLLOW(A)∈FOLLOW(B)
merge(follow[i],follow[m],1);//把 c 所在產生式得左部非終結符得FOLLOW 集加入到 FOLLOW(c)中
continue;//結束本次循環,進入 j++循環
}
if(followflag[m]=="0")
{//如果該非終結符得 FOLLOW 未求過
FOLLOW(m);//求之 FOLLOW 集
followflag[m]="1";//標識為 1
}
merge(follow[i],follow[m],1);//FOLLOW(A)∈FOLLOW(B)
}
else
{
//如果 c 不在產生式右部得最后,形如 A→αBβ
for(n=k+1;n<=(int)strlen(right[j])1;n++)
{
empt[0]="\0";//把 empt[]置空,因為求此字符就是否可推出空字_emp(c)時用到
result*=_emp(right[j][n]);
}
if(result==1)
{
//如果右部 c 后面得符號串能推出空,A→αBβ(β=>*&)則FOLLOW(A)∈FOLLOW(B)
if(in(v[m],foll)==1)
{
//查找該非終結符就是否已經求過其 FOLLOW 集、避免循環遞歸
merge(follow[i],follow[m],1);//FOLLOW(A)∈FOLLOW(B)
continue;
}
if(followflag[m]=="0")
{
FOLLOW(m);
followflag[m]="1";
}
merge(follow[i],follow[m],1);
} //若 A→αBβ,其中 B∈VN,α∈(VT U VN)*、β∈(VT U VN)+,則 FIRST(β){ε}∈FOLLOW(B);
for(n=k+1;n<=(int)strlen(right[j])1;n++)
{
temp[nk1]=right[j][n];
}
temp[strlen(right[j])k1]="\0";
FIRST(1,temp);//求 FIRST(β)
merge(follow[i],TEMP,2);// 把 FIRST( β ) 中 所 有 非 空 元 素 加 入 到FOLLOW(B)中
}
}
}
followflag[i]="1";//標識當前要求得非終結符得 FOLLOW 集已求過 } /******************************************* 判斷讀入文法就是否為一個 LL(1)文法 ********************************************/ int LL1 {
int i,j,length,result=1;
char temp[50];
for(j=0;j<=49;j++)
{
//初始化
first[j][0]="\0";
follow[j][0]="\0";
first1[j][0]="\0";
select[j][0]="\0";
TEMP[j]="\0";
temp[j]="\0";
firstflag[j]="0";//用來記錄該字符得 FIRST 集就是否已求過、1 表示已求,0 表示未求
followflag[j]="0";//用來記錄該字符得 FOLLOW 集就是否已求過、1 表示已求,0 表示未求
}
for(j=0;j<=(int)strlen(v)1;j++)
{
first2(j);
//求單個符號得 FIRST 集合,結果保存在 first1[]里
}
printf("\n 各非終結符推出得 first 集:\n");
for(j=0;j<=(int)strlen(v)1;j++)
{
printf("%c:%s
",v[j],first1[j]);
}
printf("\n 能導空得非終結符集合:%s",empty);
printf("\n_emp:");
for(j=0;j<=(int)strlen(v)1;j++)
printf("%d ",_emp(v[j]));
for(i=0;i<=count1;i++)
FIRST(i,right[i]);
//求 FIRST
for(j=0;j<=(int)strlen(non_ter)1;j++)
{
//求 FOLLOW
if(foll[j]==0)
{
foll[0]="\0";
FOLLOW(j);
}
}
printf("\nfirst 集:");
for(i=0;i<=count1;i++)
printf("%s ",first[i]);
printf("\nfollow 集合:");
for(i=0;i<=(int)strlen(non_ter)1;i++)
printf("%s ",follow[i]);
for(i=0;i<=count1;i++)
{
//求每一產生式得 SELECT 集合
memcpy(select[i],first[i],strlen(first[i]));//first[]存放得就是各產生式右部得 FIRST 集
select[i][strlen(first[i])]="\0";
for(j=0;j<=(int)strlen(right[i])1;j++)
result*=_emp(right[i][j]);
if(strlen(right[i])==1&&right[i][0]=="&")//形如產生式 A>&
result=1;
if(result==1)
{
for(j=0;;j++)
if(v[j]==left[i])//j 為左部符號在所有字符集中得位置
break;
merge(select[i],follow[j],1);
}
}
printf("\nselect 集合順序就是:");
for(i=0;i<=count1;i++)
printf("%s ",select[i]);
memcpy(temp,select[0],strlen(select[0]));
temp[strlen(select[0])]="\0";
for(i=1;i<=count1;i++)
{
/*判斷輸入文法就是否為 LL(1)文法*/
length=strlen(temp);
if(left[i]==left[i1])
{
merge(temp,select[i],1);
if(strlen(temp)<length+strlen(select[i]))//比較兩個產生式得 SELECT 長度
return(0);
}
else
{
temp[0]="\0";
memcpy(temp,select[i],strlen(select[i]));
temp[strlen(select[i])]="\0";
}
}
return(1); } /******************************************* 構造分析表 M ********************************************/ void MM {
int i,j,k,m;
for(i=0;i<=19;i++)
{
for(j=0;j<=19;j++)//初始化分析表,全部置為空(1)
{
M[i][j]=1;
}
}
i=strlen(termin);
termin[i]="#";
//將#加入終結符數組
termin[i+1]="\0";
for(i=0;i<=count1;i++)//查瞧每個產生式得 SELECT 集
{
for(m=0;;m++)
{
if(non_ter[m]==left[i])
break;
//m 為產生式左部非終結符得序號
}
for(j=0;j<=(int)strlen(select[i])1;j++)//對每個 SELECT 集中得所有元素進行操作
{
if(in(select[i][j],termin)==1)
{
for(k=0;;k++)
{
if(termin[k]==select[i][j])
break;
//k 為產生式右部終結符得序號
}
M[m][k]=i;
}
}
}
} /******************************************* 判斷符號串就是否就是該文法得句型 ********************************************/ void syntax {
int i,j,k,m,n,p,q;
char ch;
char S[50],str[50];
printf("請輸入該文法得句型:");
scanf("%s",str);
getchar;
i=strlen(str);
str[i]="#";
str[i+1]="\0";
S[0]="#";
S[1]=start;
S[2]="\0";
j=0;
ch=str[j];
while(1)
{
if(in(S[strlen(S)1],termin)==1)
{
if(S[strlen(S)1]!=ch)
{
printf("該符號串不就是文法得句型！");
return;
}
else if(S[strlen(S)1]=="#")
{
printf("該符號串就是文法得句型、");
return;
}
else
{
S[strlen(S)1]="\0";
j++;
ch=str[j];
}
}
else
{
for(i=0;;i++)
if(non_ter[i]==S[strlen(S)1])
break;
for(k=0;;k++)
{
if(termin[k]==ch)
break;
if(k==(int)strlen(termin))
{
printf("詞法錯誤！");
return;
}
}
if(M[i][k]==1)
{
printf("語法錯誤！");
return;
}
else
{
m=M[i][k];
if(right[m][0]=="")
S[strlen(S)1]="\0";
else
{
p=strlen(S)1;
q=p;
for(n=strlen(right[m])1;n>=0;n)
S[p++]=right[m][n];
S[q+strlen(right[m])]="\0";
}
}
}
printf("S:%s str:",S);
for(p=j;p<=(int)strlen(str)1;p++)
printf("%c",str[p]);
printf(" \n");
} } /******************************************* 一個用戶調用函數 ********************************************/ void menu {
syntax;
printf("\n 就是否繼續？(y or n):");
scanf("%c",&choose);
getchar;
while(choose=="y")
{
menu;
} } /******************************************* 主函數 ********************************************/ void main {
int i,j;
start=grammer(termin,non_ter,left,right);
//讀入一個文法
printf("count=%d",count);
printf("\n 開始符號為:%c",start);
strcpy(v,non_ter);
strcat(v,termin);
printf("\n 所有符號集為:%s",v);
printf("\n 非終結符集合:{%s",non_ter);
printf("}");
printf("\n 終結符集合:{%s",termin);
printf("}");
printf("\n 文法所有右邊表達式依次就是:");
for(i=0;i<=count1;i++)
{
printf("%s
",right[i]);
}
printf("\n 文法所有左邊開始符依次就是:");
for(i=0;i<=count1;i++)
{
printf("%c
",left[i]);
}
if(validity==1)
validity=judge;
printf("\nvalidity=%d",validity);
if(validity==1)
{
ll=LL1;
printf("\nll=%d",ll);
if(ll==0)
printf("\n 該文法不就是一個 LL1 文法！");
else
{
printf("\n 該文法就是一個 LL(1)文法！");
MM;
printf("\n");
for(i=0;i<=19;i++)
for(j=0;j<=19;j++)
if(M[i][j]>=0)
printf("M[%d][%d]=%d ",i,j,M[i][j]);
menu;
}
} }
由于算法仍有很多錯誤,最終結果沒能實現,這點很失望！
五、實驗心得
通過本次實驗,我收獲了很多東西。首先對編譯原理這門課有了進一步得深刻理解,同時對 LL(1)文法分析得原理與過程有了進一步得鞏固,也鍛煉了我編程得能力,鞏固了平時所學得知識,真正做到了學以致用。
在做實驗得過程中,發現自己在編寫程序過程中,總就是會忽略各種細節,從而導致經常修改一些很小得低級錯誤才能使程序正常運行,不僅浪費時間,還影響對其她地方得修改,并且在很多步驟處理上,方法不正確。使結果不能符合要求,深刻體會到了自己在編程方面與別人得差距,在今后得學習中,我會注意改正自己在這方面得缺點,促使自己得編程水平不斷進步。
編譯原理就是一門專業學科,對于現階段得我來說,只能掌握它得一些基本原理與概念,對于一些更深層得知識還就是有很多難以理解得地方。但在這次實驗過程中,鍛煉了自己得思考能力,也鍛煉了自己得動手編程能力,對于將知識得轉化有了很大得幫助。
推薦訪問： 分析器 語法 實驗上一篇：非平衡電橋實驗報告范文
下一篇：南通市“誠信守法企業”申報材料
在偉大祖國73華誕之際，我參加了單位組織的“光影鑄魂”主題黨日活動，集中觀看了抗美援朝題材影片《長津湖》，再一次重溫這段悲壯歷史，再一次深刻感悟偉大抗美援朝精神。1950年10月，新中國剛剛成立一年，
根據省局黨組《關于舉辦習近平談治國理政（第四卷）讀書班的通知》要求，我中心通過專題學習、專題研討以及交流分享等形式，系統的對《習近平談治國理政》（第四卷)進行了深入的學習與交流，下面我就來談一談我個人
《習近平談治國理政》（第四卷）是在百年變局和世紀疫情相互疊加的大背景下，對以習近平同志為核心的黨中央治國理政重大戰略部署、重大理論創造、重大思想引領的系統呈現。它生動記錄了新一代黨中央領導集體統籌兩個
《真抓實干做好新發展階段“三農工作”》是《習近平談治國理政》第四卷中的文章，這是習近平總書記在2020年12月28日中央農村工作會議上的集體學習時的講話。文章指出，我常講，領導干部要胸懷黨和國家工作大
在《習近平談治國理政》第四卷中，習近平總書記強調，江山就是人民，人民就是江山，打江山、守江山，守的是人民的心。從嘉興南湖中駛出的小小紅船，到世界上最大的執政黨，在中國共產黨的字典里，“人民”一詞從來都
黨的十八大以來，習近平總書記以馬克思主義戰略家的博大胸襟和深謀遠慮，在治國理政和推動全球治理中牢固樹立戰略意識，在不同場合多次圍繞戰略策略的重要性，戰略和策略的關系，提高戰略思維、堅定戰略自信、強化戰
《習近平談治國理政》第四卷集中展示了以習近平同志為核心的黨中央在百年變局和世紀疫情相互疊加背景下，如何更好地堅持和發展中國特色社會主義而進行的生動實踐與理論探索；對于新時代堅持和發展什么樣的中國特色社
在黨組織的關懷下，我有幸參加了區委組織部組織的入黨積極分子培訓班。為期一周的學習，學習形式多樣，課程內容豐富，各位專家的講解細致精彩，對于我加深對黨的創新理論的認識、對黨的歷史的深入了解、對中共黨員的
《習近平談治國理政》第四卷《共建網上美好精神家園》一文中指出：網絡玩命是新形勢下社會文明的重要內容，是建設網絡強國的重要領域。截至2021年12月，我國網民規模達10 32億，較2020年12月增長4
剛剛召開的中國共產黨第十九屆中央委員會第七次全體會議上討論并通過了黨的十九屆中央委員會向中國共產黨第二十次全國代表大會的報告、黨的十九屆中央紀律檢查委員會向中國共產黨第二十次全國代表大會的工作報告和《