Python 近似相等運運算元實作與編譯器分析

– 13 分鐘閱讀

Python 的比較運運算元系統完善，但缺乏近似相等的功能。要實作這個功能，需要修改 Python 的語法和語義，並深入瞭解 Python 編譯器的運作方式。這涉及到詞法分析、語法分析、建立抽象語法樹（AST）、編譯成 bytecode 等步驟。修改語法需要調整解析器以識別新的運運算元，例如 ~=, 而語義修改則需定義其行為，例如允許一定範圍的誤差。 CPython 的編譯過程相當複雜，涉及到多個模組和步驟，其中包括建立和使用符號表，它儲存了程式中所有變數、函式和類別的資訊。 理解符號表的結構和如何在編譯過程中使用它，對於新增運運算元至關重要。 抽象語法樹（AST）是程式碼的樹狀表示，編譯器會遍歷 AST 來產生 bytecode。 新增運運算元需要修改 AST 的生成和遍歷方式。 此外，還需要考慮 Python 編譯過程中使用的各種旗標，例如最佳化級別、巢狀級別等，以及如何在程式碼中設定這些旗標。 這些旗標會影響編譯器的行為，因此在新增運運算元時需要仔細考慮。

現有比較運運算元

  • 小於：<
  • 大於：>
  • 相等：==
  • 不相等：!=

增加「近似相等」運運算元

為了增加「近似相等」的功能，可以引入一個新的運運算元，例如 ~=。這個運運算元可以用於比較兩個數值是否近似相等。

實作「近似相等」運運算元

為了實作「近似相等」運運算元，需要修改程式語言的語法和語義。以下是一個簡單的實作方法：

  1. 修改語法：在語法規則中新增「近似相等」運運算元的定義。
  2. 修改語義：為「近似相等」運運算元定義其語義，例如，可以將浮點數轉換為整數後進行比較。

範例

以下是一些範例，展示了「近似相等」運運算元的使用：

print(1 ~= 1)  # True
print(1 ~= 1.0)  # True
print(1 ~= 1.01)  # True
print(1 ~= 1.9)  # False

實作細節

要實作「近似相等」運運算元，需要對程式語言的語法和語義進行修改。以下是一些實作細節：

  • 修改語法規則：在語法規則中新增「近似相等」運運算元的定義。
  • 修改語義規則：為「近似相等」運運算元定義其語義，例如，可以將浮點數轉換為整數後進行比較。
  • 實作「近似相等」運運算元：根據語法和語義規則，實作「近似相等」運運算元的功能。

修改比較運運算元以支援新對

首先，我們需要了解現有的 compare_op_bitwise_or_pair 規則是如何定義的。根據給出的程式碼，這個規則涵蓋了多種比較運運算元，包括等於 (eq_bitwise_or)、不等於 (noteq_bitwise_or)、小於或等於 (lte_bitwise_or)、小於 (lt_bitwise_or)、大於或等於 (gte_bitwise_or)、大於 (gt_bitwise_or)、不在內 (notin_bitwise_or)、在內 (in_bitwise_or)、是 (is_bitwise_or) 和不是 (isnot_bitwise_or)。

現在，為了支援新的 ale_bitwise_or 對，需要將其加入到 compare_op_bitwise_or_pair 的規則中。假設 ale_bitwise_or 對的語法結構與其他對類別似，我們可以按照以下步驟進行修改：

  1. 定義 ale_bitwise_or 對的語法：首先，需要定義 ale_bitwise_or 對的具體語法結構。這可能涉及到一個新的關鍵字或符號，例如 ale。

  2. 修改 compare_op_bitwise_or_pair 規則：接下來，需要修改 compare_op_bitwise_or_pair 規則，以便它能夠支援新的 ale_bitwise_or 對。這通常涉及到在規則中新增一個新的分支或條件，以匹配 ale_bitwise_or 對的語法結構。

修改過程

