構文解析器入門

PHPカンファレンス関西2025「構文解析器入門」の発表スライド
https://2025.kphpug.jp/ #phpkansai

Transcript

1. 2025年7月19日(土) PHPカンファレンス関西2025 @ydah 構文解析器入門 1
2. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 $whoami ydah / わいだー GitHub: ydah / 旧Twitter: ydah_ Rubyコミッタ / Lrama(LRパーサージェネレータ)コミッタ ビールとパーサーとパーサージェネレーターが好き 2
3. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 3 1週間前...
4. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 $whoami ydah / わいだー GitHub: ydah / 旧Twitter: ydah_ Rubyコミッタ / Lrama(LRパーサージェネレータ)コミッタ ビールとパーサーとパーサージェネレーターが好き PHP(パーサー)コントリビューター 4 NEW!
5. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 5 今日、話すこと
6. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 6 構文解析器 (パーサー)
7. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 構文解析器周辺の知識を完全に理解する PHPコードが実行されるまでの大まかな流れを理解する パーサーの文法定義ファイルの読み方の取っ掛かりを知る 7 本日のゴール
8. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 40分で話せる内容は限られているので本当に「入門の入門」 廊下とか懇親会で質問してほしいなとおもいます 明日からすぐに役立つ知識ではない けど、そういうのって楽しいですよね 8 大前提
9. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 9 構文解析器の役割
10. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 10 PHPが実行されるまで 字 句 解 析 器 構 文 解 析 器 コ ン パ イ ラ イ ン タ プ リ タ 文字列 (バイト列) トークン列 抽象構文木 (AST) オペコード
11. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 11 バイト列は字句解析器に渡される 字 句 解 析 器 構 文 解 析 器 コ ン パ イ ラ イ ン タ プ リ タ 文字列 (バイト列) トークン列 抽象構文木 (AST) オペコード
12. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 文字の並びを解析して、意味のある最小単位(終端トークン)に 分解する 12 字句解析器(レキサー)は <?php echo "Hello, World!"; 0 : T_OPEN_TAG | "<?php\n" | Line: 1 1 : T_ECHO | "echo" | Line: 2 2 : T_WHITESPACE | " " | Line: 2 3 : T_CONSTANT_ENCAPSED_STRING | "\"Hello, World!\"" | Line: 2 4 : SYMBOL | ";"
13. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 実際にはバイト列なのでイメージはこんな感じ 13 トークンに分割する様子 3c 3f 70 68 70 0a 65 63 68 6f 20 22 48 65 6c 6c 6f 2c 20 57 6f 72 6c 64 21 22 3b <?php echo <space>
14. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 14 トークン列の確認方法
15. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 15 トークン列の確認方法 $tokens = token_get_all($sourceCode); foreach ($tokens as $index = > $token) { if (is_array($token)) { echo sprintf( "%3d: %-25s | %-15s | Line: %d\n", $index, token_name($token[0]), json_encode($token[1], JSON_UNESCAPED_UNICODE), $token[2] ); } else { echo sprintf( "%3d: %-25s | %-15s | \n", $index, 'SYMBOL', json_encode($token, JSON_UNESCAPED_UNICODE) ); } }
16. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 手書き or レキサージェネレーター レキサージェネレータ(skvadrik/re2c)で作られている 定義ファイルから生成 php-src/Zend/zend_language_scanner.l 16 レキサーの作り方
17. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 意味のある単位で切り出す 状態を管理する 切り出した文字列の種別と状態から返すトークンを決定する 17 レキサーの考え方
18. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 この状態の時に 18 読み方（ざっくり） <ST_IN_SCRIPTING>"return" { RETURN_TOKEN_WITH_IDENT(T_RETURN); } "return" を見つけたら T_RETURN というトークンを返す
19. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 19 トークン列は構文解析器へ 字 句 解 析 器 構 文 解 析 器 コ ン パ イ ラ イ ン タ プ リ タ 文字列 (バイト列) トークン列 抽象構文木 (AST) オペコード
20. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 字句解析から受け取ったトークン列が、文法的に正しいかを 検査して抽象構文木を作成する 20 構文解析器(パーサー)は T_OPEN_TAG T_FUNCTION T_WHITESPACE T_STRING SYMBOL <?php function hello() { echo "Hello, World!"; } . . . AST_STMT_LIST AST_FUNC_DECL 'hello' AST_PARAM_LIST AST_STMT_LIST AST_ECHO 'Hello, World!'
21. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 21 抽象構文木とは Abstract Syntax Tree(AST) プログラムやコードスニペットの構造を表すために使用される データ構造
22. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 22 身近な例 数式の例: 3 + 4 * 2 → 3 + (4 * 2) + 3 * 4 2
23. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 23 身近な例 数式の例: 3 + 4 * 2 → 3 + (4 * 2) + 3 4 2 *
24. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 24 身近な例 数式の例: 3 + 4 * 2 → 3 + (4 * 2) 4 2 3 8 +
25. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 25 パーサーの作り方 手書き or パーサージェネレーター パーサージェネレータ(GNU Bison)で作られている 定義ファイルから生成 php-src/Zend/zend_language_parser.y
26. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 トップダウン構文解析 再帰下降構文解析、LL法、パックラット構文解析(PEG) ボトムアップ構文解析 (BisonはLRパーサーを作成する) LR法(SLR、LALR、GLR)、アーリー法 26 パーサーの種類
27. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 27 LRパーサーとは LRとは「Left-to-right, Rightmost derivation in reverse」の 略で以下の特徴を持つ 入力を左から右へ一度だけスキャンする ボトムアップ構文解析を行い、最右導出を逆順で生成する バックトラックや推測なしに、線形時間で解析を行う
28. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 28 LRパーサーの理論 Donald Ervin Knuthが1965年に発表した論文が基盤 単に新しいアルゴリズムを提示しただけでなく、形式文法から 効率的かつ決定論的なパーサーを機械的に生成する強力な理論的 枠組みを確立した Donald E. Knuth (1965). On the Translation of Languages from Left to Right. https://www.sciencedirect.com/science/article/pii/S0019995865904262
29. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 解析木を末端の葉から始めて、文法 規則を逆に適用しながら、最終的に根 へと構築していく 29 LRパーサーの動作 Bottom-up parse tree built in numbered steps https://en.wikipedia.org/wiki/LR_parser#/media/File:Shift-Reduce_Parse_Steps_for_A*2+1.svg
30. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 30 そしてASTはコンパイルされる 字 句 解 析 器 構 文 解 析 器 コ ン パ イ ラ イ ン タ プ リ タ 文字列 (バイト列) トークン列 抽象構文木 (AST) オペコード
31. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 抽象構文木(AST)を再帰的に走査してオペコードを出力する 最適化もここで実行する zend_try_compile_special_func() 関数呼び出しから、より効率的な専用の命令にコンパイル 31 コンパイラは
32. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 文字列・型操作 (strlen / chr / ord ...) strlen("hoge") は int(4) に変換 型チェック関数 (is_null / is_int ...) 専用の型チェック命令に変換 定数の畳み込み (60 * 60 * 24) 60 * 60 * 24 は int(86400) に変換 32 最適化の例
33. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 コンピュータの機械語における命令の種類を指定するコード プロセッサに何をしてほしいのかを明示的に指示する 33 オペコードとは 0000 ECHO string("Hello, World!") 0001 RETURN int(1)
34. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 php.ini に以下の設定を追加する opcache.opt_debug_level オプションを付与して実行 34 オペコードの見方 - Opcache $ php - d opcache.opt_debug_level=0 x 10000 test.php opcache.enable_cli=1
35. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 35 実行結果 <?php echo "Hello, World!"; $_main: ; (lines=2, args=0, vars=0, tmps=0) ; (before optimizer) ; /Users/ydah/php - src/test.php:1-3 ; return [] RANGE[0 . . 0] 0000 ECHO string("Hello, World!") 0001 RETURN int(1) Hello, World! 実行時のメタ情報 オペコード
36. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 36 最適化の様子 <?php echo strlen("Hello, World!"); $_main: ; (lines=2, args=0, vars=0, tmps=0) ; (before optimizer) ; /Users/ydah/php - src/test.php:1-3 ; return [] RANGE[0 . . 0] 0000 ECHO int(13) 0001 RETURN int(1) 13 最適化されている!
37. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 37 そして実行される 字 句 解 析 器 構 文 解 析 器 コ ン パ イ ラ イ ン タ プ リ タ 文字列 (バイト列) トークン列 抽象構文木 (AST) オペコード
38. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 生成されたオペコードを、インタプリタ(Zend Engine)が順番 に実行します 38 オペコードを実行
39. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 39 パーサージェネレータの役割
40. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 構文解析器(パーサー)を作成するプログラム 文法定義を入力として受け取って、その文法に従って構文解析 を行うためのパーサーのコードを出力する PHP、PerlはGNU Bison、RubyではLramaというLRパー サージェネレーターを使用している 40 パーサージェネレータとは
41. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 1959年にTony BrookerとDerrick Morrisによって作られた Brooker Morris Compiler Compilerが最古 1970年代初頭にはStephen C. JohnsonがYaccを開発 1985年にRobert CorbettによってGNU Bisonが初回リリース 2000年代以降は下火となり手書きパーサーが主流に 41 パーサージェネレータの歴史
42. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 正確性と信頼性 理論的に証明された構文解析アルゴリズムに基づいている 文法の曖昧性の検出が可能 文法設計の段階で問題を発見し修正可能 形式的な文法仕様 言語仕様が明確になり、ドキュメントとしても機能する 42 パーサージェネレータの利点
43. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 手書きパーサーで作られる言語は多いが、一方でパーサージェ ネレータに関する論文も近年いくつか出て来ている 今、Rubyでは手書きパーサーとパーサージェネレータがある どちらかが正式に採用されるのはまだもう少し先 我々はパーサージェネレータの力を信じている 43 手書き vs パーサージェネレータ
44. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 44 閑話休題
45. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 45 PHPの場合 構 文 解 析 器 生 成 器 文法ファイル 構文解析器 (パーサー) zend_language_parser.c zend_language_parser.y
46. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 46 パーサーを完全に理解するとは 構 文 解 析 器 生 成 器 文法ファイル 構文解析器 (パーサー) こやつの読み方がわかればおk
47. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 47 文法ファイルの読みかた %code top { / / C code } %def i ne api.pref i x {zend} . . . %destructor { zend_ast_destroy($$); } <ast> . . . %precedence T_THROW . . . %token <ast> T_LNUMBER "integer" . . . %type <ast> top_statement namespace_name name statement . . . . . . % % / * Rules * / start: top_statement_list { CG(ast) = $1; (void) zendnerrs; }; . . . % % / / C code
48. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 48 文法ファイルの読みかた %code top { / / C code } %def i ne api.pref i x {zend} . . . %destructor { zend_ast_destroy($$); } <ast> . . . %precedence T_THROW . . . %token <ast> T_LNUMBER "integer" . . . %type <ast> top_statement namespace_name name statement . . . . . . % % / * Rules * / start: top_statement_list { CG(ast) = $1; (void) zendnerrs; }; . . . % % / / C code
49. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 必要なヘッダを #include していたり、マクロを定義していたり 49 ヘッダ部 %code top { #include "zend.h" #include "zend_list.h" . . . #def i ne YYSIZE_T size_t #def i ne yytnamerr zend_yytnamerr static YYSIZE_T zend_yytnamerr(char * , const char*); #ifdef _MSC_VER #def i ne YYMALLOC malloc #def i ne YYFREE free #endif }
50. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 50 文法ファイルの読みかた %code top { / / C code } %def i ne api.pref i x {zend} . . . %destructor { zend_ast_destroy($$); } <ast> . . . %precedence T_THROW . . . %token <ast> T_LNUMBER "integer" . . . %type <ast> top_statement namespace_name name statement . . . . . . % % / * Rules * / start: top_statement_list { CG(ast) = $1; (void) zendnerrs; }; . . . % % / / C code
51. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 Bisonの動作の設定は文法ファイル内で設定できる 51 Bison動作設定部 %def i ne api.pref i x {zend} %def i ne api.pure full %def i ne api.value.type {zend_parser_stack_elem} %def i ne parse.error verbose %expect 0 生成されるパーサ関数やシンボルの接頭辞の設定 エラーメッセージの設定 shift/reduce競合の期待数
52. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 52 文法ファイルの読みかた %code top { / / C code } %def i ne api.pref i x {zend} . . . %destructor { zend_ast_destroy($$); } <ast> . . . %precedence T_THROW . . . %token <ast> T_LNUMBER "integer" . . . %type <ast> top_statement namespace_name name statement . . . . . . % % / * Rules * / start: top_statement_list { CG(ast) = $1; (void) zendnerrs; }; . . . % % / / C code
53. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 パーサがエラー回復時やスタックのクリーンアップ時に、メモ リリークを防ぐための自動的なリソース解放処理を定義できる 53 デストラクタの設定 %destructor { zend_ast_destroy($$); } <ast> %destructor { if ($$) zend_string_release_ex($$, 0); } <str> ASTノードの破棄 対象の型
54. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 54 デストラクタの動作例 $a + $b の部分でASTノードが作成されていますが、構文エラーのため 使用されない %destructorにより、自動的にzend_ast_destroy()で解放されます <?php $result = $a + $b +
55. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 55 文法ファイルの読みかた %code top { / / C code } %def i ne api.pref i x {zend} . . . %destructor { zend_ast_destroy($$); } <ast> . . . %precedence T_THROW . . . %token <ast> T_LNUMBER "integer" . . . %type <ast> top_statement namespace_name name statement . . . . . . % % / * Rules * / start: top_statement_list { CG(ast) = $1; (void) zendnerrs; }; . . . % % / / C code
56. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 BisonのデフォルトのエラーメッセージフォーマットをPHP用 にカスタマイズする関数が定義されているのみ 56 ユーザー定義部 static YYSIZE_T zend_yytnamerr(char * yyres, const char * yystr) { / / লུ }
57. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 57 ここまでは雰囲気が分かればおk
58. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 58 大事なのはここ %code top { / / C code } %def i ne api.pref i x {zend} . . . %destructor { zend_ast_destroy($$); } <ast> . . . %precedence T_THROW . . . %token <ast> T_LNUMBER "integer" . . . %type <ast> top_statement namespace_name name statement . . . . . . % % / * Rules * / start: top_statement_list { CG(ast) = $1; (void) zendnerrs; }; . . . % % / / C code
59. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 生成規則という「言語の文法ルール」を定義するところ 文法をBisonに伝えるために書くのが生成規則 定義部分は2つのセクションに分かれている 宣言部: トークンを定義しているところ 規則部: 生成規則を定義しているところ 59 生成規則の定義部
60. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 バッカス・ナウア記法(BNF)で書かれている(Bison向けの亜種) 60 生成規則のフォーマット expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } ;
61. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 文脈自由文法を定義するのに使うメタ言語 John Warner BackusとPeter NaurがALGOL 60の文法定義の ために考案し1959年に論文を発表した 61 バッカス・ナウア記法 Backus, J.W. (1959). The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference. IFIP Congress. https://api.semanticscholar.org/CorpusID:44764020
62. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 簡単な足し算を表す生成規則の例 62 生成規則の書き方 expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } ;
63. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 「非終端記号」と「終端記号」 63 生成規則にあらわれる2つの記号 expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } ;
64. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 64 非終端記号 expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } ; 終端記号や、非終端記号を組み合わせて作る文法上のまとまり 「式」や「文」といった抽象的なルールやカテゴリ名 展開の途中で最終的には終端記号の集まりに置き換えられる
65. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 65 非終端記号は展開可能 expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } ; expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } ; expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } ; 展開 展開
66. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 66 終端記号 expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } ; これ以上展開できない、いちばん基本的な単語や記号 キーワード、数字、演算子など
67. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 Right Hand Side(RHS) Left Hand Side (LHS) 左辺が生成規則の名前、右辺は展開する規則 67 生成規則の左辺と右辺 expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } ;
68. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 68 複数ルールをまとめる | expr : NUMBER | expr '+' expr ; NUMBER expr + expr expr は 生成規則は複数のルールをもつことがある 例えば以下の例で「式」は「数字」もしくは「式」+「式」 もしくは
69. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 2つの基本操作を使って入力を解析する シフト(shift) 還元(reduce) 69 LRパーサの解析方法
70. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 70 %token FOO BAR BAZ % % program: FOO BAR BAZ 単純な文法の例
71. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 レキサー パーサー 71 シフト(shift) 入力から次のトークンを読み取り、構文解析器のスタックに積む操作 レキサーから来る記号をどんどんプッシュしていく FOO BAZ BAR BAZ シフト
72. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 パーサー スタック上に積まれているトークンの並びが、ある文法規則に 一致するときに、一つの非終端記号に置き換える操作 72 還元(reduce) FOO BAR BAZ program 還元
73. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 レキサー パーサー 73 シンプルな足し算の例 expr : NUMBER '+' NUMBER ;
74. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 レキサー パーサー 74 左辺の数値がレキサーから渡される expr : NUMBER '+' NUMBER ; 10 10 シフト
75. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 レキサー パーサー 75 + がレキサーから渡される expr : NUMBER '+' NUMBER ; ＋ 10 シフト ＋
76. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 レキサー パーサー 76 右辺の数値がレキサーから渡される expr : NUMBER '+' NUMBER ; 5 10 シフト ＋ 5
77. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 パーサー 77 生成規則に一致したので還元 expr : NUMBER '+' NUMBER ; 10 ＋ 5
78. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 パーサー 78 一つの非終端記号に置き換える expr : NUMBER '+' NUMBER ; expr
79. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 79 これだけではASTは作れない
80. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 Bisonではパーサーが還元する瞬間をフックすることができる 構文の「意味」を定義して、ASTを組み立てる役割を担う 80 セマンティックアクション program: FOO BAR BAZ { /* ͕͜͜ΞΫγϣϯ * / };
81. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 アクション内はCのコードだが特殊変数を使用可能 81 特殊変数 exp: exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | NUM { $$ = $1; } 規則の構成要素の意味値 現在の規則の意味値
82. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 82 簡単なASTを組み立てる例 expr: expr '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); };
83. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 83 3 がレキサーから渡される expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー 3 3 シフト
84. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 84 アクションが実行されてノード作成 expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー 3 3
85. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 85 ノードを $$ に代入 expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー 3 3
86. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 86 還元 expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3
87. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 87 + がレキサーから渡される expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3 + シフト +
88. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 88 5 がレキサーから渡される expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3 + シフト + 5
89. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 89 5 は 生成規則 term にマッチする expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー 3 5 シフト 5
90. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 90 アクションが実行されてノード作成 expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー 5 3 5
91. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 91 ノードを $$ に代入 expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー 5 3 5
92. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 92 還元 expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3
93. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 93 この状態になる expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3 term + term 5
94. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 94 expr の生成規則にマッチする expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3 term + term 5
95. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 95 アクションが実行されてノード作成 expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3 + term 5 +
96. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 96 還元 expr: term '+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term expr 3 5 +
97. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 97 ここからは宣言部
98. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 98 文法ファイルの読みかた %code top { / / C code } %def i ne api.pref i x {zend} . . . %destructor { zend_ast_destroy($$); } <ast> . . . %precedence T_THROW . . . %token <ast> T_LNUMBER "integer" . . . %type <ast> top_statement namespace_name name statement . . . . . . % % / * Rules * / start: top_statement_list { CG(ast) = $1; (void) zendnerrs; }; . . . % % / / C code
99. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 99 優先順位(precedence)と結合性(associativity) %precedence T_THROW %precedence PREC_ARROW_FUNCTION %precedence T_INCLUDE T_INCLUDE_ONCE T_REQUIRE T_REQUIRE_ONCE %left T_LOGICAL_OR %left T_LOGICAL_XOR %left T_LOGICAL_AND %precedence T_PRINT %precedence T_YIELD %precedence T_DOUBLE_ARROW %precedence T_YIELD_FROM %precedence '=' T_PLUS_EQUAL T_MINUS_EQUAL T_MUL_EQUAL T_DIV_EQUAL T_CONCAT_EQUAL T_MOD_EQUAL T_AND_EQUAL T_OR_EQUAL T_XOR_EQUAL T_SL_EQUAL T_SR_EQUAL T_POW_EQUAL T_COALESCE_EQUAL %left '?' ':' %right T_COALESCE %left T_BOOLEAN_OR %left T_BOOLEAN_AND %left '|' %left '^' %left T_AMPERSAND_NOT_FOLLOWED_BY_VAR_OR_VARARG T_AMPERSAND_FOLLOWED_BY_VAR_OR_VARARG %nonassoc T_IS_EQUAL T_IS_NOT_EQUAL T_IS_IDENTICAL T_IS_NOT_IDENTICAL T_SPACESHIP %nonassoc '<' T_IS_SMALLER_OR_EQUAL '>' T_IS_GREATER_OR_EQUAL %left T_PIPE %left '.' %left T_SL T_SR %left '+' '-' %left '*' '/' '%' %precedence '!' %precedence T_INSTANCEOF %precedence '~' T_INT_CAST T_DOUBLE_CAST T_STRING_CAST T_ARRAY_CAST T_OBJECT_CAST T_BOOL_CAST T_UNSET_CAST '@' %right T_POW %precedence T_CLONE / * Resolve danging else conflict * / %precedence T_NOELSE %precedence T_ELSEIF %precedence T_ELSE
100. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 100 優先順位(precedence) %precedence T_THROW %precedence PREC_ARROW_FUNCTION %precedence T_INCLUDE T_INCLUDE_ONCE T_REQUIRE T_REQUIRE_ONCE %left T_LOGICAL_OR %left T_LOGICAL_XOR %left T_LOGICAL_AND %precedence T_PRINT %precedence T_YIELD : 上から下へ優先順位が高くなる 同じ行にある演算子は同じ優先順位を持つ
101. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 101 ぶら下がり else 問題 if ($a) if ($b) echo "b"; else echo "else"; どちらのifに対応するelse?
102. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 102 ぶら下がり else 問題 if ($a) if ($b) echo "b"; else echo "else"; 正解はこっちのifです
103. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 103 ぶら下がり else 問題 / * Resolve danging else conflict * / %precedence T_NOELSE %precedence T_ELSEIF %precedence T_ELSE 優先度高 T_ELSEの優先順位が高い
104. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 104 ぶら下がり else 問題 if ($a) if ($b) echo "b"; else echo "else"; ここまで読み込んで この else / * Resolve danging else conflict * / %precedence T_NOELSE %precedence T_ELSEIF %precedence T_ELSE elseがないよりもある方が優先度高い
105. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 105 ぶら下がり else 問題 if ($a) if ($b) echo "b"; else echo "else"; / * Resolve danging else conflict * / %precedence T_NOELSE %precedence T_ELSEIF %precedence T_ELSE T_ELSEの優先順位が高いため内側のifに結合
106. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 106 結合性(associativity) 同じ演算子が連続して使用されたときの評価順序を決定する 例: x op y op zという式をどのようにグループ化するか 3つの結合性の定義方法がある %leftɺ%rightɺ%nonassoc
107. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 左から右へグループ化する 算術演算子の多くは左結合 107 左結合(%left) %left '+' '-' %left '*' '/' '%' (a + b) + c a + b + c
108. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 右から左へグループ化する 累乗演算子は右結合 108 右結合(%right) %right T_POW a * * (b * * c) a * * b * * c
109. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 連続使用は構文エラーになる 比較演算子は連鎖比較不可 109 非結合(%nonassoc) %nonassoc '<' '>' T_IS_EQUAL PHP Parse error a < b < c
110. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 優先順位のみ定義 代入演算子や特殊な構文要素 110 結合性なし(%precedence) %precedence '=' T_PLUS_EQUAL T_MINUS_EQUAL T_MUL_EQUAL . . .
111. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 111 文法ファイルの読みかた %code top { / / C code } %def i ne api.pref i x {zend} . . . %destructor { zend_ast_destroy($$); } <ast> . . . %precedence T_THROW . . . %token <ast> T_LNUMBER "integer" . . . %type <ast> top_statement namespace_name name statement . . . . . . % % / * Rules * / start: top_statement_list { CG(ast) = $1; (void) zendnerrs; }; . . . % % / / C code
112. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 112 記号の型を定義する %token <ast> T_LNUMBER "integer" %token <ast> T_DNUMBER "floating - point number" %token <ast> T_STRING "identif i er" . . . %type <ast> top_statement namespace_name name statement . . . %type <ast> class_declaration_statement trait_declaration_statement . . . %type <ast> interface_declaration_statement interface_extends_list . . . 終端記号は %token を使って定義する 非終端記号は %type を使って定義する
113. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 113 終端記号の型定義 %token <ast> T_LNUMBER "integer" %token <ast> T_DNUMBER "floating - point number" %token <ast> T_STRING "identif i er" %token <ast> T_NAME_FULLY_QUALIFIED "fully qualif i ed name" %token <ast> T_NAME_RELATIVE "namespace - relative name" . . . %token を使用して終端記号と型情報を紐づける 説明用の名前(エラーメッセージ) 型情報 終端記号名
114. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 114 非終端記号の型定義 %type <ast> top_statement namespace_name name statement . . . %type <ast> class_declaration_statement trait_declaration_statement . . . %type <ast> interface_declaration_statement interface_extends_list %type <ast> group_use_declaration inline_use_declarations . . . %type <ast> mixed_group_use_declaration use_declaration . . . . . . %type を使用して非終端記号と型情報を紐づける 型情報 終端記号名
115. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 115 非終端記号の型とは？ $$の型 = 非終端記号の型 %token <int> NUM %type <int> exp % % exp: exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | NUM { $$ = $1; }
116. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 116 非終端記号の型とは？ $$の型 = 非終端記号の型 %token <int> NUM %type <int> exp % % exp: exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | NUM { $$ = $1; } int int
117. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 117 非終端記号の型とは？ $$の型 = 非終端記号の型 %token <int> NUM %type <int> exp % % exp: exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | NUM { $$ = $1; } int
118. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 118 非終端記号の型とは？ $$の型 = 非終端記号の型 %token <int> NUM %type <int> exp % % exp: exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | NUM { $$ = $1; } 終端記号NUMの足し引きなのでint
119. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 119 もうこれで読めますね %code top { / / C code } %def i ne api.pref i x {zend} . . . %destructor { zend_ast_destroy($$); } <ast> . . . %precedence T_THROW . . . %token <ast> T_LNUMBER "integer" . . . %type <ast> top_statement namespace_name name statement . . . . . . % % / * Rules * / start: top_statement_list { CG(ast) = $1; (void) zendnerrs; }; . . . % % / / C code
120. ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 4つの工程を経て、コードからPHPが実行されるよ PHPはGNU Bisonでパーサーを生成しているよ 定義ファイルはBison向けのBNFで書かれているよ 生成規則の定義部を基本的に読むことになるよ 構文解析器はいいぞ パーサージェネレータはいいぞ パーサージェネレータを使っている PHP って最高ですね 120 まとめ