基于SLR(1)分析法的语法制导翻译及中间代码生成程序设计原理与实现

前言：终于良心发现开始自己写编译原理实验了，这不得来水一篇博客？

参考：编译原理：基于SLR(1)分析法的语法制导翻译及中间代码生成

函数介绍：

int main() {
    generate();                调用实验一，生成二元组
    readFileFromLab1();    　　读取实验一生成文件
    readGrammar();        读取文法
    getVnVt();                分析终结符和非终结符
    getFollow();                分析Follow集
    getDFA();                自动生成DFA
    getSLRTable();        根据DFA生成分析表
    printSLRTable();            打印分析表
    if(analysisSLR()){
        printf("分析成功！");
        printRes();       打印四元组
    }
    else printf("分析失败QAQ");
    return 0;
}    

DFA生成：

int isNotNewSt(status *a)        判断是否为新状态
status* getClosure(set<node>& content)    获取闭包
status* getStatus(const set<node>& a)    计算新增加一个字符后状态

主要数据存储方式：

vector<pair<int,string> > in;
vector<pair<char, string> > grammar;
set<char> vn,vt;
map<char,set<char> > follow;
map<char,pair<char,int> > slr[20];
一个项目
struct node{
    int pos;　　下一个要读哪个字符
    char from;　　左式
    string to;　　右式
    node(int p,char f,string t){
        pos=p;from=f;to=t;
    }
为了塞到set里得有个小于号
    bool operator < (const node &a) const{
        if(pos==a.pos){
            if(from==a.from)
                return to<a.to;
            return from<a.from;
        }
        return pos<a.pos;
    }
    bool operator == (const node &a) const{
        if(pos==a.pos){
            if(from==a.from)
                return to==a.to;
        }
        return false;
    }
};
状态描述
struct status{
    int id;　　状态序号
    set<node> content;　　状态内项目集
    bool accepted;　　是否为终结状态
    map<char,int> action;
    map<char,int> gotu;　　goto是关键字，所以换一个
    bool operator == (const status &a) const{
        if(content.size()==a.content.size()){
            for(auto i:a.content){
                if(!content.count(i)){
                    return false;
                }
            }
            return true;
        }
        return false;
    }
};
所有状态
vector<status*> allSt;
四元组
struct four{
    string op,arg1,agr2,des;
};
vector<four> res;

SLR分析表：

 分析过程（太长不截了）：

四元式：

求FOLLOW集的时候偷懒了，直接面向文法编程。

写完想象了一下整个编译器的工作量，大受震撼。

完整代码：

#include <bits/stdc++.h>
#include "generator.h"
using namespace std;

vector<pair<int,string> > in;
vector<pair<char, string> > grammar;
set<char> vn,vt;
map<char,set<char> > follow;
map<char,pair<char,int> > slr[20];

struct node{
    int pos;
    char from;
    string to;
    node(int p,char f,string t){
        pos=p;from=f;to=t;
    }
    bool operator < (const node &a) const{
        if(pos==a.pos){
            if(from==a.from)
                return to<a.to;
            return from<a.from;
        }
        return pos<a.pos;
    }
    bool operator == (const node &a) const{
        if(pos==a.pos){
            if(from==a.from)
                return to==a.to;
        }
        return false;
    }
};
struct status{
    int id;
    set<node> content;
    bool accepted;
    map<char,int> action;
    map<char,int> gotu;
    bool operator == (const status &a) const{
        if(content.size()==a.content.size()){
            for(auto i:a.content){
                if(!content.count(i)){
                    return false;
                }
            }
            return true;
        }
        return false;
    }
};

vector<status*> allSt;
struct four{
    string op,arg1,agr2,des;
};
vector<four> res;

void readFileFromLab1(){
    FILE *fp=fopen("test.txt", "r");
    char s[10];
    while(fscanf(fp,"%s",s)!=EOF){
        int len=1,id=0;
        while(s[len]>='0'&&s[len]<='9'){
            id=id*10+s[len]-'0';
            len++;
        }
        len+=2;
        char s2[20]={0};
        int cnt=0;
        while(s[len]!='\''){
            s2[cnt++]=s[len];
            len++;
        }
        in.push_back(make_pair(id,s2));
    }
    fclose(fp);
}

