一.题目要求

1. 根据简单表达式文法构造算符优先分析表
2. 根据构造出的算符优先分析表进行表达式计算

二.设计思想

模块一：解析产生式

1. 功能
   把产生式：S->aB解析成VN：S、B，VT：a。
2. 输入约定
   这实际上是词法分析的范畴，这里为了简便，默认产生式是比较简单并且按照规范来书写，大写字母代表VN、小写字母代表VT，并且是单个字符。
3. 实现思路
   把产生式以->推导符号为边界分为左右两部分，左边一定是VN，右边大写字母是VN，小写字母是VT，为了避免重复记录，可以用一个map来记录是否出现过，map里key是VN或VT，值是它们在数组里的下标。既能起到记录的作用，又能便于之后使用时快速查找。
4. 实验结果
   

模块二：构建FIRSTVT（）和LASTVT（）

1. 功能：
   根据FIRSTVT（）和LASTVT（）定义，通过深度优先搜索来遍历这两个集合。

2. 构造思想：

• FIRSTVT（）定义：
  

简单来说，FIRST集是推导出的第一个VT，它是找推出的第一个VT或第一个VN及接着VN后的VT。

• LASTVT（）定义：
  

简单来说，找最后一个VT或最后一个VN和倒数第二个VT。

3. 函数说明

函数接口	函数功能
void GetFirstvt()	计算并打印FIRSTVT集
void SearchFirstvt(int x)	搜索指定VN的FIRSTVT集
void GetLastvt()	计算并打印LASTVT集
void SearchLastvt(int x)	搜索指定VN的LASTVT集

4. 运行结果
   

模块三：构建算术优先符号表

1. 功能：
   根据求出的FIRSTVT（）和LASTVT（）集构建算术优先符号表，
2. 构造思想：

考虑下面四种情况：

• A->…ab… 则a==b
• A->…aB… 则a<FIRSTVT(B)
• A->…Ba… 则a>FIRSTVT(B)
• A->…aBb 则a==b （最后三个）

对于每条产生式判断这四种情况即可构造算术优先符号表。

3. 流程图
   

模块四：表达式语法分析

1. 功能
   根据求出的算符优先分析表进行语法分析
2. 输入约定
   只含+ - * / ( )这五种运算符，若是其他则会报错。
3. 函数接口

函数接口	函数功能
void Calculate(char t1,char t2)	计算表达式值
int GetNum(int d1,int d2,char op)	四则运算

4. 流程图
   
5. 实现方法：

遍历表达式

考虑下面五种情况：

• 当前字符是数字，则直到当前字符不是数字时才退出，并压入数据栈
• 当前字符是VT且符号栈空，压入符号栈
• 当前字符是VT且符号栈非空，通过算符优先分析表判断当前字符和符号栈顶元素的优先级，若是当前优先级大则压入栈，若相等则弹出栈顶，若小于则用当前栈顶符号来计算，小于完后要continue，其他情况都是++i。
• 表达式遍历完且符号栈非空，依次弹出栈顶符号来计算。
• 表达式遍历完且符号栈空，数据栈栈顶元素是表达式计算结果值。

模块五：运算符识别计算

1. 功能
   根据符号栈和数据栈来计算表达式的值
2. 构造思路：

数据栈：

如果表达式合法，每次运算数据栈都能弹出两个数字，并在符号栈空计算完时，数据栈存在一个数字，即表达式的结果。因此每次运算弹出两个数字，并把结果压入栈里。

符号栈：

考虑两种情况：

• + - * /四则运算，数据栈弹出两个数字，计算完结果压入即可
• 其他则报错

三.程序介绍

1. 全部函数介绍

函数接口	函数功能
int main()	输入样例，计算VN、VT集合，调用GetFirstvt() 、GetLastvt() 、GetPriorityTabel() 、Analyze()
void GetFirstvt()	计算并打印FIRSTVT集，调用SearchFirstvt（）
void SearchFirstvt(int x)	搜索指定VN的FIRSTVT集
void GetLastvt()	计算并打印LASTVT集，调用SearchLastvt（）
void SearchLastvt(int x)	搜索指定VN的LASTVT集
void GetPriorityTabel()	计算并打印算术优先符号表
void Analyze()	分析表达式，调用Calculate（）计算
void Calculate(char t1,char t2)	计算表达式值，调用GetName（）得到结果
int GetNum(int d1,int d2,char op)	四则运算
void PrintLine(string t = “-----”)	打印一行—来分割

2. 程序整体执行流程图

2. 函数调用关系图

3. 程序整体执行结果

四.源代码

测试用例：

9
E->E
E->E+T
E->T
T->T*F
T->F
F->P/F
F->P
P->(E)
P->i
3+(2+8)/2+2*6

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cctype>
const int maxn = 507;
using namespace std;

class VN{
public:
    //VN，产生式左部
    char left;
    //产生式右部
    vector<string> right;
    VN(const char c){
        left = c;
    }
    void insert(string s){
        right.push_back(s);
    }


