実験二予測分析アルゴリズムの設計と実現
41433 ワード
実験二予測分析アルゴリズムの設計と実現(8学時)一、実験目的予測分析アルゴリズムの設計と実現を通じて、上から下への文法分析方法の理解を深め、特に上から下への分析条件の理解を深める.二、実験は文法と分析すべき入力列を入力し、その予測分析過程と結果を出力することを要求する.三、実験手順1.参照データ構造(1)/生成式を定義する構文セット構造/typedef struct{char formula[200];//生成式}grammarElement;grammarElement gramOldSet[200];//元の文法の生成式セット(2)/変数定義/char terSymbol[200];//終端シンボルchar non_ter[200];//非終端符号char allSymbol[400];//すべてのシンボルchar firstSET[100][100];//各発生式右部のFIRSTセットchar followSET[100][100];//各発生式左部のFOLLOW集int M[200][200];//分析表2.文法の左再帰性を判断し,左再帰文法を非左再帰文法に変換する.(この手順は省略でき、非左再帰文法を直接入力します).3.文法に基づいてFIRSTセットとFOLLOWセットを求める.(1)/Firstセットを求めるアルゴリズム/begin if Xが終端(X線)すべての生成式でXが存在する生成式if生成式の右の最初の文字が終端または空(すなわちX線)であることを検索する®a(a線)またはX®e)thenはaまたはeをFIRST(X)に加えるif生成式右部の最初の文字が非終端文字thenif生成式右部の最初の記号は、現在の文字thenが次の生成式にジャンプして検索するif現在の非終端文字がFIRSTセットthenにFIRSTセットを検索することを求めていないことに等しく、この記号がFIRSTセットを求めた結果がXに組み込まれたFIRSTセットif現在の生成式右部記号が空字を出すことができ、前文字が右部でない最後の文字then右部記号の次の文字がすべての文字セットの位置ifこの文字のFIRSTセットがまだ検索されていないthenがFIRSTセットを探していることを取得し、その検索状態を1として求めたFIRSTセットをXのFIRSTセットifに組み込む現在の右部記号列が空で右部記号列の最後の文字であることを示す(すなわち、生成式はX® ,全ての1:i:Kに対してeパスFIRST()がある場合、eパス記号をFIRST(X)に加算するthen現在の文字Xに空字を加えたFIRSTセットelseが空字を出すことができない場合、現在の文字XがFIRSTセットを検索したことをループ識別する.end(2)/FOLLOWセットを求めるアルゴリズム/begin if Xを開始記号then#ÞFOLLOW(X)は、全ての生成式に対して、現在の文字Xを含む生成式if Xの生成式右部の最後(生成式Aのような形)を1つ探します.®aX)thenは、非終端AがFOLLOWセットを求めるか否かを調べる.ループ再帰を避けるif非終端子Aは、FOLLOWセットthenを求めてFOLLOW(A)の要素をFOLLOW(X)に加え、次の生成式にX else求AのFOLLOWセットが含まれているかどうかを調べ続け、生成式右部の最後に、Aが求めたFOLLOWセットelse ifXが存在しないとマークする(A®aBb)then ifの右部Xの後ろの記号列bは、空の字e thenを出すことができ、bがFOLLOWセットを求めたかどうかを検索することができる.ループ再帰ifを回避bを求めるFOLLOWセットthen FOLLOW(A)中の要素をFOLLOW(B)に加える今回のループelse if bは空字thenを出すことができないFIRST(b)を求めFIRST(b)中のすべての非空要素をFOLLOW(B)に加えて現在要求する非終端子Xを識別するFOLLOWセットはend 4を求めた.予測分析テーブルを作成します./構造分析表///A線の行、a線の列、M[A,a]の記入方法は以下の通りです:if(A®dÎP and aÎFIRST(d) ) do M[A,a]=‘A®d’ if (dÞ*e(eÎFIRST(d)) and aÎFOLLOW(A)) do M[A,a]=‘A®d’; else do M[A,a]=‘ERR’. 5.総制御プログラムを構築する.プログラムフローチャートを図1に示す.
図1 6.与えられた入力列に対して,解析過程と結果を与える.
四、実験報告要求1.プログラミング構想、ソースコード(またはフローチャート)を書く.2.アップロードデバッグ時に発見された問題と解決の過程を書く.3.あなたが使っているテストデータと結果を書きます.4.あなたの体験を話します.5.搭乗8時間、実験報告2時間を完了する.
プログラムコード:
図1 6.与えられた入力列に対して,解析過程と結果を与える.
四、実験報告要求1.プログラミング構想、ソースコード(またはフローチャート)を書く.2.アップロードデバッグ時に発見された問題と解決の過程を書く.3.あなたが使っているテストデータと結果を書きます.4.あなたの体験を話します.5.搭乗8時間、実験報告2時間を完了する.
プログラムコード:
#include "stdio.h"
#include "stdlib.h"
#define MaxRuleNum 8
#define MaxVnNum 5
#define MaxVtNum 5
#define MaxStackDepth 20
#define MaxPLength 20
#define MaxStLength 50
struct pRNode /* */
{
int rCursor;
struct pRNode *next;
};
struct pNode
{
int lCursor;
int rLength; /* */
struct pRNode *rHead; /* */
};
char Vn[MaxVnNum + 1]; /* */
int vnNum;
char Vt[MaxVtNum + 1]; /* */
int vtNum;
struct pNode P[MaxRuleNum];
int PNum;
char buffer[MaxPLength + 1];
char ch;
char st[MaxStLength]; /* */
struct collectNode
{
int nVt;
struct collectNode *next;
};
struct collectNode* first[MaxVnNum + 1]; /*first */
struct collectNode* follow[MaxVnNum + 1]; /*follow */
int analyseTable[MaxVnNum + 1][MaxVtNum + 1 + 1];
int analyseStack[MaxStackDepth + 1]; /* */
int topAnalyse; /* */
void Init();/* */
int IndexCh(char ch);
void InputVt(); /* */
void InputVn();/* */
void ShowChArray(char* collect, int num);/* Vn Vt */
void InputP();/* */
bool CheckP(char * st);/* */
void First(int U);
void AddFirst(int U, int nCh); /* first */
bool HaveEmpty(int nVn);
void Follow(int V);/* follow */
void AddFollow(int V, int nCh, int kind);
void ShowCollect(struct collectNode **collect);/* first follow
*/
void FirstFollow();/* first follow*/
void CreateAT();/* */
void ShowAT();/* */
void Identify(char *st);
void InitStack();
void ShowStack();
void Pop();
void Push(int r);
int main()
{
char todo,ch;
Init();
InputVn();
InputVt();
InputP();
getchar();
FirstFollow();
printf(" first ： ");
ShowCollect(first);
printf(" follow ： ");
ShowCollect(follow);
CreateAT();
ShowAT();
todo = 'y';
while('y' == todo)
{
printf("
？ (y / n):");
todo = getchar();
while('y' != todo && 'n' != todo)
{
printf("
(y / n)? ");
todo = getchar();
}
if('y' == todo)
{
int i;
InitStack();
printf(" ( # ) : ");
ch = getchar();
i = 0;
while('#' != ch && i < MaxStLength)
{
if(' ' != ch && '
' != ch)
{
st[i++] = ch;
}
ch = getchar();
}
if('#' == ch && i < MaxStLength)
{
st[i] = ch;
Identify(st);
}
else
printf(" ！
");
}
}
getchar();
}
void Init()
{
int i,j;
vnNum = 0;
vtNum = 0;
PNum = 0;
for(i = 0; i <= MaxVnNum; i++)
Vn[i] = '\0';
for(i = 0; i <= MaxVtNum; i++)
Vt[i] = '\0';
for(i = 0; i < MaxRuleNum; i++)
{
P[i].lCursor = NULL;
P[i].rHead = NULL;
P[i].rLength = 0;
}
PNum = 0;
for(i = 0; i <= MaxPLength; i++)
buffer[i] = '\0';
for(i = 0; i < MaxVnNum; i++)
{
first[i] = NULL;
follow[i] = NULL;
}
for(i = 0; i <= MaxVnNum; i++)
{
for(j = 0; j <= MaxVnNum + 1; j++)
analyseTable[i][j] = -1;
}
}
int IndexCh(char ch)
{
int n;
n = 0; /*is Vn?*/
while(ch != Vn[n] && '\0' != Vn[n])
n++;
if('\0' != Vn[n])
return 100 + n;
n = 0; /*is Vt?*/
while(ch != Vt[n] && '\0' != Vt[n])
n++;
if('\0' != Vt[n])
return n;
return -1;
}
/* Vn Vt */
void ShowChArray(char* collect)
{
int k = 0;
while('\0' != collect[k])
{
printf(" %c ", collect[k++]);
}
printf("
");
}
/* */
void InputVn()
{
int inErr = 1;
int n,k;
char ch;
while(inErr)
{
printf("
， ： ");
printf(" ， # :
");
ch = ' ';
n = 0;
/* */
while(n < MaxVnNum)
{
Vn[n++] = '\0';
}
n = 0;
while(('#' != ch) && (n < MaxVnNum))
{
if(' ' != ch && '
' != ch && -1 == IndexCh(ch))
{
Vn[n++] = ch;
vnNum++;
}
ch = getchar();
}
Vn[n] = '#'; /* "#" */
k = n;
if('#' != ch)
{
if( '#' != (ch = getchar()))
{
while('#' != (ch = getchar()))
;
printf("
！
");
inErr = 1;
continue;
}
}
/* ， ， ， */
Vn[k] = '\0';
ShowChArray(Vn);
ch = ' ';
while('y' != ch && 'n' != ch)
{
if('
' != ch)
{
printf(" ?(y/n):");
}
scanf("%c", &ch);
}
if('n' == ch)
{
printf(" ！
");
inErr = 1;
}
else
{
inErr = 0;
}
}
}
/* */
void InputVt()
{
int inErr = 1;
int n,k;
char ch;
while(inErr)
{
printf("
， ： ");
printf(" # :
");
ch = ' ';
n = 0;
/* */
while(n < MaxVtNum)
{
Vt[n++] = '\0';
}
n = 0;
while(('#' != ch) && (n < MaxVtNum))
{
if(' ' != ch && '
' != ch && -1 == IndexCh(ch))
{
Vt[n++] = ch;
vtNum++;
}
ch = getchar();
}
Vt[n] = '#';
k = n;
if('#' != ch)
{
if( '#' != (ch = getchar()))
{
while('#' != (ch = getchar()))
;
printf("
！
");
inErr = 1;
continue;
}
}
Vt[k] = '\0';
ShowChArray(Vt);
ch = ' ';
while('y' != ch && 'n' != ch)
{
if('
' != ch)
{
printf(" ?(y/n):");
}
scanf("%c", &ch);
}
if('n' == ch)
{
printf(" ！
");
inErr = 1;
}
else
{
inErr = 0;
}
}
}
/* */
void InputP()
{
char ch;
int i = 0, n,num;
printf(" ： ");
scanf("%d", &num);
PNum = num;
getchar(); /* */
printf("
%d , ： ", num);
printf("
");
while(i < num)
{
printf(" %d ： ", i);
/* */
for(n =0; n < MaxPLength; n++)
buffer[n] = '\0';
/* */
ch = ' ';
n = 0;
while('
' != (ch = getchar()) && n < MaxPLength)
{
if(' ' != ch)
buffer[n++] = ch;
}
buffer[n] = '\0';
if(CheckP(buffer))
{
pRNode *pt, *qt;
P[i].lCursor = IndexCh(buffer[0]);
pt = (pRNode*)malloc(sizeof(pRNode));
pt->rCursor = IndexCh(buffer[3]);
pt->next = NULL;
P[i].rHead = pt;
n = 4;
while('\0' != buffer[n])
{
qt = (pRNode*)malloc(sizeof(pRNode));
qt->rCursor = IndexCh(buffer[n]);
qt->next = NULL;
pt->next = qt;
pt = qt;
n++;
}
P[i].rLength = n - 3;
i++;
}
else
printf(" ， ！
");
}
}
/* */
bool CheckP(char * st)
{
int n;
if(100 > IndexCh(st[0]))
return false;
if('-' != st[1])
return false;
if('>' != st[2])
return false;
for(n = 3; '\0' != st[n]; n ++)
{
if(-1 == IndexCh(st[n]))
return false;
}
return true;
}
void First(int U)
{
int i,j;
for(i = 0; i < PNum; i++)
{
if(P[i].lCursor == U)
{
struct pRNode* pt;
pt = P[i].rHead;
j = 0;
while(j < P[i].rLength)
{
if(100 > pt->rCursor)
{
AddFirst(U, pt->rCursor);
break;
}
else
{
if(NULL == first[pt->rCursor - 100])
{
First(pt->rCursor);
}
AddFirst(U, pt->rCursor);
if(!HaveEmpty(pt->rCursor))
{
break;
}
else
{
pt = pt->next;
}
}
j++;
}
if(j >= P[i].rLength) /* */
AddFirst(U, -1);
}
}
}
/* first */
void AddFirst(int U, int nCh)
{
struct collectNode *pt, *qt;
int ch; /* Vn*/
pt = NULL;
qt = NULL;
if(nCh < 100)
{
pt = first[U - 100];
while(NULL != pt)
{
if(pt->nVt == nCh)
break;
else
{
qt = pt;
pt = pt->next;
}
}
if(NULL == pt)
{
pt = (struct collectNode *)malloc(sizeof(struct collectNode));
pt->nVt = nCh;
pt->next = NULL;
if(NULL == first[U - 100])
{
first[U - 100] = pt;
}
else
{
qt->next = pt; /*qt first */
}
pt = pt->next;
}
}
else
{
pt = first[nCh - 100];
while(NULL != pt)
{
ch = pt->nVt;
if(-1 != ch)
{
AddFirst(U, ch);
}
pt = pt->next;
}
}
}
bool HaveEmpty(int nVn)
{
if(nVn < 100)
return false;
struct collectNode *pt;
pt = first[nVn - 100];
while(NULL != pt)
{
if(-1 == pt->nVt)
return true;
pt = pt->next;
}
return false;
}
void Follow(int V)
{
int i;
struct pRNode *pt ;
if(100 == V) /* */
AddFollow(V, -1, 0 );
for(i = 0; i < PNum; i++)
{
pt = P[i].rHead;
while(NULL != pt && pt->rCursor != V)
pt = pt->next;
if(NULL != pt)
{
pt = pt->next;
if(NULL == pt)
{
if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V)
{
Follow(P[i].lCursor);
}
AddFollow(V, P[i].lCursor, 0);
}
else
{
while(NULL != pt && HaveEmpty(pt->rCursor))
{
AddFollow(V, pt->rCursor, 1);
pt = pt->next;
}
if(NULL == pt)
{
if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V)
{
Follow(P[i].lCursor);
}
AddFollow(V, P[i].lCursor, 0);
}
else
{
AddFollow(V, pt->rCursor, 1);
}
}
}
}
}
void AddFollow(int V, int nCh, int kind)
{
struct collectNode *pt, *qt;
int ch;
pt = NULL;
qt = NULL;
if(nCh < 100) /* */
{
pt = follow[V - 100];
while(NULL != pt)
{
if(pt->nVt == nCh)
break;
else
{
qt = pt;
pt = pt->next;
}
}
if(NULL == pt)
{
pt = (struct collectNode *)malloc(sizeof(struct collectNode));
pt->nVt = nCh;
pt->next = NULL;
if(NULL == follow[V - 100])
{
follow[V - 100] = pt;
}
else
{
qt->next = pt; /*qt follow */
}
pt = pt->next;
}
}
else
{
if(0 == kind)
{
pt = follow[nCh - 100];
while(NULL != pt)
{
ch = pt->nVt;
AddFollow(V, ch, 0);
pt = pt->next;
}
}
else
{
pt = first[nCh - 100];
while(NULL != pt)
{
ch = pt->nVt;
if(-1 != ch)
{
AddFollow(V, ch, 1);
}
pt = pt->next;
}
}
}
}
/* first follow */
void ShowCollect(struct collectNode **collect)
{
int i;
struct collectNode *pt;
i = 0;
while(NULL != collect[i])
{
pt = collect[i];
printf("
%c:\t", Vn[i]);
while(NULL != pt)
{
if(-1 != pt->nVt)
{
printf(" %c", Vt[pt->nVt]);
}
else
printf(" #");
pt = pt->next;
}
i++;
}
printf("
");
}
/* first follow*/
void FirstFollow()
{
int i;
i = 0;
while('\0' != Vn[i])
{
if(NULL == first[i])
First(100 + i);
i++;
}
i = 0;
while('\0' != Vn[i])
{
if(NULL == follow[i])
Follow(100 + i);
i++;
}
}
/* */
void CreateAT()
{
int i;
struct pRNode *pt;
struct collectNode *ct;
for(i = 0; i < PNum; i++)
{
pt = P[i].rHead;
while(NULL != pt && HaveEmpty(pt->rCursor))
{
ct = first[pt->rCursor - 100];
while(NULL != ct)
{
if(-1 != ct->nVt)
analyseTable[P[i].lCursor - 100][ct->nVt] = i;
ct = ct->next;
}
pt = pt->next;
}
if(NULL == pt)
{
ct = follow[P[i].lCursor - 100];
while(NULL != ct)
{
if(-1 != ct->nVt)
analyseTable[P[i].lCursor - 100][ct->nVt] = i;
else
analyseTable[P[i].lCursor - 100][vtNum] = i;
ct = ct->next;
}
}
else
{
if(100 <= pt->rCursor) /* */
{
ct = first[pt->rCursor - 100];
while(NULL != ct)
{
analyseTable[P[i].lCursor - 100][ct->nVt] = i;
ct = ct->next;
}
}
else /* */
{
if(-1 == pt->rCursor)
{
ct = follow[P[i].lCursor - 100];
while(NULL != ct)
{
if(-1 != ct->nVt)
analyseTable[P[i].lCursor - 100][ct->nVt] = i;
else /* # */
analyseTable[P[i].lCursor - 100][vtNum] = i;
ct = ct->next;
}
}
else /* */
{
analyseTable[P[i].lCursor - 100][pt->rCursor] = i;
}
}
}
}
}
/* */
void ShowAT()
{
int i,j;
printf(" ：
");
printf("\t|\t");
for(i = 0; i < vtNum; i++)
{
printf("%c\t", Vt[i]);
}
printf("#\t
");
printf("- - -\t|- - -\t");
for(i = 0; i <= vtNum; i++)
printf("- - -\t");
printf("
");
for(i = 0; i < vnNum; i++)
{
printf("%c\t|\t", Vn[i]);
for(j = 0; j <= vtNum; j++)
{
if(-1 != analyseTable[i][j])
printf("R(%d)\t", analyseTable[i][j]);
else
printf("error\t");
}
printf("
");
}
}
void Identify(char *st)
{
int current,step,r; /*r */
printf("
%s ：
", st);
printf(" \t \t \t
");
step = 0;
current = 0;
printf("%d\t",step);
ShowStack();
printf("\t\t%c\t\t- -
", st[current]);
while('#' != st[current])
{
if(100 > analyseStack[topAnalyse])
{
if(analyseStack[topAnalyse] == IndexCh(st[current]))
{
Pop();
current++;
step++;
printf("%d\t", step);
ShowStack();
printf("\t\t%c\t\t 、
", st[current]);
}
else
{
printf("%c-%c ！ ", analyseStack[topAnalyse], st[current]);
printf(" ！
");
return;
}
}
else /* */
{
r = analyseTable[analyseStack[topAnalyse] -
100][IndexCh(st[current])];
if(-1 != r)
{
Push(r);
step++;
printf("%d\t", step);
ShowStack();
printf("\t\t%c\t\t%d
", st[current], r);
}
else
{
printf(" ！
");
return;
}
}
}
if('#' == st[current])
{
if(0 == topAnalyse && '#' == st[current])
{
step++;
printf("%d\t", step);
ShowStack();
printf("\t\t%c\t\t ！
", st[current]);
printf("%s ！
", st);
}
else
{
while(topAnalyse > 0)
{
if(100 > analyseStack[topAnalyse])
{
printf(" ！
");
return;
}
else
{
r = analyseTable[analyseStack[topAnalyse] - 100][vtNum];
if(-1 != r)
{
Push(r); /* ， */
step++;
printf("%d\t", step);
ShowStack();
if(0 == topAnalyse && '#' == st[current])
{
printf("\t\t%c\t\t ！
", st[current]);
printf("%s ！
", st);
}
else
printf("\t\t%c\t\t%d
", st[current], r);
}
else
{
printf(" ！
");
return;
}
}
}
}
}
}
/* */
void InitStack()
{
int i;
/* */
for(i = 0; i < MaxStLength; i++)
st[i] = '\0';
analyseStack[0] = -1; /*#(-1) */
analyseStack[1] = 100; /* */
topAnalyse = 1;
}
/* */
void ShowStack()
{
int i;
for(i = 0; i <= topAnalyse; i++)
{
if(100 <= analyseStack[i])
printf("%c", Vn[analyseStack[i] - 100]);
else
{
if(-1 != analyseStack[i])
printf("%c", Vt[analyseStack[i]]);
else
printf("#");
}
}
}
/* */
void Pop()
{
topAnalyse--;
}
void Push(int r)
{
int i;
struct pRNode *pt;
Pop();
pt = P[r].rHead;
if(-1 == pt->rCursor)
return;
topAnalyse += P[r].rLength;
for(i = 0; i < P[r].rLength; i++)
{
analyseStack[topAnalyse - i] = pt->rCursor;/* */
pt = pt->next;
}
}