一、 实验目的：

通过设计编制调试构造FIRSTVT集、LASTVT集和构造算符优先表，了解构造算符优先分析表的步骤，对文法的要求，生成算符优先关系表的算法。

二、实验内容：

1.编写算符优先分析表的构造程序，求出给定的算符优先文法中的非终结符的FirstVT集合和LastVT集合。
2.构造算符优先表。

三、实验设备及软件环境：

PC机，主机操作系统为windows10家庭版；
Visual Studio 2019等软件

四、实验过程及结果：

在存放文法的文件in.txt内输入待判断文法产生式（文件已输入教材116页文法），格式E->a|S,注意左部和右部之间是“->”，每个产生式一行，ENTER键换行。文法结束再输入一行G->#E#。
1.先做文法判断，即可判断文法情况。
2.若是算符优先文法，则在优先表栏显示优先表。
实验样例：图中给出了终结符号表，非终结符号表，计算FirstVT和LastVT集合，并给出
了算符优先关系矩阵。

代码和实验结果分析：
test1.h代码如下：

#pragma once
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;

char str1[50][50]; //存放优先表

struct csc { //用结构体数组来存放产生式
char Left; //存放产生式的左部
char Right[100]; //存放产生式的右部
}G[100];

struct db {
char VN; //用于存放 FIRSTVT(P) 和 LASTVT(P) 的非终结符
char VtoT[100]; //用于存放 FIRSTVT(P) 和 LASTVT(P) 的终结符
}firstvt[100], lastvt[100];
class suanfu//算符类
{
public:
int filename();//从文件夹读取
int Terminator(char ch); // 判断是否是非终结符，大写字母为非终结符，其他为终结符
void Issfwf(csc G[], int length); //判断文法是否为算符文法
void Clean(db VNT[], int length1); //去掉集合中重复部分
void FIRSTVT(csc G[], db firstvt[], int length); //求各非终结符的 FIRSTVT 集合
void LASTVT(csc G[], db lastvt[], int length); //求各非终结符的 FIRSTVT 集合
void StructureTable(csc G[], db firstvt[], db lastvt[], int length); //返回非终结符个数
char GetRalation(char a, char b); //找到 a，b 对应的关系
void Judge(char* str, csc G[]);//简单的语法分析器
};

test1.cpp代码如下

#include"test1.h"

suanfu su;
int suanfu::filename()
{
    char str3[100]; // 存放一个产生式子
    char str2[100] = { 'i','+','i','*','i','#' }; // 存放待检测的字符串
    //char filename[10] = { 'i','n','.','t','x','t' };// 文件名
    char filename[10] = { 'a','.','t','x','t' };// 文件名
    int length = 0; // 记录产生式个数
    int s = 0;
    cout << "请输入要打开的文件名： ";
    //cin >> filename;
    cout << endl;
    memset(str1, 0, sizeof(str1)); //置空字符串
    ifstream fin1(filename);
    if (!fin1)
    {
        cout << "未找到对应文件名的文件\n";
        exit(1);
    }
    while (fin1)
    {
        fin1.getline(str3, 100); //读出一个产生式
        cout << str3 << endl; G[length].Left = str3[0]; //产生式的左部
        strcpy_s(G[length].Right, str3 + 3);
        length++;
    }

    length -= 1;
    return length;
}
int suanfu::Terminator(char ch) // 判断是否是非终结符，大写字母为非终结符，其他为终结符
{
  
    if (ch >= 'A'&&ch <= 'Z')
        return 1;
    else
        return 0;
}

