可配置语法分析器开发纪事（二）——构造符号表

时间：2022-06-29 16:46:55

上一篇博客讲到了构造语法树的问题。有朋友在留言问我，为什么一定要让语法分析器产生语法树，而不是让用户自己决定要怎么办呢？在这里我先解答这个问题。

1、大部分情况下都是真的需要有语法树
2、如果要直接返回计算结果之类的事情的话，只需要写一个visitor运行一下语法树就好了，除去自动生成的代码以外（反正这不用人写，不计入代价），代码量基本上没什么区别
3、加入语法树可以让文法本身描述起来更简单，如果要让程序员把文法单独放在一边，然后自己写完整的语义函数来让他生成语法树的话，会让大部分情况（需要语法树）变得特别复杂，而少数情况（不需要语法树）又没有获得什么好处。

尽管类似yacc这样的东西的确是不包含语法树的内容而要你自己写的，但是用起来难道不是很难受吗？

现在转入正题。这一篇文章讲的主要是构造符号表的问题。想要把符号表构造的好是一件很麻烦的问题。我曾经尝试过很多种方法，包括强类型的符号表，弱类型的符号表，基于map的符号表等等，最后还是挑选了跟Visual Studio自带的用来读pdb文件的DIA类其中的IDIASymbol（http://msdn.microsoft.com/en-us/library/w0edf0x4.aspx）基本上一样的结构：所有的符号都只有这么一个symbol类，然后包罗万象，什么都有。为什么最后选择这么做呢？因为在做语义分析的时候，其实做的最多的事情不是构造符号表，而是查询符号表。如果符号表是强类型的画，譬如说类型要一个类，变量要一个类，函数要一个类之类的，总是需要到处cast来cast去，也找不到什么好方法来在完成相同事情的情况下，保留强类型而不在代码里面出现cast。为什么语法树就要用visitor来解决这个问题，而符号表就不行呢？因为通常我们在处理语法树的时候都是递归的形式，而符号表并不是。在一个上下文里面，实际上我们是知道那个symbol对象究竟是什么东西的（譬如说我们查询了一个变量的type，那这返回值肯定只能是type了）。这个时候我们要cast才能用，本身也只是浪费表情而已。这个时候，visitor模式就不是和面对这种情况了。如果硬要用visitor模式来写，会导致语义分析的代码分散得过于离谱导致可读性几乎就丧失了。这是一个辩证的问题，大家可以好好体会体会。

说了这么一大段，实际上就是怎么样呢？让我们来看“文法规则”本身的符号表吧。既然这个新的可配置语法分析器也是通过parse一个文本形式的文法规则来生成parser，那实际上就跟编译器一样要经历那么多阶段，其中肯定有符号表：

class ParsingSymbol : public Object
{
public:
    enum SymbolType
    {
        Global,
        EnumType,
        ClassType,        // descriptor == base type
        ArrayType,        // descriptor == element type
        TokenType,
        EnumItem,        // descriptor == parent
        ClassField,        // descriptor == field type
        TokenDef,        // descriptor == token type
        RuleDef,        // descriptor == rule type
    };
public:
    ~ParsingSymbol();

    ParsingSymbolManager*            GetManager();
    SymbolType                        GetType();
    const WString&                    GetName();
    vint                            GetSubSymbolCount();
    ParsingSymbol*                    GetSubSymbol(vint index);
    ParsingSymbol*                    GetSubSymbolByName(const WString& name);
    ParsingSymbol*                    GetDescriptorSymbol();
    ParsingSymbol*                    GetParentSymbol();
    bool                            IsType();
    ParsingSymbol*                    SearchClassSubSymbol(const WString& name);
    ParsingSymbol*                    SearchCommonBaseClass(ParsingSymbol* classType);
};

因为文法规则本身的东西也不多，所以这里的symbol只能是上面记载的9种对象。这些对象其实特别的相似，所以我们可以看出唯一的区别就是当GetType返回值不一样的时候，GetDescriptorSymbol返回的对象的意思也不一样。而这个区别记载在了enum SymbolType的注释里面。实际上这种做法在面对超级复杂的符号表（考虑一下C++编译器）的时候并不太好。那好的做法究竟是什么呢？看上面IDIASymbol的链接，那就是答案。

不可否认，微软设计出来的API大部分还是很有道理的，除了Win32的原生GUI部分。

我们还可以看到，这个ParsingSymbol类的几乎所有成员函数都是用来查询这个Symbol的内容的。这里还有两个特殊的函数，就是SearchClassSubSymbol和SearchCommonBaseClass——当且仅当symbol是ClassType的时候才起作用。为什么有了GetSubSymbolByName，还要这两个api呢？因为我们在搜索一个类的成员的时候，是要搜索他的父类的。而一个类的父类的sub symbol并不是类自己的sub symbol，所以就有了这两个api。所谓的sub symbol的意思现在也很明了了。enum类型里面的值就是enum的sub symbol，成员变量是类的sub symbol，总之只要是声明在一个符号内部的符号都是这个符号的sub symbol。这就是所有符号都有的共性。

