一、实验目的

根据文法求出FirstVT和LastVT，构造算法优先表，根据输入二元组判断正确与否

二、实验内容

2.1任务一：构造FIRSTVT，LASTVT

FIRSTVT计算过程：
(1)若有产生式P->a...或者P->Qa...，则a∈FIRSTVT(P);
(2)若a∈FIRSTVT(Q),且有产生式P->Q...，则a∈FIRSTVT(P);
LASTVT计算过程：
(1)若有产生式P->...a或者P->...aQ，则a∈LASTVT(P);
(2)若a∈LASTVT(Q),且有产生式P->...Q，则a∈LASTVT(P);

2.2任务二：构造算符优先表

(1)对形如 P→…ab…和形如P→…aQb…，有a=b；
(2)对形如 P→…aR…，而b∈FIRSTVT(R)，有a<b；
(3)对形如 P→…Rb…，而a∈LASTVT(R)，有a>b；
(4)对文法开始符号S，有# <FIRSTVT(S)，LASTVT(S) >#，且对 #S#，有# = #。

2.3任务三：根据输入判断结果

(1)读入当前输入符号
(2)若输入符号为数字，则输入符号进OPND，输入指针后移，转第(1)步
(3)若当前输入符号为终结符，则比较当前字符和符号栈栈顶字符的优先级
(4)若输入符号和栈顶的优先级相同，则输入指针后移，符号栈出栈
(5)若输入符号优先级小于栈顶的优先级，则输入符号入符号栈，输入指针后移
(6)若输入符号优先级大于栈顶的优先级，则从数据栈中弹出两个数，符号栈中弹出符号进行计算，结果压入数据栈。继续判断符号栈栈顶和输入符号的优先级
(7)若输入符号为“#”且符号栈只剩一个“#”时，表示判断成功。

三、实验过程

3.1 开发环境

使用Visual Studio 2015开发win32控制台程序

3.2 数据结构设计

3.2.1 使用的宏定义
#define MAXSIZE 10
#define NUM_VT 7
#define NUM_VN 5

3.2.2 定义的结构体
//栈操作
typedef struct Stack
{
    char data[MAXSIZE];
    int top;
};

3.3 测试数据设计

3.3.1 文法文件“nick.txt”
S->E
E->E+T
E->T
T->T*F
T->F
F->P^F
F->P
P->(E)
P->i

