编译原理实验，完整程序的递归下降分析，生成四元式
文法：LittleC文法，需要实现if else 和 while do以及赋值语句的翻译

LittleC文法
![sp20200701_151953_303.png](https://cdn.acwing.com/media/article/image/2020/07/01/28324_47b207e6bb-sp20200701_151953_303.png) 

测试用例
![sp20200701_151813_957.png](https://cdn.acwing.com/media/article/image/2020/07/01/28324_1ea23b28bb-sp20200701_151813_957.png) 


#include <iostream>
#include <cstdio>
#include <sstream>
#include <fstream>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <iomanip>
#include <set>
#include <stack>
#include <algorithm>

using namespace std;

string keyword[7] = {"if", "else", "for", "while", "do", "int", "main"};   //关键字表
string variable[100];                                                      //标识符表
int sum_variable;
set<string> follow;
struct token{
    string val;     //单词具体值
    int type;       //单词的种别码(10是标识符，20是常数，30是关键字,41是加法，42是乘法，43是关系运算符，50是界符)
    int line;       //行号
};
struct Quad{      //定义四元式
    string result;
    string arg1;
    string arg2;
    string op;
}quad[100];

FILE *fin, *fout;    //文件流
int line = 1;        //当前的行号
int flag;            //判断是否从文件读取字符成功
string buff;         //用于存放单词
token new_word;      //单词

int quad_index = 0;  //四元式总数
int e;               //错误次数
char ch;             //从字符串形式的源程序获取的字符
int f;               //表达式中间运算符的个数
int flag1, flag2;
string op, arg1, arg2, result;
string a[200];
int a_num = 1;
int tI = 1;          //定义当前是t几了，比如t1,t2,t3;
stack<int> back_number1, back_number2, back_number3;     //用于回填的栈

int P();
int B();
int Decls();
int Decl();
int Stmts();
int Stmt();
int Sub_Stmt();
int F();
int F1();
int I();
string Expr();    //表达式
string Expr();
string Expr1(string str1);
string Term(string str1, string op1);
string Term1(string str1);
string Factor();
int J();
int TJ();
void showTable();

void getQuad(string op1, string str1, string str2, string res)  //构造四元式
{
    quad[quad_index].op = op1;
    quad[quad_index].arg1 = str1;
    quad[quad_index].arg2 = str2;
    quad[quad_index].result = res;
    quad_index ++;
}

string to_str(int a)     //整型转变为string型
{
    string s;
    while(a) s += '0' + a%10, a /= 10;
    reverse(s.begin(), s.end());
    return s;
}

string newT()            //创建临时变量
{
    int t = tI ++;
    return "t" + to_str(t);
}

void printFour()             //输出四元式
{
    ofstream out("ygro.txt");
    int i;
    for(i=0;i<quad_index;i++)
   {
      cout<<i<<":\t("<<quad[i].op<<",\t"<<quad[i].arg1<<",\t"<<quad[i].arg2<<",\t"<<quad[i].result<<")"<<endl;
      out<<i<<":\t("<<quad[i].op<<",\t"<<quad[i].arg1<<",\t"<<quad[i].arg2<<",\t"<<quad[i].result<<")"<<endl;
   }
}

void error(string s) //输出错误信息
{
    cout << "第" << new_word.line << "行出错!\t";
    cout << s << endl;
    e ++;
}

void is_decleared(string a)       //检查变量是否被声明
{
    int i;
    for(i = 0; i < sum_variable; i ++)
    {
        if(a == variable[i])
            break;
    }
    if(i > sum_variable)             //没有在声明变量表中找到
    {
        cout << "第" << new_word.line << "行出错!\t";
        cout << new_word.val << " 没有被声明！" << endl;
        e ++;
    }
}

int getWord()                    //词法分析
{
    if(!flag) ch = getc(fin);
    while(ch == ' ' || ch == '\n' || ch == '\t')     //跳过换行，缩进，空格
    {
        if(ch == '\n') line ++;
        ch = getc(fin);
        flag = 1;
    }
    if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))      //识别标识符，它可能是变量，也可能是关键字
    {
        buff = "";      //清空buff
        do{
            buff += ch;
            ch = getc(fin);
            flag = 1;
        }while((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9'));
        new_word.val = buff;
        new_word.line = line;
        int k;
        for(k = 0; k < 7; k ++){
            if(new_word.val == keyword[k])
                break;
        }
        if(k < 7)      //在关键字表中
             new_word.type = 30;            //关键字种别码30
        else
             new_word.type = 10;            //标识符种别码10
        cout << new_word.val << "\t" << new_word.type << endl;
        return 0;
    }
    else if(ch >= '0' && ch <= '9')         //整数
    {
        buff = "";
        do{
            buff += ch;
            ch = getc(fin);
            flag = 1;
        }while(ch >= '0' && ch <= '9');
        new_word.val = buff;
        new_word.type = 20;                 //整数种别码20
        new_word.line = line;
        cout << new_word.val << "\t" << new_word.type << endl;
        return 0;
    }
    else if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
    {
        buff = "";
        buff += ch;
        ch = getc(fin);
        flag = 1;
        new_word.val = buff;
        if(ch == '+' || ch == '-')
           new_word.type = 41;
        else
           new_word.type = 42;
        new_word.line = line;
        cout << new_word.val << "\t" << new_word.type << endl;
        return 0;
    }
    else if(ch == '=' || ch == '<' || ch == '>' || ch =='!')
    {
        buff = "";
        buff += ch;
        ch = getc(fin);
        flag = 1;
        if(ch == '=')
        {
            buff += ch;
            ch = getc(fin);
            flag = 1;
        }
        new_word.val = buff;
        new_word.type = 43;           //关系运算符种别码是43
        new_word.line = line;
        cout << new_word.val << "\t" << new_word.type << endl;
        return 0;
    }
    else if(ch == ',' || ch == ';' || ch == '(' || ch == ')' || ch == '{' || ch == '}')
    {
        buff = "";
        buff += ch;
        new_word.val = buff;
        new_word.type = 50;           //界符的种别码是50
        ch = getc(fin);
        flag = 1;
        cout << new_word.val << "\t" << new_word.type << endl;
        return 0;
    }
    else
    {
        new_word.type = 0;             //错误类型单词
        new_word.val += " ";
        cout << new_word.val << "\t" << new_word.type << endl;
        return 0;
    }
}

void init()
{
    follow.insert("+");    //定义Term1的follow集
    follow.insert("-");
    follow.insert(")");
    follow.insert(";");
    follow.insert("==");
    follow.insert(">=");
    follow.insert("<=");
    follow.insert(">");
    follow.insert("<");
}

int P() //(){分程序}
{
    getWord();  //{
    if(new_word.val != "{")
    { error("缺少'{'");}
        getWord();  //int
        B();
        //getWord();
    //if(new_word.val != "} ")
    //{ error("缺少'}'");}
    op="go";
    arg1="";
    arg2="";
    result="";
    getQuad(op, arg1, arg2, result);
    cout<<"语法检查完成,共发现"<<e<<"个错误。"<<endl;
    return 0;
}

int B()
{
    Decls();     //变量声明
    Stmts();
    return 0;
}

int Decls()
{
    Decl();
    if(new_word.val != ";") error("缺少;");
    getWord();
    if(new_word.val == "int") Decls();
    return 0;
}

int Decl()
{
    if(new_word.val != "int") error("缺少int");
    getWord();
    variable[++ sum_variable] = new_word.val;
    F();       //标识符表
    return 0;
}

int F()
{
    if(new_word.type == 10) getWord();
    F1();
    return 0;
}

int F1() //标识符
{
    if(new_word.val == ";") return 0;
    if(new_word.val != ",") error("标识符错误！");
    getWord();
    variable[++ sum_variable] = new_word.val;
    if(new_word.type != 10) error("标识符错误!");
    getWord();
    F1();
    return 0;
}

int Stmts()
{
    Stmt();         //语句
    Sub_Stmt();     //子语句
    return 0;
}

int Sub_Stmt()
{
    if(new_word.val == "}")
    {
        return 0;            //表示一个语句的结束
    }
    if(new_word.val == ";")
    {
        getWord();
        Stmt();
        Sub_Stmt();
    }
    if(new_word.type == 10 || new_word.type == 30)   //右递归
    {
        Stmt();
        getWord();
        if(new_word.type == 10 || new_word.type == 30)
            Stmt();
        //Sub_Stmt();
    }
    if(new_word.type == 0)
        return 0;
    //else error("语句错误！");
    return 0;
}

int Stmt()
{
    if(new_word.type == 10)  //10表示的是标识符，判定为赋值语句
    {
        is_decleared(new_word.val);
        result = new_word.val;
        getWord();
        op = new_word.val;  //op是‘=’
        I();                //赋值语句,需要识别到';'这一块
        arg2 = "";          //arg2设置为空, arg1设置为I产生的表达式
        getQuad(op, arg1, arg2, result);
        return 0;
    }
    if(new_word.val == "if")  //if E then S1 else S2 或者是 if E then S1
    {
        getWord();
        J();                  //if对应的条件语句
        return 0;
    }
    if(new_word.val == "while") //while(E) do S
    {
        getWord();     //new_word=(
        getWord();
        int quad_while = quad_index;      //记录while的标号
        TJ();
        int S_next = back_number1.top();
        back_number1.pop();
        getQuad(op, arg1, arg2, result);

        getWord();     //new_word={
        getWord();
        Stmts();       //S, 语句块
        getQuad("go", "", "", to_str(quad_while));    //goto while
        //回填E.false
        quad[S_next].result = to_str(quad_index);
        getWord();
    }
    if(new_word.type == 0) return 0;
}

int I()        //赋值语句
{
    if(new_word.val != "=") error("缺少=");
    getWord();
    arg1 = Expr();
    return 0;
}

string Expr() {
    string res, str1;
    str1 = Term("", "");
    res = Expr1(str1);
    return res;
}

string Expr1(string str1) {
    string res, str2;
    if(new_word.val == "+" || new_word.val == "-")
    {
        string t = "";
        t += new_word.val;
        getWord();
        str2 = Term(str1, t);
        res = Expr1(str2);
    }
    else if(new_word.val != ")" && new_word.val != ";" && new_word.type != 43)  //new_word.val不在Expr1的follow集中
        error("表达式错误");
    else return str1;
    return res;
}

string Term(string str1, string op1) {  //传递过来的属性是操作运算符+或者-，运算对象
    string res, str2;
    string str3 = Factor();            //Factor产生的字符
    if(new_word.val == "*" || new_word.val == "/")         //Term1非空
    {
        str2 = Term1(str3);
        if(op1.size())
        {
            res = newT();              //返回的中间变量
            getQuad(op1, str1, str2, res);
        }
        else
            res = str2;
    }
    else                               //Term1不考虑错误，为空
    {
        if(str1.size())                //传进来的str1不是""
        {
            res = newT();
            getQuad(op1, str1, str3, res);
        }
        else return str3;
    }
    return res;
}

string Term1(string str1) {
    string res, str2;
    if(new_word.val == "*" || new_word.val == "/")
    {
        string t = newT();
        string op1 = "";
        op1 += new_word.val;                     //记录操作运算符
        getWord();
        str2 = Factor();
        getQuad(op1, str1, str2, t);   //t是中间变量
        if(new_word.val == "*" || new_word.val == "/")    //非空
            res = Term1(t);
        else
        {
            return t;
        }
    }
    else if(follow.count(new_word.val) > 0)   //new_word.val是Term1的follow集
    {
        return res;
    }
    else if(follow.count(new_word.val) == 0)  //new_word.val不在Term1的follow集 + - ) #, 一定出现错误
       error("表达式错误");
    return res;
}

string Factor() {
    string res = "";
    if(new_word.type == 10 || new_word.type == 20)      //new_word是标识符或者常数
       {
           res += new_word.val;
           getWord();
           return res;
       }
    else if(new_word.val == "(")
    {
        getWord();
        res += Expr();
        if(new_word.val == ")") getWord();
        else error("表达式错误");
    }
    else error("表达式错误");
    return res;
}

int J()
{
    if(new_word.val != "(") error("缺少(");
    getWord();
    TJ();
    getQuad(op, arg1, arg2, result);                     //生成E.false
    if(new_word.val != ")") error("缺少)");
    op = "", arg1 = "", arg2 = "", result = "";          //更新为空
    getWord();
    Stmt();                                              //表达式E.true对应的执行语句
    if(new_word.val == ";") getWord();
    if(new_word.val == "else")                           //表示存在else
    {
        //出现了else, E.true对应的执行语句执行完毕之后要跳转到S.next
        back_number2.push(quad_index);
        getQuad("go", "", "", "");          //goto S.next
        //回填E.false
        quad[back_number1.top()].result = to_str(quad_index);
        back_number1.pop();
        //执行else后面的语句
        getWord();
        Stmt();
        //回填S.next
        quad[back_number2.top()].result = to_str(quad_index);
        back_number2.pop();
    }
    else                                                 //表示不存在else,回填E.false
    {
        quad[back_number1.top()].result = to_str(quad_index);
        back_number1.pop();
    }
    return 0;
}

int TJ() //生成E.false
{
    arg1 = Expr();
    if(new_word.val == ">") op = "j<=";
    if(new_word.val == "<") op = "j>=";
    if(new_word.val == ">=") op = "j<";
    if(new_word.val == "<=") op = "j>";
    if(new_word.val == "==") op = "j!=";
    if(new_word.val == "!=") op = "j==";
    if(new_word.type != 43) error("缺少关系运算符");
    getWord();
    arg2 = Expr();
    back_number1.push(quad_index);
    return 0;
}

void showTable()
{
    cout << "---------标识符表---------";
    cout << endl;
    for(int i = 1; i <= sum_variable; i ++)
        cout << variable[i] << "  ";
    cout << endl;
}

int main()
{
    if((fin = fopen("input.txt", "r")) == NULL)
    {
        printf("\n 读入文件错误！ \n");
        return 0;
    }
    init();
    P();
    if(e == 0)
    {
        showTable();
        printFour();
    }
    else
        cout << "语法存在错误！" << endl;
    return 0;
}



执行结果：
![sp20200701_152032_200.png](https://cdn.acwing.com/media/article/image/2020/07/01/28324_5febb6f4bb-sp20200701_152032_200.png)