    void print()
    {
        cout << left << "->" << right[0];
        for (int i = 1; i < right.size(); i++) {
            cout << "|" << right[i];
        }
        cout << endl;
    }
};

char priority_tabel[maxn][maxn];
vector<char> vt_set;
vector<VN> vn_set;
map<char, int>vt_pos;
map<char, int> vn_pos;
set<char> firstvt[maxn];
set<char> lastvt[maxn];
int vis[maxn];
string ex;

stack <char> sa_op;
stack <int> sa_int;


void PrintLine(string t = "-----") {
    cout << "------------" << t << "------------" << endl;
}


void SearchFirstvt(int x){
    //VN访问过去掉
    if (vis[x]) return;
    vis[x] = 1;
    //left为产生式左部
    char left = vn_set[x].left;
    //遍历产生式右部
    for (int i = 0; i < vn_set[x].right.size(); ++i)
    {
        //str为第一个生成式
        string str = vn_set[x].right[i];
        //第一个为VN
        if (isupper(str[0])){
            //y为VN2位置
            int t = vn_pos[str[0]];
            //如果生成式第二个是VT
            if (str.length() > 1 && !isupper(str[1]))
                firstvt[x].insert(str[1]);
            //搜索VN2
            SearchFirstvt(t);
            //把VN2的first加入此时VN
            for (set<char>::iterator it = firstvt[t].begin(); it != firstvt[t].end(); it++) {
                firstvt[x].insert(*it);
            }        
        }
        else {
            firstvt[x].insert(str[0]);
        }
            
    }
}


void GetFirstvt(){
    //初始化vis
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < vn_set.size(); ++i) {
        //vis[i]=1代表计算过
        if (!vis[i]) {
            SearchFirstvt(i);
        }
    }
    PrintLine("FIRSTVT集");
    for (int i = 0; i < vn_set.size(); ++i){
        cout << vn_set[i].left << ": ";
        for (set<char>::iterator it = firstvt[i].begin(); it != firstvt[i].end(); ++it) {
            cout << *it<<" ";
        }
        cout << endl;
    }
}


void SearchLastvt(int x){
    if (vis[x]) return;
    vis[x] = 1;
    for (int i = 0; i < vn_set[x].right.size(); ++i){
        string str = vn_set[x].right[i];
        //n为最后一个
        int n = str.size() - 1;
        if (isupper(str[n])){
            int t = vn_pos[str[n]];
            if (str.length() > 1 && !isupper(str[n - 1]))
                lastvt[x].insert(str[1]);
            SearchLastvt(t);
            for (set<char>::iterator it = lastvt[t].begin(); it != lastvt[t].end(); ++it)
                lastvt[x].insert(*it);
        }
        else {
            lastvt[x].insert(str[n]);
        }
            
    }
}


void GetLastvt()
{
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < vn_set.size(); i++) {
        if (!vis[i]) {
            SearchLastvt(i);
        }
    }

    PrintLine("LASTVT集");

    for (int i = 0; i < vn_set.size(); ++i){
        cout << vn_set[i].left<<": ";
        for (set<char>::iterator it = lastvt[i].begin(); it != lastvt[i].end(); ++it) {
            cout << *it << " ";
        }
        cout << endl;
    }

}


void GetPriorityTabel(){
    for (int i = 0; i < vn_set.size(); i++)
        for (int j = 0; j < vn_set[i].right.size(); j++)
        {
            //i是VN，j是生成式位置，str是生成式
            string str = vn_set[i].right[j];
            //遍历生成式
            for (int k = 0; k < str.length() - 1; k++)
            {
                //A->...ab...  则a==b
                if (!isupper(str[k]) && !isupper(str[k + 1]))
                    priority_tabel[vt_pos[str[k]]][vt_pos[str[k + 1]]] = '=';
                //A->...aB...   则a<FIRSTVT(B)
                if (!isupper(str[k]) && isupper(str[k + 1]))
                {
                    int x = vn_pos[str[k+1]];                  
                    for (set<char>::iterator it = firstvt[x].begin(); it != firstvt[x].end(); it++)
                        priority_tabel[vt_pos[str[k]]][vt_pos[*it]] = '<';
                }
                //A->...Ba...   则a>FIRSTVT(B)
                if (isupper(str[k]) && !isupper(str[k + 1]))
                {
                    int x = vn_pos[str[k]];         
                    for (set<char>::iterator it = lastvt[x].begin(); it != lastvt[x].end(); it++) {
                        priority_tabel[vt_pos[*it]][vt_pos[str[k + 1]]] = '>';
                    }
            
                        
                }
                //A->...aBb  则a==b
                if (k+2<=str.size()-1 && !isupper(str[k]) && !isupper(str[k + 2]) && isupper(str[k + 1])) {
              //      cout << i << " " << j << " " << k << " " << str[k] << " " << str[k + 2] << endl;
                    priority_tabel[vt_pos[str[k]]][vt_pos[str[k + 2]]] = '=';
                }
                 
                    
            }
        }




    for (int i = 0; i < vt_pos.size() * 5; i++)
        printf("-");
    printf("算符优先关系表");
    for (int i = 0; i < vt_set.size() * 5; i++)
        printf("-");
    puts("");
    printf("|%8s|", "");
    for (int i = 0; i < vt_set.size(); i++)
        printf("%5c%5s", vt_set[i], "|");
    puts("");
    for (int i = 0; i < (vt_set.size() + 1) * 10; i++)
        printf("-");
    puts("");
    for (int i = 0; i < vt_set.size(); i++)
    {
        printf("|%4c%5s", vt_set[i], "|");
        for (int j = 0; j < vt_set.size(); j++)
            printf("%5c%5s", priority_tabel[vt_pos[vt_set[i]]][vt_pos[vt_set[j]]], "|");
        puts("");
        for (int i = 0; i < (vt_set.size() + 1) * 10; i++)
            printf("-");
        puts("");
    }


}


