可设置语法阐明器开拓纪事（二） 结构标记表

副标题#e#

上一篇博客讲到告终构语法树的问题。有伴侣在留言问我，为什么必然要让语法阐明器发生语法树，而不是让用户本身抉择要怎么办呢？在这里我先解答这个问题。

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);
};

本栏目

#p#副标题#e#

因为文礼貌则自己的对象也不多，所以这里的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。这就是所有标记都有的共性。

#p#分页标题#e#

虽然，有了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不太一样，领略起来略有难度。所以我想需要用单独的一篇文章来通俗的讲一讲。