语法分析之算符优先算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#include <conio.h>

typedef struct {
    char* formula;//产生式
    char  right[100][100]; //产生式右部
    int   rightNum;	//产生式右部个数
    char  left;	//产生式左部
    char* firstVT[100];
    char* lastVT[100];
}grammarElement;


typedef struct {
    char nonTer;
    char ter;
}symbolPair;

typedef struct {
    symbolPair *base;
    symbolPair *top;
    int  size;
}Stack;
Stack analyzeStack;

typedef struct {
    char *base;
    char *top;
    int size;
}Stack2;
Stack2 processStack;


grammarElement  gramOldSet[200];//原始文法的产生式集;
int gramOldSetNum;
char terSymbol[200];    //终结符号
char non_ter[200];      //非终结符号
int F[200][200];        //FirstVT集
int L[200][200];        //LastVT集
char P[200][200];       //优先关系表
char* input;

/*将光标移动到X,Y坐标处*/
void toxy(int x, int y){
    COORD pos = { x , y };
    HANDLE Out = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleCursorPosition(Out, pos);
}

/*初始化文法并筛选出其中的终结符与非终结符*/
void init(){
   /* gramOldSet[0].formula="E->E+T|T";
    gramOldSet[1].formula="T->T*F|F";
    gramOldSet[2].formula="F->P^F|P";
    gramOldSet[3].formula="P->(E)|i";
    gramOldSetNum=4; */
    gramOldSet[0].formula="E->E+T|E-T|T";
    gramOldSet[1].formula="T->T*F|T/F|F";
    gramOldSet[2].formula="F->(E)|i";
    gramOldSetNum=3;
    //input="((i-i))/i+i#";
    input="(i+)i+(i*i))#";
    for(int i=0;i<gramOldSetNum;i++){
        for (int j = 3; j < strlen(gramOldSet[i].formula); j++) {
            char ch=gramOldSet[i].formula[j];
            if(ch!='|'){
                if(ch>='A'&&ch<='Z'){
                    int flag=0;
                    for(int k=0;k<strlen(non_ter);k++){
                        if(ch==non_ter[k]){
                            flag=1;
                        }
                    }
                    if(flag==0){
                        non_ter[strlen(non_ter)]=ch;
                    }
                } else{
                    int flag=0;
                    for(int k=0;k<strlen(terSymbol);k++){
                        if(ch==terSymbol[k]){
                            flag=1;
                        }
                    }
                    if(flag==0){
                        terSymbol[strlen(terSymbol)]=ch;
                    }
                }
            }
        }
    }
}

/*对每个产生式进行初始化准备*/
void prepare(){
    for (int i = 0; i <gramOldSetNum; i++) {
        gramOldSet[i].left=gramOldSet[i].formula[0];
        int rightNum=0,mark=3;
        for(int j=3;j<strlen(gramOldSet[i].formula);j++){
            if(gramOldSet[i].formula[j]=='|'){
                for(int k=mark;k<j;k++){
                    gramOldSet[i].right[rightNum][k-mark]=gramOldSet[i].formula[k];
                }
                mark=j+1;
                rightNum++;
            }
        }
        for(int k=mark;k<strlen(gramOldSet[i].formula);k++){
            gramOldSet[i].right[rightNum][k-mark]=gramOldSet[i].formula[k];
        }
        rightNum++;
        gramOldSet[i].rightNum=(rightNum);
    }
}

/*初始化栈*/
void initStack(){
    analyzeStack.base=(symbolPair*)malloc(50*sizeof(symbolPair));
    analyzeStack.size=50;
    analyzeStack.top=analyzeStack.base;
}

/*入栈操作*/
int push(symbolPair a){
    if(analyzeStack.top-analyzeStack.base>analyzeStack.size){
        return 0;
    }
    *analyzeStack.top=a;
    analyzeStack.top++;
    return 1;
}

/*出栈操作*/
symbolPair pop(){
   /* if(analyzeStack.top==analyzeStack.base){
        return NULL;
    }*/
    analyzeStack.top--;
    symbolPair ch=*analyzeStack.top;
    return ch;
}

