P - 简单的代码生成程序【编译原理】

4 2
T:=A-B
U:=A-C
V:=T+U
W:=V+U

LD R0, A
SUB R0, B
LD R1, A
SUB R1, C
ADD R0, R1
ADD R0, R1

#include <bits/stdc++.h>

using namespace std;

char p[100];// 模拟寄存器的个数
char s[100][100];// 输入表达式字符串
int n,m,top = 0;//n输入的表达式，m是寄存器个数

// 寄存器中是否存在该变量
int get(char ch)
{
    for(int i = 0; i < m;i ++)
    {
        if(ch == p[i])
            return i;
    }
    return -1;
}
///寄存器的使用顺序为:
///寄存器中存有 > 空寄存器 > 内存中存有 > 以后不再使用 > 最远距离使用
//判断后面是否还会使用
//x是输入表达式的编号，语句执行顺序
//ch需要判断的字符
int use(int x, char ch)
{
    for(int i = x; i < n; i ++)
    {
        // A:=B+C这里就是B、C
        // 如果有就返回第几句用到
        if(ch == s[i][3] || ch == s[i][5])
            return i;
    }
    return n;
}
///寄存器的使用顺序为:
///寄存器中存有 > 空寄存器 > 内存中存有 > 以后不再使用 > 最远距离使用
int find(int x)
{
    // 如果top小于m，就说明就空的寄存器可以使用
   if(top < m) return top++;
   //否则就是
   int t = -1;
   int ans = -1;
   for(int i = 0; i < m; i ++)
   {
       // 逐个判断在第x句之后，存在寄存器中的字符的使用顺序
       // 返回值k是执行顺序的标号
       int k = use(x,p[i]);
       // 我们的目的是找到最远不适用的，如果返回值越大，那就是最远不适用的
       // 记录标号存在t里面
       if(k > ans)
       {
           ans = k;
           t = i;
       }
   }
   return t;
}
// 减加乘除
void print1(char ch)
{
    if(ch == '+')printf("ADD ");
    else if(ch == '-') printf("SUB ");
    else if(ch == '*') printf("MUL ");
    else if(ch == '\\') printf("DIV ");
}
// 第二个操作数的使用
void print2(char ch)
{
    // 查看是否在寄存器中
    int x = get(ch);
    // 如果在寄存器中，那就直接使用
    if(x != -1){
        printf("R%d\n",x);
    }
    else {
            // 否则就直接使用内存中的即可，因为已经有一个寄存器了
        printf("%c\n",ch);
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n;i ++)
    {
        cin >> s[i];
    }
    for(int i = 0; i < n; i ++)
    {
        // 将第1个操作数取出来，get()来获取寄存器中是否存在该变量
        // T:=A-B中的A
        int x = get(s[i][3]);//如果不为-1，得到的x为所在寄存器的标号
        // 如果x为-1说明该数不在寄存器中，需要做处理
        if(x == -1)
        {
            //此时的x是我们可以使用的寄存器标号
            x = find(i);
            // 如果p[x]中有东西，并且use(i,p[x]) < n即后面会使用到
            //那我们就把原来在寄存器中的字符ST到内存中
            if(p[x] != '\0' && use(i,p[x]) < n)
            {
                printf("ST R%d, %c\n",x,p[x]);
                p[x] = NULL;
            }
            //将该操作数加载到我们使用的寄存器标号中
            printf("LD R%d, %c\n",x,s[i][3]);
        }
        // 这里下面的操作就是执行运算
        // 1、输出操作符，这里是加减乘除
        print1(s[i][4]);
        //2、输出寄存器标号，需要的操作数已经加载到里面了
        printf("R%d, ",x);
        //3、第二个操作数的使用
        print2(s[i][5]);
        // 寄存器中当前存的数值就是该表示的左边的字符,即T:=A-B中的T
        p[x] = s[i][0];
    }
    return 0;
}