読者です 読者をやめる 読者になる 読者になる

Goでインタプリタ実装本を読んで2 parser

Parserまで読み終えたのでまとめておく。

Parser

この工程では、Lexerによってソースコードを字句解析した後、それらをよりアクセスしやすい形式に変換する。具体的にはトークンからASTを構築する。

例えば、以下のソースコード

let add = fn(x, y) { return x + y; };

Lexerによって以下の様に字句解析し

{Type:LET Literal:let}
{Type:IDENT Literal:add}
{Type:= Literal:=}
{Type:FUNCTION Literal:fn}
{Type:( Literal:(}
{Type:IDENT Literal:x}
{Type:, Literal:,}
{Type:IDENT Literal:y}
{Type:) Literal:)}
{Type:{ Literal:{}
{Type:RETURN Literal:return}
{Type:IDENT Literal:x}
{Type:+ Literal:+}
{Type:IDENT Literal:y}
{Type:; Literal:;}
{Type:} Literal:}}
{Type:; Literal:;}

Parserによって以下の様なASTを構築する。

{
   "Statements":[
      {
         "Token":{
            "Type":"LET",
            "Literal":"let"
         },
         "Name":{
            "Token":{
               "Type":"IDENT",
               "Literal":"add"
            },
            "Value":"add"
         },
         "Value":{
            "Token":{
               "Type":"FUNCTION",
               "Literal":"fn"
            },
            "Parameters":[
               {
                  "Token":{
                     "Type":"IDENT",
                     "Literal":"x"
                  },
                  "Value":"x"
               },
               {
                  "Token":{
                     "Type":"IDENT",
                     "Literal":"y"
                  },
                  "Value":"y"
               }
            ],
            "Body":{
               "Token":{
                  "Type":"{",
                  "Literal":"{"
               },
               "Statements":[
                  {
                     "Token":{
                        "Type":"RETURN",
                        "Literal":"return"
                     },
                     "ReturnValue":{
                        "Token":{
                           "Type":"+",
                           "Literal":"+"
                        },
                        "Left":{
                           "Token":{
                              "Type":"IDENT",
                              "Literal":"x"
                           },
                           "Value":"x"
                        },
                        "Operator":"+",
                        "Right":{
                           "Token":{
                              "Type":"IDENT",
                              "Literal":"y"
                           },
                           "Value":"y"
                        }
                     }
                  }
               ]
            }
         }
      }
   ]
}

parsingにはいくつか種類があるようだけど、本書ではtop-down parsingと呼ばれる手法の中の1つであるPratt parserが紹介されている。

Pratt parserは、1973年にスタンフォード大学のVaughan Pratt氏による Top down operator precedence という論文によって説明されている手法で、JSLintにも使われている手法とのこと。JSLintの作者である Douglas Crockford氏がJavaScriptでそれを詳しく説明しているブログエントリを見つけた。

本書では、ここで書かれているようなことがGoで書かれている。 今回は、これを実際に実装してみたパーサーをまとめたい。

statement

まずASTを構築するためには、ASTをどのようなデータ構造にするかということを決めておかなければいけない。 本書では、ソースコードをいくつかの塊として扱い、その塊をstatementと呼んでいる。

例えば、

let a = 1;

は、 LetStatementと呼ばれ、以下のようなpseudocodeで表現出来る。

type LetStatement {
    Identifier
    ExpressionStatement
}

変数 Identifier の情報と、式 ExpressionStatement の情報で成り立っている。

また、

return 1;

は、 ReturnStatementと呼ばれ、こちらは以下で表現出来る。

type ReturnStatement {
    ExpressionStatement
}

単に式 ExpressionStatement の情報のみ。

そして、それ以外の全てが ExpressionStatement になる。

1;
1 + 2 / 3;
a * b;
fn(x, y) { return x + y; };

最後の fn(x, y) { return x + y; }; は、ExpressionStatementの中にReturnStatementが存在することを示している。

parserは、ソースコード

  • LetStatement
  • ReturnStatement
  • ExpressionStatement

に変換し、それらの親子関係をツリー状のデータ構造で表現、つまりASTを構築することが目的となる。