/*初始化栈*/
void initStack2(){
    processStack.base=(char*)malloc(50*sizeof(char));
    processStack.size=0;
    processStack.top=processStack.base;
}

/*入栈操作*/
int push2(char ch){
    if(processStack.top-processStack.base>processStack.size){
        return 0;
    }
    *processStack.top=ch;
    processStack.top++;
    processStack.size++;
    return 1;
}

/*出栈操作*/
char pop2(){
     if(processStack.top==processStack.base){
         return 0;
     }
     processStack.top--;
     processStack.size--;
     char ch=*processStack.top;
     return ch;
}

char getTop(){
    return *(processStack.top-1);
}

//遍历栈
void stackTraverse(){
    char *temp=processStack.base;
    while(temp!=processStack.top){
        printf("%c",*temp);
        temp++;
    }
}

void destroyStack(){
    analyzeStack.base=NULL;
    analyzeStack.top=NULL;
    analyzeStack.size=0;
}

int isStackEmpty(){
    if(analyzeStack.top==analyzeStack.base){
        return 1;
    }
    return 0;
}

int isTerSymbol(char ch){
    for (int i = 0; i < strlen(terSymbol); ++i) {
        if(ch==terSymbol[i]){
            return 1;
        }
    }
    return 0;
}

int isNonTerSymbol(char ch){
    for(int i=0;i<strlen(non_ter);i++){
        if(ch==non_ter[i]){
            return 1;
        }
    }
    return 0;
}

int getNonTerPoint(char ch){
    for(int h=0;h<gramOldSetNum;h++){
        if(gramOldSet[h].left==ch){
            return h;
        }
    }
    return -1;
}

int getTerPoint(char ch){
    for(int h=0;h<strlen(terSymbol);h++){
        if(ch==terSymbol[h]){
            return h;
        }
    }
    return -1;
}

void getFirstVT(){
    for (int i = 0; i <gramOldSetNum; i++) {
        for (int j = 0; j <gramOldSet[i].rightNum; ++j) {
            char left=gramOldSet[i].left;
            char ch1=gramOldSet[i].right[j][0];
            char ch2=gramOldSet[i].right[j][1];
            if(isTerSymbol(ch1)){
                F[getNonTerPoint(left)][getTerPoint(ch1)]=1;
            } else if(isNonTerSymbol(ch1)&&isTerSymbol(ch2)){
                F[getNonTerPoint(left)][getTerPoint(ch2)]=1;
            }
        }
    }
    initStack();
    for(int i=0;i<gramOldSetNum;i++){
        for(int j=0;j<strlen(terSymbol);j++){
            if(F[i][j]==1){
                symbolPair s;
                s.nonTer=gramOldSet[i].left;
                s.ter=terSymbol[j];
                push(s);
            }
        }
    }
    while (!isStackEmpty()){
        symbolPair s=pop();
        char nonTer1=s.nonTer;
        char nonTer2;
        char ter=s.ter;
        for (int i=0;i<gramOldSetNum;i++){
            for (int j = 0; j < gramOldSet[i].rightNum; ++j) {
                if(gramOldSet[i].right[j][0]==nonTer1){
                    nonTer2=gramOldSet[i].left;
                    if(F[getNonTerPoint(nonTer2)][getTerPoint(ter)]!=1){
                        F[getNonTerPoint(nonTer2)][getTerPoint(ter)]=1;
                        symbolPair temp;
                        temp.nonTer=nonTer2;
                        temp.ter=ter;
                        push(temp);
                    }
                }
            }
        }
    }
    destroyStack();
}