int GetNum(int d1,int d2,char op) {
    if (op == '+') {
        cout << d1 << " + " << d2 << " = " << d1 + d2 << endl;
        return d1 + d2;
    }
    if (op == '*') {
        cout << d1 << " * " << d2 << " = " << d1 * d2 << endl;
        return d1 * d2;
    }
    if (op == '/') {
        cout << d2 << " / " << d1 << " = " << d2 / d1 << endl;
        return d2 / d1;
    }
    if (op == '-') {
        return d1 - d2;
    }
}


void Calculate(char t1,char t2) {
         //取数据栈两个操作数
       int d1 = sa_int.top();
        sa_int.pop();
        int d2 = sa_int.top();
        sa_int.pop();
        //计算并压栈
        sa_int.push(GetNum(d1, d2, t1));
        sa_op.pop();
}


void Analyze() {
    //获取表达式长度
    int len = ex.size();

    //遍历表达式
    for (int i = 0; i < len;) {
        //是数字
        if (isdigit(ex[i])) {
            int t = (int)(ex[i] - '0');
            while (i < len && isdigit(ex[++i])) {
                t = t * 10 + (int)(ex[i] - '0');
            }

            sa_int.push(t);
            continue;
        }
        //是算符

        if (vt_pos.find(ex[i]) != vt_pos.end()) {
            char t2 = ex[i];
                  //栈非空
            if (!sa_op.empty()) {
                char t1 = sa_op.top();
                //t2是当前,t1是栈顶
                //如果当前优先级比栈顶优先级大，则入栈
                if (priority_tabel[vt_pos[t1]][vt_pos[t2]] == '<') {
                    sa_op.push(t2);
                }
                //优先级相等，则栈顶出栈
                else if(priority_tabel[vt_pos[t1]][vt_pos[t2]]=='='){
                    sa_op.pop();
                    //break;
                }
                else{
                    //用栈顶符号计算
                    Calculate(t1, t2);
                    //主要要continue！！！
                    continue;
                }
            }
            else {
                sa_op.push(t2);
            }
            ++i;
        }
        else {
            cout << ex[i]<<" 输入的运算符有误" << endl;
            return;
        }
    }
        //剩余部分计算
        while (!sa_op.empty()) {
            int t1 = sa_op.top();
            Calculate(t1, t1);
        }
        cout << "结果为：" << sa_int.top();
        return;
    
}


int main(){
    int n;
    string s;
    cin >> n;
    for (int i = 0; i < n; ++i){
        //s是当前推导式
        cin >> s;
        int len = s.size();

        //VN第一次出现，值为VN位置
        char vn = s[0];
        if (vn_pos.find(vn)==vn_pos.end()){
            vn_set.push_back(VN(vn));
            vn_pos[vn] = vn_set.size()-1;
        }
        //产式子右部插入

        vn_set[vn_pos[vn]].insert(s.substr(3));

         //j为产生式左部位置
        for (int j = 3; j < len; ++j) {
            if (!isupper(s[j]))
            {
                char vt = s[j];
                //如果是VT
                //VT压栈，used里存着VT的位置

                if (vt_pos.find(vt) == vt_pos.end()) {
                    vt_set.push_back(vt);
                    vt_pos[vt] = vt_set.size() - 1;
                }
            }
        }

    }


    
    PrintLine("产生式");
    for (int i = 0; i < vn_set.size(); i++)
        vn_set[i].print();

    //打印VT和VN
    PrintLine("VT集");
    for (int i = 0; i < vt_set.size(); i++) {
        cout << vt_set[i] << " ";
    }
    cout << endl;
 
    PrintLine("VN集");

    for (int i = 0; i < vn_set.size(); i++) {
        cout << vn_set[i].left << " ";
    }
    cout << endl;


    GetFirstvt();
    GetLastvt();
    GetPriorityTabel();


    cin >> ex;
    Analyze();
    return 0;
}