自顶向下生成语法树和汇编代码

前言

写了这篇使用文法规则实现四则运算博客, 顺手也写了本篇。

这里涉及到树, 对树结构感兴趣且没有什么基础的小伙伴可以查看这个:详细二叉树实现c++, 我当时写的挺详细的，就是当时初学，代码没有优化…

生成语法树

//
// Created by Andy Dennis on 2020/12/9.
// 文法规则:
/*exp -> term {addop term}
 * addop -> + | -
 * term -> factor {mulop factor}
 * mulop -> * | /
 * factor -> (exp) | n
 * */

# include <iostream>
# include <cmath>

using namespace std;

// 全局变量token
char token;
// 待处理的字符串
string str;
// 字符串读取到的地方
int strIndex = 0;
// 存放数字
string num;

struct BinTreeNode {
    string data;   // 存储数据
    BinTreeNode *leftChild, *rightChild;

    BinTreeNode() : leftChild(nullptr), rightChild(nullptr) {}
};

// 用到的函数, 先提前声明
void getToken();

void match(char expectToken, int errorId);

void Error(int errorId, char expectToken);

void PrintBinTree(BinTreeNode *BT);

BinTreeNode *exp();

BinTreeNode *term();

BinTreeNode *factor();

int main() {
    string examples[3] = {"3.2-5+8", "3+8/2-6", "(5*(9-2)+1)/9"};
    for (int i = 0; i < 3; i++) {
        str = examples[i];
        strIndex = 0;
        cout << "task "<< i + 1 << ": " << str << endl;
        getToken();
        BinTreeNode *root = exp();
        PrintBinTree(root);
        cout << endl;
    }
//    测试一下getToken函数
//    while (token != '$') {
//        getToken();
//        if (token == '0')
//            cout << num << endl;
//        else
//            cout << token << endl;
//    }
}

BinTreeNode *exp() {
    char errorId = 0;
    BinTreeNode *temp, *newTemp;
    temp = term();
    while (token == '+' || token == '-') {
        newTemp = new BinTreeNode();
        newTemp->data = token;
        match(token, errorId);
        newTemp->leftChild = temp;
        newTemp->rightChild = term();
        temp = newTemp;
    }
    return temp;
}

BinTreeNode *term() {
    char errorId = 1;
    BinTreeNode *temp, *newTemp;
    temp = factor();
    while (token == '*' || token == '/') {
        newTemp = new BinTreeNode();
        newTemp->data = token;
        match(token, errorId);
        newTemp->leftChild = temp;
        newTemp->rightChild = factor();
        temp = newTemp;
    }
    return temp;
}

BinTreeNode *factor() {
    BinTreeNode *temp;
    char errorId = 2;
    if (token == '(') {
        match('(', errorId);
        temp = exp();
        match(')', errorId);
    } else if (token == '0') {
        match('0', errorId);
        temp = new BinTreeNode();
        temp->data = num;
        // temp->leftChild = nullptr;
        // temp->rightChild = nullptr;
    } else {
        cout << "---> col " << strIndex << ",at the character " << str[strIndex - 1] << endl;
        cout << "error at factor -> (exp) | n, expected token is ( or num, but not found!" << endl;
        exit(EXIT_FAILURE); // 非正常退出
    }
    return temp;
}


void getToken() {
    if (strIndex < str.length()) {
        if (str[strIndex] >= '0' && str[strIndex] <= '9') {
            string tempNumStr;
            while (strIndex < str.length() && (str[strIndex] >= '0' && str[strIndex] <= '9' || str[strIndex] == '.')) {
                tempNumStr += str[strIndex];
                strIndex++;
            }
            num = tempNumStr;
            token = '0';   // token == 0 代表这个token的内容是 num
        } else { // + - * / （）
            token = str[strIndex];
            strIndex++;
        }
    } else {
        token = '$';  // 结束符
    }
}

void Error(int errorId, char expectToken) {
    string grammar[3] = {"exp -> term {addop term}", "term -> factor {mulop factor}",
                         "factor -> (exp) | n"};
    cout << "---> col " << strIndex << ",at the character " << str[strIndex - 1] << endl;
    cout << "error at " << grammar[errorId] << ", expected token is "
         << expectToken << " but not found!" << endl;
    exit(EXIT_FAILURE);  // 表示当前操作系统下未能成功退出的终止代码
}

void match(char expectToken, int errorId) {
    if (token == expectToken) {
        getToken();
    } else {
        Error(errorId, expectToken); // Error函数
    }
};