void getLastVT(){
    for (int i = 0; i <gramOldSetNum; i++) {
        for (int j = 0; j <gramOldSet[i].rightNum; ++j) {
            char left=gramOldSet[i].left;
            int rightLength=strlen(gramOldSet[i].right[j]);
            if(rightLength==1){
                char ch=gramOldSet[i].right[j][rightLength-1];
                if(isTerSymbol(ch)){
                    L[getNonTerPoint(left)][getTerPoint(ch)]=1;
                }
            } else{
                char ch1=gramOldSet[i].right[j][rightLength-1];
                char ch2=gramOldSet[i].right[j][rightLength-2];
                if(isTerSymbol(ch1)){
                    L[getNonTerPoint(left)][getTerPoint(ch1)]=1;
                } else if(isNonTerSymbol(ch1)&&isTerSymbol(ch2)){
                    L[getNonTerPoint(left)][getTerPoint(ch2)]=1;
                }
            }
        }
    }
    initStack();
    for(int i=0;i<gramOldSetNum;i++){
        for(int j=0;j<strlen(terSymbol);j++){
            if(L[i][j]==1){
                symbolPair s;
                s.nonTer=gramOldSet[i].left;
                s.ter=terSymbol[j];
                push(s);
            }
        }
    }
    while (!isStackEmpty()){
        symbolPair s=pop();
        char nonTer1=s.nonTer;
        char nonTer2;
        char ter=s.ter;
        for (int i=0;i<gramOldSetNum;i++){
            for (int j = 0; j < gramOldSet[i].rightNum; ++j) {
                int rightLength=strlen(gramOldSet[i].right[j]);
                if(gramOldSet[i].right[j][rightLength-1]==nonTer1){
                    nonTer2=gramOldSet[i].left;
                    if(L[getNonTerPoint(nonTer2)][getTerPoint(ter)]!=1){
                        L[getNonTerPoint(nonTer2)][getTerPoint(ter)]=1;
                        symbolPair temp;
                        temp.nonTer=nonTer2;
                        temp.ter=ter;
                        push(temp);
                    }
                }
            }
        }
    }
    destroyStack();
}

void createPreTable(){
    for(int i=0;i<gramOldSetNum;i++){
        for (int j = 0; j <gramOldSet[i].rightNum; ++j) {
            int rightLength=strlen(gramOldSet[i].right[j]);
            if(rightLength>1){
                for(int k=0;k<rightLength-1;k++){
                    char ch1=gramOldSet[i].right[j][k];
                    char ch2=gramOldSet[i].right[j][k+1];
                    if(isTerSymbol(ch1)&&isTerSymbol(ch2)){
                        P[getTerPoint(ch1)][getTerPoint(ch2)]='=';
                    }
                    if(k<=rightLength-3&&isTerSymbol(ch1)&&isTerSymbol(gramOldSet[i].right[j][k+2])&&isNonTerSymbol(ch2)){
                        P[getTerPoint(ch1)][getTerPoint(gramOldSet[i].right[j][k+2])]='=';
                    }
                    if(isTerSymbol(ch1)&&isNonTerSymbol(ch2)){
                        for(int h=0;h<strlen(terSymbol);h++){
                            if(F[getNonTerPoint(ch2)][h]==1){
                                P[getTerPoint(ch1)][getTerPoint(terSymbol[h])]='<';
                            }
                        }
                    }
                    if(isNonTerSymbol(ch1)&&isTerSymbol(ch2)){
                        for(int h=0;h<strlen(terSymbol);h++){
                            if(L[getNonTerPoint(ch1)][h]==1){
                                P[getTerPoint(terSymbol[h])][getTerPoint(ch2)]='>';
                            }
                        }
                    }
                }
            }
        }
    }
}

char compare(char ch1, char ch2){
    if(ch1=='#'&&ch2!='#'&&ch2!=')'){
        return '<';
    } else if(ch1!='#'&&ch1!='('&&ch2=='#'){
        return '>';
    } else if(ch1=='#'&&ch2=='#'){
        return '=';
    } else{
        return P[getTerPoint(ch1)][getTerPoint(ch2)];
    }
}