假設 ale_bitwise_or 對的語法結構為 'ale' a=bitwise_or...，我們可以按照以下方式修改 compare_op_bitwise_or_pair 規則：

compare_op_bitwise_or_pair[CmpopExprPair*]:
    | eq_bitwise_or
    | noteq_bitwise_or
    | lte_bitwise_or
    | lt_bitwise_or
    | gte_bitwise_or
    | gt_bitwise_or
    | notin_bitwise_or
    | in_bitwise_or
    | isnot_bitwise_or
    | is_bitwise_or
    | ale_bitwise_or  // 新增對應ale_bitwise_or的規則
;

ale_bitwise_or[CmpopExprPair*]: 'ale' a=bitwise_or...  // 定義ale_bitwise_or的語法結構

如何在Python中實作位元運算

Python是一種高階語言，提供了多種位元運算子，包括位元或（OR）、位元與（AND）、位元異或（XOR）、位元左移（Left Shift）、位元右移（Right Shift）和位元反向（NOT）。

位元或（OR）

位元或運算使用|符號，兩個位元如果有一個為1，則結果為1。

a = 5   # 101
b = 3   # 011
result = a | b  # 111
print(result)  # 7

位元與（AND）

位元與運算使用&符號，兩個位元都為1，則結果為1。

a = 5   # 101
b = 3   # 011
result = a & b  # 001
print(result)  # 1

位元異或（XOR）

位元異或運算使用^符號，兩個位元不同，則結果為1。

a = 5   # 101
b = 3   # 011
result = a ^ b  # 110
print(result)  # 6

位元左移（Left Shift）

位元左移運算使用<<符號，將位元向左移動指定的位數。

a = 5   # 101
result = a << 1  # 1010
print(result)  # 10

位元右移（Right Shift）

位元右移運算使用>>符號，將位元向右移動指定的位數。

a = 10  # 1010
result = a >> 1  # 101
print(result)  # 5

位元反向（NOT）

位元反向運算使用~符號，將位元反轉。

a = 5   # 101
result = ~a  #...111010 (假設32位元整數)
print(result)  # -6 (因為Python的整數是帶符號的)

在Python中定義新的運算子

Python不允許直接定義新的運算子，但是可以透過定義特殊方法來實作自定義的運算。

例如，可以定義一個類別來實作「幾乎相等」的運算：

class AlmostEqual:
    def __init__(self, value):
        self.value = value

    def __eq__(self, other):
        return abs(self.value - other) < 1e-6

# 使用
ae = AlmostEqual(5)
print(ae == 5.000001)  # True

這裡定義了一個AlmostEqual類別，實作了「幾乎相等」的運算。這種方法可以用來實作自定義的運算，但是需要注意的是，這不是真正的運算子過載。

Python 的語法解析和編譯過程

Python 的語法解析和編譯過程涉及多個步驟，包括詞法分析、語法分析、抽象語法樹（AST）的構建、編譯等。

詞法分析

詞法分析是將 Python 程式碼分解為一個個的詞元（token）的過程。Python 的詞法分析器會將程式碼分解為關鍵字、識別符號、運算子等。

語法分析

語法分析是根據 Python 的語法規則對詞元進行分析和組合，形成抽象語法樹（AST）的過程。AST 是一個樹狀結構，代表了 Python 程式碼的語法結構。

抽象語法樹（AST）

抽象語法樹（AST）是 Python 程式碼的中間表示形式。它是一個樹狀結構，節點代表了 Python 程式碼的不同部分，例如函式定義、類別定義、條件陳述式等。

編譯

編譯是將 AST 轉換為 Python 的 bytecode 的過程。bytecode 是 Python 虛擬機器（PVM）可以直接執行的程式碼。

新增新的運算子