void suanfu::Issfwf(csc G[], int length) //判断文法是否为算符文法
{
    int flag = 0;
    for (int i = 0; i<length; i++)
    {
        for (unsigned j = 0; j < strlen(G[i].Right) - 1; j++)
        if (su.Terminator(G[i].Right[j]) == 1 && su.Terminator(G[i].Right[j + 1]) == 1)
        {
            flag = 1;
            break;
        }
    }
    if (flag == 1)
    {
        cout << " 该文法不是算符文法 !" << endl;
        return;
    }
    else
    {
        cout << " 该文法是算符文法 !" << endl;
    }
}
void suanfu::Clean(db VNT[], int length1) //去掉集合中重复部分
{
    char str1[20];
    char str2[20][100];
    int i, k, t;
    int length;
    int flag;
    for (i = 0; i<length1; i++)
    {
        str1[i] = VNT[i].VN;
        strcpy_s(str2[i], VNT[i].VtoT);
    }
    for (i = 0; i<length1; i++)
        memset(VNT[i].VtoT, 0, sizeof(VNT[i].VtoT));
    for (i = 0; i<length1; i++)
    {
        t = 0;
        length = strlen(str2[i]);
        for (int j = 0; j < length; j++)
        {
            flag = 1;
            for (k = 0; k < t; k++)
            {
                if (VNT[i].VtoT[k] == str2[i][j])
                {
                    flag = 0;
                }
            }
            if (flag == 1)
            {
                VNT[i].VtoT[t++] = str2[i][j];
            }
        }
        length = strlen(VNT[i].VtoT);
    }
}
void suanfu::FIRSTVT(csc G[], db firstvt[], int length) //求各非终结符的 FIRSTVT 集合
{
    int flag = 0, length1 = 0;
    int i, j, k;
    for (i = 0; i < 100; i++)
    {
        memset(firstvt[i].VtoT, 0, sizeof(firstvt[i].VtoT));
    }
    while (flag < length)
    {
        j = 0;
        firstvt[length1].VN = G[flag].Left;
        while (firstvt[length1].VN == G[flag].Left)
        {
            if (Terminator(G[flag].Right[0]) == 0) //P->a...则将 a加入 firstvt(P) 中
            {
                firstvt[length1].VtoT[j++] = G[flag].Right[0];
            }
            else if (Terminator(G[flag].Right[0]) == 1 && Terminator(G[flag].Right[1]) == 0) //P->Qa...则将 a加入 firstvt(P) 中
            {
                firstvt[length1].VtoT[j++] = G[flag].Right[1];
            }
            flag++;
        }
        length1++;
    }
    for (i = length - 1; i >= 0; i--) //P->Q...，则将 Q 中的终结符加入 P 中
    {
        if (Terminator(G[i].Right[0]) == 1 && G[i].Left != G[i].Right[0])
        {
            for (j = 0; j < length1; j++)
            {
                if (firstvt[j].VN == G[i].Right[0])
                {
                    break;
                }
            }
            for (k = 0; k < length1; k++)
            {
                if (firstvt[k].VN == G[i].Left)
                {
                    break;
                }
            }
            strcat_s(firstvt[k].VtoT, firstvt[j].VtoT);
        }
    }
    Clean(firstvt, length1);
    for (i = 0; i<length1; i++) //集合输出
    {
        cout << "FIRSTVT(";
        cout << firstvt[i].VN << ")" << "=" << "{";
        cout << firstvt[i].VtoT[0];
        for (unsigned j = 1; j < strlen(firstvt[i].VtoT); j++)
        {
            cout << "," << firstvt[i].VtoT[j];
        }
        cout << "}" << endl;
    }
}
void suanfu::LASTVT(csc G[], db lastvt[], int length) //求各非终结符的 FIRSTVT 集合
{
    int flag = 0, length1 = 0;
    int i, j, k, t;
    for (i = 0; i < 100; i++)
    {
        memset(lastvt[i].VtoT, 0, sizeof(lastvt[i].VtoT));
    }
    while (flag<length)
    {
        j = 0;
        lastvt[length1].VN = G[flag].Left;
        while (lastvt[length1].VN == G[flag].Left)
        {
            t = strlen(G[flag].Right) - 1; 
            if (Terminator(G[flag].Right[t]) == 0) //P->...a 则将 a加入 lastvt(P)中
            {
                lastvt[length1].VtoT[j++] = G[flag].Right[t];
            }
            else if (Terminator(G[flag].Right[t]) == 1 && Terminator(G[flag].Right[t - 1]) == 0) //P->...aQ 则将 a 加入 lastvt(P)中
            {
                lastvt[length1].VtoT[j++] = G[flag].Right[t - 1];
            }
            flag++;
        }
        length1++;
    }
    for (i = length - 1; i >= 0; i--) //P->...Q，则将 Q 中的终结符加入 P 中
    {
        t = strlen(G[flag].Right) - 1;
        if (Terminator(G[i].Right[t]) == 1 && G[i].Left != G[i].Right[t])
        {
            for (j = 0; j < length1; j++)
            {
                if (lastvt[j].VN == G[i].Right[t])
                {
                    break;
                }
            }
            for (k = 0; k < length1; k++)
            {
                if (lastvt[k].VN == G[i].Left)
                {
                    break;
                }
            }
            strcat_s(lastvt[k].VtoT, lastvt[j].VtoT);
        }
    }
    Clean(lastvt, length1);
    for (i = 0; i<length1; i++) //集合输出
    {
        cout << "LASTVT(";
        cout << lastvt[i].VN << ")" << "=" << "{";
        cout << lastvt[i].VtoT[0];
        for (unsigned j = 1; j < strlen(lastvt[i].VtoT); j++)
        {
            cout << "," << lastvt[i].VtoT[j];
        }
        cout << "}" << endl;
    }
}
void suanfu::StructureTable(csc G[], db firstvt[], db lastvt[], int length) //返回非终结符个数
{
    char str[50]; //存放终结符
    int i,j,k,flag,i1,length1;
    int t = 0;
    for (i = 0; i < 50; i++)
    {
        memset(str1[i], 0, sizeof(str1[i]));
    }
    memset(str, 0, sizeof(str));
    for (i = 0; i<length; i++) //求所有非终结符
    {
        j = strlen(G[i].Right);
        flag = 1;
        for (k = 0; k < j; k++)
        {
            if (Terminator(G[i].Right[k]) == 0)
            {
                for (i1 = 0; i1 < t; i1++)
                {
                    if (G[i].Right[k] == str[i1])
                    {
                        flag = 0;
                    }
                }
                if (flag == 1)
                {
                    str[t++] = G[i].Right[k];
                }
            }
        }
    } 
    for (i = 0; i < strlen(str); i++) // 将 #置于最后一个
    {
        if (str[i] == '#')
        {
            break;
        }
        swap(str[i], str[strlen(str) - 1]);
    }
    for (unsigned i = 1; i <= strlen(str); i++)
    {
        str1[0][i] = str[i - 1];
        str1[i][0] = str[i - 1];
    }
    for (i = 0; i<length; i++)
    {
        length1 = strlen(G[i].Right);
        for (j = 0; j<length1 - 1; j++)
        {
            if (Terminator(G[i].Right[j]) == 0 && Terminator(G[i].Right[j + 1]) == 0)
            {
                for (unsigned i1 = 0; i1 <= strlen(str); i1++)
                {
                    for (unsigned i2 = 0; i2 <= strlen(str); i2++)
                    {
                        if (str1[0][i1] == G[i].Right[j] && str1[i2][0] == G[i].Right[j + 1])
                        {
                            if (str1[i1][i2] != 0)
                            {
                                cout << "该文法不是算符优先文法！ " << endl;
                                return;
                            }
                            else
                            {
                                str1[i1][i2] = '=';
                            }
                        }
                    }
                }
            }
            if (j<length1 - 2 && Terminator(G[i].Right[j]) == 0 && Terminator(G[i].Right[j + 2]) == 0 && Terminator(G[i].Right[j + 1]) == 1)
            {
                for (unsigned i1 = 0; i1 <= strlen(str); i1++)
                {
                    for (unsigned i2 = 0; i2 <= strlen(str); i2++)
                    {
                        if (str1[0][i1] == G[i].Right[j] && str1[i2][0] == G[i].Right[j + 2])
                        {
                            if (str1[i1][i2] != 0)
                            {
                                cout << "该文法不是算符优先文法！ " << endl;
                                return;
                            }
                            else
                            {
                                str1[i1][i2] = '=';
                            }
                        }
                    }
                }
            }
            if (Terminator(G[i].Right[j]) == 0 && Terminator(G[i].Right[j + 1]) == 1)
            {
                for (i1 = 0; str1[0][i1] != G[i].Right[j]; i1++);
                {
                    for (k = 0; firstvt[k].VN != G[i].Right[j + 1]; k++);
                    {
                        for (unsigned i2 = 0; i2 <= strlen(str); i2++)
                        {
                            for (unsigned t = 0; t < strlen(firstvt[k].VtoT); t++)
                            {
                                if (str1[i2][0] == firstvt[k].VtoT[t])
                                {
                                    if (str1[i1][i2] != 0)
                                    {
                                        cout << "该文法不是算符优先文法！ " << endl;
                                        return;
                                    }
                                    else
                                    {
                                        str1[i1][i2] = '<';
                                    }
                                }
                            }
                        }
                    }
                }
            }
            if (Terminator(G[i].Right[j]) == 1 && Terminator(G[i].Right[j + 1]) == 0)
            {
                for (t = 0; lastvt[t].VN != G[i].Right[j]; t++);
                {
                    for (unsigned k = 0; k < strlen(lastvt[t].VtoT); k++)
                    {
                        for (unsigned i1 = 0; i1 <= strlen(str); i1++)
                        {
                            for (unsigned i2 = 0; i2 <= strlen(str); i2++)
                            {
                                if (str1[0][i1] == lastvt[t].VtoT[k] && str1[i2][0] == G[i].Right[j + 1])
                                {
                                    if (str1[i1][i2] != 0)
                                    {
                                        cout << " 该文法不是算符优先文法！ " << endl;
                                        return;
                                    }
                                    else
                                    {
                                        str1[i1][i2] = '>';
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    for (unsigned i = 0; i <= strlen(str); i++)
    {
        cout << "---------------------------------";
        cout << endl;
        cout << "|";
        for (unsigned j = 0; j <= strlen(str); j++)
        {
            cout <<" "<< str1[i][j] << " " << "|";
        }
        cout << endl;
    }
        cout << "---------------------------------";
        cout << endl;
}
char suanfu::GetRalation(char a, char b) //找到 a，b 对应的关系
{
    int i, j;
    for (i = 0; str1[0][i] != a; i++);
    {
        for (j = 0; str1[j][0] != b; j++);
        {
            return str1[i][j]; 
        }
    }
}
void suanfu::Judge(char *str, csc G[])
{
    char Q;
    char a;
    char S[100]; 
    int flag = 0;
    int i = 0;
    int j, k;
    int s = 0, step = 1;
    cout.width(5); // 输出表头
    cout.setf(ios::left); cout << "步骤 ";
    cout.width(10);
    cout.setf(ios::left); cout << "符号栈 ";
    cout.width(5);
    cout.setf(ios::left); cout << "关系 ";
    cout.width(10);
    cout.setf(ios::left); cout << "输入串 ";
    cout.width(10);
    cout.setf(ios::left); cout << "动作 " << endl << endl;
    memset(S, 0, sizeof(S));
    a = str[0];
    k = 1;
    S[k] = '#';
    while (a != '#')
    {
        a = str[flag++];
        if (Terminator(S[k]) == 0)
        {
            j = k;
        }
        else
        {
            j = k - 1;
        }
        while (GetRalation(S[j], a) == '>')
        {
            Q = S[j];
            while (GetRalation(S[j], Q) != '<')
            {
                Q = S[j];
                if (Terminator(S[j - 1]) == 0)
                {
                    j = j - 1;
                }
                else
                {
                    j = j - 2;
                }
            }
            cout.width(5);
            cout.setf(ios::left);
            cout << step++;
            cout.width(10);
            cout << S + 1;
            cout.width(5);
            cout << GetRalation(S[j], a);
            cout.width(10);
            cout.setf(ios::left);
            cout << str + flag - 1;
            cout.width(10);
            cout.setf(ios::left); cout << "规约 " << endl;
            for (i = j + 2; i <= k; i++)
            {
                S[i] = 0;
            }
            k = j + 1;
            S[k] = 'N';
        }
        if (GetRalation(S[j], a) == '<' || GetRalation(S[j], a) == '=')
        {
            cout.width(5);
            cout.setf(ios::left);
            cout << step++;
            cout.width(10);
            cout << S + 1;
            cout.width(5);
            cout << GetRalation(S[j], a);
            cout.width(10);
            cout << str + flag - 1;
            if (a != '#')
            {
                cout.width(10);
                cout.setf(ios::left); cout << "移进 " << endl;
            }
            k = k + 1;
            S[k] = a;
        }
        else
        {
            cout << " 抱歉，输入的句子有误 " << endl; return;
        }
    } 
    cout << "接受 " << endl;
    cout << "恭喜你！分析成功！ " << endl;
}
int main()
{
    char str2[100] = { 'i','+','i','*','i','#' }; // 存放待检测的字符串
    int length = su.filename(); // 记录产生式个数
    su.Issfwf(G, length);
    cout << endl << "非终结符的 FIRSTVT 集合： " << endl;
    su.FIRSTVT(G, firstvt, length);
    cout << endl << "非终结符的 LASTVT 集合： " << endl;
    su.LASTVT(G, lastvt, length);
    cout << endl << "构造分析表如下： " << endl;
    su.StructureTable(G, firstvt, lastvt, length);
    cout << endl << "请输入分析的句子 (以#号键结束 )：" << endl;
    //cin >> str2;
    cout << str2 << endl;
    su.Judge(str2, G);
    return 0;
}

运行结果如下图所示：

实验成绩： 指导教师： 年 月 日