上一篇博客讲到了构造语法树的问题。有朋友在留言问我，为什么一定要让语法分析器产生语法树，而不是让用户自己决定要怎么办呢？在这里我先解答这个问题。
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-28 08:50
陈梓瀚(vczh) 阅读(6807)
评论(6) 编辑 收藏 引用 所属分类:
C++