WIP Writing An Interpreter In Go
REPLを作るためにはソースコードを分解してTokenizeしてそしてASTを作りたい。
Source Code -> Tokens (Lexical Analysis - lexier or tokenizer or scanner) -> Abstract Syntax Tree(AST)
実装イメージで勝手に字句解析で先に全てトークンに分解して配列とかに保持してから、それを使ってパースするもんだと思ったら違った。字句解析->パースを逐一実行していた。
流れ
バイト文字単位で走査
トークン
1文字
2文字
識別子/キーワード
トークンを走査
AST
statement(文)
expression(式)
Lexical Analysis(字句解析)
ソースコードをトークンに分解するだけ。
Example of Lexical Analysis:
code:example
"let x = 5 + 5;"
↓
[
LET,
IDENTIFIER("x"),
EQUAL_SIGN,
INTEGER(5),
PLUS_SIGN,
INTEGER(5),
SEMICOLON
]
手順
TOKENの定義
INTとかPLUSとかを構造体で定義する
Lexierの作成
ソースコードをinputにとり、TOKENをoutputする。
まずは1文字ずつ読み取って1文字のオペレータやオペランドのみを判別できるようにしてみる。
次はIndetifier/keywordに使える文字とそうでないILLEGALな文字を判別する。Indetifier/keywordの可能性のある文字に出会ったらwhile/forでidentifier/keywordでない文字が出てくるまで読み進める。
code:example.go
for isLetter(ch byte) bool {
// ASCIIのアルファベットと_のみ変数に使える仕様の場合
return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_'
}
その他の1文字のオペレータなどのtokenとreturnなどのキーワードも追加。
次に2文字のオペレータ(==,!=)に対応する。1文字先を覗くメソッドを追加して=と!でそれぞれ分岐処理する感じ。
Parsing
ソースコードをinputにしてデータ構造に変換する。JSON Parserが良い例。
code:json
input = '{"name": "Hoge", age: 12}'
output = JSON.parse(input);
output
{"name": "Hoge", age: 12}
output.name
"Hoge"
output.age
12
プログラミング言語の場合は内部表現のデータ構造としてASTを作るのがParserの役割。
CFG/BNF/EBNFなどの既存のパーサージェネレータはあるし質はもちろんそれらの方が良いし早いが、まず自分で書いたことがないのであれば自分でやってみる方が良い。
expression(式): valueを返す
statement(文): valueを返さない
Statement
基本は今のトークンを元に次のトークンをみて正しいstatementになっているか確認し、仕様に合致すればstatementsにappend、というのを全トークンに対して繰り返していく。
Expression
expressionのパースは下記のような一筋縄ではいかない式だらけなので結構大変。statementのパースで行ったやり方では無理がある。
code:hard.example
5 + 10
5 + 6 * 3
3 * (5 + 6)
-5 - 10
5 * (add(2, 3) + 10)
Prattパーサーはパーサージェネレータは使わず、演算子の優先度を重視して構文木を構築する。
Prattパーサーは常に現在の読み込み位置とその次の位置を確認しながら解析する。これをLL(1)文法と言う。例えば「3+5*4」であれば、まず「3」と「+」を読んで次に「+」と「5」を読んでというのを繰り返しながら構文木を構築する。 Prattパーサーは現在の優先順位と、次に追加するものの優先順位を比較することで、新しく読み込んだものの、構文木のなかでの位置を決定する。
詳しい解説は本書の2.7のHow works Pratt parser?を読め。
自前で四則演算のみを扱うPratt Parserを書いてみた
prefix operator: --5
postfix operator: foo++
operator: ++
operand: foo
infix operators: 5 + 8の+
operator precedence(order of operations): 5 + 5 * 10