void readGrammar(){
    FILE *fp= fopen("gramma.txt","r");
    char s[50];
    while(fscanf(fp,"%s",&s)!=EOF){
        char s1=s[0];
        int len=3;
        while(1) {
            char s2[20]={0};
            int cnt=0;
            while (s[len] != '|') {
                if(s[len]=='\0'){
                    grammar.push_back(make_pair(s1,s2));
                    goto nxt;
                }
                s2[cnt++]=s[len];
                len++;
            }
            grammar.push_back(make_pair(s1,s2));
            len++;
            if(len=='\0') break;
        }
        nxt:;
    }
    fclose(fp);
}

void getVnVt(){
    vn.insert('S');
    for(auto [_,i]:grammar) {
        for (int k = 0; k < i.length(); k++) {
            if (i[k] >= 'A' && i[k] <= 'Z') {
                vn.insert(i[k]);
            } else vt.insert(i[k]);
        }

    }
}

void getFollow() {
    follow['S'].insert('#');
    for (auto[m, j]: grammar) {
        for (int i = 0; i < j.length() - 1; i++) {
            if (vn.count(j[i]) && vt.count(j[i + 1])) {
                follow[j[i]].insert(j[i + 1]);
            }
        }
    }
    for (auto[m, j]: grammar) {
        char end = j[j.length() - 1];
        if (vn.count(end)) {
            for (auto i: follow[m]) {
                follow[end].insert(i);
            }
        }
    }
}

status* getClosure(set<node>& content){
    bool accepted=true;
    set<char> clo;
    queue<char> q;
    for(auto [pos,from,to]:content){
        if(vn.count(to[pos])){
            if(!clo.count(to[pos])){
                clo.insert(to[pos]);
                q.push(to[pos]);
            }
        }
    }
    while(!q.empty()){
        char now=q.front();
        q.pop();
        for(auto[x,y]:grammar) {
            if (x == now) {
                content.insert(node(0, x, y));
                if (vn.count(y[0])) {
                    if (!clo.count(y[0])) {
                        clo.insert(y[0]);
                        q.push(y[0]);
                    }
                }
            }
        }
    }
    for(auto [pos,from,to]:content){
        if(pos!=to.size()) accepted=false;
    }
    status* res=new status;
    res->content=content;
    res->accepted=accepted;
    return res;
}

status* getStatus(const set<node>& a){
    set<node> content;
    for(auto [pos,from,to]:a){
        if(pos<to.length())
            content.insert(node(pos+1,from,to));
    }
    return getClosure(content);
}

int isNotNewSt(status *a){
    for(int i=0;i<allSt.size();i++){
        if(*allSt[i]==*a) return i;
    }
    return 0;
}

void getDFA(){
    set<node> extra;
    extra.insert(node(0,'Z',"S"));
    status* begin=getClosure(extra);
    begin->id=0;

    queue<status*> q;
    q.push(begin);
    allSt.push_back(begin);
    map<char,int> vis;
    while(!q.empty()){
        status* now=q.front();
        q.pop();
        vis.clear();
        set<node> s;
        for(auto [pos,from,to]:now->content){
            char temp=to[pos];
            if(vis[temp]) continue;
            s.clear();
            for(auto i:now->content){
                if(i.to[i.pos]==temp&&i.pos<i.to.length()){
                    s.insert(i);
                }
            }
            if(s.empty()) continue;
            status* nxt=getStatus(s);
            int id;
            if(!(id=isNotNewSt(nxt))) {
                id=allSt.size();
                if(!nxt->accepted) q.push(nxt);
                allSt.push_back(nxt);
                vis[temp]=1;
            }
            nxt->id=id;
            if (vn.count(temp)) now->gotu[temp] = nxt->id;
            if (vt.count(temp)) now->action[temp] = nxt->id;
        }
    }
}

int getPos(node a){
    for(int j=0;j<grammar.size();j++){
        if(grammar[j].first==a.from&&grammar[j].second==a.to){
            return j;
        }
    }
    return 0;
}

void getSLRTable() {
    vt.insert('#');
    for(int i=0;i<allSt.size();i++){
        for(auto j:vt) slr[i][j].first='n';
        for(auto j:vn) slr[i][j].first='n';
    }

    for(int i=0;i<allSt.size();i++){
        for(auto j:allSt[i]->content){
            if(j.pos==j.to.length()){
                if(j.from=='Z') {
                    slr[i]['#'].first='a';
                    continue;
                }
                for(auto k:follow[j.from]) {
                    slr[i][k].first = 'r';
                    slr[i][k].second = getPos(j);
                }
            }
        }
    }
    for (int i = 0; i < allSt.size(); i++) {
        if(allSt[i]->accepted){
            node a=*(allSt[i]->content.begin());
            int id= getPos(a);
            for(auto j:follow[a.from]){
                slr[i][j].first='r';
                slr[i][j].second=id;
            }
        }
        for(auto [x,y]:allSt[i]->action){
            slr[i][x].first='s';
            slr[i][x].second=y;
        }
        for(auto [x,y]:allSt[i]->gotu){
            slr[i][x].first='g';
            slr[i][x].second=y;
        }
    }
}

