编译器实现之旅——第十七章 终章

经过漫长的旅途,我们的编译期实现之旅终于到达了终点。感慨之余,就让我们最后一次共同回顾与展望这段遥远的旅程吧。

1. 回顾与展望

在编译器实现之旅的最初几章中,我们手写了一个针对CMM语言的词法分析器。实际上,我们使用的是一种被称为“手工编码的词法分析器”的实现方案。词法分析器实际上是具有通过程序进行自动生成的能力的,这部分内容主要包括正则表达式,有穷自动机及其相关算法等。

接着,我们手写了一个CMM语言的语法分析器。这里,我们使用的是一种被称为“递归下降的语法分析器”的实现方案。语法分析器的实现方案非常多,且同样具有通过程序进行自动生成的能力,这部分内容主要包括LR分析及其相关算法等。

此外,我们在实现语法分析器时也刻意的略过了形式化的消除左递归,以及形式化的获取First集合的方法;此外,我们还忽略了诸如提取左因子,Follow集合等内容。

在接下来的后端旅程中,我们看到了符号表、虚拟机、代码生成器等等这些名词究竟是什么样的一些东西。我想,最令人惊讶的便是:我们仅仅使用了如此简单的一台虚拟机和一套指令集,就实现了一门其实也并不是很简单的语言。此间往事与回味,就待读者慢慢思考与感悟了...

2. 测试程序

最后,我们给出两个适用于CMM编译器的测试程序。

第一个程序用于计算两数的最大公约数:

/*
    A program to perform Euclid's
    Algorithm to compute greatest common divisor.
*/

/*//////////////////////////////////////////////////////////////////////////////
// Calc Greatest Common Divisor
//////////////////////////////////////////////////////////////////////////////*/

int CalcGreatestCommonDivisor(int lhs, int rhs)
{
    if (rhs == 0)
    {
        return lhs;
    }
    else return CalcGreatestCommonDivisor(rhs, lhs - lhs / rhs * rhs);
}


/*//////////////////////////////////////////////////////////////////////////////
// Main Program Define
//////////////////////////////////////////////////////////////////////////////*/

void main(void)
{
    int lhs;
    int rhs;

    lhs = input();
    rhs = input();

    output(CalcGreatestCommonDivisor(lhs, rhs));
}

第二个程序实现了一个选择排序算法:

/*
    A program to perform selection sort on a 10
    element array.
*/

/*//////////////////////////////////////////////////////////////////////////////
// Global Variable Define
//////////////////////////////////////////////////////////////////////////////*/

int globalNumArray[10];


/*//////////////////////////////////////////////////////////////////////////////
// Get Min Index
//////////////////////////////////////////////////////////////////////////////*/

int getMinIdx(int numArray[], int beginIdx, int endIdx)
{
    int minIdx;
    int minNum;
    int nowIdx;

    minIdx = beginIdx;
    minNum = numArray[beginIdx];
    nowIdx = beginIdx + 1;

    while (nowIdx < endIdx)
    {
        if (numArray[nowIdx] < minNum)
        {
            minIdx = nowIdx;
            minNum = numArray[nowIdx];
        }

        nowIdx = nowIdx + 1;
    }

    return minIdx;
}


/*//////////////////////////////////////////////////////////////////////////////
// Sort Num List
//////////////////////////////////////////////////////////////////////////////*/

void sortNumList(int numArray[], int beginIdx, int endIdx)
{
    int nowIdx;
    int minIdx;
    int tmpNum;

    nowIdx = beginIdx;

    while (nowIdx < endIdx - 1)
    {
        minIdx = getMinIdx(numArray, nowIdx, endIdx);
        tmpNum = numArray[minIdx];
        numArray[minIdx] = numArray[nowIdx];
        numArray[nowIdx] = tmpNum;
        nowIdx = nowIdx + 1;
    }
}


/*//////////////////////////////////////////////////////////////////////////////
// Main Program Define
//////////////////////////////////////////////////////////////////////////////*/

void main(void)
{
    int idx;

    idx = 0;

    while (idx < 10)
    {
        globalNumArray[idx] = input();
        idx = idx + 1;
    }

    sortNumList(globalNumArray, 0, 10);

    idx = 0;

    while (idx < 10)
    {
        output(globalNumArray[idx]);
        idx = idx + 1;
    }
}

注:本文实现的CMM编译器的完整源代码可于本文作者的Github站点查看:https://github.com/yingyulou/CMM

上一篇:php开发一套随机调取全网壁纸内容


下一篇:web版电子表格二