当然，有了ParsingSymbol，还要有他的manager才可以完成整个符号表的操作：

class ParsingSymbolManager : public Object
{
public:
    ParsingSymbolManager();
    ~ParsingSymbolManager();

    ParsingSymbol*                    GetGlobal();
    ParsingSymbol*                    GetTokenType();
    ParsingSymbol*                    GetArrayType(ParsingSymbol* elementType);

    ParsingSymbol*                    AddClass(const WString& name, ParsingSymbol* baseType, ParsingSymbol* parentType=0);
    ParsingSymbol*                    AddField(const WString& name, ParsingSymbol* classType, ParsingSymbol* fieldType);
    ParsingSymbol*                    AddEnum(const WString& name, ParsingSymbol* parentType=0);
    ParsingSymbol*                    AddEnumItem(const WString& name, ParsingSymbol* enumType);
    ParsingSymbol*                    AddTokenDefinition(const WString& name);
    ParsingSymbol*                    AddRuleDefinition(const WString& name, ParsingSymbol* ruleType);

    ParsingSymbol*                    CacheGetType(definitions::ParsingDefinitionType* type, ParsingSymbol* scope);
    bool                            CacheSetType(definitions::ParsingDefinitionType* type, ParsingSymbol* scope, ParsingSymbol* symbol);
    ParsingSymbol*                    CacheGetSymbol(definitions::ParsingDefinitionGrammar* grammar);
    bool                            CacheSetSymbol(definitions::ParsingDefinitionGrammar* grammar, ParsingSymbol* symbol);
    ParsingSymbol*                    CacheGetType(definitions::ParsingDefinitionGrammar* grammar);
    bool                            CacheSetType(definitions::ParsingDefinitionGrammar* grammar, ParsingSymbol* type);
};

这个ParsingSymbolManager有着符号表管理器的以下两个典型作用

1、创建符号。
2、讲符号与语法树的对象绑定起来。譬如说我们在一个context下面推导了一个expression的类型，那下次对于同样的context同样的expression就不需要再推导一次了（语义分析有很多个pass，对同一个expression求类型的操作经常会重复很多次），把它cache下来就可以了。
3、搜索符号。具体到这个符号表，这个功能被做进了ParsingSymbol里面。
4、保存根节点。GetGlobal函数就是干这个作用的。所有的根符号都属于global符号的sub symbol。

因此我们可以怎么使用他呢？首先看上面的Add函数。这些函数不仅会帮你在一个符号表里面添加一个sub symbol，还会替你做一些检查，譬如说阻止你添加相同名字的sub symbol之类的。语法树很复杂的时候，很多时候我们有很多不同的方法来给一个符号添加子符号，譬如说C#的成员变量和成员函数。成员变量不能同名，成员函数可以，但是成员函数和成员变量却不能同名。这个时候我们就需要把这些添加操作封装起来，这样才可以在处理语法树（声明一个函数的方法可以有很多，所以添加函数符号的地方也可以有很多）的时候不需要重复写验证逻辑。

其次就是Cache函数。其实Cache函数这么写，不是用来直接调用的。举个例子，在分析一个文法的时候，我们需要把一个“类型”语法树转成一个“类型”符号（譬如说要决定一个文法要create什么类型的语法树节点的时候）。因此就有了下面的函数：

ParsingSymbol* FindType(Ptr<definitions::ParsingDefinitionType> type, ParsingSymbolManager* manager, ParsingSymbol* scope, collections::List<Ptr<ParsingError>>& errors)
{
    ParsingSymbol* result=manager->CacheGetType(type.Obj(), scope);
    if(!result)
    {
        FindTypeVisitor visitor(manager, (scope?scope:manager->GetGlobal()), errors);
        type->Accept(&visitor);
        result=visitor.result;
        manager->CacheSetType(type.Obj(), scope, result);
    }
    return result;
}

很明显，这个函数做的事情就是，查询一个ParsingDefinitionType节点有没有被查询过，如果有直接用cache，没有的话再从头计算他然后cache起来。因此这些Cache函数就是给类似FindType的函数用的，而语义分析的代码则直接使用FindType，而不是Cache函数，来获取一个类型的符号。聪明的朋友们可以看出来，这种写法蕴含着一个条件，就是语法树创建完就不会改了（废话，当然不会改！）。

这一篇的内容就讲到这里了。现在的进度是正在写文法生成状态机的算法。下一篇文章应该讲的就是状态机究竟是怎么运作的了。文法所需要的状态机叫做下推状态机（push down automaton），跟regex用的NFA和DFA不太一样，理解起来略有难度。所以我想需要用单独的一篇文章来通俗的讲一讲。

标签：

相关文章