golangでインタプリンタを作る２

第二章、構文解析器

構文解析器とは

• 入力を受け取りデータ構造を形成する。
• 入力が正しい構文かチェックする。
• 字句解析器の後段に置かれる。

データ構造

AST(Abstract syntax tree) 抽象構文木とは

https://ist.ksc.kwansei.ac.jp/~ishiura/prevxcpl/ast.pdf

今回は独自の AST を定義し、AST のインスタンスを構築していくが、どうやらパーサージェネレータというものが存在するらしい。
パーサーは人間の作ったソースコードからデータ構造を形成し、機械語に翻訳する。
パーサージェネレータはそのパーサーを自動生成することができる技法。

https://garop.com/228/

プログラミング言語を少しでも深く理解することを目標としているので、このようなものは使用せず、
自作で構文解析器を作っていく。それが二章のテーマとなっている。

解析器の全体像

構造体の定義: ast

今回作成した解析器は、解析結果を golang の構造体として表現する。
そして、全ての構造体が Node インターフェイスを満たし、
それぞれの構造体が文(Statement インターフェイス)または、式(Expression インターフェイス)どちらかのインターフェイスを満たす。
つまり、それぞれの構造体を文として扱うか、式として扱うかをインターフェイスによって分類する。

構造体の生成: parser

parser では、一章で字句解析した結果を受け取り、ast で定義した構造体を生成していく。
最終的に解析結果を Program 構造体で出力する。

上記の二つのパッケージで解析をする。

解析方法の全ては紹介しきれないので、いくつか絞って解説する。

文

let 文の解析

let x = 5;

上記の文を例に解析していく。

上の画像のように Let 文は identifier ノード、＝、expression ノードからなる文である。

それぞれのノードの中にトークンがありその中に実際の値が入っている。上記の画像を golang で表現する。

構造体の定義

ast.go

type LetStatement struct {
	Token token.Token // the token.LET token
	Name  *Identifier
	Value Expression
}

func (ls *LetStatement) statementNode()       {}
func (ls *LetStatement) TokenLiteral() string { return ls.Token.Literal }
func (ls *LetStatement) String() string {
    // デバッグ用
}

まず初めに、それぞれのフィールドを定義し、解析器の全体像で紹介した Node インターフェイスとStatement インターフェイスを
満たすのに、それぞれのメソッドを定義する。
次に、実際に生成するパッケージ、parser で LetStatement を生成する。

パサー

1. 初めに ParseProgram で Program 構造体を初期化
2. parseStatement の switch 文で parseLetStatement を呼び出す。
3. parseExpression でどんな式かを判定し、今回は数字の５だけなので、parseIntegerLiteral を呼び出す。
4. parseIntegerLiteral で実際の値(５)を格納する。

上記の流れで let 文を解析する。

式

if 式の解析

if 式は

• 条件(condition)
• 結果(consequence)
• 代替(alternative)

上記の三つノードからなる。
今回作成した IfExpression は else をノードとして定義しない。
なので、else の記述を省略を許している。
省略できない言語は、AST の中に else をスキップさせないような構造になっていると思われる。

構造体の定義

ast.go

type IfExpression struct {
	Token       token.Token // The 'if' token
	Condition   Expression
	Consequence *BlockStatement
	Alternative *BlockStatement
}

func (ie *IfExpression) expressionNode()      {}
func (ie *IfExpression) TokenLiteral() string { return ie.Token.Literal }
func (ie *IfExpression) String() string {
	// デバッグ用
}

if 式は、文ではなく式に分類されるので、Node インターフェイスとExpression ノードを満たす。

パサー

図で表してみたのですが、とても大きくなってしまいました。
ここからかなりややこしく、うまく解説できていないかもしれません。

優先度

　　LOWEST: 1
　　!=: 2
　　==: 2
　　>: 3
　　<: 3
　　+: 4
　　-: 4
　　*: 5
　　/: 5
　　(: 6

1. 最初に Program、ExpressionStatement、IfExpression を初期化する。
2. トークンを二つ進め、IfExpression の Condition 部分を解析していく。
   1. Condition は中値演算子で真ん中に記号が入り、両サイドに式が入る。
      中値演算子には、InfixExpression という構造体を用いる。
   2. "("が curToken に来ていることを確認し、トークンを二つ進める。
   3. 二つ進めたら、parseExpression を呼び出し、curToken の６を parseIntegerLiteral 関数で解析し、解析結果をparseExpressionに返す。
   4. 次に peekPrecedence という関数を呼び出す。この関数は中値演算子において演算の優先順位を決める関数である。
      "("が優先順位が一番高く、LOWEST が一番低い。
      IfExpression から parseExpression を呼び出す際は、LOWEST を引数として渡す。
      parseExpression は curToken を解析した後、peekToken と引数でもらった優先度を比較する。
      peekToken は">"になるので引数で受け取った LOWEST より peekToken の方が優先順位が高い。
      引数の方が優先度が低いかつ、peekToken がセミコロンではない場合に for 文に入っていく。
   5. for 文で parseInfixExpression を呼び出しす。引数には初めに解析した IntegerLiteral を入れる。
      parseInfixExpression では、初めに InfixExpression 構造体に記号と引数で受け取った IntegerLiteral をセットする。
      次に、curToken の優先度を調べ、一つトークンを進める。curToken が記号の左側に来るタイミングで、parseExpression を呼び出す。引数には curToken の優先度を渡す
      再び呼び出された parseExpression は前回同様、初めに curToken を解析する。その後 peekPrecedence を呼び出すのだが、peekToken は")"で優先順位を決める中に")"は入っていない。
      入っていない場合は一番低い LOWEST を返す。引数に渡された優先度と peekPrecedence の返値を比較すると引数の方が優先度が高いので、今回は for 文に入らず解析結果を返す。
   6. 解析結果を受け取った parseInfixExpression は InfixExpression のフィールド Right に解析結果をセットし返り値に渡す。
   7. 返り値を受け取った parseIfExpression は、IfExpression のフィールド Condition に返り値をセットする。
3. Consequence フィールドは if 式の true の処理にあたる。{}内で記述される文である。これを BlockStatement 構造体で作成する。
   1. 初めに curToken が"{"が来たタイミングで parseBlockStatement を呼び出し、トークンを一つすすめて解析を開始する。
   2. for 文で"}"が来るか、文の終わりが来るまで繰り返し parseStatement を呼び出し{}内の文を解析していく。
      そして解析結果をBlockStatementの Statement フィールド（配列）に追加していく。"}"が来たタイミングで for 文が終了し IfExpression に解析結果 block を返す。
   3. IfExpression の Consequence に解析結果 block をセットする。
4. Alternative は Consequence の解析が終わった後、curToken が else の場合トークンを一つ進め、"{"が来たタイミングで再び parseBlockStatement を呼び出す。
   1. 3 と同様の処理を行い、解析結果 block2 を返す。その後、IfExpression の Alternative に block2 をセットする。
5. 最後に ExpressionStatement の Expression フィールドに IfExpression をセット、ExpressionStatement を Program の Statement にセット。

終わりに

構文解析器の解説はあまりうまく説明できた手応えがないですが、自分の理解はこの記事を書く前より、一段深まった気がしています。
本を読んでる最中は複雑で処理が追いついていなかったが、シーケンス図やクラス図に起こすことで非常に複雑に見えた処理が、意外とシンプルだったという発見がありました。
また、一つ一つの関数の処理も非常にシンプルで、組み合わせによって様々な処理を実現できることに少し感動を覚えました。
最後に第三章も記事を書きたいと思っています。