Share
Embed
Transcript
120 slides
-
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 $whoami ydah / わいだー GitHub: ydah / 旧Twitter:
ydah_ Rubyコミッタ / Lrama(LRパーサージェネレータ)コミッタ ビールとパーサーとパーサージェネレーターが好き 2 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 $whoami ydah / わいだー GitHub: ydah / 旧Twitter:
ydah_ Rubyコミッタ / Lrama(LRパーサージェネレータ)コミッタ ビールとパーサーとパーサージェネレーターが好き PHP(パーサー)コントリビューター 4 NEW! -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 10 PHPが実行されるまで 字 句 解 析 器 構
文 解 析 器 コ ン パ イ ラ イ ン タ プ リ タ 文字列 (バイト列) トークン列 抽象構文木 (AST) オペコード -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 11 バイト列は字句解析器に渡される 字 句 解 析 器 構
文 解 析 器 コ ン パ イ ラ イ ン タ プ リ タ 文字列 (バイト列) トークン列 抽象構文木 (AST) オペコード -
ぴーえいちぴーカンファレンスかんさい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 | ";" -
ぴーえいちぴーカンファレンスかんさい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> -
ぴーえいちぴーカンファレンスかんさい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) ); } } -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 19 トークン列は構文解析器へ 字 句 解 析 器 構
文 解 析 器 コ ン パ イ ラ イ ン タ プ リ タ 文字列 (バイト列) トークン列 抽象構文木 (AST) オペコード -
ぴーえいちぴーカンファレンスかんさい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!' -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 22 身近な例 数式の例: 3 + 4 * 2
→ 3 + (4 * 2) + 3 * 4 2 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 23 身近な例 数式の例: 3 + 4 * 2
→ 3 + (4 * 2) + 3 4 2 * -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 24 身近な例 数式の例: 3 + 4 * 2
→ 3 + (4 * 2) 4 2 3 8 + -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 25 パーサーの作り方 手書き or パーサージェネレーター パーサージェネレータ(GNU Bison)で作られている 定義ファイルから生成
php-src/Zend/zend_language_parser.y -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 27 LRパーサーとは LRとは「Left-to-right, Rightmost derivation in reverse」の 略で以下の特徴を持つ
入力を左から右へ一度だけスキャンする ボトムアップ構文解析を行い、最右導出を逆順で生成する バックトラックや推測なしに、線形時間で解析を行う -
ぴーえいちぴーカンファレンスかんさい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 -
ぴーえいちぴーカンファレンスかんさい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 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 30 そしてASTはコンパイルされる 字 句 解 析 器 構
文 解 析 器 コ ン パ イ ラ イ ン タ プ リ タ 文字列 (バイト列) トークン列 抽象構文木 (AST) オペコード -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 文字列・型操作 (strlen / chr / ord ...) strlen("hoge")
は int(4) に変換 型チェック関数 (is_null / is_int ...) 専用の型チェック命令に変換 定数の畳み込み (60 * 60 * 24) 60 * 60 * 24 は int(86400) に変換 32 最適化の例 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 php.ini に以下の設定を追加する opcache.opt_debug_level オプションを付与して実行 34 オペコードの見方 - Opcache
$ php - d opcache.opt_debug_level=0 x 10000 test.php opcache.enable_cli=1 -
ぴーえいちぴーカンファレンスかんさい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! 実行時のメタ情報 オペコード -
ぴーえいちぴーカンファレンスかんさい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 最適化されている! -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 37 そして実行される 字 句 解 析 器 構
文 解 析 器 コ ン パ イ ラ イ ン タ プ リ タ 文字列 (バイト列) トークン列 抽象構文木 (AST) オペコード -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 1959年にTony BrookerとDerrick Morrisによって作られた Brooker Morris Compiler Compilerが最古 1970年代初頭にはStephen
C. JohnsonがYaccを開発 1985年にRobert CorbettによってGNU Bisonが初回リリース 2000年代以降は下火となり手書きパーサーが主流に 41 パーサージェネレータの歴史 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 45 PHPの場合 構 文 解 析 器 生
成 器 文法ファイル 構文解析器 (パーサー) zend_language_parser.c zend_language_parser.y -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 46 パーサーを完全に理解するとは 構 文 解 析 器 生
成 器 文法ファイル 構文解析器 (パーサー) こやつの読み方がわかればおk -
ぴーえいちぴーカンファレンスかんさい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 -
ぴーえいちぴーカンファレンスかんさい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 -
ぴーえいちぴーカンファレンスかんさい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 } -
ぴーえいちぴーカンファレンスかんさい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 -
ぴーえいちぴーカンファレンスかんさい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競合の期待数 -
ぴーえいちぴーカンファレンスかんさい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 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 パーサがエラー回復時やスタックのクリーンアップ時に、メモ リリークを防ぐための自動的なリソース解放処理を定義できる 53 デストラクタの設定 %destructor { zend_ast_destroy($$); }
<ast> %destructor { if ($$) zend_string_release_ex($$, 0); } <str> ASTノードの破棄 対象の型 -
ぴーえいちぴーカンファレンスかんさい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 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 BisonのデフォルトのエラーメッセージフォーマットをPHP用 にカスタマイズする関数が定義されているのみ 56 ユーザー定義部 static YYSIZE_T zend_yytnamerr(char *
yyres, const char * yystr) { / / লུ } -
ぴーえいちぴーカンファレンスかんさい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 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 バッカス・ナウア記法(BNF)で書かれている(Bison向けの亜種) 60 生成規則のフォーマット expr : NUMBER { $$
= $1; } | expr '+' expr { $$ = $1 + $3; } ; -
ぴーえいちぴーカンファレンスかんさい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 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 簡単な足し算を表す生成規則の例 62 生成規則の書き方 expr : NUMBER { $$
= $1; } | expr '+' expr { $$ = $1 + $3; } ; -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 「非終端記号」と「終端記号」 63 生成規則にあらわれる2つの記号 expr : NUMBER { $$
= $1; } | expr '+' expr { $$ = $1 + $3; } ; -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 64 非終端記号 expr : NUMBER { $$ =
$1; } | expr '+' expr { $$ = $1 + $3; } ; 終端記号や、非終端記号を組み合わせて作る文法上のまとまり 「式」や「文」といった抽象的なルールやカテゴリ名 展開の途中で最終的には終端記号の集まりに置き換えられる -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 65 非終端記号は展開可能 expr : NUMBER { $$ =
$1; } | expr '+' expr { $$ = $1 + $3; } ; expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } ; expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } ; 展開 展開 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 66 終端記号 expr : NUMBER { $$ =
$1; } | expr '+' expr { $$ = $1 + $3; } ; これ以上展開できない、いちばん基本的な単語や記号 キーワード、数字、演算子など -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 Right Hand Side(RHS) Left Hand Side (LHS) 左辺が生成規則の名前、右辺は展開する規則
67 生成規則の左辺と右辺 expr : NUMBER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } ; -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 68 複数ルールをまとめる | expr : NUMBER | expr
'+' expr ; NUMBER expr + expr expr は 生成規則は複数のルールをもつことがある 例えば以下の例で「式」は「数字」もしくは「式」+「式」 もしくは -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 70 %token FOO BAR BAZ % % program:
FOO BAR BAZ 単純な文法の例 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 レキサー パーサー 75 + がレキサーから渡される expr : NUMBER
'+' NUMBER ; + 10 シフト + -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 レキサー パーサー 76 右辺の数値がレキサーから渡される expr : NUMBER '+'
NUMBER ; 5 10 シフト + 5 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 アクション内はCのコードだが特殊変数を使用可能 81 特殊変数 exp: exp '+' exp {
$$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | NUM { $$ = $1; } 規則の構成要素の意味値 現在の規則の意味値 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 82 簡単なASTを組み立てる例 expr: expr '+' term { $$
= create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 83 3 がレキサーから渡される expr: term '+' term {
$$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー 3 3 シフト -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 84 アクションが実行されてノード作成 expr: term '+' term { $$
= create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー 3 3 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 85 ノードを $$ に代入 expr: term '+' term
{ $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー 3 3 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 86 還元 expr: term '+' term { $$
= create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 87 + がレキサーから渡される expr: term '+' term {
$$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3 + シフト + -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 88 5 がレキサーから渡される expr: term '+' term {
$$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3 + シフト + 5 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 89 5 は 生成規則 term にマッチする expr: term
'+' term { $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー 3 5 シフト 5 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 90 アクションが実行されてノード作成 expr: term '+' term { $$
= create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー 5 3 5 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 91 ノードを $$ に代入 expr: term '+' term
{ $$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー 5 3 5 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 92 還元 expr: term '+' term { $$
= create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 93 この状態になる expr: term '+' term { $$
= create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3 term + term 5 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 94 expr の生成規則にマッチする expr: term '+' term {
$$ = create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3 term + term 5 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 95 アクションが実行されてノード作成 expr: term '+' term { $$
= create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term 3 + term 5 + -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 96 還元 expr: term '+' term { $$
= create_op_node('+', $1, $3); }; term: NUMBER { $$ = create_number_node($1); }; レキサー パーサー term expr 3 5 + -
ぴーえいちぴーカンファレンスかんさい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 -
ぴーえいちぴーカンファレンスかんさい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 -
ぴーえいちぴーカンファレンスかんさい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 : 上から下へ優先順位が高くなる 同じ行にある演算子は同じ優先順位を持つ -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 101 ぶら下がり else 問題 if ($a) if ($b)
echo "b"; else echo "else"; どちらのifに対応するelse? -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 102 ぶら下がり else 問題 if ($a) if ($b)
echo "b"; else echo "else"; 正解はこっちのifです -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 103 ぶら下がり else 問題 / * Resolve danging
else conflict * / %precedence T_NOELSE %precedence T_ELSEIF %precedence T_ELSE 優先度高 T_ELSEの優先順位が高い -
ぴーえいちぴーカンファレンスかんさい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がないよりもある方が優先度高い -
ぴーえいちぴーカンファレンスかんさい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に結合 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 106 結合性(associativity) 同じ演算子が連続して使用されたときの評価順序を決定する 例: x op y op
zという式をどのようにグループ化するか 3つの結合性の定義方法がある %leftɺ%rightɺ%nonassoc -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 左から右へグループ化する 算術演算子の多くは左結合 107 左結合(%left) %left '+' '-' %left
'*' '/' '%' (a + b) + c a + b + c -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 右から左へグループ化する 累乗演算子は右結合 108 右結合(%right) %right T_POW a *
* (b * * c) a * * b * * c -
ぴーえいちぴーカンファレンスかんさい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 -
ぴーえいちぴーカンファレンスかんさい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 を使って定義する -
ぴーえいちぴーカンファレンスかんさい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 を使用して終端記号と型情報を紐づける 説明用の名前(エラーメッセージ) 型情報 終端記号名 -
ぴーえいちぴーカンファレンスかんさい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 を使用して非終端記号と型情報を紐づける 型情報 終端記号名 -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 115 非終端記号の型とは? $$の型 = 非終端記号の型 %token <int> NUM
%type <int> exp % % exp: exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | NUM { $$ = $1; } -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 116 非終端記号の型とは? $$の型 = 非終端記号の型 %token <int> NUM
%type <int> exp % % exp: exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | NUM { $$ = $1; } int int -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 117 非終端記号の型とは? $$の型 = 非終端記号の型 %token <int> NUM
%type <int> exp % % exp: exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | NUM { $$ = $1; } int -
ぴーえいちぴーカンファレンスかんさい2025 構文解析器入門 118 非終端記号の型とは? $$の型 = 非終端記号の型 %token <int> NUM
%type <int> exp % % exp: exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; } | NUM { $$ = $1; } 終端記号NUMの足し引きなのでint -
ぴーえいちぴーカンファレンスかんさい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