? ? ? ? 繞來繞去，千辛萬苦，我們終于創(chuàng)建了抽象語法樹，完成了對整個(gè)源代碼結(jié)構(gòu)性的分析，似乎可以喘一口氣了。但是，對于下面的代碼：
int main()
{
a = 1;
return;
}
可以得到下面的抽象語法樹圖示：
但并不代表代碼已經(jīng)沒有語法錯(cuò)誤了。很明顯，因?yàn)檫@里并沒有定義變量
a，而且函數(shù)也沒有返回值。針對這樣的情況，還需要對代碼進(jìn)行進(jìn)一步的檢查。? ? ? ? 在進(jìn)行檢查之前，我們先研究如何遍歷這棵樹。回顧一下，我們使用
AST派生出多種節(jié)點(diǎn)來存儲各種不同的表達(dá)式、聲明和語句。比如存儲函數(shù)定義的節(jié)點(diǎn)FunctionDefn：
class FunctionDefn(AST):
"""A node representing a function definition"""
def __init__(self, declaration, body):
self.name = declaration.name
self.type = declaration.type
self.return_type = declaration.type.child
self.body = body
是由多個(gè)其它類型的節(jié)點(diǎn)組成，并且相互之間存在聯(lián)系。對訪問函數(shù)體而言，其實(shí)就是訪問CompoundStatement節(jié)點(diǎn)。而該節(jié)點(diǎn)則由更多的聲明節(jié)點(diǎn)Declaration和具體的語句節(jié)點(diǎn)如IfStatement組成。因此，可以從根節(jié)點(diǎn)出發(fā)，按照節(jié)點(diǎn)的具體類型進(jìn)行逐次地遍歷。基于這種方法，我們引入python中的屬性函數(shù)getattr()，進(jìn)行如下設(shè)計(jì)：
- 修改模板節(jié)點(diǎn)
class AST(object):
...
def visit(self, visitor):
return self.dig_visit(self.__class__, visitor)
def dig_visit(self, node, visitor):
"""appending the class' name with 'visit_'"""
method_name = 'visit_' + node.__name__
visitor_method = getattr(visitor, method_name, None)
if visitor_method is None:
# call the class's superclass
bases = node.__bases__
last = None
for child in bases:
last = self.dig_visit(child, visitor)
return last
else:
return visitor_method(self)
我們將從當(dāng)前節(jié)點(diǎn)出發(fā)，遍歷所有用visit_前綴和具體節(jié)點(diǎn)類名組成的定義在visitor中的函數(shù)，稱之為節(jié)點(diǎn)函數(shù)，如果沒有對應(yīng)的實(shí)現(xiàn)，則會往父類方向遍歷，直到模板節(jié)點(diǎn)AST為止，因?yàn)槲覀儠x一個(gè)模板節(jié)點(diǎn)的函數(shù)，以阻止遍歷往更基類的方向進(jìn)行。
? ? ? ? 有了上面遍歷抽象語法樹的方式，我們將語義分析分成聲明檢查、流程檢查和類型檢查三個(gè)部分進(jìn)行分別檢查。
6.1 聲明檢查
? ? ? ? 簡單地說，就是看變量使用之前是否已經(jīng)被聲明。由于C語言允許在不同作用域定義同名變量。因此，這部分檢查還需要考慮作用域，其一般用大括號對{}劃分。我們先定義一個(gè)這樣的作用域類：
class ScopedSymbolTable:
"""scoped symbol table for look up"""
def __init__(self, enclosing_scope=None):
self._symbols = {}
self.enclosing_scope = enclosing_scope
# insert symbols
def insert(self, name, value):
"""add symbol with the given value"""
if name in self._symbols:
if not self._symbols[name].type == value.type:
comment = f"Variable '{name}' has declared before."
raise Exception(comment)
self._symbols[name] = value
# look up symbols
def lookup(self, name):
symbol = self._symbols.get(name)
if symbol is not None:
return symbol
# recursively go up the chain and lookup the name
if self.enclosing_scope is not None:
return self.enclosing_scope.lookup(name)
else:
return None
其中，symbols用來存儲所有聲明的變量，而每一個(gè)作用域enclosing_scope都會有自己的_symbols。整個(gè)類型檢查的邏輯就是：變量在聲明的時(shí)候，會被插入到當(dāng)前作用域的_symbols中。當(dāng)某個(gè)變量被使用的時(shí)候，則用lookup進(jìn)行查找，如果不能在當(dāng)前或者更上一層的作用域范圍內(nèi)找到，則可以判斷該變量沒有被聲明。那么，剩下的任務(wù)就是遍歷抽象語法樹，找到可能存在變量聲明和使用的地方。
? ? ? ? 接下來，我們開始遍歷抽象語法樹。首先定義如下的類：
class NodeVisitor(object):
def visit(self, node):
return node.visit(self)
def visit_list(self, _list):
"""like NodeList in parser"""
last = None
for child in _list:
last = child.visit(self)
return last
class SymbolTableVisitor(NodeVisitor):
def __init__(self):
self.current_scope = None
def push_table(self, node):
"""push the current_scope into stack and create a child scope"""
self.current_scope = ScopedSymbolTable(
enclosing_scope=self.current_scope
)
def pop_table(self):
"""restore the parent scope"""
self.current_scope = self.current_scope.enclosing_scope
基類NodeVisitor的引入有助于我們調(diào)用getattr()獲取當(dāng)前的visit_函數(shù)。同時(shí)，我們使用push和pop方法來保護(hù)當(dāng)前父作用域，同時(shí)創(chuàng)建出新的子作用域。例如，CompoundStatement節(jié)點(diǎn)中會引入大括號，從而將引入新的作用域，因此訪問這個(gè)節(jié)點(diǎn)函數(shù)時(shí)，我們需要先將當(dāng)前作用域壓入棧，創(chuàng)建新的作用域，然后訪問組成它的節(jié)點(diǎn)，訪問完畢再從棧中彈出父作用域，這樣就有效地保護(hù)了不同作用域聲明的變量。
? ? ? ? 考慮這部分最開頭的源代碼，我們在SymbolTableVisitor中定義所關(guān)心的可能會包含變量的節(jié)點(diǎn)函數(shù)：
def visit_AST(self, node):
pass
"""root"""
def visit_TranslationUnit(self, node):
"""the entry of the file"""
self.current_scope = ScopedSymbolTable(
enclosing_scope=self.current_scope
)
self.visit_NodeList(node)
node.scope_symbol = self.current_scope
"""for all list derived from NodeList, eg. DeclarationList."""
def visit_NodeList(self, node):
self.visit_list(node.nodes)
"""expressions"""
def visit_BinOp(self, node):
node.left.visit(self)
node.right.visit(self)
"""functions"""
def visit_FunctionDefn(self, node):
self.add_symbol(node)
self.push_table(node)
node.body.visit(self)
self.pop_table()
"""statements"""
def visit_CompoundStatement(self, node):
self.push_table(node)
node.declarations.visit(self)
node.statements.visit(self)
self.pop_table()
def visit_ExpressionStatement(self, node):
node.expr.visit(self)
def visit_ReturnStatement(self, node):
node.expr.visit(self)
上面函數(shù)名前綴為visit_的即為節(jié)點(diǎn)函數(shù)。從visit_TranslationUnit進(jìn)入，通過visit函數(shù)，我們會遍歷以下的節(jié)點(diǎn)函數(shù)：
visit_TranslationUnit -> visit_FunctionDefn->visit_CompoundStatement\
->visit_ExpressionStatement->visit_BinOp->visit_AST
那么，我們?nèi)绾闻袛嘧兞渴欠袷褂弥耙呀?jīng)聲明了呢？
def visit_Id(self, node):
symbol = self.current_scope.lookup(node.expr)
if symbol is None:
comment = f"Identifier '{node.expr}' not found."
raise Exception(comment)
由于所有的變量都用節(jié)點(diǎn)Id存儲，訪問BinOp之后將訪問Id，從而檢查出對應(yīng)的問題。如果對源代碼進(jìn)行修改如果，在最上面添加：
int a;
那么，我們遍歷到聲明節(jié)點(diǎn)，并通過visit_Declaration插入變量：
"""declarations"""
def visit_Declaration(self, node):
self.current_scope.insert(node.name, node)
當(dāng)再次經(jīng)由BinOp訪問Id時(shí)，就能夠找到對應(yīng)的已經(jīng)聲明的變量了。
? ? ? ? 但是，我們研究的這段源代碼中還有一個(gè)問題尚未解決：返回值檢查。這部分內(nèi)容，將在下一部分的流程檢查中進(jìn)行。
實(shí)現(xiàn)簡易的C語言編譯器（part 0）
實(shí)現(xiàn)簡易的C語言編譯器（part 1）
實(shí)現(xiàn)簡易的C語言編譯器（part 2）
實(shí)現(xiàn)簡易的C語言編譯器（part 3）
實(shí)現(xiàn)簡易的C語言編譯器（part 4）
實(shí)現(xiàn)簡易的C語言編譯器（part 5）
實(shí)現(xiàn)簡易的C語言編譯器（part 6）
實(shí)現(xiàn)簡易的C語言編譯器（part 7）
實(shí)現(xiàn)簡易的C語言編譯器（part 9）
實(shí)現(xiàn)簡易的C語言編譯器（part 10）
實(shí)現(xiàn)簡易的C語言編譯器（part 11）
