語義分析實戰：Python 實現 C 表達式語法樹生成（遞歸轉迭代）

核心挑戰：遞歸語法的迭代化

語義分析難點在於運算符優先級與結合性導致的深層遞歸。關鍵在於識別最深層遞歸結構特徵，將其迭代化，再自底向上處理高優先級運算符。

運算符優先級表（共 13 級）

語法樹節點資料結構

# 節點類型標記
'@var'  : 變數      ["@var", "name"]
'@num'  : 常數      ["@num", "123"]
'@expr' : 運算式    ["@expr", "運算符", 左子樹, 右子樹...]
'@func' : 函數調用  ["@func", "funcName", 參數列表]
'@expr_list' : 運算式列表

核心演算法：parse_simple_expr（無括號/函數）

def parse_simple_expr(lis):
    # 自優先級 1 到 11 迭代處理一元/二元運算符
    for pri in range(1, 12):
        i = 0
        while True:
            if len(lis) == 1 and lis[0][0][0] == '@': return 0  # 歸約完成
            if i >= len(lis): break
            if lis[i][0] in operator_priority_tuple[pri]:
                if module_dic_tuple[pri][lis[i][0]](lis, i) == 0:
                    i = 0  # 成功歸約，重掃
                    continue
            i += 1

    # 優先級 12：三元運算符 ?:
    # 優先級 13：逗號運算符
    return module_dic_tuple[13][','](lis, 0)

每個 module_x_y 函數負責特定運算符的歸約邏輯（彈出操作數、建立 @expr 節點、替換列表片段）。

處理括號與函數調用：parse_comp_expr

def parse_comp_expr(lis):
    while True:
        if len(lis) == 1 and lis[0][0][0] == '@': return 0
        place = module_parenthesis_place(lis)  # 找最內層匹配括號
        if place[0] == 0:
            mirror = lis[place[1]+1 : place[2]]  # 括號內內容
            if parse_simple_expr(mirror) == 0:   # 遞歸處理內部
                # 函數調用檢測：前一個 token 為 @var
                if place[1] >= 1 and lis[place[1]-1][0] == '@var':
                    funcName = lis[place[1]-1][1]
                    del lis[place[1]-1 : place[2]+1]
                    lis.insert(place[1]-1, ["@func", funcName, mirror[0]])
                else:
                    del lis[place[1] : place[2]+1]
                    lis.insert(place[1], mirror[0])
            else: return 1  # 語法錯誤
        else:
            return parse_simple_expr(lis)  # 無括號，直接處理
    return 1

實驗驗證

>> ls = [['(',None],['@var','f'],['(',None],['@num','1'],[,None],['@num','2'],[,None],['@num','3'],[,None],['!',None],['-',None],['@var','x'],['?',None],['@var','y'],[:,None],['~',None],['@var','z'],[')',None],['-',None],['@num','3'],[')',None],['/',None],['@num','4']]
>>> parse_comp_expr(ls)
0
>>> ls
[['@expr', '/', ['@expr', '-', ['@func', 'f', ['@expr_list', ['@num','1'], ['@num','2'], ['@num','3'], ['@expr', '?:', ['@expr', '!', ['@expr', '-', ['@var','x']]], ['@var','y'], ['@expr', '~', ['@var','z']]]]], ['@num','3']], ['@num','4']]]

成功將複雜表達式 f(1,2,3,!-x?y:~z)-3/4 轉換為結構化語法樹。

總結

• 遞歸下降解析器易理解但難處理左遞歸；本文採用運算符優先級解析（算符優先文法），以迭代替代遞歸。
• 關鍵技術：Token 列表就地歸約、優先級驅動的多遍掃描、括號匹配與函數調用識別。
• 代碼模組化：每優先級一組處理函數，擴展新運算符只需增函數並註冊字典。
• Python 動態列表特性極適合此類符號操作原型開發。