新增新的運算子到 Python 中，需要修改詞法分析器、語法分析器和編譯器。以下是新增新的運算子 ~= 的步驟：

  1. 修改詞法分析器：在 PyToken_TwoChars 函式中新增新的運算子 ~=。
  2. 修改語法分析器：在 ast_for_comp_op 函式中新增新的運算子 AlE。
  3. 修改編譯器：更新 PyAST_CompileObject 函式，以便它可以處理新的運算子。

CPython 的編譯過程

CPython 的編譯過程涉及多個步驟，包括：

  1. 建立 AST：根據 Python 程式碼建立抽象語法樹（AST）。
  2. 編譯 AST：將 AST 轉換為 bytecode。
  3. 執行 bytecode：Python 虛擬機器（PVM）執行 bytecode。

CPython 的編譯過程是一個複雜的過程，涉及多個步驟和多個模組。瞭解這個過程可以幫助我們更好地理解 Python 的工作原理。

重要術語

  • 抽象語法樹（AST）：Python 程式碼的中間表示形式。
  • Bytecode：Python 虛擬機器（PVM）可以直接執行的程式碼。
  • 編譯器：將 AST 轉換為 bytecode 的模組。
  • 詞法分析器：將 Python 程式碼分解為一個個的詞元（token）的模組。
  • 語法分析器：根據 Python 的語法規則對詞元進行分析和組合，形成 AST 的模組。

Understanding the CPython Compiler

As we delve into the inner workings of the CPython compiler, it’s essential to understand the decades of development and computer science that have shaped it. Although the compiler may seem complex, breaking it down into logical steps makes it more manageable.

Source Files

The following source files are relevant to the compiler:

  • compile.c: Implementation of the compiler
  • compile.h: API and type definitions for the compiler

Key Terms

Some key terms that may be unfamiliar include:

  • Compiler state: Implemented as a container type, holding a symbol table and other information.
  • Symbol table: Contains variable names and may include nested symbol tables.
  • Compilation unit: Contains multiple names, including variables, constants, and segment variables.
  • Basic block: Contains multiple bytecode instructions.

The compiler state and its components can be visualized as follows:

  • Symbol table
    • Compiler state
    • Compilation unit
    • Constant
    • Name
    • Variable name
    • Segment variable
    • Symbol table entry
    • Symbol table entry
    • Name
    • Variable name
    • Basic block
    • Instruction

Creating a Compiler Instance

Before running the compiler, a global compiler state is created. The compiler state structure (type compiler) contains properties used by the compiler, such as flags, a stack, and a PyArena. It also references other data structures, like the symbol table.

The fields of the compiler state include:

  • c_arena: A pointer to a memory arena
  • c_const_cache: A Python dictionary (dict) containing all constants, including tuples
  • c_do_not_emit_bytecode: A flag to disable bytecode compilation
  • c_filename: The name of the file being compiled (a Python string)
  • c_flags: Inherited compiler flags (see “Compiler Flags” section)

By understanding these components and their relationships, we can better appreciate the complexity and functionality of the CPython compiler.

Mermaid 圖表：

  graph LR
    A[Compiler State] --> B[Symbol Table]
    A --> C[Compilation Unit]
    C --> D[Basic Block]
    D --> E[Instruction]
    B --> F[Constant]
    B --> G[Variable Name]
    B --> H[Segment Variable]

圖表翻譯：

此圖表展示了編譯器狀態、符號表、編譯單元、基本塊和指令之間的關係。編譯器狀態包含符號表和編譯單元，編譯單元包含基本塊，基本塊包含指令。符號表包含常數、變數名稱和段變數。這個圖表幫助我們理解編譯器的結構和邏輯。

Python 編譯過程中使用的旗標

在 Python 的編譯過程中，使用了多種旗標（flags）來控制編譯行為。這些旗標可以分為兩類別：未來功能旗標（future feature flags）和編譯器旗標（compiler flags）。

未來功能旗標

未來功能旗標用於啟用或停用特定的語言功能或行為。例如，在 Python 3.7 中引入了延遲註解處理的功能，可以透過 from __future__ import annotations 來啟用。

