自制 MC90 编译系统开发日记

写日记的原因

从下决心要自己从零开始写一个 C 语言编译器开始到现在,已经过了一个多月时间了。其实,我作为一名身负着学业的大三普通学生,基本上没有太多的时间完完全全地投入到自制编译器的开发过程中,因为只能在闲暇时构思设计方案以及实现代码,所以开发进展很缓慢,开发周期会比较长。这样的话,编写详细的代码注释和开发日记就很重要,注释能提高代码的可读性,以便于今后长期的开发工作能够可持续地进行下去,而开发日记更像是对自己在开发过程中的思路、遇到的问题进行阶段性的归纳总结。尤其像编译系统这种代码量相比原来大得多的项目,开发日记就显得更加重要。

MC90 编译系统

这个编译器的名字叫做 MC90,MC90 意思就是 “迷你的、兼容 C90 标准的编译器” (Mini C 90)。说到这儿,其实很多朋友可能会建议,可以采用更加个性的、霸气的名字来命名这个 C 语言编译器。我觉得没那个必要,因为我自认为自己水平有限,写出来的编译器配不上某些炫酷霸气的名字,而且我想编写这个编译器的初衷其实是想提高编程能力。比起炫技什么的,开发过程中的乐趣反而更加地吸引我。这份乐趣同样也是支持我学习并实践编程技术的持续动力,它有时可以使我忘记生活中的烦恼不开心的事情,在编程中获得喜悦感和成就感。而 MC90 这朴实无华的名字正合我心意。

2019年10月25日

既然要设计 C 语言编译器,那么预处理器的设计是首先需要考量的。预处理也正是 C 语言编译系统编译过程的第一步。

到目前为止,mc90 预处理器已经完成了一部分了,主要有三个模块:

行扫描器模块字符扫描器模块预处理单词扫描器模块

行扫描器模块主要由 CombinedLine 类以及 LineScanner 类组成。CombinedLine 是针对 C 语言源程序文本的、以行划分的基本数据结构,一个 CombinedLine 对象包含一个或多个 SingleLine 底层对象(封装采用 std::vector<SingleLine> 实现)。SingleLine 是 std::wstring 类的别名,CombinedLine 描述一行组合行的信息,组合行由一个或多个单行组成,这些单行除最后一行以外结尾都以行延续符 ‘\’ 结尾。

LineScanner 类提供从输入流中扫描并读取组合行的功能,它维护一个可回溯的线性容器,用于存放实际上已经被读取出的、连续的 CombinedLine 对象,其内部采用一个指示器来对底层线性结构进行抽象,并提供组合行扫描过程的回溯和前进的功能。无论如何,LineScanner 类都将保证流中的组合行对象的可回溯性和完整性。

字符扫描器模块主要由 BasicCharacterScanner 类以及 PracticalCharacterScanner 类组成。BasicCharacterScanner 以一个 CombinedLine 对象作为输入,能够扫描并读取其中的字符。这个读取过程被抽象成线性的,并且 BasicCharacterScanner 内部基于 CombinedLine 对象提供的可回溯机制,同样提供了字符的回溯和前进功能。PracticalCharacterScanner 是对 BasicCharacterScanner 的更高级的封装,PracticalCharacterScanner 能有效地过滤掉 CombinedLine 中存在的单行注释和多行注释,并返回除此之外对预处理器和编译器有实际意义的字符。

这些字符最终被封装成 CharacterInfo 数据结构,用于返回字符的值,还有字符所处的行、列的位置信息,便于调用者进行错误定位和汇报。

预处理单词扫描器模块主要由 PreToken 类和 PreTokenScanner 类组成。PreTokenScanner 内部维护一个 PracticalCharacterScanner 对象,通过对 CombinedLine 输入进行字符读取,使用一套特定的有限状态机算法实现由字符到单词的构造功能,这套算法刚好利用了 PracticalCharacterScanner 对象的可回溯机制。扫描器内部也维护了存放 PreToken 对象的线性容器。同样地,PreTokenScanner 提供了可回溯机制,使得上层模块能够在单词流中回溯或前进,这为语法分析提供了基本的数据结构和算法。

PreToken 对象是预处理单词对象,它主要描述了单词的类型和值(单词内容)以及单词的起始行号和起始列号,这些单词最终会被 PreParser 拿去用于构造语法分析树,当然,PreParser 也是通过 PreTokenScanner 来抽取这些 PreToken 对象的。

