语法制导翻译 7-1 AST的生成

在本实验中，您需要使用C++进行编程，实现如下功能。

根据预测分析法的自顶向下分析过程，创建一棵树存储对应的抽象语法树(Abstract Syntax Tree,AST)，并在预测分析完成后将AST横向输出。

题目链接：https://pintia.cn/problem-sets/1645430534803410944/exam/problems/1645430650163556352

输入格式:

第一部分是文法产生式，

一行“----------”，

第二部分是一行待分析的句子，

一行“----------”，

第三部分是预测分析的过程（共三列，分别为分析栈、剩余符号串和推导所用产生式或匹配，每列输出宽度为15）。

输出格式:

横向的AST。

注意：

① 第一行第一个符号是AST的根节点，即文法的开始符号；

② AST树中每一层节点同列；

③ AST列与列之间用一个空格分隔；

④ AST每一行的最后一个字符后没有空格；

⑤ 样例中所有非大写字母均为终结符，且只占一个字符，其中ε用@代替；

⑥ 样例中的所有句子一定可以分析成功。

输入样例：

A->Bc
A->d
B->bA
B->@
----------
bcc
----------
             #A           bcc#          A->Bc
            #cB           bcc#          B->bA
           #cAb           bcc#        b match
            #cA            cc#          A->Bc
           #ccB            cc#           B->@
            #cc            cc#        c match
             #c             c#        c match
              #              #            acc

输出样例：

A B b
    A B @
      c
  c

核心算法：

深度优先遍历（dfs）

核心数据结构：

因为我们需要根据预测分析法的自顶向下分析过程，构建一棵抽象语法树，而这棵树是一个多叉树，即一个结点可以有多个儿子。

例如我们对于推导式：A->CDE，我们就可以得到，A的儿子结点按照顺序有C、D、E。所以我们在遇到需要推导的时候，建立相应的结点，然后建立相应的儿子关系即可。

我们采取这样的数据结构来存储多叉树：

const int N = 110;
struct Tree{
    char e;//e表示这个结点所存的字符
    int l,r;//表示儿子结点所在的区间
}tree[N];
int idx;//idx可以用来表示现在已经创建了多少个结点，也可以表示需要创建的新的结点的下标的位置
//实际代码中为了方便，没有使用结构体，而是用的零散的数组，不过是一个意思

由于我们是根据一个推导式来建立相应的结点和儿子关系，所以一个结点的儿子结点一定是连续的，即儿子结点对应的下标一定处在一个连续的区间，即[l,r]。我们在最开始使用推导式A->Bc的时候，为A、B、c分别建立下标为0、1、2的结点，同时A的儿子结点区间为[l,r] = [1,2]。

同时，我们也需要建立一个分析栈，只不过这个栈不是用来存字符的，而是用来存结点的下标的，这样的话我们就可以根据栈顶得到对应的结点，然后由推导关系建立儿子关系（即建立树）或者根据匹配关系，结束这个结点的子树的建立。我们可以模拟出一下过程

             #A           bcc#          A->Bc
             栈顶这个结点还未建立过，故建立三个结点,e[0]='A',并且l[0]=1,r[0]=2，即给栈顶结点加上1，2的儿子栈顶弹栈，然后推导式右部倒序入栈，分析栈为[2,1]
            #cB           bcc#          B->bA
            栈顶结点建立过，根据B->bA，再建立两个结点，下标分别为3,4，同时给栈顶的结点加上3，4的儿子
            弹栈，然后倒序入栈，分析栈为[2,4,3]
           #cAb           bcc#        b match
           match的情况弹栈即可
            #cA            cc#          A->Bc
            再建立两个结点，分别为B,c，下标分别为5，6，弹栈，倒序入栈，分析栈为[2,4,6,5]
           #ccB            cc#           B->@
           建立一个结点@，下标为7，同时建立栈顶的儿子，7，弹栈即可，不需要倒序入栈
            #cc            cc#        c match
             #c             c#        c match
              #              #            acc

代码中建立结点建立儿子关系的函数为add，add_side。

经过上述的思维过程，我们的抽象语法树就已经建立好了，而输出就是深度优先遍历树的过程：，我们先来分析一下输出：

