PHPでつくるインタプリタ入門 / introduction interpreter by PHP

PHPerKaigi2020 Day1 PHPでつくるインタプリタ入門 の資料です。

https://fortee.jp/phperkaigi-2020/proposal/0f7ef74b-17ba-41b6-9ca6-abff2d30f9a7

参考文献などはブログでリンクをまとめています。
https://budougumi0617.github.io/2020/02/10/phperkaigi2020/

Transcript

1. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 2020/02/10 PHPerKaigi 2020 @budougumi0617 PHPでつくるインタプリタ入門
2. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 自己紹介 • 清水 陽一郎 @budougumi0617 • BASE BANK, inc. Dev Division ◦ PHP歴3ヶ月。PHP/Go/Python/AWS etc... • コミュニティ: golang.tokyo / Go Conference運営 • 趣味: ボルダリング/毎週ブログを書くこと ◦ https://budougumi0617.github.io/ Go Conferenece
3. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 自己紹介 • 技術書典8に出典します ◦ 技術書典8 Day 1 あ33 golang.tokyo • コミュニティ有志による合同誌 • Goの本ですが、立ち読みだけでもお越しください
4. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • インタプリタとは？ • インタプリタを作ると何が得られるのか？ • 字句解析、構文解析、評価とはなにか。それぞれの役割 • PHPUnitと型を使ったPHP7.4での実装アプローチ • （時間が余ったら）デモ ◦ https://github.com/budougumi0617/php-go • まとめ アジェンダ
5. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • インタプリタがどんな理論を使っているのか、実装方法がわかる ◦ インタプリタに関わるキーワードを知っている • tree-walking型インタプリタの処理の流れがわかる • 他の言語のインタプリタを作るときの参考になる ◦ TDDを使った漸進的なアプローチ • 「こういう流れでやればいいのね、意外と簡単」って気分になる 今日のゴール
6. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 実装方針 １ ２ ３ PHPUnitを使ったTDD 型を使った契約設計 漸進的アプローチ
7. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • 仕様が決まっている、かつコマンドラインツールなので練習として取り組みやすい • 再帰処理、オートマトンや構文木と仲良くなれる • いろいろな言語のパーサーも読めるようになる ◦ [Re:VIEW] textlintのlintエラーからttインライン命令で装飾された文字列を除 外する ◦ https://budougumi0617.github.io/2020/01/19/textlint-ignore-tt-inlines • 構文解析ができるようになると自前の静的解析ができるようになる ◦ https://github.com/budougumi0617/layer インタプリタを作る理由
8. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • Go言語で作るインタプリタ（オライリー） ◦ 原著 https://interpreterbook.com/ （未訳だが続編のコンパイラ本もある） ◦ Goでオリジナル言語Monkeyのインタプリタを作る • コンパイラ | 情報系教科書シリーズ第9巻 （オーム社） ◦ 学生のころの教科書だったため。今はもっといい本があるのかもしれない？ • 低レイヤを知りたい人のためのCコンパイラ作成入門（by Rui Ueyama） ◦ https://www.sigbus.info/compilerbook ◦ 「9ccの本」と言ったほうが通じるかもしれない 参考文献
9. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. インタプリタとは
10. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • インタプリタ ◦ あるプログラミング言語を解釈する装置。 ◦ REPL, LL言語 • コンパイラ ◦ 生成物が存在する（*.o, *.exe, *.jar etc...) • パーサー ◦ 構文解析まで（実行可否・実行結果はわからない） そもそもインタプリタってなんだ？
11. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. インタプリタの処理の大きく3工程に分かれる １ ２ ３ 字句解析（Lexical analysis） 構文解析（Syntax analysis） 評価（Evaluate）
12. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 1. 字句解析（Lexical analysis） ◦ 文字列をトークンに変換していく 2. 構文解析（Syntax analysis） ◦ トークン→抽象構文木（AST, Abstract Syntax Tree） ◦ パーサーはこのへんまでしかしない 3. 評価 ◦ AST→実際に結果を評価 ◦ コンパイラの場合は意味解析（Semantic analysis）してコード生成に進む インタプリタの処理の流れ
13. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 字句解析
14. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 字句解析（Lexical analysis） ソースプログラムのテキストを、字句要素（Lexeme）と呼ばれる文字列に分ける。 個々の字句要素はトークン（Token）と呼ばれるデータに変換させる。 各トークンは、字句要素の種類を区別するための情報と、付加的な情報を蓄えている。
15. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 字句要素の例（Go） break chan defer case const interface = etc... + != 1
16. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • 一番馴染みのある（？）文字列マッチング ◦ 正規表現 • ここで使うのはオートマトンの原理 どうやって文字列からトークンを生成していくのか？
17. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • 有限個の状態（state）を持ち、文字を1文字ずつ読み込むことに よって自分自身の状態を変化させる、仮想計算機の一種 • 各状態を円で表し、受理状態を二重の円で表す • 状態遷移と対応する矢印に入力文字αを添えることで、状態遷移を <q, α, q'>を表す 有限オートマトン（Finite Automaton） q q’ α
18. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • 任意の状態qと任意の文字αに対して、状態遷移が高々1つしか存在 しないとき、有限オートマトンを決定性有限オートマトンと呼ぶ。 ◦ 解釈が複数あると字句解析は成り立たない 決定性有限オートマトン （DFA, Deterministic Finite Automaton） q q’ α
19. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • 1:キーワード if 2:識別子 <英字><英数字>* 3:空白 <スペース>* DFAの簡単な例 i 1 英数字 f f以外の英数字 i以外の英数字 英数字 スペース スペース 2 3 2
20. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 字句解析の実装
21. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. ... x + y = 5 ... 2 （基本的には）素直に一文字ずつ読んでいく 現在位置 xを読み込んだ後の位置
22. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 2 トークンのデータ構造
23. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. トークンの種類を定義
24. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 2 テストランナーを作って少しずつ
25. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 2 少しずつテストケースを追加していく
26. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 文字を読んで現在位置を進めていくだけ • キーワード文字があったら即トークンを生成 • 文字列を見つけたらスペースまで読み込む ◦ その後、予約語か判断してトークン生成 • 数字も同様
27. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. \n x = ... 2 ちょっと面倒なパターン 「代入」トークン？
28. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. \n x = = 2 ちょっと面倒なパターン 比較トークン
29. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 「現在位置」を動かず先読みしてしまう 2
30. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • トークンを取得しただけではまだ何もわからない • プログラミング言語として、意味ある（解釈可能な）トークン文 字列になっているかはわからない • プログラミング言語として文法を解釈していくには… ◦ 構文解析を行なう！ トークンを取得したが…
31. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 構文解析
32. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 構文解析（Syntax analysis） 構文解析では、トークン列を解析することによって、それが、言語の文法に従ったものであ るかどうかをチェックし、木構造の構文木（Syntax tree）を生成する。
33. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 式（Expression）と文（Statement） • 式（Expression） ◦ 値を返す処理 • 文（Statement） ◦ 値を返さない処理 • 言語によって一概に言えない処理もある（式であるifもある） • Goの場合は宣言（Declation）という見方もしている
34. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • 例: 1 + 2 + 3 のAST 抽象構文木（AST, Abstract Syntax Tree） 1 BinayExpression BinayExpression BasicLiteral BasicLiteral BasicLiteral 2 3
35. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • 単純に左辺から組み立てていくだけではできない ◦ 四則演算、言語固有の評価の優先順位 • 再帰的に評価を行なっていく どうやってトークンからASTを導出していくのか？
36. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 再帰的下降構文解析（Recursive decent parsing） • 直感的な構文解析方法。 ◦ ボトムアップ構文解析もある。 • 左再帰とバックトラックが入ると複雑になってくる ◦ 左再帰…生成規則の左辺に自らが存在する場合の無限再帰 ◦ バックトラック…複数候補があって解析失敗にしたとき、元の位 置に戻って評価をやり直す
37. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. Pratt構文解析 • 再帰的下降構文解析のひとつ ◦ 文法のトークンごとに解析関数を実装する ◦ トークンと解析関数が対になるので実装もわかりやすい ◦ 演算子に優先順位を付けて解析できる
38. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • 例: 1 + 2 ✕ 3 のAST 優先順位が必要な理由 2 BinayExpression BinayExpression BasicLiteral BasicLiteral 3 BasicLiteral 1
39. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 構文解析の実装
40. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. その前に プログラミング言語って どういう風に定義されている？ 何が正しくて何が間違った書き方？
41. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. BNF記法 • 生成規則：文法を再帰的に定義する • BNF：生成規則をコンパクトで平易に記述するための一つの記法 ◦ 現在はBNF記法を拡張したEBNFが多く使われている ◦ Goも言語仕様としてEBNFの記載がある ▪ https://golang.org/ref/spec#Notation
42. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. EBNFを読めばパースすべき正解が分かってくる • https://golang.org/ref/spec
43. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 構文解析の実装 • Goの構文解析は結構難しい ◦ 終端を判断するのが難しい（PHPの「;」のような目印がない） ◦ 唐突に一つの式で複数の変数を宣言できる ▪ x, y, z := 10, 20, 30 • 左辺が配列になるし”var”みたいな予告がない… ◦ 関数の引数も書き方にバリエーションがある ▪ func Myfunc(x, y int, z string)
44. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. ひたすらgo/parserを移植する • Goで実装されたGoのパーサー ◦ https://github.com/golang/go/tree/master/src/go/parser • ひたすらこれをTDDで移植していく ◦ テストが通る === 移殖成功 • 型構造もほぼ同じように移殖 ◦ Goの場合はExpression, Statementの他にDeclationもある • 例外と型アサーションで失敗に気づきやすくしておく
45. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. ASTのクラス構造 NodeInterface StatementInterface DecrationInterface UnaryExpr ExpressionInterface BinaryExpr AssignStatement ReturnStatement GenDecl FuncDecl
46. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. パーサーもトークンがなくなるまでループするだけ 4
47. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. トークンに対応する 関数を実装する 4
48. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. テストを書く 4
49. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. ASTで使うクラス定義を書く 4
50. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. テストが通るまで実装する 5
51. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. キャストを使って誤操作を防ぐ& IDEを使いこなす 5
52. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 未実装部分には例外を仕込んで誤再帰を防ぐ 5
53. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • 入力文字列がプログラミング言語として何を表現しようとしてい るのわかった！ ◦ いよいよ実行結果を評価する！ 構文解析が終わると
54. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 評価
55. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 構文を評価するために必要なこと あとは実行していくだけ！ …では終わらない
56. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • スコープ（Scope）を考えないといけない 式文を評価するために必要なこと これは何？ この変数は定義済み？ 関数の中にはない。 これは何？ この関数は定義済み？ コードの中にはない。
57. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • 定義が関数内になかったら？ • ファイルの中になかったら？ • スコープの作り方は言語依存 メモリ空間を表現したScopeクラスを用いる
58. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 評価の実装
59. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. Parserでパースした型に合わせて評価を実施 5
60. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 評価関数も再帰を繰り返す 6
61. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. 評価の実装 • Scopeから”add”関数の定義を探す • 引数の”x”, “10”をScope内で評価する ◦ “x”という名前の変数の定義を探す ◦ “10”はIntegerオブジェクトとして評価 • 評価した引数を使って”add”関数を実行 add(x, 10) というような関数呼び出しを評価する場合
62. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. ここまでするとやっと…
63. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. まとめ
64. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • 思っていたより固く書けてよかった ◦ （私のプログラミング経歴がC/C++/Java/C#/Goらへんが通っているので） • 標準ライブラリだけで実装できている ◦ （テストではPHPUnitを用いている） • PhpStormでゴリゴリ書いていると楽しい • array使い始めると型情報が欠落してしまうのどうにかならないかな… PHPでインタプリタを実装してみて
65. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • インタプリタがどんな理論を使っているのか、実装方法がわかる • tree-walking型インタプリタの処理の流れがわかる • 他の言語のインタプリタを作るときの参考になる ◦ TDDを使った漸進的なアプローチ • 「こういう流れでやればいいのね、意外と簡単」って気分になる 今日のゴール
66. © 2012-2019 BASE, Inc. © 2012-2020 BASE, Inc. • 足し算の結果を出力するところまではできました（やや無念） ◦ https://github.com/budougumi0617/php-go • インタプリタの基本的な処理とその役割を説明 ◦ 字句解析、構文解析、評価 • PHPUnitと型を使ったPHP7.4での実装アプローチ ◦ TDDでデグレを防ぎながら実装していく ◦ 型を使っていると契約設計的に異常検知ができる • 実際に作ってみてコンパイラのキモチが少し分かるようになった まとめ