未來功能旗標的例子包括：

  • annotations：啟用延遲註解處理。
  • barry_as_FLUFL：啟用 Barry As FLUFL 的功能。

在 Python 3.9 中，大部分未來功能旗標已經成為預設行為，並且會自動啟用。

編譯器旗標

編譯器旗標用於控制編譯過程的行為。例如，可以使用 c_optimize 旗標來設定編譯器的最佳化級別。

編譯器旗標的例子包括：

  • c_optimize：設定編譯器的最佳化級別。
  • c_nestlevel：設定當前的巢狀級別。
  • c_interactive：設定是否為互動式模式。

旗標的設定

旗標可以在兩個地方設定：

  1. 在組態狀態中：可以透過環境變數或命令列引數來設定旗標。
  2. 在原始碼中：可以使用 __future__ 來設定未來功能旗標。

Python 編譯過程中的符號表

在 Python 的編譯過程中，符號表（Symtable）扮演著重要的角色。符號表是一種資料結構，負責儲存程式碼中定義的符號（如變數、函式、類別等）的資訊。

符號表的結構

符號表的結構包含了多個欄位，包括：

  • recursion_depth: 目前的遞迴深度
  • recursion_limit: 遞迴深度的限制
  • st_blocks: 一個字典，儲存著 AST 節點和符號表元素的對應關係
  • st_cur: 目前的符號表元素
  • st_filename: 被編譯的檔案名稱
  • st_future: 模組的未來功能特性
  • st_global: 全域符號的參照
  • st_nblocks: 使用中的區塊數量
  • st_private: 目前的類別名稱（如果有）
  • st_stack: 一個列表，儲存著名稱空間的資訊
  • st_top: 模組的符號表元素

符號表的使用

Python 的標準函式庫中有一個名為 symtable 的模組，提供了對符號表的存取。開發者可以使用這個模組來分析程式碼的符號表，並取得有關變數、函式、類別等的資訊。

以下是一個使用 symtable 模組的範例：

import symtable

# 載入程式碼
code = """
x = 5
def foo():
    y = 10
    return y
"""

# 建立符號表
symtable = symtable.symtable(code, "example.py", "exec")

# 列印符號表的內容
print(symtable.get_symbols())

這個範例建立了一個符號表，並列印出其中的符號。

Python 符號表實作

Python 的符號表（symtable）是用於儲存程式中變數、函式等符號的資訊。下面是 Python 中符號表的實作過程。

符號表結構

Python 的符號表結構如下：

class Symtable:
    def __init__(self, name, type):
        self.name = name
        self.type = type
        self.symbols = []

其中，name 是符號表的名稱，type 是符號表的型別（例如，模組、互動式、表示式或函式），symbols 是一個列表，儲存著符號表中的符號。

建立符號表

建立符號表的過程如下：

def PySymtable_BuildObject(mod, filename, future):
    st = Symtable(mod.name, mod.type)
    seq = mod.body
    i = 0
    while i < len(seq):
        node = seq[i]
        if isinstance(node, ast.FunctionDef):
            # 處理函式定義
            func_def = node
            st.symbols.append(func_def.name)
        elif isinstance(node, ast.Assign):
            # 處理指定陳述式
            assign = node
            st.symbols.append(assign.targets[0].id)
        #...
        i += 1
    return st

其中，mod 是模組物件，filename 是檔案名稱，future 是未來特性物件。函式 PySymtable_BuildObject 建立了一個新的符號表，並遍歷模組中的節點，新增符號到符號表中。

遍歷 AST 節點

遍歷 AST 節點的過程如下：

def traverse_node(node, st):
    if isinstance(node, ast.FunctionDef):
        # 處理函式定義
        func_def = node
        st.symbols.append(func_def.name)
    elif isinstance(node, ast.Assign):
        # 處理指定陳述式
        assign = node
        st.symbols.append(assign.targets[0].id)
    #...
    for child in node.body:
        traverse_node(child, st)