A B b//从A结点遍历子树，先遍历B子树，B的子树有b这颗子树
    A B @//在同一个深度遍历另一颗子树，也就是B的另外一个子树A，需要换行，A还需要遍历自己的子树，B,B的子树为@
      c//同时，A的另一颗子树，为c
  c//A的子树B遍历完了，再来遍历A的第二棵子树c
//我们可以根据缩进的长度来判断此时已经遍历的深度

观察输入，我们可以知道：

• 在遍历一个结点的子树时，更换子树遍历是需要换行的。

• 而我们在输出的时候，如果一个结点已经没有子树了，即这个结点是叶子结点，则我们就不能输入后面的空格。

• 对于前面的缩进，我们可以根据当前的深度来判断，例如样例中下标为4的结点，深度为2（深度从0开始），所以缩进为2*2。

下面是具体的代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<iomanip>

using namespace std;
const int N = 110;

//存储一个多叉树的结构
char e[N];
int l[N],r[N],idx;
//idx表示结点所在的下标
//e[i]表示这个结点所代表的字符

string st;//分析栈,只不过这里存的是结点的下标

void cin_init();
void add(char left,string right);
void add_side(int p,string right);
void dfs(int u,int x);//参数表示的分别是结点的下标和深度

int main()
{
    cin_init();
    dfs(0,0);
    return 0;
}
void dfs(int u,int x)
{
    // 先输出根节点
    cout<<e[u];
    if(l[u]!=-1)cout<<" ";
    if(l[u]==-1){cout<<endl;return;}//没有子树可以输出了，则换行
    bool flag = false;
    for(int i=l[u];i<=r[u];i++)
    {
        if(flag)
        cout<<setw(2*(x+1))<<" ";
        dfs(i,x+1);
        flag = true;
    }
}

void add(char left,string right)//建立结点的同时，倒序入栈
{
    e[idx] = left;
    l[idx] = idx+1;
    r[idx] = idx+right.size();
    idx++;
    string temp;
    for(int i=0;i<right.size();i++)
    {
        e[idx] = right[i];
        char t = '0'+idx;
        temp+=t;
        idx++;
    }
    if(right=="@")return;
    reverse(temp.begin(),temp.end());
    st+=temp;//倒序入栈
}

void add_side(int p,string right)
{
    l[p] = idx;
    r[p] = idx+right.size()-1;
    string temp;
    for(int i=0;i<right.size();i++)
    {
        e[idx] = right[i];
        char t = '0'+idx;
        temp+=t;
        idx++;
    }
    if(right=="@")return;
    reverse(temp.begin(),temp.end());
    st+=temp;//倒序入栈
}

void cin_init()
{
    string temp;
    for(int i=0;i<3;i++)//输入分3部分
    {
        if(i!=2)
        {
            while(getline(cin,temp)&&temp!="----------");
        }
        else//只需要处理第三部分
        {
            //初始化树
            memset(l,-1,sizeof(l));
            memset(r,-1,sizeof(r));
            st+='0';//初始化分析栈
            while(getline(cin,temp))
            {
                // cout<<temp<<endl;
                string a = temp.substr(0,15);
                string b = temp.substr(15,15);
                string c = temp.substr(30,15);

                //先判断是匹配还是推导
                if(c.substr(c.size()-5,5)=="match")//匹配
                {
                    //分析栈弹栈
                    //不过一次match只能匹配一个，所以一次只能弹一个元素
                    st = st.substr(0,st.size()-1);
                }
                else if(c.substr(c.size()-3,3)=="acc")//接受
                continue;
                else//推导
                {
                    //推导就需要增加结点和子树
                    c.erase(remove(c.begin(),c.end(),' '),c.end());
                    int t = c.find('>');
                    char left = c[0];
                    string right = c.substr(t+1,c.size()-t-1);

                    int st_top = st[st.size()-1]-'0';
                    st = st.substr(0,st.size()-1);//还是需要先把推导的非终结符弹出来

                    if(st_top>=idx)//说明还没有建立这样的结点
                    add(left,right);//建立结点的同时，倒序入栈
                    else//结点已建立，但需要重写子树
                    add_side(st_top,right);
                }
            }
        }
    }
}