void printSLRTable(){
    printf("   | ");
    for(auto i:vt) printf("%c    ",i);
    printf("| ");
    for(auto i:vn) printf("%c    ",i);
    printf("\n");
    for(int i=1;i<=14;i++) printf("-----");
    printf("\n");
    for(int i=0;i<allSt.size();i++){
        printf("%-2d | ",i);
        for(auto j:vt){
            if(slr[i][j].first=='a') printf("acc  ");
            else if(slr[i][j].first=='n') printf("     ");
            else printf("%c%-2d  ",slr[i][j].first,slr[i][j].second);
        }
        printf("| ");
        for(auto j:vn){
            if(slr[i][j].first=='n') printf("     ");
            else printf("%-2d   ",slr[i][j].second);
        }
        printf("\n");
    }
}

int analysisSLR(){
    stack<int> st;
    stack<char> ch;
    stack<string> ch2;
    auto printStack=[&st,&ch,&ch2](char nxt){
        stack<char> t2=ch;
        vector<char> t1;
        while(!t2.empty()){
            t1.push_back(t2.top());
            t2.pop();
        }
        reverse(t1.begin(),t1.end());
        printf("char  :[");
        for(auto i:t1) printf("%c",i);
        printf("\tnext:%c\n",nxt);

        stack<int> t3=st;
        t1.clear();
        while(!t3.empty()){
            t1.push_back(t3.top());
            t3.pop();
        }
        reverse(t1.begin(),t1.end());
        printf("status:[");
        for(auto i:t1) printf("%d ",i);

        printf("\n\n");
    };
    st.push(0);
    ch.push('#');
    ch2.push("#");
    int i=0;
    int cnt=1;
    while(!st.empty()){
        if(i>in.size()) return 0;
        char nxt;
        string nxtName;
        if(i<in.size()) {
            auto[id, name]=in[i];
            nxt = id == 12 ? 'i' : name[0];
            nxtName=name;
        }
        else nxt='#';

        printStack(nxt);

        char sta=slr[st.top()][nxt].first;
        if(sta=='n') {
            printf("error at %d.",i);
            return 0;
        }
        if(sta=='s'){
            int now=slr[st.top()][nxt].second;
            st.push(now);
            ch.push(nxt);
            ch2.push(nxtName);
            i++;
        }
        if(sta=='r'){
            int num=slr[st.top()][nxt].second;
            int len=grammar[num].second.length()-1;
            int flag1=grammar[num].second.find('+')!=-1||grammar[num].second.find('-')!=-1||
                     grammar[num].second.find('*')!=-1||grammar[num].second.find('/')!=-1||
                    grammar[num].second.find('=')!=-1;
            int flag2=grammar[num].second.find('(')!=-1||grammar[num].second.find(')')!=-1;
            string temp[4];int cnt2=0;
            while(ch.top()==grammar[num].second[len]){
                if(flag1){
                    temp[cnt2++]=ch2.top();
                    ch2.pop();
                }
                if(flag2){
                    temp[cnt2++]=ch2.top();
                    ch2.pop();
                }
                ch.pop();
                st.pop();
                len--;
            }
            if(flag1) {
                ch2.push("T" + to_string(cnt++));
                res.push_back({temp[1],temp[0],temp[2],ch2.top()});
            }
            if(flag2)
                ch2.push(temp[1]);
            ch.push(grammar[num].first);
            st.push(slr[st.top()][ch.top()].second);
        }
        if(sta=='a'){
            return 1;
        }
    }
    return 0;
}

void printRes(){
    printf("生成四元式：\n");
    for(auto[a,s,d,f]:res){
        cout<<'('+a+','+s+','+d+','+f+')'<<endl;
    }
}

int main() {
    generate();
    readFileFromLab1();
    readGrammar();
    getVnVt();
    getFollow();
    getDFA();
    getSLRTable();
    printSLRTable();
    if(analysisSLR()){
        printf("分析成功！");
        printRes();
    }
    else printf("分析失败QAQ");
    return 0;
}