其中，node 是 AST 節點，st 是符號表。函式 traverse_node 遍歷 AST 節點，並新增符號到符號表中。

顯示符號表

顯示符號表的過程如下：

def show_symtable(st):
    print("Symtable {0} ({1})".format(st.name, st.type))
    print(tabulate.tabulate([
        (symbol, symbol.is_global(), symbol.is_local(), symbol.get_namespaces())
        for symbol in st.symbols
    ], headers=["name", "global", "local", "namespaces"], tablefmt="grid"))

其中，st 是符號表。函式 show_symtable 顯示了符號表的名稱、型別和符號列表。

例項

下面是一個例項：

code = """
def calc_pow(a, b):
    return a ** b

a = 1
b = 2
c = calc_pow(a, b)
"""

st = PySymtable_BuildObject(code, "example.py", None)
show_symtable(st)

這個例項建立了一個符號表，並顯示了符號表的內容。

Python 的符號表建立過程

Python 的符號表（symtable）是一個重要的資料結構，負責儲存程式中定義的變數、函式和類別等符號的資訊。在編譯過程中，Python 會建立一個符號表，以便於之後的語法分析和執行。

符號表的建立

符號表的建立是由 PySymtable_BuildObject 函式負責的。這個函式會遍歷模組中的所有命令，並呼叫 symtable_visit_stmt 函式來處理每個命令。

st->st_top = st->st_cur;

switch (mod->kind) {
    case Module_kind:
        seq = mod->v.Module.body;
        for (i = 0; i < asdl_seq_LEN(seq); i++)
            if (!symtable_visit_stmt(st, (stmt_ty)asdl_seq_GET(seq, i)))
                goto error;
        break;
   ...
}

命令的處理

symtable_visit_stmt 函式是一個巨大的 switch 陳述式，根據命令的型別來決定如何處理。例如，對於函式定義命令（FunctionDef_kind），會進行以下步驟：

  1. 檢查當前的遞迴深度是否超過限制。
  2. 將函式名稱新增到符號表中。
  3. 處理函式的引數和預設值。
  4. 處理函式的型別註解和裝飾器。
  5. 進入函式的內部並處理其內容。
case FunctionDef_kind:
    if (!symtable_add_def(st, s->v.FunctionDef.name, DEF_LOCAL))
        VISIT_QUIT(st, 0);

    if (s->v.FunctionDef.args->defaults)
        VISIT_SEQ(st, expr, s->v.FunctionDef.args->defaults);
   ...

引數預設值的處理

對於引數預設值，Python 會將其視為對符號表中變數的參照。這意味著，如果引數預設值是可變的，則每次呼叫函式時都會使用相同的物件。

if (s->v.FunctionDef.args->defaults)
    VISIT_SEQ(st, expr, s->v.FunctionDef.args->defaults);

這也是為什麼 Python 的引數預設值是可變的原因。因為它們是對符號表中變數的參照，所以每次呼叫函式時都會使用相同的物件。

內容解密：

上述程式碼片段是Python編譯器中的一部分，負責處理抽象語法樹（AST）中的節點。這個特定片段關注的是函式定義的存取和處理。

if (s->v.FunctionDef.args->kw_defaults)
    VISIT_SEQ_WITH_NULL(st, expr, s->v.FunctionDef.args->kw_defaults);

這行程式碼檢查函式定義中的kw_defaults是否存在，如果存在，就會對其進行存取。kw_defaults代表了函式中帶有預設值的引數的預設值。

接下來，

if (!symtable_visit_annotations(st, s, s->v.FunctionDef.args, s->v.FunctionDef.returns))
    VISIT_QUIT(st, 0);

這部分程式碼負責存取函式引數和傳回值的註解。如果存取失敗，就會離開存取過程。

然後，

if (s->v.FunctionDef.decorator_list)
    VISIT_SEQ(st, expr, s->v.FunctionDef.decorator_list);

