語義分析實戰：C 語言表達式語法樹生成器 Python 實現 (算術/邏輯/三元/函數調用)

編輯：關於C語言

專案目標

實現一個 C 語言表達式的語義分析器，將 Token 序列轉換為抽象語法樹 (AST)，支援：

一元運算符：+ - ! ~
二元運算符：* / % + - << >> < <= > >= == != & ^ | && ||
三元運算符：? :
逗號運算符：,
括號分組：( )
函數調用：func(arg1, arg2...)
變量、數字字面量

核心難點：遞歸下降 vs 算符優先級解析

表達式文法天然左遞歸，直接遞歸下降會無限遞歸。本實現採用迭代式算符優先級解析 (Operator Precedence Parsing)，將遞歸問題轉化為優先級驅動的迭代歸約。

數據結構：統一節點表示


# 節點類型標記
'@var'   : ['@var', 'varName']           # 變量
'@num'   : ['@num', 'num_string']        # 數字
'@expr'  : ['@expr', 'Operator', child...] # 運算表達式
'@func'  : ['@func', 'funcName', [arg...]] # 函數調用
'@expr_list' : ['@expr_list', node...]   # 參數列表
'(' , ')' : ['(', None], [')', None]     # 括號標記

算符優先級表 (數字越大優先級越高)


operator_priority_tuple = (
    (),                              # 0 佔位
    ('+', '-', '!', '~'),            # 1 一元
    ('*', '/', '%'),                 # 2 乘除模
    ('+', '-'),                      # 3 加減
    ('<<', '>>'),                    # 4 移位
    ('>', '>=', '<', '<='),          # 5 關係
    ('==', '!='),                    # 6 相等
    ('&',),                          # 7 位與
    ('^',),                          # 8 位異或
    ('|',),                          # 9 位或
    ('&&',),                         # 10 邏輯與
    ('||',),                         # 11 邏輯或
    ('?', ':'),                      # 12 三元
    (',',)                           # 13 逗號
)

核心解析算法：parse_simple_expr


def parse_simple_expr(lis):
    # lis: 可變列表，原地歸約
    for pri in range(1, 12):  # 優先級 1-11 (一元到邏輯或)
        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]:
                # 調用對應處理函數 module_pri_idx
                if module_dic_tuple[pri][lis[i][0]](lis, i) == 0:
                    i = 0  # 歸約成功，重掃
                    continue
            i += 1
    
    # 三元運算符特殊處理 (右結合，從 ':' 開始歸約)
    for pri in range(12, 13):
        i = 0
        while True:
            if len(lis) == 1 and lis[0][0][0] == '@': return 0
            if i >= len(lis): break
            if lis[i][0] == ':':
                if module_dic_tuple[pri]['?:'](lis, i) == 0:
                    i = 0; continue
            i += 1
    
    return module_dic_tuple[13][','](lis, 0)  # 逗號運算符

歸約模塊示例：二元運算符


# module_3_0 對應 '+' (優先級 3, 索引 0)
def module_3_0(lis, i):  # 處理 '+' 
    # 檢查左右操作數皆為 @ 節點
    if i-1 >= 0 and i+1 < len(lis) and \
       lis[i-1][0][0] == '@' and lis[i+1][0][0] == '@':
        # 構建新 @expr 節點替換三元組
        new_node = ['@expr', '+', lis[i-1], lis[i+1]]
        del lis[i-1:i+2]  # 刪除 left, op, right
        lis.insert(i-1, new_node)
        return 0  # 成功
    return 1  # 失敗 (語法錯誤)

括號與函數調用處理：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)  # 返回 [status, left_idx, right_idx]
        if place[0] != 0: return 1  # 括號不匹配
        
        # 提取括號內表達式遞歸解析
        inner = lis[place[1]+1 : place[2]]
        if parse_simple_expr(inner) != 0: return 1
        
        # 檢查是否為函數調用：左側緊鄰 @var
        if place[1] >= 1 and lis[place[1]-1][0] == '@var':
            func_name = lis[place[1]-1][1]
            del lis[place[1]-1 : place[2]+1]
            lis.insert(place[1]-1, ['@func', func_name, inner[0]])
        else:
            del lis[place[1] : place[2]+1]
            lis.insert(place[1], inner[0])
    return 1

實驗驗證


# 輸入: f(1,2,3,!-x?y:~z)-3/4
# Token 化後列表:
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)
# 結果:
# [['@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']
# ]]