当前位置:天才代写 > tutorial > C语言/C++ 教程 > 可设置语法阐明器开拓纪事(二) 结构标记表

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

2017-11-02 08:00 星期四 所属: C语言/C++ 教程 浏览:52

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

 

    关键字:


天才代写-代写联系方式