檢查函式是否有裝飾器，如果有，就會對裝飾器列表進行存取。

之後，

if (!symtable_enter_block(st, s->v.FunctionDef.name, FunctionBlock, (void *)s, s->lineno, s->col_offset))
    VISIT_QUIT(st, 0);

這行程式碼嘗試進入函式的作用域。如果進入失敗，就會離開存取過程。

接著，

VISIT(st, arguments, s->v.FunctionDef.args);
VISIT_SEQ(st, stmt, s->v.FunctionDef.body);

分別對函式的引數和函式體進行存取。

最後，

if (!symtable_exit_block(st, s))
    VISIT_QUIT(st, 0);

嘗試離開函式的作用域。如果離開失敗，就會離開存取過程。

這個過程確保了函式定義中的各個部分都被正確地存取和處理，為後續的編譯和執行做好了準備。

圖表翻譯：

  flowchart TD
    A[開始] --> B[檢查kw_defaults]
    B -->|存在|> C[存取kw_defaults]
    B -->|不存在|> D[存取註解]
    D -->|失敗|> E[離開存取]
    D -->|成功|> F[檢查裝飾器]
    F -->|存在|> G[存取裝飾器]
    F -->|不存在|> H[進入函式作用域]
    H -->|失敗|> E
    H -->|成功|> I[存取函式引數]
    I --> J[存取函式體]
    J --> K[離開函式作用域]
    K -->|失敗|> E
    K -->|成功|> L[結束]

這個流程圖描述了函式定義的存取和處理過程，包括檢查和存取kw_defaults、註解、裝飾器、函式引數和函式體，以及進入和離開函式作用域。

基本編譯

現在，當 PyAST_CompileObject() 擁有編譯器狀態、符號表和以 AST 形式存在的模組時，可以開始實際的編譯。基本編譯器解決兩個問題：

  1. 將編譯器狀態、符號表和 AST 轉換為控制流程圖（CFG）。

  2. 透過捕捉邏輯錯誤和程式碼錯誤來預防執行階段的異常。

從編譯器架構的底層實作到程式碼解析的應用層面來看，本文深入探討了 Python 如何處理近似相等運運算元以及其編譯過程中的關鍵機制。透過分析現有比較運運算元的語法結構和語義規則，我們闡述瞭如何擴充套件語法以容納新的近似相等運運算元 ~=，並以修改 compare_op_bitwise_or_pair 規則為例，具體說明瞭如何在程式語言的語法樹中加入新的運運算元節點。

進一步地，文章詳細解析了 Python 的位元運算機制，並點明瞭 Python 不支援直接定義新運算子的限制。針對此限制，我們提出了以定義特殊方法（例如 __eq__）來模擬近似相等運算的替代方案，同時也指出了這種方法並非真正的運算子過載，存在一定的侷限性。此外，文章還深入探討了 Python 的語法解析和編譯過程，包含詞法分析、語法分析、AST 構建和 bytecode 生成等步驟，並詳細說明瞭如何在 CPython 中修改詞法分析器、語法分析器和編譯器以實作新的運算子。最後，我們也分析了 CPython 編譯過程中使用的旗標和符號表機制，以及它們在程式碼解析和編譯最佳化中的作用。

展望未來，近似相等運運算元的引入將有助於提升 Python 在數值計算和科學運算領域的應用能力。對於開發者而言，深入理解 Python 的編譯過程和符號表機制，將有助於編寫更高效、更穩定的程式碼。同時，持續關注 CPython 的發展，特別是新功能和最佳化策略的演進，將有助於掌握 Python 的最新技術趨勢。玄貓認為，儘管直接修改 CPython 編譯器來新增新運算子的門檻較高，但透過深入理解其底層機制，開發者可以更好地利用現有功能，並探索更具創造性的解決方案，例如開發根據 Python 的領域特定語言（DSL）來實作特定的運算需求。

玄貓

玄貓

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。