void analyzeInput(){
    initStack2();
    int line=30;
    toxy(0,line);
    printf("堆栈");
    toxy(15,line);
    printf("优先关系");
    toxy(30,line);
    printf("当前符号");
    toxy(45,line);
    printf("输入串");
    toxy(70,line);
    printf("动作");
    push2('#');
    int index=0;
    int flag=1;
    char inputChar = 0,relative=0;
    char* operate="预备";
    line++;
    toxy(0,line);
    stackTraverse();
    toxy(15,line);
    printf("%c",relative);
    toxy(30,line);
    printf("%c",inputChar);
    toxy(43,line);
    for(int i=index;i<strlen(input);i++){
        printf("%c",input[i]);
    }
    toxy(67,line);
    printf("%s",operate);
    while (flag>0){
        line++;
        toxy(0,line);
        stackTraverse();
        char ch=getTop();
        inputChar=input[index];
        relative=compare(ch,inputChar);
        toxy(15,line);
        printf("%c",relative);
        toxy(30,line);
        printf("%c",inputChar);
        toxy(43,line);
        if(ch=='#'&&inputChar=='#'){
            flag=-1;
            operate="结束";
        } else{
            for(int i=index+1;i<strlen(input);i++){
                printf("%c",input[i]);
            }
            if(relative=='<'||relative=='='){
                push2(inputChar);
                //k++;
                index++;
                flag=1;
                operate="移进";
            } else if(relative=='>'){
                int length=processStack.size;
                for(int i=0;i<length-1;i++){
                    char ch1=*(processStack.top-i-1);
                    char ch2=*(processStack.top-i-2);
                    char temp=compare(ch2,ch1);
                    if(temp=='='){
                        continue;
                    } else if(temp=='<'){
                        flag=1;
                        for(int j=0;j<=i;j++){
                            pop2();
                            operate="规约";
                            flag=1;
                        }
                        break;
                    } else {
                        flag=0;
                    }

                }
            } else{
                flag=0;
            }
        }
        toxy(67,line);
        printf("%s",operate);
    }
    if(flag==0){
        printf("\n输入错误!!!");
    } else if(flag==1){
        printf("\n输入正确");
    }

}

void showInfo(){
    printf("%s\n",non_ter);
    printf("%s\n",terSymbol);
    for(int i=0;i<gramOldSetNum;i++){
        printf("%s\t%c\t%d\t",gramOldSet[i].formula,gramOldSet[i].left,gramOldSet[i].rightNum);
        for(int j=0;j<gramOldSet[i].rightNum;j++){
            printf("%s\t",gramOldSet[i].right[j]);
        }
        printf("\n");
    }
    printf("FirstVT集\n\t");
    for(int i=0;i<strlen(terSymbol);i++){
        printf("%c\t",terSymbol[i]);
    }
    printf("\n");
    for(int i=0;i<gramOldSetNum;i++){
        char ch=gramOldSet[i].left;
        printf("%c\t",ch);
        for(int j=0;j<strlen(terSymbol);j++){
            if(F[getNonTerPoint(ch)][getTerPoint(terSymbol[j])]==1){
                printf("1\t");
            } else{
                printf("\t");
            }
        }
        printf("\n");
    }
    printf("LastVT集\n\t");
    for(int i=0;i<strlen(terSymbol);i++){
        printf("%c\t",terSymbol[i]);
    }
    printf("\n");
    for(int i=0;i<gramOldSetNum;i++){
        char ch=gramOldSet[i].left;
        printf("%c\t",ch);
        for(int j=0;j<strlen(terSymbol);j++){
            if(L[getNonTerPoint(ch)][getTerPoint(terSymbol[j])]==1){
                printf("1\t");
            } else{
                printf("\t");
            }
        }
        printf("\n");
    }
    printf("优先关系表\n\t");
    for (int i = 0; i <strlen(terSymbol) ; i++) {
        printf("%c\t",terSymbol[i]);
    }
    printf("\n");
    for(int i=0;i<strlen(terSymbol);i++){
        printf("%c\t",terSymbol[i]);
        for (int j = 0; j < strlen(terSymbol); ++j) {
            printf("%c\t",P[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int main() {
    init();
    prepare();
    getFirstVT();
    getLastVT();
    createPreTable();
    showInfo();
    analyzeInput();
}

可能有些问题，望大神指教