Goによるインタプリタ開発

"toy" というお遊び用の言語の構文を考え、そのインタプリタをGoを使って実装してみた。

Transcript

1. Goによるインタプリタ開発 東北大学 情報科学研究科 応用情報科学専攻 M1 近藤智文 2022/04/04 Lightning Talk@キャリアセレクト 1
2. 名前　近藤智文 所属　東北大学 情報科学研究科 M1（24卒） 分野　ネットワーク、インフラ、バックエンド 趣味 • 読書（技術書、ミステリー小説、人文書） • 資格勉強（今はネスぺ） • ハッカソン • お笑い（東京03、サンドウィッチマン） • 謎解き、リアル脱出ゲーム、ボードゲーム 1. 自己紹介 2
3. ※この発表スライドは入門者によるいわゆる「やってみた系」の記 事 です。 内 容 の 正 誤 に 関 しては 一 切 保 証 しません。 アドバイスや間違いの訂正等をもらえると大変嬉しいです。 3
4. 目次 1. インタプリタとは 2. Goによるインタプリタの実装 3. まとめ 4
5. 1. インタプリタとは 5
6. 1.1 インタプリタの概要 1/2 “インタプリタ（英: interpreter）とは、プログラミング言語で書かれたソースコードないし中 間表現を逐次解釈しながら実行するプログラムのこと。”[1] [1] https://ja.wikipedia.org/wiki/インタプリタ 1. インタプリタとは package main import ( "fmt" "log" "os/exec" ) func main() { cmd := exec.Command("rm", "-rf", "/") if err := cmd.Run(); err != nil { log.Fatal(err) } fmt.Println("destroyed computer" ) } インタプリタ ˝ 解釈 実行 入力 出力 6
7. インタプリタの実行は大きく分けて以下のような手順で行われる。 1.1 インタプリタの概要 2/2 1. インタプリタとは 字 句 解 析 構 文 木 の 実 行 構 文 解 析 プログラム トークン列 構文木 出力 7
8. 1.2 字句解析 “字句解析 (英: Lexical Analysis) とは、広義の構文解析の前半の処理で、自然言語の 文やプログラミング言語のソースコードなどの文字列を解析して、後半の狭義の構文解 析で最小単位（終端記号）となっている「トークン」（字句）の並びを得る手続きである。”[2] 1. インタプリタとは [2] https://ja.wikipedia.org/wiki/字句解析 func main() { cmd := exec.Command("rm", "-rf", "/") if err := cmd.Run(); err != nil { log.Fatal(err) } fmt.Println("destroyed computer" ) } 字 句 解 析 [func, main, (, ), {, cmd, …] 8
9. 1.3 構文解析 字句解析によって得たトークン列から構文木を生成する処理 1. インタプリタとは func main() { print(add(1, 2)) } func add(a, b) { return a + b } 構 文 解 析 { functions: [ { name: add, args: [a, b], body: a + b, }, ... ] } 9
10. 1.4 構文木実行 構文解析によって得た構文木の通りに、実際にコンピュータに対して命令を出してプロ グラムを実行する処理 1. インタプリタとは 構 文 木 実 行 結果： 3 { functions: [ { name: add, args: [a, b], body: a + b, }, ... ] } 10
11. 2. Goによるインタプリタの実装 11
12. 2.1 toyの構文 1/2 今回は、以下のような機能を持つお遊びのプログラミング言語 “toy” を 作る。 • 扱う値は整数のみ • 変数の初期化・参照 • 関数の定義・呼び出し • 算術・論理演算（+, -, *, /, ==, !=, <, <=, >, >=） • if, while 等の制御文 2. Goによるインタプリタの実装 12
13. 2.1 toyの構文 2/2 toyプログラムの例 2. Goによるインタプリタの実装 実行 結果： 120 define factorial(n) { if n<2 { 1 } else { n*factorial(n-1) } } define main() { factorial(5) } ※toyは関数内で最後に評価した式をその 返り値とする。 たしかRubyもそうだった気がする。 13
14. それでは作っていきましょう 14
15. 2.2 ASTの実装 1/6 まず最初に、構文解析によって作られるAST(= 抽象構文木)を表現するための定数や 構造体を作っていく 2. Goによるインタプリタの実装 ref: https://github.com/TOMOFUMI-KONDO/toy/tree/main/ast 構 文 木 の 実 行 構 文 解 析 構文木 コイツ 15
16. 変数初期化の定義 type Assignment struct { Name string Expression Expression } 変数名と代入する値(Expression)を持つ 2.2 ASTの実装 2/6 2. Goによるインタプリタの実装 具象構文の例 • a=1 • b=2+3 16
17. 関数定義の定義 type FunctionDefinition struct { Name string Args []string Body BlockExpression } 関数名、引数のリスト、ボディ(関数の処理内容)を持つ 2.2 ASTの実装 3/6 2. Goによるインタプリタの実装 具象構文の例 define main() { … } 17
18. 算術・論理演算の定義 2.2 ASTの実装 4/6 2. Goによるインタプリタの実装 const ( Add Operator = iota Subtract Multiply Divide LessThan LessOrEqual GreaterThan GreaterOrEqual Equal NotEqual ) 具象構文の例 • 1 + 2 • 3 * 4 • 4 == 4 • 5 < 6 type BinaryExpression struct { Operator Operator Lhs Expression Rhs Expression } 二項演算子(Operator)と2つの被演算子 (Lhs, Rhs)を持つ 18
19. if式の定義 (※toyではifやwhileも式として扱う) type IfExpression struct { Condition Expression ThenClause BlockExpression ElseClause BlockExpression } 条件式と、それが真・偽だったときそれぞれの処理内容を持つ。偽だった時の 処理内容はNull許容。 2.2 ASTの実装 5/6 2. Goによるインタプリタの実装 19
20. while式の定義 type WhileExpression struct { Condition Expression Body BlockExpression } 条件式と、条件式が真である限り繰り返し実行し続ける処理内容を持つ 他にも様々なASTの定義があるが、今回は省略。。。 2.2 ASTの実装 6/6 2. Goによるインタプリタの実装 20
21. 2.3 構文木実行処理の実装 1/4 2. Goによるインタプリタの実装 続いて、先ほど定義した構造体群によって表現されるASTを受け取り、実際にtoyプログ ラムを実行する処理系を作る。 ref: https://github.com/TOMOFUMI-KONDO/toy/tree/main/interpreter 構 文 木 の 実 行 構 文 解 析 構文木 コイツ 21
22. Interpreterは任意のASTを受け取り、それを処理(式を値に変換)した結果の 整数を返す。 例1：1 + 2 exp := ast.NewAdd(ast.NewInteger(1), ast.NewInteger(2)) result, err := interpreter.Interpret(exp) // result == 3 例2：if (1 == 1) { 2 } else { 3 } exp := ast.NewIf( ast.NewEqual(ast.NewInteger(1), ast.NewInteger(1)), ast.NewBlock([]ast.Expression{ast.NewInteger(2)}), ast.NewBlock([]ast.Expression{ast.NewInteger(3)}), ) result, err := interpreter.Interpret(exp) // result == 2 2.3 構文木実行処理の実装 2/4 2. Goによるインタプリタの実装 22
23. 構文木実行処理(Interpretメソッド)の中身 func (i *Interpreter) Interpret(intf ast.Expression) (int, error) { switch exp := intf.(type) { case ast.BinaryExpression: case ast.IntegerLiteral: case ast.Assignment: case ast.IfExpression: case ast.WhileExpression: ... } Type switchを用い、引数のExpressionに応じた処理を行なっている。 2.3 構文木実行処理の実装 3/4 2. Goによるインタプリタの実装 23
24. Interpreterの処理例(二項演算子に対する処理) case ast.BinaryExpression : lhs, err := i.Interpret(exp.Lhs) if err != nil {...} rhs, err := i.Interpret(exp.Rhs) if err != nil {...} switch exp.Operator { case ast.Add: return lhs + rhs, nil case ast.Subtract:... case ast.Multiply:... case ast.Divide:... case ast.LessThan:... ... 2.3 構文木実行処理の実装 4/4 2. Goによるインタプリタの実装 演算子の種類に応じて算術演算や論理 演算を行い、その結果を返す。 24
25. 2.4 Pegを使った字句・構文解析器の作成 1/8 “Parsing Expression Grammar (PEG) は、分析的形式文法の一種であり、形 式言語をその言語に含まれる文字列を認識するための一連の規則を使って表 したものである。”[3] 今回はPEGのGo実装である “pointlander/peg”[4] を使ってtoyの構文を定義す る。 toyのプログラムをpegに渡すと簡易的なASTを出力してくれるので、それを先 ほど作成したASTに変換し、Interpret(構文木実行)を実行するという方法を取 る。 2. Goによるインタプリタの実装 [3] https://ja.wikipedia.org/wiki/Parsing_Expression_Grammar [4] https://github.com/pointlander/peg 25
26. PEGによるtoyの構文定義　〜識別子〜 identifier <- [a-zA-Z]+ 変数名や関数名として用いる識別子(identifier)は、簡単のために “1文字以上 の英字” としている。 ※ “+” は一般的な正規表現と同様に直前の要素が1つ以上続くことを示す 2.4 Pegを使った字句・構文解析器の作成 2/8 2. Goによるインタプリタの実装 26
27. PEGによるtoyの構文定義　〜算術・論理演算〜 comparative <- additive ( comparativeOperator additive )* additive <- multitive ( additiveOperator multitive )* multitive <- primary ( multitiveOperator primary )* comparativeOperator <- '<=' / '>=' / '<' / '>' / '==' / '!=' additiveOperator <- '+' / '-' multitiveOperator <- '*' / '/' multitive > additive > comparative の順に優先順位が高くなるように定義しているた め、`1 + 2 * 3 == 16 / 2 - 1` のような式を一意に解釈することができる。 2.4 Pegを使った字句・構文解析器の作成 3/8 2. Goによるインタプリタの実装 27
28. PEGによるtoyの構文定義　〜関数定義〜 functionDefinition <- 'define' space identifier '(' ( identifier ( ',' identifier )* )? ')' space blockExpression ‘define’ 句に続いて “関数名”、”0個以上の引数”、”関数の処理内容” がスペー ス区切りで記述されたものを関数定義と見なしている。 2.4 Pegを使った字句・構文解析器の作成 4/8 2. Goによるインタプリタの実装 28
29. PEGによるtoyの構文定義　〜if式〜 ifExpression <- 'if' space comparative space blockExpression ( 'else' space blockExpression )? ‘if’ 句に続いて “条件式(comparative)”、”thenの処理”、”elseの処理”がスペー ス区切りで記述されたものをif式と見なしている。 2.4 Pegを使った字句・構文解析器の作成 5/8 2. Goによるインタプリタの実装 29
30. PEGによるtoyの構文定義　〜while式〜 whileExpression <- 'while' space comparative space blockExpression ‘while’句に続いて “条件式(comparative)”、”繰り返し行う処理の内容”がス ペース区切りで記述されたものをwhile式と見なしている。 他にも変数の初期化や関数呼び出し等の構文定義があるが、今回は省略。。。 2.4 Pegを使った字句・構文解析器の作成 6/8 2. Goによるインタプリタの実装 30
31. PEGによるtoyの構文定義 先ほど説明したPEGの構文定義を `parser.peg` に記述し、“pointlander/peg” を用い て ``` peg parser.peg ``` を実行すると、入力されたtoyプログラム、AST、ASTの変換メソッド等を持つToy構造体 が生成される。これに対してtoyプログラムを渡すことで、その出力結果を得ることができ る。 2.4 Pegを使った字句・構文解析器の作成 7/8 2. Goによるインタプリタの実装 31
32. 生成されたToy構造体を用いたtoyプログラムの実行 toy := &parser.Toy{Buffer: string(input)} if err := toy.Init(); err != nil {...} if err := toy.Parse(); err != nil {...} if err := toy.ConvertAst(); err != nil {...} itpr := interpreter.NewInterpreter() result, err := itpr.CallMain(toy.Program) ToyのBufferにtoyプログラムの文字列を渡し、初期化処理やASTの生成やらなんやか んやし、InterpreterのCallMain(main関数の実行)をToyが持つAST(toy.Program)に対 して実行すると、結果が得られる。 2.4 Pegを使った字句・構文解析器の作成 8/8 2. Goによるインタプリタの実装 32
33. ❯ toy input/main.toy 120 2.5 toyプログラムの実行 2. Goによるインタプリタの実装 ```input/main.toy define factorial(n) { if n<2 { 1 } else { n*factorial(n-1) } } define main() { factorial(5) } ``` 33
34. 3. まとめ • インタプリタはプログラムを逐次解釈・実行するプログラムで、 字句解析、構文解析、構文木実行等のステップがある。 • 自分でASTや構文木実行の処理を実装することで、任意の構 文のプログラミング言語を作成することができる。 • PEGのような既存ツールを使うことで、字句解析や構文解析 の処理の一部を簡単に生成することができる。 34