?? ll_1.cpp
字號:
// ***************************************************************
// LL_1.CPP version: 1.0 謝偉純 05軟件工程 date: 05/22/2008
// -------------------------------------------------------------
// 程序名：LL(1) 語法分析程序
// -------------------------------------------------------------
// Copyright (C) 2008 - All Rights Reserved
// ***************************************************************
// 說明：本程序可對用戶輸入的合法（無多余規(guī)則，無遞歸產(chǎn)生式）文法，
// 進行是否為LL(1)文法判斷，并生成相應的文法預測分析表。在分析表產(chǎn)
// 生后，用戶可輸入要分析的字符串，進行分析。
// ***************************************************************
#include <iostream>
#include <string>
#include <conio.h>
#include <stdio.h>
using namespace std;
//////////////////////////////////////////////////////////////////////////
//全局變量字典{
int i = 0, j = 0, t = 0, n = 0, m = 0, x = 0, y = 0; //下標或臨時變量
int len = 0; //字符串長度
int isENum = 0; //能推出e的終結符數(shù)量
bool isE = false; //標記是否能推出e
bool isUpdate = false; //標記是否更新過結果集
bool isSame = false; //標記是否有相同SELECT結果集
char strTemp[100] = "\0"; //臨時字符串 或 要分析的字符串
char cTemp = '\0'; //臨時字符
int grammarNum = 0; //文法數(shù)量
char (*grammar)[32]; //文法 grammar[grammarNum][32]
char noEndSign[30]; //非終結符
char endSign[100]; //終結符
char (*grammarTemp)[32]; //臨時文法 grammarTemp[grammarNum][32]
char (*isDerivation_e)[2]; //標記非終結符是否推出e數(shù)組 isDerivation_e[strlen(noEndSign)][2]
char (*frist)[100]; //每個文法符號的FRIST集 frist[strlen(noEndSign) + strlen(endSign)][100]
char (*bringFrist)[2][100]; //產(chǎn)生式的FRIST集 bringFrist[grammarNum][2][100]
char (*fllow)[100]; //非終結符的FLLOW集 fllow[strlen(noEndSign)][100]
char (*select)[2][100]; //select集 select[grammarNum][2][100]
char construeArray[100]; //分析棧
char bringStr[100]; //推導所用的產(chǎn)生式或匹配字符串
char stepNum[10]; //步聚數(shù)
char construeTop = '\0'; //棧頂字符
char strTempTop = '\0'; //剩余輸入串頭字符
//全局變量字典}
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//輸入文法
void InputGrammar()
{
//初始數(shù)據(jù)
do
{
n = 0; //標記成功賦值的變量數(shù)
fflush(stdin); //清空輸入緩存區(qū)
cout<<"請輸入文法數(shù)量（1<=n<=20）：";
n = scanf("%d", &grammarNum);
} while(!n || grammarNum < 1 || grammarNum > 20);
grammar = new char[grammarNum][32];
//輸入文法字符串
cout<<"\n"<<"文法輸入規(guī)則如下：\n\na、大寫英文字母表示非終結符。\
\nb、e表示空產(chǎn)生式。 \
\nc、除大寫字母、#、'、| 外的單字符表示終結符。\
\nd、不能出現(xiàn)遞歸文法。（如 S->S或S->A, A->S;）\
\ne、不能出現(xiàn)多余文法規(guī)則。（如 S->A，A不是非終結符；程序不檢測）\
\nf、文法產(chǎn)生式長度不超過10個字符。（程序不檢測）"<<"\n"<<endl;
for (i = 0; i < grammarNum; ++i)
{
cout<<i+1<<" ";
//輸入文法左部
strTemp[0] = getch();
if ( strTemp[0] >= 'A' && strTemp[0] <= 'Z')
{
grammar[i][0] = strTemp[0];
cout<<grammar[i][0]<<"->";
}
else
{
cout<<"請輸入非終結符！"<<endl;
--i;
continue;
}
//輸入文法右部
cin>>strTemp;
for (j = 0; j < strlen(strTemp); ++j)
{
grammar[i][j+1] = strTemp[j];
}
grammar[i][++j] = '\0';
//檢測文法合法性
len = strlen(grammar[i]);
for (j = 1; j < len; ++j)
{
//是否為空串
if (j == 1 && grammar[i][j] == 'e' && grammar[i][j+1] == '\0')
{
continue;
}
if(grammar[i][j] == '#' || grammar[i][j] == '|' || grammar[i][j] == 'e' || grammar[i][j] == '\'')
{
cout<<"產(chǎn)生式含有非法字符，請重新輸入："<<endl;
--i;
break;
}
}
//檢測遞歸產(chǎn)生式
for(j=1; j<len; ++j)
{
if (grammar[i][0] != grammar[i][j])
{
break;
}
}
if (j == len)
{
cout<<"文法存在遞歸產(chǎn)生式，請重新輸入："<<endl;
--i;
}
}
cout<<'\n'<<endl;
//顯示文法
cout<<"你輸入的文法是："<<'\n'<<endl;
for (i = 0; i < grammarNum; ++i)
{
cout<<i+1<<" "<<grammar[i][0]<<"->";
for (j = 1; j < strlen(grammar[i]); ++j)
{
cout<<grammar[i][j];
}
cout<<endl;
}
cout<<endl;
}
//////////////////////////////////////////////////////////////////////////
//獲取，顯示終結符和非終結符
void Count_noEndSign_endSign()
{
//初始數(shù)據(jù)
strcpy(noEndSign, "\0");
strcpy(endSign, "\0");
for (i = 0; i < grammarNum ; ++i)
{
//非終結符判斷
if (!strchr(noEndSign, grammar[i][0]))
{
len = strlen(noEndSign);
noEndSign[len] = grammar[i][0];
noEndSign[len+1] = '\0';
}
//終結符判斷
for (j = 1, m = 0; j < strlen(grammar[i]); ++j)
{
if (!strchr(endSign, grammar[i][j]) && (grammar[i][j] < 'A' || grammar[i][j] > 'Z') && grammar[i][j] != 'e')
{
len = strlen(endSign);
endSign[len] = grammar[i][j];
endSign[len+1] = '\0';
}
}
}
//顯示終結符和非終結符
n = 0;
cout<<"非終結符是：";
while (noEndSign[n] != '\0')
{
cout<<noEndSign[n++]<<" ";
}
cout<<endl;
n = 0;
cout<<"終結符是：";
while (endSign[n] != '\0')
{
cout<<endSign[n++]<<" ";
}
cout<<'\n'<<endl;
}
//////////////////////////////////////////////////////////////////////////
//求出能推出e的非終結符
void Count_isDerivation_e()
{
//初始數(shù)據(jù)
grammarTemp = new char[grammarNum][32];
for (i = 0; i < grammarNum; ++i)
{
strcpy(grammarTemp[i], grammar[i]);
}
isDerivation_e = new char[strlen(noEndSign)][2];
//1、初始標記數(shù)組，全部設為'2'（'0'表示不能推出e，'1'表示能推出e，'2'表示未定）
for (i = 0; i < len; ++i)
{
isDerivation_e[i][0] = noEndSign[i];
isDerivation_e[i][1] = '2';
}
//2、掃描文法中的產(chǎn)生式
for (i = 0; i < grammarNum; ++i)
{
//是否推出e的非終結符
if (grammarTemp[i][1] == 'e')
{
for (j = 0; j < strlen(noEndSign); ++j)
{
if (isDerivation_e[j][0] == grammarTemp[i][0])
{
isDerivation_e[j][1] = '1';
}
}
continue;
}
//是否含有終結符
len = strlen(grammarTemp[i]);
for (j = 1; j < len; ++j)
{
if (strchr(endSign, grammarTemp[i][j]))
{
grammarTemp[i][0] = '\0';
break;
}
}
}
//標記不能推出e的非終結符
for (i=0; i<strlen(noEndSign); ++i)
{
for (j=0; j<grammarNum; ++j)
{
if (isDerivation_e[i][0] == grammarTemp[j][0])
{
break;
}
}
if (j == grammarNum)
{
isDerivation_e[i][1] = '0';
}
}
//3、掃描產(chǎn)生式右部的每一符號
//是
do
{
isUpdate = false; //標記此次操作是否有更新過數(shù)據(jù)
for (i=0; i<grammarNum; ++i)
{
for (j=1; j<strlen(grammarTemp[i]); ++j)
{
if (strchr(noEndSign, grammarTemp[i][j]))
{
for (t=0; t<strlen(noEndSign); ++t)
{
if (isDerivation_e[t][0] == grammarTemp[i][j] && isDerivation_e[t][1] == '1')
{
grammarTemp[i][j] = 32;
}
}
}
}
}
for (i=0; i<strlen(noEndSign); ++i)
{
for (j=0; j<grammarNum; ++j)
{
if (isDerivation_e[i][0] == grammarTemp[j][0])
{
for (t=1; t<strlen(grammarTemp[j]); ++t)
{
if (grammarTemp[j][t] != 32)
{
break;
}
}
if (t == strlen(grammarTemp[j]))
{
isDerivation_e[i][1] = '1';
isUpdate = true;
//刪除該非終結符在左部的所有產(chǎn)生式
for (n=0; n<grammarNum; ++n)
{
if (grammarTemp[j][0] == grammarTemp[n][0] && j!= n)
{
grammarTemp[n][0] = '\0';
}
}
grammarTemp[j][0] = '\0';
}
}
}
}
//否
for (i=0; i<grammarNum; ++i)
{
for (j=1; j<strlen(grammarTemp[i]); ++j)
{
if (strchr(noEndSign, grammarTemp[i][j]))
{
for (t=0; t<strlen(noEndSign); ++t)
{
if (isDerivation_e[t][0] == grammarTemp[i][j] && isDerivation_e[t][1] == '0')
{
grammarTemp[i][0] = '\0';
}
}
}
}
}
for (i=0; i<strlen(noEndSign); ++i)
{
if (isDerivation_e[i][1] != '2')
{
continue;
}
for (j=0; j<grammarNum; ++j)
{
if (isDerivation_e[i][0] ==grammarTemp[j][0])
{
break;
}
}
if (j == grammarNum)
{
isDerivation_e[i][1] = '0';
isUpdate = true;
}
}
} while(isUpdate);
//顯示結果
cout<<"非終結符能否推導出e的表"<<endl;
cout<<"------------------------------------------------------------------"<<endl;
for (i=0; i<strlen(noEndSign); ++i)
{
cout<<" "<<isDerivation_e[i][0]<<" ";
}
cout<<"\n"<<endl;
for (i=0; i<strlen(noEndSign); ++i)
{
switch(isDerivation_e[i][1])
{
case '0':
cout<<" 否 ";
break;
case '1':
cout<<" 是 ";
break;
default:
break;
}
}
cout<<"\n"<<"------------------------------------------------------------------"<<endl;
cout<<endl;
}
//////////////////////////////////////////////////////////////////////////
//計算FRIST集
void Count_Frist()
{
//初始數(shù)據(jù)
len = strlen(noEndSign) + strlen(endSign);
frist = new char[len][100];
n = 0;
for (i=0; i<strlen(noEndSign); ++i)
{
frist[n][0] = noEndSign[i];
frist[n++][1] = '\0';
}
for (i=0; i<strlen(endSign); ++i)
{
frist[n][0] = endSign[i];
frist[n++][1] = '\0';
}
//計算每個符號的FRIST集
//1、屬于終結符情況
for (i=0; i<len; ++i)
{
if (strchr(endSign, frist[i][0]))
{
frist[i][1] = frist[i][0];
frist[i][2] = '\0';
}
}
//2、屬于非終結符，產(chǎn)生式首字符為終結符
for (i=0; i<strlen(noEndSign); ++i) //遍歷非終結符的FRIST集frist[i][0]
{
for (j=0; j<grammarNum; ++j) //遍歷文法grammar[j][0]
{
if (frist[i][0] == grammar[j][0] && strchr(endSign, grammar[j][1]))
{
len = strlen(frist[i]);
frist[i][len] = grammar[j][1];
frist[i][len+1] = '\0';
}
}
}
//3、能推出e的非終結符
for (i=0; i<strlen(noEndSign); ++i) //遍歷非終結符的FRIST集frist[i][0]
{
for (j=0; j<strlen(noEndSign); ++j) //遍歷能否推出e情況表
{
if (frist[i][0] == isDerivation_e[j][0] && isDerivation_e[j][1] == '1' && !strchr(frist[i], 'e'))
{
len = strlen(frist[i]);
frist[i][len] = 'e';
frist[i][len+1] = '\0';
break;
}
}
}
//4、5、產(chǎn)生中的非終結符能推出e的情況處理
do
{
isE = true;
isENum = 0;
isUpdate = false;
for (i=0; i<strlen(noEndSign); ++i) //遍歷frist[i]
{
for (j=0; j<grammarNum; ++j) //遍歷grammar[j]
{
if (frist[i][0] == grammar[j][0])
{
for (t=1; t<strlen(grammar[j]); ++t) //遍歷grammar[j][t]
{
//是否為非終結符
if (strchr(endSign, grammar[j][t]))
{
break;
}
//判斷是否能推出e
for (n=0; n<strlen(noEndSign); ++n) //遍歷isDerivation_e[n]
{
if (grammar[j][t] == isDerivation_e[n][0])
{
if (isDerivation_e[n][1] == '1')
{
++isENum;
break;
}
else
{
isE = false;
break;
}
}
}
if (isE == 0)
{
isE = true;
break;
}
}
//判斷產(chǎn)生式中字符的推出e數(shù)量，并處理
len = strlen(grammar[j]);
//前部分能推出e
if (isENum != len -1)
{
for (t=1; t<=isENum+1; ++t) //遍歷grammar[j][t]
{
for (n=0; n<strlen(noEndSign); ++n) //遍歷frist[n]
{
if (grammar[j][t] == frist[n][0])
{
for (m=1; m<strlen(frist[n]); ++m) //遍歷frist[n][m]
{
if (t != isENum+1)
{
if (!strchr(frist[i], frist[n][m]) && frist[n][m] != 'e')
{
x = strlen(frist[i]);
frist[i][x] = frist[n][m];
frist[i][x+1] = '\0';
isUpdate = true;
}
}
else
{
if (!strchr(frist[i], frist[n][m]))
{
x = strlen(frist[i]);
frist[i][x] = frist[n][m];
frist[i][x+1] = '\0';
isUpdate = true;
}
}
}
}
}
}
}
//全部都能推出e
if (isENum == len - 1)
{
for (t=1; t<=isENum+1; ++t) //遍歷grammar[j][t]
{
for (n=0; n<strlen(noEndSign); ++n) //遍歷frist[n]
{
if (grammar[j][t] == frist[n][0])
{
for (m=1; m<strlen(frist[n]); ++m) //遍歷frist[n][m]
{
if (!strchr(frist[i], frist[n][m]))
{
x = strlen(frist[i]);
frist[i][x] = frist[n][m];
frist[i][x+1] = '\0';
isUpdate = true;
}
}
}
}
}
//并e
if (!strchr(frist[i], 'e'))
{
x = strlen(frist[i]);
frist[i][x] = frist[n][m];
frist[i][x+1] = '\0';
isUpdate = true;
}
}
}
isENum = 0;
}
}
} while(isUpdate);
//求字符串FRIST集
//初始數(shù)組
bringFrist = new char[grammarNum][2][100];
for (i=0; i<grammarNum; ++i)
{
bringFrist[i][0][0] = '\0';
for (j=1; j<strlen(grammar[i]); ++j)
{
len = strlen(bringFrist[i][0]);
bringFrist[i][0][len] = grammar[i][j];
bringFrist[i][0][len+1] = '\0';
}
}
for (i=0; i<grammarNum; ++i)
{
strcpy(bringFrist[i][1], "\0");
}
//產(chǎn)生式首字符能否推出e情況處理
for (i=0; i<grammarNum; ++i)
{
isENum = 0;
len = strlen(noEndSign);
for (j=0; j<len; ++j)
{
if (bringFrist[i][0][0] == isDerivation_e[j][0] && isDerivation_e[j][1] == '1')
{
isENum = 1;
break;
}
}
if (1 == isENum)
{
for (j=1; j<strlen(bringFrist[i][0]); ++j) //遍歷產(chǎn)生式字符
{
for (t=0; t<strlen(noEndSign); ++t) //判斷是否能推出e
{
if (bringFrist[i][0][j] == isDerivation_e[t][0] && isDerivation_e[t][1] == '1')
{
++isENum;
}
}
if (t == strlen(noEndSign))
{
break;
}
}
//產(chǎn)生式全部字符能推出e
if (isENum == strlen(bringFrist[i][0]))
{
for (j=0; j<strlen(bringFrist[i][0]); ++j) //遍歷產(chǎn)生式
{
for (t=0; t<strlen(noEndSign); ++t) //遍歷FRIST集
{
if (bringFrist[i][0][j] == frist[t][0]) //是否為非終結符的FRIST集
{
for (m=1; m<strlen(frist[t]); ++m) //遍歷FRIST集
{
if (!strchr(bringFrist[i][1], frist[t][m]))
{
len = strlen(bringFrist[i][1]);
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -