19. 解析
#19. 解析
解析は、トークン ストリームを構文構造に変換する段階です。
トークナイザーは語彙単位を認識します。パーサーは文法構造を認識します。一連のトークンが有効な Python プログラムであるかどうかを判断し、有効な場合は抽象構文ツリーを構築します。
このソースの場合:python def add(a, b): return a + b トークナイザーは次のようなトークンを生成します。text NAME "def" NAME "add" LPAR "(" NAME "a" COMMA "," NAME "b" RPAR ")" COLON ":" NEWLINE "\n" INDENT " " NAME "return" NAME "a" PLUS "+" NAME "b" NEWLINE "\n" DEDENT "" ENDMARKER "" パーサーはこれらのトークン構造を次のように与えます。text Module FunctionDef name="add" arguments arg "a" arg "b" body Return BinOp Name "a" Add Name "b" その違いは重要です。トークン化はそれを知っていますdef、add、(、a、 そして:存在する。解析では、これらが一緒になって関数定義を形成することがわかります。
19.1 コンパイルパイプラインでの位置
解析はトークン化とセマンティックコンパイルの間に位置します。```text source bytes ↓ encoding detection ↓ tokenization ↓ parsing ↓ abstract syntax tree ↓ symbol table ↓ compiler ↓ code object ↓ bytecode execution
その主な責任は次のとおりです。```text
recognize valid Python grammar
reject invalid syntax
group tokens into statements and expressions
apply operator precedence
handle indentation-based blocks
build AST nodes
produce useful syntax errors
```Python 言語リファレンスは、CPython で使用される完全な文法を公開しています。`Grammar/python.gram`ただし、コード生成とエラー回復に関連する実装の詳細は省略します。 ([Python ドキュメント][1])
## 19.2 CPython は PEG パーサーを使用します
最新の CPython は PEG パーサーを使用します。
PEG は表現文法の解析を意味します。 CPython は、Python 3.9 で古い LL(1) パーサーから PEG パーサーに切り替えました。 PEG パーサーを使用すると、Python の文法をより直接的に表現できるようになり、構文を追加する際の CPython の柔軟性が高まります。
PEG パーサーは、代替文法を順番に試すことによって機能します。成功した最初の選択肢が選択されます。
単純化されたルールは次のようになります。```text
statement:
| function_def
| class_def
| if_stmt
| while_stmt
| simple_stmt
```入力トークンが与えられると、パーサーはステートメントの照合を試みます。最初の代替案が失敗した場合は、次の代替案が試行されます。
この順序付けされた選択は、選択肢が順序付けされていない一部の文脈自由文法システムとは異なります。 PEG では順序が重要です。
## 19.3 文法規則
文法は有効なトークン シーケンスを定義します。
簡略化された関数定義ルールは次のように想像できます。```text
function_def:
"def" NAME "(" parameters? ")" ":" block
```これはつまり：```text
the keyword def
then a function name
then an opening parenthesis
then optional parameters
then a closing parenthesis
then a colon
then a block
```実際の CPython 文法は、デコレーター、非同期関数、アノテーション、位置のみのパラメーター、キーワードのみのパラメーター、デフォルト値、型パラメーター、戻りアノテーション、およびエラー回復をサポートしているため、さらに詳細になっています。
それでも、基本的なモデルは変わりません。```text
tokens are matched against grammar rules
rules call other rules
successful rules produce AST structure
failed rules produce backtracking or syntax errors
```## 19.4 ステートメントと式
Python 構文にはステートメントと式があります。
ステートメントはアクションを実行します。```python
x = 1
return x
if x:
print(x)
```式は値を生成します。```python
x + 1
f(a, b)
items[0]
lambda x: x + 1
```すべての式がどこでも許可されるわけではなく、すべてのステートメントが式内に出現できるわけでもないため、パーサーはこれらを区別する必要があります。
有効：```python
if ready:
run()
```無効：```python
x = if ready: run()
```有効：```python
value = a if ready else b
```文法はこれらの区別をエンコードします。`if`ステートメントは 1 つの文法領域に属するためです。条件式は別のものに属します。
## 19.5 ブロックとスイート
Python ブロックは次のように表されます。`INDENT`そして`DEDENT`トークン。
パーサーはスペースを直接カウントしません。トークナイザーはすでにインデントを構造トークンに変換しています。
例：```python
if x:
a = 1
b = 2
c = 3
```トークンの形状:```text
NAME "if"
NAME "x"
COLON ":"
NEWLINE
INDENT
NAME "a"
EQUAL
NUMBER "1"
NEWLINE
NAME "b"
EQUAL
NUMBER "2"
NEWLINE
DEDENT
NAME "c"
EQUAL
NUMBER "3"
NEWLINE
ENDMARKER
```パーサーはブロックをスイートとして認識します。```text
If
test: Name "x"
body:
Assign a = 1
Assign b = 2
Module body:
Assign c = 3
```この設計により、インデントの処理がほとんどの文法規則から外されます。文法は「ブロック」と言うことができ、トークナイザーによって生成されたものに依存します。`INDENT`そして`DEDENT`トークン。
## 19.6 式の解析と優先順位
式の解析には優先順位が必要です。
考慮する：```python
x = 1 + 2 * 3
```パーサーは以下を生成する必要があります。```text
1 + (2 * 3)
```ない：```text
(1 + 2) * 3
```AST の形状は次のとおりです。```text
Assign
target: Name "x"
value:
BinOp Add
left: Constant 1
right:
BinOp Mult
left: Constant 2
right: Constant 3
```文法規則は、式を階層化することによって優先順位をエンコードします。
簡略化したモデル:```text
expression
conditional expression
sum
term
sum "+" term
sum "-" term
term
factor
term "*" factor
term "/" factor
factor
atom
"-" factor
"+" factor
atom
NAME
NUMBER
STRING
"(" expression ")"
```優先順位の高い構成要素は文法の奥深くに表示されます。加算ルールは乗算レベルの式をオペランドとして使用するため、乗算は加算よりも緊密にバインドされます。
## 19.7 結合性
優先順位によって、どの演算子がより緊密にバインドされるかが決まります。結合性は、同じ優先順位グループの演算子をどのように決定するかを決定します。
例：```python
x = a - b - c
```これは次のように解析されます。```text
(a - b) - c
```ない：```text
a - (b - c)
```減算は左結合です。
ただし、べき乗の動作は異なります。```python
x = a ** b ** c
```これは次のように解析されます。```text
a ** (b ** c)
```文法はこれを明示的にエンコードする必要があります。結合性は実行時プロパティではありません。これは、評価が開始される前に解析構造によって修正されます。
## 19.8 呼び出し、属性、および添字
Python には後置式の形式があります。```python
obj.attr
obj.method(x)
items[i]
items[i:j]
f(x)(y).z
```これらはしっかりと連鎖します。
例：```python
result = client.session.get(url).json()["items"][0]
```パーサーは、これを主式に対する一連の操作としてグループ化します。```text
Name "client"
Attribute "session"
Attribute "get"
Call args=[Name "url"]
Attribute "json"
Call args=[]
Subscript "items"
Subscript 0
```これが、呼び出し、属性、添え字が算術演算子よりも強く結合される理由です。```python
x = f(a) + b.c
```呼び出しと属性は、加算式が形成される前に解析されます。
## 19.9 代入の解析
代入構文は式構文よりも制限されています。
有効な割り当てターゲットには次のものがあります。```python
x = 1
obj.attr = 1
items[0] = 1
a, b = pair
```無効な割り当てターゲットには次のものがあります。```python
1 = x
a + b = x
f() = x
```パーサーは、代入の左側が単なる式ではないことを認識する必要があります。有効なターゲットである必要があります。
これは拡張割り当てにも影響します。```python
x += 1
obj.value *= 2
items[i] -= 3
```注釈付きの割り当て:```python
x: int = 1
name: str
```CPython のパーサーと AST ビルダーは、読み取りに使用される式と書き込みに使用されるターゲットの違いを保持する必要があります。
AST レベルでは、名前にはコンテキストが含まれます。```text
Name id="x", ctx=Load
Name id="x", ctx=Store
Name id="x", ctx=Del
```例：```python
x = x + 1
```左`x`は`Store`。右`x`は`Load`。
## 19.10 曖昧さと順序付けられた選択
PEG 解析では、順序付けられた代替が使用されます。
複数の代替文法が同様に始まる構文を検討してください。パーサーは最初に 1 つの代替を試みます。成功すると、その結果が使用されます。失敗した場合は、後の代替手段が試行される可能性があります。
これにより、文法の作成者は曖昧さを解決するための制御された方法を得ることができます。
簡略化した例:```text
small_stmt:
| assignment
| expression
```代入は式のようなターゲットで始まることが多いため、単純な式の代替よりも先に代入の代替案を検討する必要があります。
入力：```python
x = 1
```接頭語`x`式を始めることもできますが、ステートメント全体は代入です。文法は、割り当てが優先されるように順序付けされ、構造化されている必要があります。
PEG は、CPython 文法表記の「cut」演算子もサポートしています。言語リファレンスには次のことが記載されています`~`文法内のマーカーは、現在の代替案にコミットし、代替案が失敗した場合にルールを失敗させるカットとして使用されます。 ([Python ドキュメント][1])
カットはパフォーマンスと診断に役立ちます。パーサーは、どの構造を解析しているかを知るのに十分なトークンを確認すると、無関係な代替案の検討を停止できます。
## 19.11 Lookahead
パーサーは多くの場合、何を解析するかを決定する前に、今後のトークンを検査する必要があります。
Lookahead は、「次のトークンまたは次のトークン シーケンスはこのパターンに一致しますか?」と尋ねます。
例：```python
x: int
```これにより、注釈付きの割り当てが開始される可能性があります。
例：```python
x + y
```これは式ステートメントです。
どちらも次から始まります`NAME`。パーサーには、最初のトークンよりも多くのコンテキストが必要です。
先読みは、構文を早期に拒否し、より適切なエラー メッセージを選択するのにも役立ちます。
簡略化された先読みモデル:```text
if next token is NAME and following token is ":":
parse annotated assignment
else:
parse expression statement
```実際の CPython 文法では、より豊富なメカニズムが使用されていますが、メンタル モデルは同じです。一部の決定では、トークンを永続的に消費せずに先を確認する必要があります。
## 19.12 バックトラッキング
PEG パーサーはバックトラックできます。
バックトラッキングとは、パーサーが文法パスを試行して失敗し、前のトークンの位置に戻して別のパスを試行することを意味します。
モデル例:```text
try parse async function definition
if it fails:
restore token position
try parse normal function definition
if it fails:
restore token position
try parse simple statement
```バックトラッキングにより、厳密な単一トークン先読みパーサーよりも柔軟な文法オーサリングが可能になります。
しかし、無制限のバックトラッキングはコストがかかる可能性があります。 CPython のパーサーは、文法構造、カット、メモ化、および対象を絞ったルールを使用して、解析の効率を維持します。
## 19.13 AST 建設
CPython での解析は、単に構文を受け入れたり拒否したりするだけではありません。 ASTを構築します。
ソース例:```python
x = 1 + 2
```AST形状:```text
Module
Assign
targets:
Name id="x", ctx=Store
value:
BinOp
left: Constant 1
op: Add
right: Constant 2
```Python レベルでは:```python
import ast
tree = ast.parse("x = 1 + 2\n")
print(ast.dump(tree, indent=4))
```これにより、構造化されたツリーが生成されます。
AST はまだバイトコードではありません。これは、コンテキストのロード/ストアやソースの場所などのセマンティックな注釈を備えた構文ツリーです。
## 19.14 ソースの場所
AST ノードはソースの位置情報を伝えます。
これには、行番号と列オフセットが含まれます。最新の CPython は、多くのノードの終了位置も追跡します。
例：```python
import ast
tree = ast.parse("x = 1 + 2\n")
node = tree.body[0]
print(node.lineno)
print(node.col_offset)
print(node.end_lineno)
print(node.end_col_offset)
```ソースの場所は以下をサポートします。```text
tracebacks
syntax errors
debuggers
coverage tools
profilers
AST tools
editor integrations
```正確なソース位置がなくても、CPython はコードを実行できますが、診断とツールの品質は大幅に低下します。
## 19.15 構文エラー
解析が失敗すると、CPython は次のエラーを発生させます。`SyntaxError`または次のようなサブクラス`IndentationError`。
構文エラーは次のように報告されます。```text
filename
line number
column offset
source text
message
```例：```python
if x
pass
```パーサーは、`if`ステートメントにコロンがありません。
解析が不可能になった場所の近くに有用なエラー ポイントがあります。```text
SyntaxError: expected ':'
```解析エラーは必ずしも単純なわけではありません。パーサーはバックトラックする可能性があるため、最終的に失敗した代替案だけを記憶するのではなく、最も有用な失敗場所を記憶する必要があります。
適切な構文エラーは、パーサー エンジニアリングの主要な部分を占めます。
## 19.16 無効なルールとより適切な診断
CPython の文法には、特にエラー メッセージを改善するために使用されるルールが含まれています。
パーサーは一般的に不正な構文を拒否できます。```text
SyntaxError: invalid syntax
```ただし、CPython はよくある間違いを検出しようとします。```python
if x = 1:
pass
```これにより、一般的な解析エラーよりも役立つメッセージが生成される可能性があります。
無効な文法規則はプログラムを受け入れることを目的としていません。これらは、間違ったフォームを認識し、より適切な診断を行うために使用されます。
実用的なモデル:```text
normal grammar accepts valid Python
invalid rules recognize common invalid Python
error machinery reports a targeted message
```これにより、ユーザー エクスペリエンスが向上しながら、パーサーの厳密性が維持されます。
## 19.17 パーサー出力はまだ完全には検証されていません
解析が成功した場合は、ソースが Python 文法と一致することを意味します。これは、プログラムがあらゆる意味で完全に有効であることを意味するものではありません。
解析後にいくつかのチェックが行われます。
例：```python
return 1
```モジュール レベルでは、これは構文的には return ステートメントのような形になりますが、関数の外では無効です。
別の例:```python
break
```モジュール レベルでは、これは文法的には Break ステートメントですが、ループの外では無効です。
これらの制約は、AST 検証、シンボル テーブル分析、またはコンパイル中にチェックされることがよくあります。
フェーズは別々です。```text
parser:
Can these tokens form a syntax tree?
later compiler checks:
Is this syntax legal in this context?
Which names are local, global, free, or cell variables?
Can this construct be compiled here?
```##19.18`ast.parse`一般の人々`ast.parse()`関数は、CPython の解析機構を Python レベルで公開します。
例：```python
import ast
src = """
def add(a, b):
return a + b
"""
tree = ast.parse(src)
print(ast.dump(tree, indent=4))
```これは次の場合に役立ちます。```text
linters
formatters
static analyzers
code generation tools
security scanners
refactoring tools
documentation tools
```しかし`ast.parse()`トークンやバイトコードではなく、AST を返します。
バイトコードの場合は、次を使用します`compile()`そして`dis`:
```python
import dis
code = compile("x = 1 + 2\n", "<input>", "exec")
dis.dis(code)
```関係は次のとおりです。```text
tokenize.tokenize() source to tokens
ast.parse() source to AST
compile() source or AST to code object
dis.dis() code object to bytecode display
```## 19.19 解析モード
Python ソースはさまざまなモードで解析できます。
共通モード:
|モード |意味 |
| -------- | -------------------------------------- |
|`exec`|モジュールまたはステートメントのシーケンスを解析する |
|`eval`|単一の式を解析する |
|`single`|対話型入力を解析する |
例：```python
compile("x = 1", "<input>", "exec")
compile("1 + 2", "<input>", "eval")
compile("print(1)", "<input>", "single")
evalモードはステートメントを拒否します。```python
compile("x = 1", "", "eval")
解析モードによって文法の開始記号が決まります。
## 19.20 F 文字列とパーサー
最新の CPython は、パーサー機構を通じて f 文字列式を解析します。
Python 3.12 より前では、f-string 式の解析にはより特殊な動作がありました。 Python 3.12 では PEP 701 を通じて f-string が変更され、より完全に文法に組み込まれました。 Python 3.12 のドキュメントには、f-string が PEG パーサーで解析されるため、より正確なエラー メッセージが可能になること、およびこれらの変更によりトークン化のパフォーマンスが向上したことが記載されています。 ([Python ドキュメント][2])
例:```python
name = "Ada"
text = f"hello {name.upper()}"
```埋め込まれた式:```python
name.upper()
```Python 式構文として解析されます。
これは、f-string が実行時の単なる文字列補間ではないことを意味します。これらには、構造的に解析して表現する必要がある入れ子になった構文が含まれています。
## 19.21 CPython のパーサー ファイル
重要なパーサー関連のソース領域には次のものがあります。```text
Grammar/python.gram
Parser/
Python/ast.c
Include/internal/
Lib/ast.py
Lib/test/test_grammar.py
Lib/test/test_syntax.py
```正確なファイル境界は変更される可能性がありますが、概念的な分割は安定しています。
|エリア |役割 |
| ---------------- | ------------------------------------------ |
|文法 | Python 構文を定義します |
|パーサージェネレーター |文法からパーサー実装を生成 |
|パーサーランタイム |トークンを消費し、文法規則を適用します。
| AST建設 | AST ノードを構築する |
| AST 検証 |構造の正しさをチェックします |
|テスト |構文と診断を保護する |
CPython を読むときは、文法から始めます。次に、文法規則が AST ノードを作成する方法に従います。
## 19.22 例: 関数の解析
出典:```python
def square(x):
return x * x
```トークンレベルのビュー:```text
NAME "def"
NAME "square"
LPAR "("
NAME "x"
RPAR ")"
COLON ":"
NEWLINE
INDENT
NAME "return"
NAME "x"
STAR "*"
NAME "x"
NEWLINE
DEDENT
ENDMARKER
```AST レベルのビュー:```text
Module
FunctionDef
name: "square"
args:
arguments
arg: "x"
body:
Return
BinOp
left: Name "x", Load
op: Mult
right: Name "x", Load
```文法が次のように述べているため、パーサーはこの階層を作成します。```text
a module contains statements
a function definition is a statement
a function body is a block
a return statement can contain an expression
a multiplication expression contains two operands
a name expression loads a value
```各レベルはフラットなトークン ストリームに意味を与えます。
## 19.23 例:`if`声明
出典:```python
if score >= 60:
result = "pass"
else:
result = "fail"
```AST形状:```text
Module
If
test:
Compare
left: Name "score"
op: GtE
comparator: Constant 60
body:
Assign
target: Name "result", Store
value: Constant "pass"
orelse:
Assign
target: Name "result", Store
value: Constant "fail"
```パーサーはアタッチする必要があります`else`正しく`if`。
ここでインデントトークンが役に立ちます。の`else`の後に表示されます`DEDENT`最初のブロックは終了しますが、ブロックと同じインデントレベルで終了します。`if`。
これは、Python のレイアウトに依存する構文がパーサー構造と直接対話する場所の 1 つです。
## 19.24 例: 内包表記の解析
出典:```python
squares = [x * x for x in values if x > 0]
```AST形状:```text
Assign
target: Name "squares", Store
value:
ListComp
element:
BinOp
Name "x"
Mult
Name "x"
generators:
comprehension
target: Name "x", Store
iter: Name "values", Load
ifs:
Compare
Name "x"
Gt
Constant 0
```内包表記は式構文ですが、代入のようなターゲットとネストされた句が含まれています。
パーサーは以下を区別する必要があります。```python
[x * x for x in values]
```リストリテラルから:```python
[x * x, y]
```どちらも次から始まります`[`そして表情。最初の式の後のトークン シーケンスによって、パーサーがどの構造を構築するかが決まります。
## 19.25 パーサーの境界
パーサーはコードを実行しません。
関数は呼び出しません。```python
f()
```呼び出しノードを構築するだけです。
モジュールはインポートされません。```python
import os
```インポートノードのみを構築します。
名前は解決されません。```python
x + y
```名前ノードと二項演算ノードのみを構築します。
AST レイヤーが表すものを超える定数は評価されません。
パーサーの仕事は構造的なものです。後のフェーズでは、スコープを割り当て、バイトコードを生成し、操作を実行します。
## 19.26 最小限のメンタルモデル
このモデルを使用します。```text
The tokenizer emits a flat stream of tokens.
The parser matches that stream against Python grammar.
CPython’s modern parser is PEG-based.
Grammar alternatives are ordered.
The parser builds an AST.
The AST records statements, expressions, contexts, and source locations.
Syntax errors are raised when the token stream cannot form valid grammar.
Some validity checks happen after parsing.
```解析では、ソース テキストが最初にツリー状になります。この段階以降のすべては、生のトークンの順序ではなく構造に基づいて機能します。