編譯原理的課程設(shè)計(jì)


假設(shè)文檔的內(nèi)容為
i a 
* nul
i b
+ nul
i c
# nul
是個(gè)單詞二元式,對(duì)他進(jìn)行不帶回溯的自上而下的語法分析.


/*
    用預(yù)測分析法（即LL（1）分析法）構(gòu)造文法G[E]：
    E->E + T / T
    T->T * F / F
    F->(E) / i / x / y
    的預(yù)測分析程式（即語法分析器）。
    by wzt 
    
    date : 2007.1.14
*/
#include stdio.h>
#include string.h>
#define MAXSIZE 200
#define MAX 20
//#define DEBUG
char c[MAX]; /* 要判斷的符號(hào)串 */
char *str[]={"TD","+TD","","FS","*FS","","(E)","i","x","y"}; /* 任何產(chǎn)生式 */
char Symbol_VT[MAX] = "+*()ixy#"; /* 任何終結(jié)符號(hào) */
char Symbol_VN[MAX] = "EDTSF"; /* 任何非終結(jié)符號(hào) */
char stack[MAX] = {'#','E'}; /* 分析棧 */
int top = 1;
char temp[MAX];
FILE *s_fp,*t_fp;
int M[][8] = { /* 存放str的下標(biāo)，-1表示不存在 */
            {-1,-1,0,-1,0,0,0,-1},
            {1,-1,-1,2,-1,-1,-1,2},
            {-1,-1,3,-1,3,3,3,-1},
            {5,4,-1,5,-1,-1,-1,5},
            {-1,-1,6,-1,7,8,9,-1}
             };
void usage(char *pro); /* 程式幫助信息 */
void do_analyses(); /* 分析符號(hào)串 */
int VN_to_lin(char X); /* 判斷非終結(jié)符所在的下標(biāo) */
int VT_to_col(char X); /* 判斷終結(jié)符所在的下標(biāo) */
int is_VN(char X); /* 判斷字符是否是非終結(jié)符 */
int is_VT(char X); /* 判斷字符是否是終結(jié)符 */
void print_symbols(int i); /* 打印余留符號(hào)串 */
void print_stack(); /* 打印分析棧 */
int main(int argc,char **argv)
{
    char temp_str[MAXSIZE];
    char temp_code,temp_val[MAX];
    int j = 0;
    if( argc  3 )
        usage(argv[0]);
    if( (s_fp = fopen(argv[1],"r")) == NULL ){
        printf("Can not open %s.\n",argv[1]);
        exit(1);
    }
    if( (t_fp = fopen(argv[2],"w+")) == NULL ){
        printf("Can not open %s.\n",argv[1]);
        exit(1);
    }
    while( fgets(temp_str,MAXSIZE,s_fp) != NULL ){ /* 從文檔讀取單詞二元式 */
        sscanf(temp_str,"%c %s",&temp_code,temp_val);
        c[j++] = temp_code;
#ifdef DEBUG
        printf("%c %s\n",temp_code,temp_val);
#endif
    }
    c[j] = '\0';
#ifdef DEBUG
    printf("%s\n",c);
#endif
    do_analyses();
    fclose(s_fp);
    fclose(t_fp);
    return 0;
}
void usage(char *pro) /* 程式幫助信息 */
{
    printf("usage : %s  \n",pro);
    exit(0);
}
void do_analyses() /* 分析符號(hào)串 */
{
    char temp_str[MAXSIZE];
    char temp_str1[MAXSIZE];
    char X;
    int i,j = 0,m,n,k;
    printf("Step Stack Symbols Syntax\n");
    for( i = 0 ; i  strlen(c) ; i++ ){
        X = stack[top--]; /*彈出棧頂元素 */
        print_symbols(i);
        stack[top + 2 ] = '\0';
        sprintf(temp_str,"%2d %-8s %-13s",j++,stack,temp);
        printf("%s",temp_str);
        fputs(temp_str,t_fp);
        if( X == '#' ){ /* 符號(hào)串匹配成功 */
            if( X == c ){
                printf("Acc.\n");
            }
            else{
                printf("Symbols Error.\n");
            }
            exit(0);
        }
        if( is_VT(X) ){ /* X是終結(jié)符號(hào)且和要判斷的字符相等，就繼續(xù)循環(huán) */
            printf("\n");
            fputs("\n",t_fp);
            if( X == c )
                continue;
            else{
                printf("Error at %d.\n",i);
            }
        }
        if( is_VN(X) ){ /* X是非終結(jié)符號(hào) */
            m = VN_to_lin(X); /* 求X在M數(shù)組中的縱坐標(biāo) */
            n = VT_to_col(c); /* 求要判斷的字符在M數(shù)組中的橫坐標(biāo) */
            for( k = strlen(str[M[m][n]]) - 1 ; k >= 0 ; k-- )
                stack[++top] = *(str[M[m][n]] + k ); /* 取得產(chǎn)生式并反向壓棧 */
            i --; /* !!! i減1，符號(hào)串要重新開始判斷 */
            sprintf(temp_str1,"%c->%s\n",X,str[M[m][n]]);
            printf("%s",temp_str1);
            fputs(temp_str1,t_fp);
        }
    }
}
int VN_to_lin(char X) /* 求X在M數(shù)組中的縱坐標(biāo) */
{
    int i;
    for( i = 0 ; i  strlen(Symbol_VN) ; i++ ){
        if( X == Symbol_VN )
            return i;
    }
    printf("Error. X is not in Symbol_VN \n");
    exit(0);
}
int VT_to_col(char X) /* 求要判斷的字符在M數(shù)組中的橫坐標(biāo) */
{
    int i;
    for( i = 0 ; i  strlen(Symbol_VT) ; i++ ){
        if( X == Symbol_VT )
            return i;
    }
    printf("Error. %c is not in Symbol_VT \n",X);
    exit(0);
}
int is_VN(char X) /* X是非終結(jié)符號(hào) */
{
    int i;
    for( i = 0 ; i  strlen(Symbol_VN) ; i++ ){
        if( X == Symbol_VN )
            return 1;
    }
    return 0;
}
int is_VT(char X) /* X是終結(jié)符號(hào) */
{
    int i;
    for( i = 0 ; i  strlen(Symbol_VT) ; i++ ){
        if( X == Symbol_VT )
            return 1;
    }
    return 0;
}
void print_symbols(int i) /* 打印余留符號(hào)串 */
{
    int j,k=0;
    for( j = i ; j  strlen(c) ; j++ )
        temp[k++] = c[j];
    temp[k] = '\0';
}
void print_stack() /* 打印分析棧 */
{
    int i;
    printf(" ");
    for( i = 0 ; i = top ; i++ )
        printf("%c",stack);
}