3.3.2 输入文件“Input.txt”
(i,1)
(+,)
(i,2)
(*,)
(i,3)
(#,)

四、实验结果

五、源代码

源代码如下：

/*
*功能:算符优先
*作者：王文堃
*创建时间：2016/5/15
*/
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 10
#define NUM_VT 7
#define NUM_VN 5

//栈操作
typedef struct Stack
{
    char data[MAXSIZE];
    int top;
};

char WenFa[MAXSIZE][MAXSIZE]; //存放从文件中读取的文法
int g_num_wenfa = 0; //存放文法的个数，初值为0
char vt[NUM_VT] = {'+','*','^','i','(',')','#'}; //所有终结符
char vn[NUM_VN] = {'E','T','F','P','S'}; //存放所有非终结符
int firstvt[NUM_VN][NUM_VT]; //存放每一个非终结符的firstvt
int lastvt[NUM_VN][NUM_VT]; //存放每一个非终结符的lastvt
int labelofch[MAXSIZE]; //存放已ch打头的所有文法的标号
char OPT[NUM_VT][NUM_VT];  //算符优先表
char Input[MAXSIZE][MAXSIZE]; //保存输入
int g_num_input = 0; //存放输入的个数
int g_step = 0; //存储步骤数
Stack *OPTR; //符号栈
Stack *OPND; //数据栈

/*------------------------------函数声明----------------------------*/
//计算FIRSTVT
bool readfromfile(char* str); //读取文法
int isVt(char ch); //判断文法中字符是否为终结符
int isVn(char ch); //判断文法中字符是否为非终结符
int findit(char ch); //找到以ch开头的文法的下标
int Vn2num(char ch); //将非终结符转换成下标
int Vt2num(char ch); //将终结符转换成下标
void get_firstvt(char ch); //求FIRSTVT(ch)
void do_firstvt(); //计算所有firstvt
void output_firstvt(); //输出firstvt表

//计算LASTVT
int get_last(int num); //找到下标为num的文法的最后一个字符的下标
void get_lastvt(char ch); //求LASTVT(ch)
void do_lastvt(); //计算所有lastvt
void output_lastvt(); //输出lastvt表

//构造算符优先表
void do_less(char vtch1, char vnch2); //处理小于的情况,a<FIRSTVT(R)
void do_more(char vnch1, char vtch2); //处理大于的情况,LASTVT(R)>a
void dosharp(); //处理#号
void OperatorPrecedence(); //构造算法优先表
void output_OPT(); //输出算符优先表

//处理输入判断结果
void init_Stack(Stack **s); //初始化栈
bool empty_Stack(Stack *s); //判断栈空
void Push(Stack *s, char x); //入栈
char Pop(Stack *s); //出栈
char Top(Stack *s); //取栈顶元素
void print_Stack(Stack *s); //输出栈
bool inputformfile(char* str); //从文件中读取输入
int judge(char ch); //判断输入字符的类型
int char2int(char ch); //将int行数字传化成char型
void output_step(int s, char* str); //处理过程输出
bool doinput(); //处理输入


int main()
{
    if (readfromfile("nick.txt"))
    {
        do_firstvt();  //构造firstvt
        output_firstvt(); //输出firstvt
        do_lastvt();  //构造lastvt
        output_lastvt(); //输出lastvt
        OperatorPrecedence(); //构造算符优先表
        output_OPT(); //输出算符优先表

        inputformfile("input.txt");
        bool result = doinput();
        if (result != 0)
        {
            printf("最终结果正确\n");
        }
        else
        {
            printf("最终结果错误\n");
        }

    }
    getchar();
    return 0;
}



/*--------------------计算FIRSTVT---------------------------*/

//读取文法
bool readfromfile(char* str)
{
    FILE* fp = fopen(str, "r");
    if (fp) //succeed
    {
        while (EOF != fscanf(fp, "%s", WenFa[g_num_wenfa]))
        {
            g_num_wenfa++;
        }
        fclose(fp);
        return true;
    }
    else
    {
        printf("error to open the file\n");
        return false;
    }
}

//判断文法中字符是否为终结符
int isVt(char ch)
{
    for (int i = 0; i < NUM_VT; i++)
    {
        if (ch == vt[i])
        {
            return true;
        }
    }
    return false;
}

//判断文法中字符是否为非终结符
int isVn(char ch)
{
    for (int i = 0; i < NUM_VN; i++)
    {
        if (ch == vn[i])
        {
            return true;
        }
    }
    return false;
}

//找到以ch开头的文法的下标
int findit(char ch)
{
    int num = 0;
    for (int i = 0; i < g_num_wenfa; i++)
    {
        if (WenFa[i][0] == ch)
            labelofch[num++] = i;
    }
    return num; //返回以ch开头文法的个数
}

//将非终结符转换成下标
int Vn2num(char ch)
{
    switch (ch)
    {
    case 'E':
        return 0;
        break;
    case 'T':
        return 1;
        break;
    case 'F':
        return 2;
        break;
    case 'P':
        return 3;
        break;
    case 'S':
        return 4;
        break;
    default:
        return -1;
    }
}

//将终结符转换成下标
int Vt2num(char ch)
{
    switch (ch)
    {
    case '+':
        return 0;
        break;
    case '*':
        return 1;
        break;
    case '^':
        return 2;
        break;
    case 'i':
        return 3;
        break;
    case '(':
        return 4;
        break;
    case ')':
        return 5;
        break;
    case '#':
        return 6;
        break;
    default:
        return -1;
    }
}

//求FIRSTVT(ch)
void get_firstvt(char ch)
{
    if (isVn(ch)) //对终非结符ch
    {
        int firstnum = Vn2num(ch); //ch所对应的编号
        int num = findit(ch); //找到以该非终结符开头文法的下标
        for (int i = 0; i < num; i++)
        {
            char rightfirst = WenFa[labelofch[i]][3]; //取出文法推到的第一个字符
            if (isVt(rightfirst)) //该文法推出的第一个字符是终结符
            {
                firstvt[firstnum][Vt2num(rightfirst)] = 1;
            }
            else //该文法推出的第一个字符是非终结符
            {
                char rightsc = WenFa[labelofch[i]][4];
                if (isVt(rightsc)) //判断该非终结符之后的符号是不是终结符
                {
                    firstvt[firstnum][Vt2num(rightsc)] = 1;
                }

                if (ch != rightfirst)
                {
                    get_firstvt(rightfirst); //计算这个非终结符的firstvt集
                    int newvn = Vn2num(rightfirst);
                    for (int j = 0; j < NUM_VT; j++)
                    {
                        if (firstvt[newvn][j] == 1)
                        {
                            firstvt[firstnum][j] = 1;
                        }
                    }
                }
            }
        }


    }
}

//计算所有firstvt
void do_firstvt()
{
    for (int i = 0; i < NUM_VN; i++)
    {
        get_firstvt(vn[i]);
    }

}

//输出firstvt表
void output_firstvt()
{
    int i = 0;
    printf("---------------firstvt----------------\n");
    printf(" ");
    for (i = 0; i < NUM_VT; i++)
    {
        printf("%5c", vt[i]);
    }
    printf("\n");
    for (i = 0; i < NUM_VN; i++)
    {
        printf("%c", vn[i]);
        for (int j = 0; j < NUM_VT; j++)
        {
            printf("%5d", firstvt[i][j]);
        }
        printf("\n");
    }
    printf("--------------------------------------\n");
    printf("\n");
}

/*------------------------计算LASTVT-------------------------*/
//找到下标为num的文法的最后一个字符的下标
int get_last(int num)
{
    for (int i = 0; i < MAXSIZE; i++)
    {
        if (WenFa[num][i] == '\0')
        {
            return (i-1); 
        }
    }
}

//求LASTVT(ch)
void get_lastvt(char ch)
{
    if (isVn(ch)) //对终非结符ch
    {
        int lastnum = Vn2num(ch); //ch所对应的编号
        int num = findit(ch); //找到以该非终结符开头文法的下标
        for (int i = 0; i < num; i++)
        {
            int ilast = get_last(labelofch[i]);
            char rightlast = WenFa[labelofch[i]][ilast]; //获得文法的最后一个字符
            if (isVt(rightlast)) //该文法推出的最后一个字符是终结符
            {
                lastvt[lastnum][Vt2num(rightlast)] = 1;
            }
            else //该文法推出的最后一个字符是非终结符
            {
                char rightlastsc = WenFa[labelofch[i]][ilast -1]; //文法倒数第二个字符
                if (isVt(rightlastsc)) //判断倒数第二个字符是不是终结符
                {
                    lastvt[lastnum][Vt2num(rightlastsc)] = 1;
                }

                if (ch != rightlast)
                {
                    get_lastvt(rightlast); //计算这个非终结符的lastvt集
                    int newvn = Vn2num(rightlast);
                    for (int j = 0; j < NUM_VT; j++)
                    {
                        if (lastvt[newvn][j] == 1)
                        {
                            lastvt[lastnum][j] = 1;
                        }
                    }
                }
            }
        }


    }
}

//计算所有lastvt
void do_lastvt()
{
    for (int i = 0; i < NUM_VN; i++)
    {
        get_lastvt(vn[i]);
    }
}

//输出lastvt表
void output_lastvt()
{
    int i = 0;
    printf("----------------lastvt----------------\n");
    printf(" ");
    for (i = 0; i < NUM_VT; i++)
    {
        printf("%5c", vt[i]);
    }
    printf("\n");
    for (i = 0; i < NUM_VN; i++)
    {
        printf("%c", vn[i]);
        for (int j = 0; j < NUM_VT; j++)
        {
            printf("%5d", lastvt[i][j]);
        }
        printf("\n");
    }
    printf("--------------------------------------\n");
    printf("\n");
}


/*---------------------------构造算符优先表------------------*/
//处理小于的情况,a<FIRSTVT(R)
void do_less(char vtch1, char vnch2)
{
    int x = Vt2num(vtch1); //a
    int i = Vn2num(vnch2); //firstvt表中的行
    for (int j = 0; j < NUM_VT; j++) //遍历firstvt表
    {
        if (firstvt[i][j] == 1)
            OPT[x][j] = '<';
    }
}

//处理大于的情况,LASTVT(R)>a
void do_more(char vnch1, char vtch2)
{
    int y = Vt2num(vtch2);
    int i = Vn2num(vnch1);
    for (int j = 0; j < NUM_VT; j++) //遍历LASTVT表
    {
        if (lastvt[i][j] == 1)
        {
            OPT[j][y] = '>';
        }
    }
}

//处理#号
void dosharp()
{
    //添加“#=#”
    int temp = Vt2num('#');
    OPT[temp][temp] = '=';
    //添加'#'<FIRSTVT(S)、LASTVT(S)>'#'
    for (int i = 0; i < NUM_VT; i++)
    {
        int x = Vn2num('S');
        int j = Vt2num('#');
        if (firstvt[x][i] == 1)
        {
            OPT[j][i] = '<';
        }
        if (lastvt[x][i] == 1)
        {
            OPT[i][j] = '>';
        }
    }
}

//构造算法优先表
void OperatorPrecedence()
{
    int i = 0; //循环变量
    for (i = 0; i < g_num_wenfa; i++) //对所有的文法
    {
        int j = 3; //内部循环变量，从推出来的第一个字符开始

        while (WenFa[i][j] != '\0') //该文法没有完
        {
            char ch = WenFa[i][j];
            if (isVt(ch)) //判断当前字符是不是终结符
            {
                //判断下一个字符是不是终结符
                if (isVt(WenFa[i][j + 1]))
                {
                    //若是，则这两个终结符的优先级相等
                    OPT[Vt2num(ch)][Vt2num(WenFa[i][j + 1])] = '=';
                }
                else
                {
                    //做小于
                    do_less(ch, WenFa[i][j + 1]);

                    //继续判断下一个字符是不是终结符
                    if (isVt(WenFa[i][j + 2]))
                    {
                        //若是，则这两个终结符的优先级依然相等
                        OPT[Vt2num(ch)][Vt2num(WenFa[i][j + 2])] = '=';
                    }
                }
            }
            else //当前是非终结符
            {
                if (isVt(WenFa[i][j + 1])) //判断下一个字符
                {
                    //大于
                    do_more(ch, WenFa[i][j + 1]);
                }
            }
            j++;
        }
    }
    dosharp(); //处理#
}

//输出算符优先表
void output_OPT()
{
    int i = 0;
    printf("------------------OPT-----------------\n");
    printf(" ");
    for (i = 0; i < NUM_VT; i++)
    {
        printf("%5c", vt[i]);
    }
    printf("\n");
    for (i = 0; i < NUM_VT; i++)
    {
        printf("%c", vt[i]);
        for (int j = 0; j < NUM_VT; j++)
        {
            printf("%5c", OPT[i][j]);
        }
        printf("\n");
    }
    printf("--------------------------------------\n");
    printf("\n");
}

/*---------------------------处理输入判断结果------------------------------*/
//初始化栈
void init_Stack(Stack **s)
{
    *s = (Stack*)malloc(sizeof(Stack));
    (*s)->top = -1;
}

//判断栈空
bool empty_Stack(Stack *s)
{
    if (s->top == -1)
    {
        return true;
    }
    else
    {
        return false;
    }   
}

//入栈
void Push(Stack *s, char x)
{
    if (s->top == MAXSIZE - 1)
    {
        printf("栈已经满了,无法完成入栈操作\n");
    }
    else
    {
        s->top++;
        s->data[s->top] = x;
    }
}

//出栈
char Pop(Stack *s)
{
    char temp;
    if (s->top == -1)
    {
        printf("栈已经空了,无法完成出栈操作");
        return NULL;
    }
    else
    {
        temp = s->data[s->top];
        s->top--;
        return temp;
    }
}

//取栈顶元素
char Top(Stack *s)
{
    return s->data[s->top];
}

//输出栈
void print_Stack(Stack *s)
{
    for (int i = 0; i <= s->top; i++)
    {
        printf("%c ", s->data[i]);
    }
}

//从文件中读取输入
bool inputformfile(char* str)
{
    FILE* fp = fopen(str, "r");
    if (fp) //succeed
    {
        while (EOF != fscanf(fp, "%s", Input[g_num_input]))
        {
            g_num_input++;
        }
        fclose(fp);
        return true;
    }
    else
    {
        printf("error to open the file\n");
        return false;
    }
}

//判断输入字符的类型
int judge(char ch)
{
    switch (ch)
    {
    case 'i':
        return 0; //表示数字
        break;
    case '+':
        return 1; //表示'+'号
        break;
    case '*':
        return 2; //表示'*'号
        break;
    default:
        return -1;
    }
}

//将int行数字传化成char型
int char2int(char ch)
{
    if (ch >= 48 && ch <= 57) //数字
    {
        return ch - 48;
    }
}

//处理过程输出
void output_step(int s, char* str)
{
    //步骤    当前输入字符  符号栈 数据栈 处理
    printf("%d\t  ", g_step++);
    for (int i = s; i < g_num_input - 1; i++)
    {
        if (Input[i][1] == 'i')
        {
            printf("%c", Input[i][3]);
        }
        else
        {
            printf("%c", Input[i][1]);
        }   
    }
    printf("\t\t\t");
    print_Stack(OPTR);
    printf("\t\t");
    print_Stack(OPND);
    printf("\t\t");
    printf("%s", str);
    printf("\n-----------------------------------------------------------------------------\n");
}

//处理输入
bool doinput()
{
    init_Stack(&OPND);
    init_Stack(&OPTR);
    int iInput = 0; //指向输入下标
    printf("\n------------------------------处理过程如下-----------------------------------\n");
    printf("步骤\t  当前输入字符\t      符号栈\t      数据栈\t\t  操作\n");
    printf("-----------------------------------------------------------------------------\n");
    //#入符号栈
    Push(OPTR, '#');
    output_step(iInput, "无操作"); //输出
    while (iInput != (g_num_input-1)  || !empty_Stack(OPTR)) //将输入遍历完
    {
        char* str = Input[iInput]; //取出第一个输入
        int result = judge(str[1]);
        if (result == 0) //数字
        {
            Push(OPND, str[3]);
            output_step(iInput, "数字入栈"); //输出
        }
        else //是符号
        {
            //判断符号栈顶的符号和当前符号的优先级
            int topofstack = Vt2num(Top(OPTR));
            int topofinput = Vt2num(str[1]);
            if (OPT[topofstack][topofinput] == '<') //栈顶小于输入就入栈
            {
                Push(OPTR, str[1]);
                output_step(iInput, "符号入栈"); //输出
            }
            else if (OPT[topofstack][topofinput] == '>')//否则运算
            {
                int i = char2int(Top(OPND));
                Pop(OPND);
                int j = char2int(Top(OPND));
                Pop(OPND);

                int vtnum = Vt2num(Top(OPTR));
                if (vtnum == 0) //+
                {
                    Push(OPND, i + j + 0x30);
                    Pop(OPTR);
                }
                else if (vtnum == 1) //*
                {
                    Push(OPND, i * j + 0x30);
                    Pop(OPTR);
                }
                output_step(iInput, "运算"); //输出
            }
            else //如果相等就出栈
            {
                Pop(OPTR);
            }
        }
        if (iInput != (g_num_input-1))
        {
            iInput++;
        }
    }

    //判断
    if (empty_Stack(OPTR))
    {
        return true;
    }
    else
    {
        return false;
    }
}