ソースコードは、上記3つのstatementがそれぞれ再帰的に繋がったような構造になっていて、これを operator(+,-,/,*,fnなど)の優先度を加味してパースするのが Prett parser の特徴である。

expression

式の優先度を加味してパースする、とは、

1 * -2 + 3;

(1 * (-2)) + 3;

と優先度を付けてASTを構築すること。これを1つのExpressionStatementと呼ぶ。

これをデータ構造で表現すると以下のようになる。

{
   "Statements":[
      {
         "Token":{
            "Type":"INT",
            "Literal":"1"
         },
         "Expression":{
            "Token":{
               "Type":"+",
               "Literal":"+"
            },
            "Left":{
               "Token":{
                  "Type":"*",
                  "Literal":"*"
               },
               "Left":{
                  "Token":{
                     "Type":"INT",
                     "Literal":"1"
                  },
                  "Value":1
               },
               "Operator":"*",
               "Right":{
                  "Token":{
                     "Type":"-",
                     "Literal":"-"
                  },
                  "Operator":"-",
                  "Right":{
                     "Token":{
                        "Type":"INT",
                        "Literal":"2"
                     },
                     "Value":2
                  }
               }
            },
            "Operator":"+",
            "Right":{
               "Token":{
                  "Type":"INT",
                  "Literal":"3"
               },
               "Value":3
            }
         }
      }
   ]
}

式内のトークンが nuds(null denotations)なのか、leds(left denotations)なのかを判定し、式を左辺と右辺に分割していく。

  • nuds
    • 左辺を持たない式(e.g, 1,-,!,fnなど)
  • leds
    • 左辺を持つ式(e.g, +,*,/など)

それらを演算子の優先順位を加味してデータ構造を作り上げていく。 上記例は以下のように定義づけられる。

(        (        1 *  (-2) ) + 3    )
         |        |     |   |   |
         |        |     |   |   |
         |        |     |   |   |
leds(+)(leds(*)( nuds, nuds ), nuds  )

ちなみに演算子の優先順位は以下のように定義している。

const (
    _ int = iota
    LOWEST
    EQUALS      // ==
    LESSGREATER // > or <
    SUM         // +
    PRODUCT     // *
    PREFIX      // -X or !X
    CALL        // myFunction(X)
)

var (
    precedences = map[token.TokenType]int{
        token.EQ:       EQUALS,
        token.NOT_EQ:   EQUALS,
        token.LT:       LESSGREATER,
        token.GT:       LESSGREATER,
        token.PLUS:     SUM,
        token.MINUS:    SUM,
        token.SLASH:    PRODUCT,
        token.ASTERISK: PRODUCT,
        token.LPAREN:   CALL,
    }
)

precedences の下に行くほど優先度が高い。

これを見て僕はparser実装めっちゃめんどいのでは、と思ったけど、Pratt parserではこれをシンプルな再帰関数で解決していてちょっと感動した。そのままのコードを紹介するためには依存する各データ構造まで出さないといけないので割愛。。

ざっくりと言うと、以下のような処理を再帰的に行っている。

  • 1 をパース
    • nudsなのでそのまま左辺へ保存(1, )
  • * をパース(* 1, )
    • ledsなので次の - パース
    • nudsだとわかるのでそのまま 2 をパースして右辺へ -2 を保存(* 1, -2)
    • + をパース
    • * より優先度が低いため、ツリーを戻り ( 1, -2)を左辺へ保存(+ ( 1, -2), )
  • 3 をパース
    • 右辺へ保存(+ (* 1, -2), 3)

ちょっとわかりづらいね・・

感想

これまで、parserと聞くと何やらすごい難解なイメージを持っていたけれど、実際に実装してみるとそれは結構泥臭くて、味わい深いものがあることがわかった。

今回やってみて、parser実装はそのアルゴリズムは面白いけれど、実装は結構退屈な感じだったので、yaccなどのパーサージェネレーターにも興味が湧いてきた。

さて、次はEvaluationを読み進める。ここ結構面倒くさそうな気がしている。