2019年10月30日

在开发过程中,我发现如果 PracticalCharacterScanner 对每一个以 CombinedLine 对象来做底层封装的 BasicCharacterScanner 进行消除注释处理,那么这个工作过程将变得十分繁琐。

首先,CombinedLine 由 LineScanner 从 std::ifstream 对象中产生 (这里我定义了别名 InputFileStream,下文都用这个别名来表示字符文件输入流),这时每一个 CombinedLine 对象都是完整的。BasicCharacterScanner 以 CombinedLine 作为输入进行字符读取,而 PracticalCharacterScanner 通过对 BasicCharacterScanner 的封装,调用其读取字符的同时也消除注释。那么,问题就出现了。

注释有行注释和块注释两种,这两种注释都可以以跨越多行的形式出现,块注释自然不用说,行注释也能通过换行之前的行延续符(反斜线“\”)实现跨越一行或者多行(除最后一行之外都使用行延续符)。

如果注释跨越多行,那么 PracticalCharacterScanner 对某一个 CombinedLine 对象的处理显然是不够的,对于跨越多行的注释消除操作,需要一次对多个 CombinedLine 对象进行处理,这样设计就会变得十分复杂。而且,LineScanner 在对 InputFileStream 进行读取并生成 CombinedLine 对象时,CombinedLine 的类型就已经被确定下来(预处理器指令行或者普通程序行),这将直接影响预处理器对此行的处理操作,预处理器只会处理预处理器指令行。那么,如果遇到某种多行注释,刚好延续到某行的预处理器指令之前,那么首先 LineScanner 是不会将此行作为预处理器指令行的,会作为普通程序行进行处理 (LineScanner 会判断一行的首个字符除空格和制表符是否是“#”号,若是,则确定是预处理器指令行,显然,这种情况下,首个非空白的字符不可能是“#”)。

除此之外,延续行符运用在单行注释上的情形,与上述情形类似。如果行注释延续到某一个注释内容的下一行,假设下一行的开头是 “#” 号 (哈哈,当然这种情况很少),按常规情况,这以 “#” 开头的一行也应该被当作注释,可惜,LineScanner “并不知晓” 它是注释行,而且会把此行当作预处理器指令行。

其实,说那么多,设计过程中的问题其实就是“剔除注释”和“确定组合行类型”的先后顺序的问题

最近我已经想到了解决方法,其实很简单,让 BasicCharacterScanner 直接对 InputFileStream 进行字符读取,PracticalCharacterScanner 基于 BasicCharacterScanner 从 InputFileStream 进行字符读取的同时,使用有限状态机算法,消除行注释和块注释,用空白字符去一一替换原有在注释内容中的字符,除了换行符之外。最后 LineScanner 将负责调用 PracticalCharacterScanner,将根据剔除了注释的字符,处理并生成 CombinedLine 对象,这时结果将是正确的。

2019年11月18日

武汉轻工大学 2019/11/18

这些天改来改去的,事情也比较多,重构了一些代码,实现了一些工具类和工具函数,最近想着全力将 PreTokenScanner 实现,朝这个方向持续推进下去吧

2019年11月23日

最近实现了 PpTrace 模块,这在长期来看是有很多好处的,程序具备了底层调试信息的输出功能,将来各个模块的 Debug 将更加容易。经过代码的堆砌,到今天为止,预处理器的词法分析器 (PreTokenScanner) 已经基本上完成了。稳定性方面的话,目前只做了一些简单的测试,PreTokenScanner 运转正常。考虑后续再做一些测试,保证 PreTokenScanner 能够产生相对稳定的单词 (Token) 流,然后就可以基于 PreTokenScanner 来进行预处理语法分析器的编写工作。哈哈,加油!

2019年12月11日

最近一些天我在编写预处理器的语法分析器,删删改改的。现在也临近期末,要准备一些专业课的复习了,不得不把时间花在复习上面,加油!可不能挂科呀。现在因为时间问题,所以最多就是一些加文档注释的工作,维护一些已经实现的模块的注释。这个学期结束后,我会再继续开发,加油!

一种C语言编译系统的实现设想

可能的方案选择

  • 1、可直接将标准C90的代码编译成特定目标机器语言(x86)的编译器
  • 2、将标准C90的代码编译成某种约定好的VM字节码的编译器,以及可执行此字节码的虚拟机

实现的大概说明

我设想用 C++ 编程语言来实现这个编译器(可能附带虚拟机)

如果要实现第二种模式的话,也需要设计一套满足具体执行需求的虚拟机指令集(Virtual Machine Instruction Set)

词法分析器、语法分析器,语义分析及代码生成器,甚至是装载器、虚拟机等模块,也得基于底层给出 C++ 类的实现,直到构造、组合成一套完整的编译系统

对于本人而言的技术难点

  • 语义分析及代码生成器这部分我曾经没有实现经验,这次实现是摸着石头过河,也是一种新的挑战
  • C90 标准的细节需要自己去更深层次地掌握,避免出现与C90标准规定不符合、不兼容的内容
  • 编译系统的实现的复杂度比较高,整体模块设计十分复杂,从底层一层一层地设计、然后加以实现、甚至是编写过程中的排错工作,对于本人也是不小的挑战

COM 学习笔记 (2) : 接口查询

IUnknown 接口概述

引述

客户对组件的了解是非常有限的,为知道某个组件是否支持某个特定的接口,客户可以在运行时询问组件。即使组件不支持所需要的某个接口,客户也可以在请求失败时很好地处理这种情形

IUnknown 接口

COM 中所有内容最终都起于接口、又最终归于接口。所有的 COM 接口都继承于 IUnknown 接口,该接口的定义如下:

// 该接口在头文件 unknwn.h 中定义,interface 是与 struct 绑定的宏,这样所有成员默认是 public 的,刚好符合接口的封装需求

interface IUnknown {
	virtual HRESULT __stdcall QueryInterface(const IID& iid, void** ppv) = 0;
	virtual ULONG __stdcall AddRef() = 0;
	virtual ULONG __stdcall Release() = 0;
};

接口查询

因为 所有的 COM 接口都继承于 IUnknown 接口,所以客户只需要一个 IUnknown 接口的指针,而且无需知道它所拥有的接口指针到底是什么类型的,就可以查询其他接口

由于所有的 COM 接口都继承了 IUnknown,所以每个接口的虚函数表(vtbl)中的前三个函数都是 QueryInterface、AddRef 和 Release。这便使得所有 COM 接口都可当做 IUnknown 接口来处理

纯虚函数 QueryInterface

IUnknown 包含一个名为 QueryInterface 的纯虚成员函数,客户可以通过此函数来查询某个组件是否支持某个特定的接口。若支持,则 QueryInterface 将返回一个指向此接口的指针,否则返回值将是一个错误代码。然后客户可以接着查询其他接口或将组件卸载

  • QueryInterface 的函数原型
HRESULT __stdcall QueryInterface(const IID &iid, void **ppv);
  • 参数 iid

iid 是一个接口标识符(IID)结构, 用于标识客户所需的接口,从客户的角度上来说,指定一个 IID 以使得 QueryInterface 函数利用此接口标识符来查询接口

  • 参数 ppv

ppv 是一个二级指针,QueryInterface 函数将存放客户所请求的接口的地址到其中

  • 返回值(HRESULT 类型)

HRESULT 是具有特定格式的 32 位值,此函数返回 S_OK 或者 E_NOINTERFACE。对其返回值进行判断时应该使用 SUCCEEDED 宏或 FAILED 宏,不应该直接比较


// 使用示例
void foo(IUnknown *pI) {
    // 为接口定义一个指针
    IX *pIX = nullptr;
    
    // 使用 IUnknown 的 QueryInterface 函数来查询接口 IX(接口标识符是 IID_IX)
    HRESULT hr = pI->QueryInterface(IID_IX, (void **)&pIX);

    // 检查返回值
    if (SUCCEEDED(hr)) {
        // 可以使用接口了 (比如调用某个函数)
        pIX->Fx();
    }
} 

QueryInterface 的实现

QueryInterface 的实现其实比较简单。它只需根据某个给定的 IID(接口标识符),返回相应接口的指针。若组件支持,函数就返回 S_OK 以及相应的接口的指针,否则函数就应返回 E_NOINTERFACE,并将指针值置为 nullptr

  • 示例代码
// 一些示例接口、实现类
interface IX : IUnknown { /*...*/ };
interface IY : IUnknown { /*...*/ };
class CA : public IX, public IY { /*...*/ };

// QueryInterface 在 CA 类上的实现
HRESULT __stdcall CA::QueryInterface(const IID &iid, void **ppv) {

    if (iid == IID_IUnknown) {
        // 客户需要 IUnknown 接口
        *ppv = static_cast<IX *>(this);

    } else if (iid == IID_IX) {
        // 客户需要 IX 接口
        *ppv = static_cast<IX *>(this);

    } else if (iid == IID_IY) {
        // 客户需要 IY 接口
        *ppv = static_cast<IY *>(this);

    } else {
        // 不支持的接口,返回 E_NOINTERFACE,并将返回指针置为 nullptr
        *ppv = nullptr;
        return E_NOINTERFACE;
    }
    
    // 增加引用计数(暂时先不关心)
    static_cast<IUnknown *>(*ppv)->AddRef();

    // 接口受支持,返回 S_OK
    return S_OK;
}

完整示例代码

// 本代码修改自《COM技术内幕》第 35 页

#include <iostream>
#include <objbase.h>

using namespace std;

void trace(const char* msg) { cout << msg << endl; }

interface IX : IUnknown {
    virtual void __stdcall Fx() = 0;
};

interface IY : IUnknown {
    virtual void __stdcall Fy() = 0;
};

interface IZ : IUnknown {
    virtual void __stdcall Fz() = 0;
};

extern const IID IID_IX;
extern const IID IID_IY;
extern const IID IID_IZ;

class CA : public IX, public IY {
    // IUnknown implementation
    virtual HRESULT __stdcall QueryInterface(const IID& iid, void** ppv);
    virtual ULONG __stdcall AddRef() { return 0; }
    virtual ULONG __stdcall Release() { return 0; }

    // Interface IX implementation
    virtual void __stdcall Fx() { cout << "Fx" << endl; }
	
    // Interface IY implementation
    virtual void __stdcall Fy() { cout << "Fy" << endl; }
};

HRESULT __stdcall CA::QueryInterface(const IID& iid, void** ppv) {
	if (iid == IID_IUnknown) {
	    trace("QueryInterface: Return pointer to IUnknown");
	    *ppv = static_cast<IX *>(this);
	}
	else if (iid == IID_IX) {
	    trace("QueryInterface: Return pointer to IX");
	    *ppv = static_cast<IX *>(this);
	}
	else if (iid == IID_IY) {
	    trace("QueryInterface: Return pointer to IY");
	    *ppv = static_cast<IY *>(this);
	}
	else {
	    trace("QueryInterface: Interface not supported.");
	    *ppv = NULL;
	    return E_NOINTERFACE;
	}

	reinterpret_cast<IUnknown *>(*ppv)->AddRef();
	return S_OK;
}

IUnknown* CreateInstance() {
	IUnknown* pI = static_cast<IX*>(new CA);
	pI->AddRef();
	return pI;
}

static const IID IID_IX = 
{ 0x32bb8320, 0xb41b, 0x11cf, {0xa6, 0xbb, 0x0, 0x80, 0xc7, 0xb2, 0xd6, 0x82} };

static const IID IID_IY =
{ 0x32bb8321, 0xb41b, 0x11cf, {0xa6, 0xbb, 0x0, 0x80, 0xc7, 0xb2, 0xd6, 0x82} };

static const IID IID_IZ =
{ 0x32bb8322, 0xb41b, 0x11cf, {0xa6, 0xbb, 0x0, 0x80, 0xc7, 0xb2, 0xd6, 0x82} };

int main() {
    HRESULT hr;
    trace("Client: Get an IUnknown pointer.");
    IUnknown* pIUnknown = CreateInstance();

    trace("Client: Get interface IX.");
    IX *pIX = NULL;
    hr = pIUnknown->QueryInterface(IID_IX, (void**)& pIX);
    if (SUCCEEDED(hr)) {
        trace("Client: Succeeded getting IX.");
        pIX->Fx();
    }

    trace("Client: Get interface IY.");
    IY *pIY = NULL;
    hr = pIUnknown->QueryInterface(IID_IY, (void**)& pIY);
    if (SUCCEEDED(hr)) {
        trace("Client: Succeeded getting IY.");
        pIY->Fy();
    }

    trace("Client: Ask for an unsupported interface.");
    IZ *pIZ = NULL;
    hr = pIUnknown->QueryInterface(IID_IZ, (void**)& pIZ);
    if (SUCCEEDED(hr)) {
        trace("Client: Succeeded getting IZ.");
        pIZ->Fz();
    }
    else {
        trace("Client: Could not get interface IZ.");
    }

    trace("Client: Get interface IY from interface IX.");
    IY *pIYfromIX = NULL;
    hr = pIX->QueryInterface(IID_IY, (void**)& pIYfromIX);

    if (SUCCEEDED(hr)) {
        trace("Client: Succeeded getting IY.");
        pIYfromIX->Fy();
    }

    trace("Client: Get interface IUnknown from IY.");
    IUnknown *pIUnknownFromIY = NULL;
    hr = pIX->QueryInterface(IID_IUnknown, (void**)& pIUnknownFromIY);
    if (SUCCEEDED(hr)) {
        cout << "Are the IUnknown pointers equal?    ";
        if (pIUnknownFromIY == pIUnknown) {
	    cout << "Yes, pIUnknownFromIY == pIUnknown." << endl;
        }
        else {
            cout << "No, pIUnknownFromIY != pIUnknown." << endl;
        }
    }

    delete pIUnknown;
    return 0;
}

若运行将有如下输出结果

Client: Get an IUnknown pointer.
Client: Get interface IX.
QueryInterface: Return pointer to IX
Client: Succeeded getting IX.
Fx
Client: Get interface IY.
QueryInterface: Return pointer to IY
Client: Succeeded getting IY.
Fy
Client: Ask for an unsupported interface.
QueryInterface: Interface not supported.
Client: Could not get interface IZ.
Client: Get interface IY from interface IX.
QueryInterface: Return pointer to IY
Client: Succeeded getting IY.
Fy
Client: Get interface IUnknown from IY.
QueryInterface: Return pointer to IUnknown
Are the IUnknown pointers equal?    Yes, pIUnknownFromIY == pIUnknown.

参考资料

[1] (美)Dale Rogerson , 李忠 , 王晓波 . COM 技术内幕 – 微软组件对象模型 [M] . 北京 : 清华大学出版社 , 1991.

COM 学习笔记 (1) : COM 简明概念

COM 的简明概念

面向组件编程的优点

  • 应用的可定制性

用户希望能够定制他们的应用,而程序员可以为用户建立应用定制方案 —— 通过组件架构本身的可定制性(用户能使用需要的组件来将某个组件替换掉)

  • 组件库

组件架构拥有快速应用开发的优点,程序员可以某个组件库中取出所需的组件并将其快速地组装到一起,构造出所需的应用(如同搭积木)

  • 分布式组件

对于 C/S(客户机 / 服务器)模式的应用而言,应用已经被划分成位于远程的各个功能部分,因为任一组件均可做替换,所以可以将某个组件替换为专门负责同某个远程组件通信的组件

COM 的特点

COM 可以满足前面讨论过的所有组件架构的要求。它使用 DLL 来提供可在运行时被替换掉的组件。COM 借助于如下一些手段保证这些组件可以充分利用动态链接所带来的各种好处

  • 提供了一个所有组件都应遵守的标准
  • 允许使用组件的多个不同的版本,而且这一点对于客户机而言几乎是透明的
  • 使得可以按相同的方式来处理类似的组件
  • 定义了一个与语言无关的架构
  • 支持对远程组件的透明链接

COM 接口(Interface)

在 COM 中,接口是一个包含一个函数指针数组的结构,数组的每一个元素包含的是一个由组件实现的函数的地址

对 COM 而言,接口就是这个内存结构,其他的都不是 COM 需要关心的细节

在 C++ 中,我们使用抽象基类(abstract base class)来实现 COM 接口

因为一个 COM 组件可以支持任意数目的接口,因为对于此类组件,应使用抽象基类的多重继承来实现之

COM 接口的关键要素

  • COM 接口在 C++ 中是用纯抽象基类实现的
  • 一个 COM 组件可以支持多个接口
  • 一个 C++ 类可以使用多继承来实现多个接口的组件

参考资料

[1] (美)Dale Rogerson , 李忠 , 王晓波 . COM 技术内幕 – 微软组件对象模型 [M] . 北京 : 清华大学出版社 , 1991.