Writing An Interpreter In Go - Parsing 1 -


Parsers

この章では与えられた文字列をASTに変換するParserを作ります。Yaccなどのparser generatorは使わずに、全て自分たちでparse処理するmethodを書いていきます。

Parsingのやり方は大きく二種類あり、Top down parsingとBottom up parsingがあります。本書ではPlattt parserと呼ばれる再帰下降構文解析のひとつを実装します。

Parser's first steps: parsing let statements

変数、関数宣言を行うlet statementを解析できるように処理を実装します。

letは以下の形式に則ります。

let <identifier> = <expression>;

ここでstatementとexpressionは、expressionは値を評価し、statementは値を評価しないという違いがあります。プログラミング言語によってどのリテラルがstatementかexpressionかは異なって定義されています。

Node, Statement, Expressionというinterfaceを定義し、LetStatement struct、Identifier structでそれぞれinterfaceを満たすようなmethodを定義します。

Program structはStatementの配列を持ちます。ProgramはASTのRoot Nodeとなります。構造としては、Monkey言語は連続したStatementです。Programが複数のStatementを持ち、各LetStatementがIdentifierとExpressionを持ちます。

parser structは現在読み取ったTokenと次のToken情報を保持しています。次のTokenを保持しているのは、lexerのときと同じように、次の値によって挙動が変わるからです。例えば5;という数字が与えられたとき、次に改行コードが来るのか演算子が来るのかで挙動が変わります。

ParseProgram()がparserのメインとなるmethodです。EOFまでstatementごとにlet statementかどうかを検査してast.Statements[]に格納していきます。この一つのstatementごとに検査していく処理がAbstract Syntax treeそのものになります。

この段階では、statementはLetStatementしか検査しません。letはidentifierと=とexpressionで構成されており、parseLetStatement()はその3つが順番になっているかを検査します。この段階では、expressionを検査するのは複雑なので、let identifier =まで検査し、それ以降のexpressionは;までskipします。もちろんここは後で実装します。

curTokenIs()、peekTokenIs()、expectPeek()はこれからも使う処理なので、ここで名前をつけてリファクタリングしておきます。

デバッグ用の仕組みを作っておくと、実装時やtestを書くときに便利です。Parser structのerrorsはstatemetのparseに失敗したときその失敗したTokenTypeを格納します。小さなプログラムでもデバッグ用の機構を意識して書くと設計力が上がると思います。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

インタプリタ・コンパイラまとめ

インタプリタとコンパイラの理解のための記事をまとめたnoteです
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。