上一篇博客講到了構造語法樹的問題。有朋友在留言問我，為什么一定要讓語法分析器產生語法樹，而不是讓用戶自己決定要怎么辦呢？在這里我先解答這個問題。
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) 閱讀(6837)
評論(6) 編輯 收藏 引用 所屬分類:
C++