void PrintBinTree(BinTreeNode *BT) {
    if (BT != nullptr) {
        cout << BT->data;
        if (BT->leftChild != nullptr || BT->rightChild != nullptr) {
            cout << "(";
            PrintBinTree(BT->leftChild);  // 递归输出左子树
            if (BT->rightChild != nullptr) {
                cout << ",";
                PrintBinTree(BT->rightChild); // 递归输出右子树
            }
            cout << ")";
        }
    }
}

自顶向下生成语法树和汇编代码

生成汇编代码

//
// Created by Andy Dennis on 2020/12/9.
// 文法规则:
/*exp -> term {addop term}
 * addop -> + | -
 * term -> factor {mulop factor}
 * mulop -> * | /
 * factor -> (exp) | n
 * */

# include <iostream>
# include <cmath>

using namespace std;

// 全局变量token
char token;
// 待处理的字符串
string str;
// 字符串读取到的地方
int strIndex = 0;
// 存放数字
string num;
// 存放生成的汇编代码结果
string assemblyCode;

// 用到的函数, 先提前声明
void getToken();

void match(char expectToken, int errorId);

void Error(int errorId, char expectToken);

void exp();

void term();

void factor();

void gen(const string& code);

int main() {
    string examples = "3+8/2-6";
    str = examples;
    strIndex = 0;
    getToken();
    exp();
    cout << "the generation assembly code:" << endl;
    cout << assemblyCode << endl;
}

void exp() {
    char errorId = 0;
    term();
    while (token == '+' || token == '-') {
        if (token == '+') {
            match(token, errorId);
            term();
            gen("Adi");
        } else if (token == '-') {
            match(token, errorId);
            term();
            gen("Sbi");
        }
    }
}

void term() {
    char errorId = 1;
    factor();
    while (token == '*' || token == '/') {
        if (token == '*') {
            match(token, errorId);
            factor();
            gen("Mpi");
        } else if (token == '/') {
            match(token, errorId);
            factor();
            gen("Dvi");
        }
    }
}

void factor() {
    char errorId = 2;
    if (token == '(') {
        match('(', errorId);
        exp();
        match(')', errorId);
    } else if (token == '0') {
        match('0', errorId);
        gen("Ldc " + num);
    } else {
        cout << "---> col " << strIndex << ",at the character " << str[strIndex - 1] << endl;
        cout << "error at factor -> (exp) | n, expected token is ( or num, but not found!" << endl;
        exit(EXIT_FAILURE); // 非正常退出
    }
}


void getToken() {
    if (strIndex < str.length()) {
        if (str[strIndex] >= '0' && str[strIndex] <= '9') {
            string tempNumStr;
            while (strIndex < str.length() && (str[strIndex] >= '0' && str[strIndex] <= '9' || str[strIndex] == '.')) {
                tempNumStr += str[strIndex];
                strIndex++;
            }
            num = tempNumStr;
            token = '0';   // token == 0 代表这个token的内容是 num
        } else { // + - * / （）
            token = str[strIndex];
            strIndex++;
        }
    } else {
        token = '$';  // 结束符
    }
}

void Error(int errorId, char expectToken) {
    string grammar[3] = {"exp -> term {addop term}", "term -> factor {mulop factor}",
                         "factor -> (exp) | n"};
    cout << "---> col " << strIndex << ",at the character " << str[strIndex - 1] << endl;
    cout << "error at " << grammar[errorId] << ", expected token is "
         << expectToken << " but not found!" << endl;
    exit(EXIT_FAILURE);  // 表示当前操作系统下未能成功退出的终止代码
}

void match(char expectToken, int errorId) {
    if (token == expectToken) {
        getToken();
    } else {
        Error(errorId, expectToken); // Error函数
    }
};

void gen(const string& code) {
    assemblyCode += code + "\n";
}

自顶向下生成语法树和汇编代码

结语

编译原理摸爬滚打中…

自顶向下生成语法树和汇编代码

前言

生成语法树

生成汇编代码

结语

继续阅读

LEX自动生成词法分析器

lex && yacc

PERL原码分析2

vs2008中的lex&yacc

分析Perl的Lex和Yacc部分

Perl原码分析3

Cygwin环境的熟悉和lex的使用1一. 目的：二. 内容：三．要求：四．参考：五．源代码：六．结果及分析：七.附录

如何在 JavaScript 中使用宏

Android源代码编译原理与前期准备

Antlr实现任意四则运算表达式求值

【编译原理】作业十三编译原理第13次作业

编译原理上机实战---词法分析

英语语法-语法树概述

在Windows 10上将C语言程序转成16位8086汇编代码

_stdcall与_cdecl的区别 _stdcall与_cdecl的区别

Ting Machine完全指令集