?? 預測分析.cpp
字號:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
//===========================================================================================
typedef struct{
char formule[6][15]; //用于存放產生式,從0到6對應+,*,(,),i,#;
char word; //用于存放非終結符
}Table;
typedef struct{ //定義棧(符號棧)
char elem[20];
int top;
}SeqStack;
//==========================================================================================
char Letter[10]; //定義全局變量，用來存放產生式里面出現的大寫字母
char LessLetter[10]; //存放產生式里面出現的終結符
int LetterNumber; //存放非終結符的數目
int LessNumber; //存放終結符的數目
int location; //存放express數組里的位置
int mark=0; //作為標志位,mark=0 表示沒有左遞歸 mark=1 表示存在左遞歸
char FIRST[10][15]; //存放非終結符的FIRST集合
char FOLLOW[10][15]; //存放非終結符的FOLLOW集合
int k1=0;
int step=0; //記錄預測分析的步驟
SeqStack signStack; //符號棧
//===========================================================================================
//函數聲明
void Search(char express[][15],char a);
void First(char a[],char express[][15],int i,int s);
void Follow(char express[][15],char a);
//===========================================================================================
void init(char a[][15]){ //對數組進行初始化
for(int i=0;i<10;i++)
for(int j=0;j<15;j++)
a[i][j]='\0';
}
void InitTable(Table analyse[]){ //對預測分析表進行初始化
int i,j,k;
for(i=0;i<5;i++)
for(j=0;j<6;j++)
for(k=0;k<15;k++){
analyse[i].word=' ';
analyse[i].formule[j][k]='\0';
}
}
void InitSeqStack(){ //對符號棧進行初始化
int i;
for(i=0;i<20;i++)
signStack.elem[i]='\0';
signStack.top=-1;
}
void input(char temp[][15],int number){
for(int i=0;i<number;i++){
printf("\n輸入產生式%d:",i+1);
scanf("%s",temp[i]);
}
}
void output(char temp[][15],int number){
for(int i=0;i<number;i++)
printf("%s\n",temp[i]);
}
bool IsLetter(char a){
if((a<='Z')&&(a>='A'))
return true;
else
return false;
}
bool judge(char a){ //判斷字母a是否出現在非終結字母表中
int i;
for(i=0;i<10;i++)
if(a==Letter[i])
return false;
return true;
}
bool judgement(char a){ //判斷字母a是否出現在終結字母表中
int i;
for(i=0;i<10;i++)
if(a==LessLetter[i])
return false;
return true;
}
void MakeLetter(char temp[][15],int number){ //生成非終結符字母表
int i,j;
for(i=0;i<number;i++)
for(j=0;j<15;j++){
if(IsLetter(temp[i][j])){
if(judge(temp[i][j]))
Letter[LetterNumber++]=temp[i][j];
}
}
Letter[LetterNumber]='\0';
}
void MakeLessLetter(char temp[][15],int number){ //生成終結符字母表
int i,j;
for(i=0;i<number;i++)
for(j=3;j<15;j++){
if(!IsLetter(temp[i][j])&&temp[i][j]!='|'){
if(judgement(temp[i][j]))
LessLetter[LessNumber++]=temp[i][j];
}
}
LessLetter[LessNumber++]='#';
LessLetter[LessNumber]='\0';
}
char DefineLetter(){ //查看還有哪個大寫字母沒有在字母表中出現
for(char ch='A';ch<='Z';ch++)
if(judge(ch)){
Letter[LetterNumber++]=ch;
return ch;
}
return 'Z';
}
void remove(char temp[],int number,char express[][15]){ //消除左遞歸
int i,j,r,k,t;
char ch;
for(i=0;i<15;i++)
if(temp[i]=='|'){
r=i;
for(j=r+1;j<15;j++)
if(temp[j]=='|'||temp[j]=='\0'){
k=j;
break;
}
}
ch=DefineLetter();
for(i=0;i<3;i++)
express[location][i]=temp[i];
for(t=r+1;t<k;t++)
express[location][i++]=temp[t];
express[location][i]=ch;
location++;
express[location][0]=ch;
express[location][1]='-';
express[location][2]='>';
i=3;
for(j=4;j<r;j++)
express[location][i++]=temp[j];
express[location][i++]=ch;
express[location][i++]='|';
express[location][i++]='@';
location++;
}
void manage(char temp[][15],int number,char express[][15]){
int i,j,t;
int flag[10]; //作為標志位,flag=0 表示沒有左遞歸 flag=1 表示存在左遞歸
for(i=0;i<number;i++)
flag[i]=0;
for(i=0;i<number;i++)
for(j=3;j<15;j++){
if(temp[i][0]==temp[i][j]){
flag[i]=1;
mark=1;
t=j;
remove(temp[i],number,express);
}
}
for(i=0;i<number;i++){
if(flag[i]==0){
for(j=0;j<15;j++)
express[location][j]=temp[i][j];
location++;
}
}
}
void Search(char express[][15],char a,int j){
int i;
for(i=0;i<location;i++)
if(express[i][0]==a)
First(express[i],express,i,j);
}
void First(char a[],char express[][15],int i,int s){ //求FIRST集合
int j,k=0,t;
if(IsLetter(a[3]))
Search(express,a[3],s);
else{
FIRST[s][k++]=a[3];
for(j=3;j<15;j++)
if(a[j]=='|')
FIRST[s][k++]=a[j+1];
FIRST[s][k]='\0';
}
if(i!=s){ //表示求左遞歸時候進行了遞歸運算,即產生式右邊第一個是非終結符
for(t=0;t<15;t++)
if(FIRST[s][t]=='@')
First(a,express,i,s);
}
}
void outFIRST(char express[][15]){ //將FIRST集合輸出到屏幕上
int i,j,k=0;
printf("\nFIRST集合:\n");
for(i=0;i<location;i++){
printf("FIRST(%c)={",express[i][0]);
for(j=0;j<15;j++)
if(FIRST[i][j+1]=='\0'){
printf("%c}\n",FIRST[i][j]);
break;
}
else
printf("%c,",FIRST[i][j]);
}
}
bool estimate(char a[],char b){ //判斷字母b是否在數組a中
for(int i=0;i<15;i++)
if(b==a[i])
return true;
return false;
}
void addFollow(int i,int j){ //將FOLLOW[i]加到FOLLOW[j]中
int a;
for(a=0;a<15;a++)
if(!estimate(FOLLOW[j],FOLLOW[i][a]))
FOLLOW[j][k1++]=FOLLOW[i][a];
}
void Solve(char express[][15],char a[],int p,int j){
int i,t,r,temp;
k1=0;
if(a[j+1]=='\0'){ //若FOLLOW[p]已經求出，則直接加入到FOLLOW[a[j]]中
if(FOLLOW[p][0]!='\0'){
for(int r=0;r<location;r++)
if(express[r][0]==a[j]){
temp=r;
break;
}
addFollow(p,temp);
}
else
Follow(express,express[p][0]); //若FOLLOW[p]還沒有求出，則先求出FOLLOW[p];
}
else if(!IsLetter(a[j+1])&&a[j+1]!='|'){
if(a[j]==express[0][0]){
k1++;
FOLLOW[0][k1++]=a[j+1];
}
else{
for(r=0;r<location;r++)
if(express[r][0]==a[j]){
FOLLOW[r][k1++]=a[j+1];
break;
}
}
}
else if(IsLetter(a[j+1])){
for(i=0;i<location;i++)
if(express[i][0]==a[j+1]){
for(int s=0;s<15;s++){
if(express[i][s]=='@'&&express[i][s-1]=='|') //若非終結符能直接推出@
if( FOLLOW[i][0]!='\0'){
for(int r=0;r<location;r++)
if(express[r][0]==a[j]){
temp=r;
break;
}
addFollow(i,temp);
}
else
Follow(express,express[i][0]);
}
for(t=0;t<15;t++) //將FIRST[a[j+1]]加入到FOLLOW[i]中
if(!estimate(FOLLOW[temp],FIRST[i][t]))
if(FIRST[i][t]!='@')
FOLLOW[temp][k1++]=FIRST[i][t];
}
}
}
void Follow(char express[][15],char a){ //求FOLLOW集合
int i,j;
if(a==express[0][0]) //若為開始符號則把#號加入到FOLLOW集合中
FOLLOW[0][0]='#';
for(i=0;i<location;i++)
for(j=3;j<15;j++)
if(express[i][j]==a&&express[i][0]!=a){
Solve(express,express[i],i,j);
}
}
void outFOLLOW(char express[][15]){ //將FIRST集合輸出到屏幕上
int i,j,k=0;
printf("\nFOLLOW集合:\n");
for(i=0;i<location;i++){
printf("FOLLOW(%c)={",express[i][0]);
for(j=0;j<15;j++)
if(FOLLOW[i][j+1]=='\0'){
printf("%c}\n",FOLLOW[i][j]);
break;
}
else
printf("%c,",FOLLOW[i][j]);
}
}
bool opinion(char a,int i){ //判斷字母a是否出現在FIRST集合中
int j;
for(j=0;j<15;j++)
if(a==FIRST[i][j])
return true;
return false;
}
bool judgeFollow(char a,int i){ //判斷字母a是否出現在FOLLOW集合中
int j,k;
for(j=0;j<15;j++)
if(FIRST[i][j]=='@'){
for(k=0;k<15;k++)
if(a==FOLLOW[i][k])
return true;
}
return false;
}
int Creat(Table &tab,char express[],int j){ //將產生式放入分析表中
int i;
tab.word=express[0];
for(i=0;i<15;i++)
if(express[i]=='|')
if(express[i+1]==LessLetter[j]){
tab.formule[j][0]=express[0];
tab.formule[j][1]='-';
tab.formule[j][2]='>';
tab.formule[j][3]=LessLetter[j];
return 1;
}
for(i=0;i<15;i++){
if(express[i]!='|')
tab.formule[j][i]=express[i];
else
break;
}
return 0;
}
void CreatTable(Table analyse[],char express[][15]){ //構造預測分析表
int i,j;
for(i=0;i<location;i++)
for(j=0;j<LessNumber;j++)
if(opinion(LessLetter[j],i))
Creat(analyse[i],express[i],j);
else{
if(judgeFollow(LessLetter[j],i)){
analyse[i].formule[j][0]=express[i][0];
analyse[i].formule[j][1]='-';
analyse[i].formule[j][2]='>';
analyse[i].formule[j][3]='@';
}
}
}
void outTable(Table analyse[]){ //輸出預測分析表
int i,j;
printf("\n預測分析表:\n");
for(j=0;j<LessNumber;j++)
printf("\t%c",LessLetter[j]);
printf("\n");
for(i=0;i<5;i++){
printf("%c\t",analyse[i].word);
for(j=0;j<6;j++)
printf("%s\t",analyse[i].formule[j]);
printf("\n");
}
}
bool judgeStack(char a){ //判斷字母a與符號棧頂元素是否相同
if(signStack.elem[signStack.top]==a)
return true;
return false;
}
int settle(char bunch[],Table analyse[],char express[][15]){
int i,j,t,s,r;
int flag=0;
for(i=0;i<location;i++)
if(express[i][0]==signStack.elem[signStack.top]){
j=i;
break;
}
if(judgeStack(bunch[0])&&bunch[0]=='#') //如果符號棧頂為'#'且輸入串也為'#'號時候結束，分析成功了。
return 1;
else if(judgeStack(bunch[0])){ //如果符號棧頂和輸入串第一位相同，則把符號棧的棧頂元素彈出，且輸入串第一位也刪除
for(i=0;i<10;i++)
bunch[i-1]=bunch[i];
signStack.elem[signStack.top]='\0';
signStack.top--;
printf("%d\t%s\t%s\t\n",step++,signStack.elem,bunch);
}
else{
for(t=0;t<LessNumber;t++){
if(bunch[0]==LessLetter[t]){
s=t;
if(analyse[j].formule[s][3]=='@'){ //如果對應的產生式為X->@,則直接把棧頂元素彈出，輸入串不變
signStack.elem[signStack.top]='\0';
signStack.top--;
flag=1;
break;
}
else{
for(r=15;r>=3;r--){ //找到符號棧頂和輸入串第一位對應的產生式，將產生式右部反序壓入到符號棧中
if(analyse[j].formule[s][r]!='\0'){
signStack.elem[signStack.top]=analyse[j].formule[s][r];
signStack.top++;
}
}
}
if(flag==0)
signStack.top--;
break;
}
}
printf("%d\t%s\t%s\t%s\n",step++,signStack.elem,bunch,analyse[j].formule[s]);
}
return 0;
}
void inputString(char bunch[],Table analyse[],char express[][15]){
int i,j,k;
printf("\n句子分析:\n");
scanf("%s",bunch);
printf("\n利用預測分析表進行預測分析的步驟如下:\n");
signStack.top++;
signStack.elem[signStack.top]='#'; //首先將'3'號壓入符號棧
signStack.top++;
signStack.elem[signStack.top]=express[0][0]; //將開始符號壓入棧頂
printf("步驟\t符號棧\t輸入串\t所用產生式\n");
printf("%d\t%s\t%s\t\n",step++,signStack.elem,bunch); //找到開始符號和輸入串第一位對應的產生式，將產生式右部反序壓入到符號棧中
for(i=0;i<LessNumber;i++){
if(LessLetter[i]==bunch[0]){
j=i;
for(k=15;k>=3;k--)
if(analyse[0].formule[j][k]!='\0'){
signStack.elem[signStack.top]=analyse[0].formule[j][k];
signStack.top++;
}
}
}
printf("%d\t%s\t%s\t%s\n",step++,signStack.elem,bunch,analyse[0].formule[j]);
signStack.top--;
while(signStack.elem[signStack.top]!='#')
settle(bunch,analyse,express);
printf("分析成功!\n");
}
int main(){
char temp[10][15];
char express[10][15];
int number; //記錄文法里面產生式的個數
int i;
char bunch[10]; //存放輸入串
for(i=0;i<10;i++)
bunch[i]='\0';
Table analyse[5]; //存放預測分析表
init(temp);
init(express);
init(FIRST);
init(FOLLOW);
InitTable(analyse);
InitSeqStack();
for(i=0;i<10;i++)
Letter[i]='\0';
printf("\n產生式個數:");
scanf("%d",&number);
input(temp,number);
MakeLetter(temp,number);
MakeLessLetter(temp,number);
manage(temp,number,express);
if(mark==1){
printf("\n存在左遞歸!\n");
printf("消除左遞歸后:\n");
output(express,location);
}
for(i=0;i<location;i++)
First(express[i],express,i,i);
for(i=0;i<location;i++)
Follow(express,express[i][0]);
outFIRST(express);
outFOLLOW(express);
CreatTable(analyse,express);
outTable(analyse);
inputString(bunch,analyse,express);
return 1;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -