Following system colour scheme - Python 增強提案 Selected dark colour scheme - Python 增強提案 Selected light colour scheme - Python 增強提案

Python 增強提案

PEP 617 – CPython 新的 PEG 解析器

作者:
Guido van Rossum <guido at python.org>, Pablo Galindo <pablogsal at python.org>, Lysandros Nikolaou <lisandrosnik at gmail.com>
討論至:
Python-Dev 列表
狀態:
最終版
型別:
標準跟蹤
建立日期:
2020年3月24日
Python 版本:
3.9
釋出歷史:
2020年4月2日
目錄

重要

本 PEP 是一份歷史文件。最新、規範的文件現可在完整語法規範中找到。

×

有關如何提出更改，請參閱 PEP 1。

概述

本 PEP 提議用新的基於 PEG 的解析器替換 CPython 當前基於 LL(1) 的解析器。這個新解析器將允許消除現有語法中為規避 LL(1) 限制而存在的多個“技巧”。它將大幅降低與編譯管道相關的一些領域（如語法、解析器和 AST 生成）的維護成本。新的 PEG 解析器還將解除當前 Python 語法上的 LL(1) 限制。

LL(1) 解析器背景

當前的 Python 語法是基於 LL(1) 的語法。如果一個語法能夠被 LL(1) 解析器解析，那麼它就可以被稱為 LL(1) 語法。LL(1) 解析器則定義為一種自頂向下、從左到右解析輸入、執行最左推導、只向前看一個 token 的解析器。構建或生成 LL(1) 解析器的傳統方法是生成一個**解析表**，該表編碼瞭解析器所有可能狀態之間的轉換。這些表通常由語法的**First 集合**和**Follow 集合**構建而成。

  • 給定一個規則，**First 集合**是該規則完整推導中可能首先出現的所有終結符的集合。直觀地，這有助於解析器在規則中的備選項之間做出決定。例如，給定規則
    rule: A | B

    如果只有 A 可以以終結符 *a* 開頭，只有 B 可以以終結符 *b* 開頭，並且解析器在解析此規則時看到 token *b*，它就知道需要跟隨非終結符 B。

  • 當一個規則可能擴充套件到空字串時，需要擴充套件這個簡單概念。給定一個規則，**Follow 集合**是部分推導中可能緊跟在該規則右側出現的所有終結符的集合。直觀地，這解決了空備選項的問題。例如，給定此規則
    rule: A 'b'

    如果解析器有 token *b* 且非終結符 A 只能以 token *a* 開頭，那麼解析器可以判斷這是一個無效程式。但如果 A 可以擴充套件到空字串（稱為 ε-產生式），那麼解析器就會識別一個有效的空 A，因為下一個 token *b* 在 A 的 **Follow 集合**中。

當前的 Python 語法不包含 ε-產生式，因此在建立解析表時不需要 Follow 集合。目前，在 CPython 中，一個解析器生成程式讀取語法並生成一個解析表，該表表示一組確定性有限自動機 (DFA)，可以包含在一個 C 程式中，即解析器。該解析器是一個下推自動機，它使用這些資料生成一個具體語法樹 (CST)，有時直接稱為“解析樹”。在這個過程中，First 集合在生成 DFA 時被間接使用。

LL(1) 解析器和語法通常高效且易於實現和生成。然而，在 LL(1) 限制下，無法以一種對語言設計者和讀者都自然的方式表達某些常見結構。這包括 Python 語言中的一些。

由於 LL(1) 解析器只能向前看一個 token 來區分可能性，因此語法中的某些規則可能存在歧義。例如，規則

rule: A | B

如果 A 和 B 的 First 集合有一些共同元素，則會產生歧義。當解析器在輸入程式中看到一個 token，並且 *A* 和 *B* 都可以以此 token 開頭時，它不可能推斷出應該擴充套件哪個選項，因為無法檢查程式的更多 token 來消除歧義。該規則可以轉換為等效的 LL(1) 規則，但這可能使人類讀者更難理解其含義。本文件後面的一些示例表明，當前的基於 LL(1) 的語法在此情況下受到了很大的影響。

LL(1) 排除的另一大類規則是左遞迴規則。如果一個規則可以推匯出一個以自身為最左符號的句型，那麼該規則就是左遞迴的。例如，這個規則

rule: rule 'a'

是左遞迴的，因為該規則可以擴充套件為以自身開頭的一個表示式。正如後面將描述的，左遞迴是直接在語法中表達某些所需語言屬性的自然方式。

PEG 解析器背景

PEG（解析表示式文法）與上下文無關文法（如當前文法）的區別在於，其書寫方式更接近解析器在解析時如何操作。根本的技術區別在於選擇運算子是有序的。這意味著當編寫

rule: A | B | C

上下文無關文法解析器（如 LL(1) 解析器）將生成給定輸入字串時**推斷**哪個備選項（A、B 或 C）必須被擴充套件的構造，而 PEG 解析器將檢查第一個備選項是否成功，並且只有當它失敗時，才會按照它們書寫的順序繼續嘗試第二個或第三個。這使得選擇運算子不具有交換律。

與 LL(1) 解析器不同，基於 PEG 的解析器不能有歧義：如果一個字串被解析，它只有一個有效的解析樹。這意味著基於 PEG 的解析器不會遭受上一節中描述的歧義問題。

PEG 解析器通常構建為遞迴下降解析器，其中語法中的每個規則都對應於實現解析器的程式中的一個函式，而解析表示式（規則的“擴充套件”或“定義”）表示該函式中的“程式碼”。每個解析函式在概念上都將其輸入字串作為引數，併產生以下結果之一：

  • “成功”結果。此結果表示表示式可以由該規則解析，並且函式可以選擇性地前進或消耗其提供的輸入字串的一個或多個字元。
  • “失敗”結果，在這種情況下不消耗任何輸入。

請注意，“失敗”結果並不意味著程式不正確或解析失敗，因為由於選擇運算子是有序的，“失敗”結果僅僅表示“嘗試下一個選項”。將 PEG 解析器直接實現為遞迴下降解析器在最壞情況下會呈現指數級時間效能，與 LL(1) 解析器相比，因為 PEG 解析器具有無限前瞻（這意味著它們在決定一個規則之前可以考慮任意數量的 token）。通常，PEG 解析器透過一種稱為“packrat parsing”[1] 的技術來避免這種指數級時間複雜性，該技術不僅在解析前將整個程式載入到記憶體中，而且還允許解析器任意回溯。透過記憶每個位置已匹配的規則，這種方式變得高效。記憶化快取的代價是解析器將比簡單的 LL(1) 解析器（通常基於表）自然使用更多的記憶體。我們將在本文件後面解釋為什麼我們認為這個代價是可以接受的。

基本原理

在本節中，我們描述了 CPython 中當前解析器機制存在的一系列問題，這些問題促使我們需要一個新的解析器。

有些規則實際上不是 LL(1)

儘管 Python 語法在技術上是 LL(1) 語法（因為它由 LL(1) 解析器解析），但有幾個規則不是 LL(1)，並且在語法和 CPython 的其他部分實施了幾個變通方法來處理這個問題。例如，考慮賦值表示式的規則

namedexpr_test: [NAME ':='] test

這個簡單的規則與 Python 語法不相容，因為 _NAME_ 在規則 _test_ 的 First 集合中。為了解決這個限制，當前語法中出現的實際規則是

namedexpr_test: test [':=' test]

這是一個比前一個規則更寬泛的規則，允許像 [x for x in y] := [1,2,3] 這樣的構造。該規則被限制為所需形式的方式是透過在將解析樹轉換為抽象語法樹時停用這些不需要的構造。這不僅不優雅，而且是一個相當大的維護負擔，因為它迫使 AST 建立例程和編譯器處於一種需要知道如何將有效程式與無效程式分開的情況，這應該是解析器唯一的責任。這也導致實際的語法檔案未能正確反映**實際**語法（即所有有效 Python 程式的集合）。

類似的變通方法出現在當前語法的其他多個規則中。有時這個問題無法解決。例如，bpo-12782: 多個上下文表達式不支援跨行繼續的括號 顯示瞭如何建立一個支援編寫的 LL(1) 規則

with (
    open("a_really_long_foo") as foo,
    open("a_really_long_baz") as baz,
    open("a_really_long_bar") as bar
):
  ...

是不可能的，因為可以作為上下文管理器出現的語法項的 First 集合包括左括號，使得規則產生歧義。這個規則不僅與其他語言部分（如多重匯入規則）一致，而且對自動格式化工具也非常有用，因為帶括號的組通常用於將元素分組以便一起格式化（就像這些工具對列表、集合的內容進行操作一樣）。

複雜的 AST 解析

當前解析器的另一個問題是 AST 生成例程與所生成解析樹的特定形狀之間存在巨大的耦合。這使得生成 AST 的程式碼特別複雜，因為許多操作和選擇都是隱式的。例如，AST 生成程式碼根據給定解析節點中存在的子節點數量來知道某個規則的哪些備選項被生成。這使得程式碼難以理解，因為此屬性與語法檔案不直接相關，並且受實現細節的影響。因此，相當一部分 AST 生成程式碼需要處理檢查和推斷其接收到的解析樹的特定形狀。

缺乏左遞迴

如前所述，LL(1) 語法的一個限制是它們不允許左遞迴。這使得編寫一些規則非常不自然，並且與程式設計師通常思考程式的方式相去甚遠。例如，這個結構（當前語法中幾個規則的簡化變體）

expr: expr '+' term | term

不能被 LL(1) 解析器解析。傳統的補救措施是重寫語法以規避此問題

expr: term ('+' term)*

這種形式出現的問題是解析樹被迫具有一種非常不自然的形狀。這是因為，對於輸入程式 a + b + c，此規則將使解析樹扁平化（['a', '+', 'b', '+', 'c']），並且必須經過後處理才能構建左遞迴解析樹（[['a', '+', 'b'], '+', 'c']）。被迫編寫第二個規則不僅導致解析樹未能正確反映所需的結合性，而且還對後續編譯階段施加了進一步的壓力，以檢測和後處理這些情況。

中間解析樹

當前解析器存在的最後一個問題是中間生成一個解析樹或具體語法樹，該樹隨後被轉換為抽象語法樹。儘管 CST 的構建在解析器和編譯器管道中非常常見，但在 CPython 中，這個中間 CST 並沒有被其他任何東西使用（它只被 *parser* 模組間接暴露，並且 CST 生成中極小一部分程式碼在該模組中被重用）。更糟糕的是：整個樹都儲存在記憶體中，保留了許多由單子節點鏈組成的枝條。這已被證明會消耗大量記憶體（例如在 bpo-26415: Python 解析器記憶體峰值消耗過大 中）。

在語法和 AST 之間不得不產生中間結果不僅不理想，而且還使 AST 生成步驟複雜得多，大大增加了維護負擔。

新提議的 PEG 解析器

新提出的 PEG 解析器包含以下部分：

  • 一個解析器生成器，可以讀取語法檔案並生成用 Python 或 C 編寫的 PEG 解析器，該解析器可以解析所述語法。
  • 一個 PEG 元語法，它自動生成一個 Python 解析器，該解析器用於解析器生成器本身（這意味著沒有手動編寫的解析器）。
  • 一個生成的解析器（使用解析器生成器）可以直接生成 C 和 Python AST 物件。

左遞迴

PEG 解析器通常不支援左遞迴，但我們實現了一種類似於 Medeiros 等人 [2] 中描述的技術，但使用備忘錄快取而不是靜態變數。這種方法更接近於 Warth 等人 [3] 中描述的方法。這使我們不僅可以編寫簡單的左遞迴規則，還可以編寫更復雜的涉及間接左遞迴的規則，例如

rule1: rule2 | 'a'
rule2: rule3 | 'b'
rule3: rule1 | 'c'

以及“隱藏的左遞迴”，例如

rule: 'optional'? rule '@' some_other_rule

語法

語法由以下形式的規則序列組成

rule_name: expression

可選地，可以在規則名稱後包含一個型別，它指定了與該規則對應的 C 或 Python 函式的返回型別

rule_name[return_type]: expression

如果省略返回型別，則在 C 中返回 void *，在 Python 中返回 Any。

語法表示式

# 註釋

Python 風格註釋。

e1 e2

匹配 e1，然後匹配 e2。

rule_name: first_rule second_rule
e1 | e2

匹配 e1 或 e2。

為了格式化目的，第一個備選項也可以出現在規則名稱的下一行。在這種情況下，第一個備選項前必須使用 |，如下所示：

rule_name[return_type]:
    | first_alt
    | second_alt
( e )

匹配 e。

rule_name: (e)

一個稍微複雜且更有用的例子包括將分組運算子與重複運算子一起使用

rule_name: (e1 e2)*
[ e ] 或 e?

可選匹配 e。

rule_name: [e]

一個更有用的例子包括定義尾隨逗號是可選的

rule_name: e (',' e)* [',']
e*

匹配零個或多個 e 的出現。

rule_name: (e1 e2)*
e+

匹配一個或多個 e 的出現。

rule_name: (e1 e2)+
s.e+

匹配一個或多個用 s 分隔的 e 的出現。生成的解析樹不包含分隔符。這與 (e (s e)*) 完全相同。

rule_name: ','.e+
&e

如果 e 可以被解析，則成功，不消耗任何輸入。

!e

如果 e 可以被解析，則失敗，不消耗任何輸入。

一個取自提議的 Python 語法的例子指出，一個 primary 由一個 atom 組成，其後不能跟著 . 或 ( 或 [

primary: atom !'.' !'(' !'['
~

即使解析失敗，也提交當前備選項。

rule_name: '(' ~ some_rule ')' | some_alt

在此示例中，如果解析了左括號，即使 some_rule 或 ')' 解析失敗，也不會考慮其他備選項。

語法中的變數

子表示式可以透過在其前面加上一個識別符號和 = 符號來命名。該名稱隨後可以在動作中使用（見下文），如下所示

rule_name[return_type]: '(' a=some_other_rule ')' { a }

語法動作

為了避免模糊語法與 AST 生成之間關係的中間步驟，所提議的 PEG 解析器允許透過語法動作直接為規則生成 AST 節點。語法動作是特定於語言的表示式，當語法規則成功解析時會進行評估。這些表示式可以用 Python 或 C 編寫，具體取決於解析器生成器的期望輸出。這意味著如果一個人想用 Python 生成一個解析器，另一個人想用 C 生成一個解析器，則應該編寫兩個語法檔案，每個檔案都有一組不同的動作，除了這些動作之外，兩個檔案中的所有其他內容都保持相同。作為一個帶有 Python 動作的語法的例子，解析器生成器中解析語法檔案的部分是從一個帶有 Python 動作的元語法檔案自舉的，該檔案在解析後生成語法樹。

在針對 Python 新提出的 PEG 語法的特定情況下，擁有動作允許直接在語法本身中描述 AST 如何構成，使其更清晰、更易於維護。AST 生成過程透過使用一些輔助函式來支援，這些函式將常見的 AST 物件操作和一些與語法不直接相關的其他必需操作進行分解。

為了指示這些動作，每個備選項後面都可以跟著用大括號括起來的動作程式碼，這指定了備選項的返回值

rule_name[return_type]:
    | first_alt1 first_alt2 { first_alt1 }
    | second_alt1 second_alt2 { second_alt1 }

如果省略了動作並且正在生成 C 程式碼，則有兩種不同的可能性：

  1. 如果備選項中只有一個名稱，則返回該名稱。
  2. 如果沒有，則返回一個虛擬名稱物件（應避免這種情況）。

如果省略了動作並且正在生成 Python 程式碼，則返回一個包含所有已解析表示式的列表（這用於除錯）。

PEG 生成器支援的語法的完整元語法是

start[Grammar]: grammar ENDMARKER { grammar }

grammar[Grammar]:
    | metas rules { Grammar(rules, metas) }
    | rules { Grammar(rules, []) }

metas[MetaList]:
    | meta metas { [meta] + metas }
    | meta { [meta] }

meta[MetaTuple]:
    | "@" NAME NEWLINE { (name.string, None) }
    | "@" a=NAME b=NAME NEWLINE { (a.string, b.string) }
    | "@" NAME STRING NEWLINE { (name.string, literal_eval(string.string)) }

rules[RuleList]:
    | rule rules { [rule] + rules }
    | rule { [rule] }

rule[Rule]:
    | rulename ":" alts NEWLINE INDENT more_alts DEDENT {
          Rule(rulename[0], rulename[1], Rhs(alts.alts + more_alts.alts)) }
    | rulename ":" NEWLINE INDENT more_alts DEDENT { Rule(rulename[0], rulename[1], more_alts) }
    | rulename ":" alts NEWLINE { Rule(rulename[0], rulename[1], alts) }

rulename[RuleName]:
    | NAME '[' type=NAME '*' ']' {(name.string, type.string+"*")}
    | NAME '[' type=NAME ']' {(name.string, type.string)}
    | NAME {(name.string, None)}

alts[Rhs]:
    | alt "|" alts { Rhs([alt] + alts.alts)}
    | alt { Rhs([alt]) }

more_alts[Rhs]:
    | "|" alts NEWLINE more_alts { Rhs(alts.alts + more_alts.alts) }
    | "|" alts NEWLINE { Rhs(alts.alts) }

alt[Alt]:
    | items '$' action { Alt(items + [NamedItem(None, NameLeaf('ENDMARKER'))], action=action) }
    | items '$' { Alt(items + [NamedItem(None, NameLeaf('ENDMARKER'))], action=None) }
    | items action { Alt(items, action=action) }
    | items { Alt(items, action=None) }

items[NamedItemList]:
    | named_item items { [named_item] + items }
    | named_item { [named_item] }

named_item[NamedItem]:
    | NAME '=' ~ item {NamedItem(name.string, item)}
    | item {NamedItem(None, item)}
    | it=lookahead {NamedItem(None, it)}

lookahead[LookaheadOrCut]:
    | '&' ~ atom {PositiveLookahead(atom)}
    | '!' ~ atom {NegativeLookahead(atom)}
    | '~' {Cut()}

item[Item]:
    | '[' ~ alts ']' {Opt(alts)}
    |  atom '?' {Opt(atom)}
    |  atom '*' {Repeat0(atom)}
    |  atom '+' {Repeat1(atom)}
    |  sep=atom '.' node=atom '+' {Gather(sep, node)}
    |  atom {atom}

atom[Plain]:
    | '(' ~ alts ')' {Group(alts)}
    | NAME {NameLeaf(name.string) }
    | STRING {StringLeaf(string.string)}

# Mini-grammar for the actions

action[str]: "{" ~ target_atoms "}" { target_atoms }

target_atoms[str]:
    | target_atom target_atoms { target_atom + " " + target_atoms }
    | target_atom { target_atom }

target_atom[str]:
    | "{" ~ target_atoms "}" { "{" + target_atoms + "}" }
    | NAME { name.string }
    | NUMBER { number.string }
    | STRING { string.string }
    | "?" { "?" }
    | ":" { ":" }

作為一個說明性示例，這個簡單的語法檔案允許直接生成一個完整的解析器，該解析器可以解析簡單的算術表示式並返回一個有效的基於 C 的 Python AST

start[mod_ty]: a=expr_stmt* $ { Module(a, NULL, p->arena) }
expr_stmt[stmt_ty]: a=expr NEWLINE { _Py_Expr(a, EXTRA) }
expr[expr_ty]:
    | l=expr '+' r=term { _Py_BinOp(l, Add, r, EXTRA) }
    | l=expr '-' r=term { _Py_BinOp(l, Sub, r, EXTRA) }
    | t=term { t }

term[expr_ty]:
    | l=term '*' r=factor { _Py_BinOp(l, Mult, r, EXTRA) }
    | l=term '/' r=factor { _Py_BinOp(l, Div, r, EXTRA) }
    | f=factor { f }

factor[expr_ty]:
    | '(' e=expr ')' { e }
    | a=atom { a }

atom[expr_ty]:
    | n=NAME { n }
    | n=NUMBER { n }
    | s=STRING { s }

這裡的 EXTRA 是一個宏，它擴充套件為 start_lineno, start_col_offset, end_lineno, end_col_offset, p->arena，這些都是解析器自動注入的變數；p 指向一個儲存解析器所有狀態的物件。

一個類似語法，旨在生成 Python AST 物件

start: expr NEWLINE? ENDMARKER { ast.Expression(expr) }
expr:
    | expr '+' term { ast.BinOp(expr, ast.Add(), term) }
    | expr '-' term { ast.BinOp(expr, ast.Sub(), term) }
    | term { term }

term:
    | l=term '*' r=factor { ast.BinOp(l, ast.Mult(), r) }
    | term '/' factor { ast.BinOp(term, ast.Div(), factor) }
    | factor { factor }

factor:
    | '(' expr ')' { expr }
    | atom { atom }

atom:
    | NAME { ast.Name(id=name.string, ctx=ast.Load()) }
    | NUMBER { ast.Constant(value=ast.literal_eval(number.string)) }

遷移計劃

本節描述瞭如果此 PEP 被接受，遷移到新的基於 PEG 的解析器時的遷移計劃。遷移將分一系列步驟執行，以便在需要時最初可以回退到以前的解析器

  1. 從 Python 3.9 alpha 6 開始，在 CPython 中包含新的基於 PEG 的解析器機制，並提供命令列標誌和環境變數，允許在新舊解析器之間切換，以及允許獨立呼叫新舊解析器的顯式 API。在此步驟中，所有 Python API（如 ast.parse 和 compile）將使用由標誌或環境變數設定的解析器，預設解析器將是新的基於 PEG 的解析器。
  2. 在 Python 3.9 和 Python 3.10 之間，舊的解析器及相關程式碼（如“parser”模組）將保留，直到新的 Python 版本釋出（Python 3.10）。在此期間，在舊解析器被移除之前，**不會新增任何需要 PEG 解析器的新 Python 語法**。這意味著語法將保持 LL(1) 直到舊解析器被移除。
  3. 在 Python 3.10 中，移除舊解析器、命令列標誌、環境變數和“parser”模組及相關程式碼。

效能和驗證

我們對新解析器進行了廣泛的時間和驗證，這使我們相信新解析器具有足夠高的質量來取代當前解析器。

驗證

為了開始驗證，我們定期編譯整個 Python 3.8 標準庫，並將生成的 AST 的各個方面與標準編譯器生成的 AST 進行比較。（在此過程中，我們發現了標準解析器在行號和列號處理方面的一些錯誤，我們已透過一系列問題和 PR 在上游修復了所有這些錯誤。）

我們還偶爾編譯了一個更大的程式碼庫（PyPI 上大約 3800 個最受歡迎的包），這幫助我們找到了新解析器中（非常）少數額外的錯誤。

（我們尚未深入探索的一個領域是拒絕所有錯誤程式。我們有單元測試來檢查一定數量的顯式拒絕，但可以做更多的工作，例如，透過使用模糊測試工具向現有程式碼中插入隨機的細微錯誤。我們歡迎在此領域提供幫助。）

效能

我們已將新解析器的效能調整到在速度和記憶體消耗方面均與當前解析器相差 10% 以內。雖然 PEG/packrat 解析演算法固有的記憶體消耗比當前的 LL(1) 解析器更多，但我們有一個優勢，因為我們不構建中間 CST。

以下是一些基準測試。這些測試主要關注將原始碼編譯為位元組碼，因為這是最真實的情況。將 AST 返回給 Python 程式碼的代表性不強，因為將**內部** AST（僅 C 程式碼可訪問）轉換為**外部** AST（ast.AST 的例項）的過程比解析器本身耗時更長。

此處報告的所有測量均在最新的 MacBook Pro 上進行，取三次執行的中位數。未特別注意停止同一機器上執行的其他應用程式。

第一個計時是針對我們的規範測試檔案，它有 100,000 行，無限重複以下三行

1 + 2 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + ((((((11 * 12 * 13 * 14 * 15 + 16 * 17 + 18 * 19 * 20))))))
2*3 + 4*5*6
12 + (2 * 3 * 4 * 5 + 6 + 7 * 8)
  • 僅解析並丟棄內部 AST 需要 1.16 秒，最大 RSS 為 681 MiB。
  • 解析並轉換為 ast.AST 需要 6.34 秒，最大 RSS 1029 MiB。
  • 解析並編譯為位元組碼需要 1.28 秒，最大 RSS 681 MiB。
  • 使用當前解析器，解析和編譯需要 1.44 秒，最大 RSS 836 MiB。

對於這個特定的測試檔案，新解析器比當前解析器更快，並且使用的記憶體更少（比較最後兩點）。

我們還使用更真實的負載（整個 Python 3.8 標準庫）進行了計時。此負載包含 1,641 個檔案，749,570 行，27,622,497 位元組。（儘管有 11 個檔案由於編碼問題無法被任何 Python 3 解析器編譯，有時是故意的。）

  • 編譯並丟棄內部 AST 用時 2.141 秒。即每秒 350,040 行，或每秒 12,899,367 位元組。最大 RSS 為 74 MiB（標準庫中最大的檔案比我們的規範測試檔案小得多）。
  • 編譯為位元組碼用時 3.290 秒。即每秒 227,861 行，或每秒 8,396,942 位元組。最大 RSS 77 MiB。
  • 使用當前解析器編譯為位元組碼用時 3.367 秒。即每秒 222,620 行，或每秒 8,203,780 位元組。最大 RSS 70 MiB。

比較最後兩點，我們發現新解析器略快，但使用的記憶體略多（大約 10%）。我們認為這是可以接受的。（此外，我們可能還可以進行一些調整來減少記憶體使用。）

被拒絕的替代方案

我們沒有認真考慮實現新解析器的其他方法，但這裡簡要討論一下 LALR(1)。

三十年前，第一作者決定採用自己的方式處理 Python 的解析器，而不是使用當時行業標準 LALR(1)（例如 Bison 和 Yacc）。原因主要是情感上的（直覺、預感），基於過去在其他專案中使用 Yacc 的經驗，當時語法開發比預期花費了更多精力（部分原因是移位-歸約衝突）。對 Bison 和 Yacc 的一個仍然成立的特定批評是，它們的元語法（用於將語法輸入解析器生成器的表示法）不支援 EBNF 的便利性，如 [optional_clause] 或 (repeated_clause)*。使用自定義解析器生成器，可以自動生成與語法結構匹配的語法樹，並且使用 EBNF，該樹可以與語法的“人類友好”結構匹配。

沒有考慮 LR 的其他變體，也沒有考慮 LL（例如 ANTLR）。選擇 PEG 是因為它在對遞迴下降解析有基本瞭解的情況下易於理解。

參考資料

[4] Guido 的 PEG 解析系列文章 https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60

來源：https://github.com/python/peps/blob/main/peps/pep-0617.rst

最後修改：2025-02-01 07:28:42 GMT