随笔-341  评论-2670  文章-0  trackbacks-0

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

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

posted on 2012-11-29 00:50 陈梓瀚(vczh) 阅读(5556) 评论(6)  编辑 收藏 引用 所属分类: C++

评论:
# re: 可配置语法分析器开发纪事(二)&mdash;&mdash;构造符号表 2012-11-29 09:21 | ooseven
我说的语法树的构造让用户自己在bnf里决定,并不是说语法树不重要或者大部分都不需要,而恰恰相反,就是因为语法树太重要了,所以,应该让用户自己决定语法树的结构,尝试构造一颗在符合任何场景,任何用户需求的语法树我觉得非必要之举。而且在bnf里定义语法树其实也就是在bnf脚本里多写一行#include语句而已,很简单。
如果,设计一个语法生成器的目的只是让作者自己使用,那当然无可非议,但是,如果想构造一个通用的语法生成器,则有过度设计之嫌。个人意见,不一定正确哈,不要生气。
  回复  更多评论
  
# re: 可配置语法分析器开发纪事(二)&mdash;&mdash;构造符号表 2012-11-29 11:50 | 陈梓瀚(vczh)
@ooseven
我没有生气哈。话说回来,难道我的语法树不是通过用户自己声明的吗,看上一篇文章。通用的语法树只是parse出来的结果而已,然后我在根据用户自己声明的语法树生成的C++代码里面,会包含一个转换过程,这样用户无论如何拿到的都是自己的语法树(当然他不做转换也可以)。  回复  更多评论
  
# re: 可配置语法分析器开发纪事(二)&mdash;&mdash;构造符号表 2012-11-29 14:16 | phoenixbing
老大,你的博客很好,代码很好,但是我们有时候消化不了这么快,有时候想找人交流交流,却找不到,我建议你建立一个群,把群号放在博客首页,这样研究你源码的人会聚集在一起,大家也可以讨论,你也不需要参与讨论,甚至你不在群里都可以,毕竟你时间有限,你还要去微博灌水,二次元啥的。

这样你也没啥损失。但对祖国的编译器苦手们就大有帮助。

你的开源代码已经够多了,也需要一个粉丝群了吧。

盼考虑。祝健康。  回复  更多评论
  
# re: 可配置语法分析器开发纪事(二)&mdash;&mdash;构造符号表 2012-11-29 18:31 | 陈梓瀚(vczh)
@phoenixbing
这个嘛,我考虑考虑……  回复  更多评论
  
# re: 可配置语法分析器开发纪事(二)&mdash;&mdash;构造符号表 2012-11-29 21:20 | P
各种理论和事实证明:群不是一个技术讨论的好载体啊。。  回复  更多评论
  
# re: 可配置语法分析器开发纪事(二)&mdash;&mdash;构造符号表 2012-11-30 13:55 | Zblc(邱震钰)
@P
个人觉得还是可以的  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理