Nimで自作インタプリタ② Pratt Parserを実装した
2019/2/7
Lexerを書いた記事の続きです。
Lexerの次にParserを作り始めたのですが、一段落したので軽く記事にまとめます。
スライド
勉強会でスライドを作って発表しました。
資料はこちらです。
内容はこのブログ記事の方が詳細です。
概要
前回に引き続き、「『Go言語でつくるインタプリタ』」本をNimで書き直しながら進めています。前回のLexerの記事から随分と時間がかかったのは、Nimのことをあまり知らない状態でGoの書き直しをしたのもあり、主にインターフェースの周りですごく詰まったからです。
この辺の苦労話はこの記事の最後の方に書きます。
記事の前半では、Parserとはそもそもなんなのかや、Pratt Parserの仕組みなどについて簡単に紹介します。
リポジトリは以下です。
参考
ParserはToken列からASTを作るやつ
Parserは日本語では「構文解析器」といいます。
ParserはLexerが作ったToken列を受け取ってASTを作ります。
簡単な手順としては以下のような感じです。
まず、入力された文字列を、Lexerが、文章の最小構成要素であるTokenに分解してくれます。
次に、Parserはそこで受け取ったTokenを読んで、その種類や内容を見ながら抽象構文木(AST)を作っていきます。
「構文解析」自体は、プログラミングだけの話ではなく、例えば自然言語処理などの界隈でも出てくるワードです。
ASTとは
AST、Abstract Syntax Tree。
日本語では「抽象構文木」。
ASTというのは、その名の通り抽象的な構文木のことです。
「抽象的」なので、空白や行末セミコロン、括弧などの、意味は同じだけど表現が異なるだけのものが省かれています。
少し横道に逸れますが、ASTは言語処理系以外のところでも使われています。
例えば、メタプログラミング、コード整形、DIを使ったデバッグやテストや、ドキュメントの自動生成などです。
言語ごとにASTを解析したり、visualizeするツールをいくつか見つけたので載せておきます。
いくつかの言語のASTを出力してくれる
Pythonの
Goの
JSの
js周辺(というかBabel周辺)のツールについては以下の本に詳しく書かれていました。
babylonなどを使ってjsのコードをASTにし、ちょっといじって、再びjsコードに変換するツールを作っていく本です。(まだ読んでる途中)
参考
Goなら以下の記事などが参考になります。
参考
具体例
構文解析の話に戻ります。
先ほどの説明だけではわかりにくいので実際の出力を見てみます。
ここでは、
let hoge = 1 + 2 * 3 / 4 + 5 - 6; という文字列(コードじゃなくてただの文字列！)を解析してみます。式と文と式文
今回の例の
let hoge = 1 + 2 * 3 / 4 + 5 - 6; のように変数に値を束縛する式を、ここでは「let文」と呼びますが、let文は以下のような構造になっています。 let <identifier> = <expression> identifierは変数名などを表し、expressionは式を表します。
「式(expression)」というのは、値を出力するもののことで、例えば、
42 だったり、 "foo" だったりが該当します。式の他に、「文(statement)」というものもあり、これは上記の
let hoge = piyopiyo だったり、 return fuga だったり、それ自体が値を生成しないものを指します。また、「式文(expression statement)」というのもあります。
これは一つの式だけからなる文のことです。
例えば、
x + 2 などです。Lexerの出力
まずは先ほどのlet文の文字列である
let hoge = 1 + 2 * 3 / 4 + 5 - 6; からTokenを作ってみます。ここでは、前回の記事のときに作ったLexerを使います。
nimvar
input = """let hoge = 1 + 2 * 3 / 4 + 5 - 6;"""
l = newLexer(input)
for i in 1..15:
var tok = l.nextToken()
echo repr tok出力は(ちょっと整形してますが)こんな感じです。
さきほどの文字列がTokenに分けられているのがわかります。
Tokens[Type = "LET", Literal = "let"]
[Type = "IDENT", Literal = "hoge"]
[Type = "=", Literal = "="]
[Type = "INT", Literal = "1"]
[Type = "+", Literal = "+"]
[Type = "INT", Literal = "2"]
[Type = "*", Literal = "*"]
[Type = "INT", Literal = "3"]
[Type = "/", Literal = "/"]
[Type = "INT", Literal = "4"]
[Type = "+", Literal = "+"]
[Type = "INT", Literal = "5"]
[Type = "-", Literal = "-"]
[Type = "INT", Literal = "6"]
[Type = ";", Literal = ";"]作られるASTオブジェクト
次に、今回作ったParserで構文解析してみると、(ちょっと整形していますが)以下のような構造体が作られます。
astToken: {
Type: 'LET',
Literal: 'let'
},
Let: {
Token: {
Type: 'IDENT',
Literal: 'hoge'
},
IdentValue: 'hoge'
},
LetValue: {
Left: {
Left: {
Token: {
Type: 'INT',
Literal: '1'
},
IntValue: 1
},
Operator: '+',
Right: {
Left: {
Left: {
Token: {
Type: 'INT',
Literal: '2'
},
IntValue: 2
},
Operator: '*',
Right: {
Token: {
Type: 'INT',
Literal: '3'
},
IntValue: 3
}
},
Operator: '/',
Right: {
Token: {
Type: 'INT',
Literal: '4'
},
IntValue: 4
}
}
},
Operator: '+',
InRight: {
Left: {
Token: {
Type: 'INT',
Literal: '5'
},
IntValue: 5
},
Operator: '*',
Right: {
Token: {
Type: 'INT',
Literal: '6'
},
IntValue: 6
}
}
}少し大きいので、わかりにくいですが、雑に図にしてみると以下のような構造になっています。
実際に動いている様子
src/repl/repl.nimを実行すると、会話的に構文解析の結果を見やすく出力してくれます。
parserが作ったASTをを元に、括弧がつけられ、最終的に以下のように出力されます。
let hoge = (((1 + ((2 * 3) / 4)) + 5) - 6); 入力の括弧と記号の優先順位をちゃんと認識しながら抽象構文木が作られているのがわかります。
まだ評価機能が実装されていないので、計算式の結果を求めるのではなく、入力を見て正しく括弧を付けるだけのものです。
Pratt構文解析器
構文解析器にもいろんな種類がありますが、今回は1973年にVaughan Pratt氏の論文で発表されたPratt構文解析器という手法で実装しています。
Pratt構文解析器がどんなものかというと論文の中では以下のように紹介されています。
>very simple to understand, trivial to implement, easy to use, extremely efficient in practice if not in theory, yet flexible enough to meet most reasonable syntactic needs of users in both categories (i) and (ii) above.
つまり、
シンプルで理解しやすい
実装が簡単
使いやすい
理論上はもちろん実用上もとても効率的
利用者の殆どの合理的な公文に耐えられるほど柔軟
参考
Pratt Parserは下向き演算子順位解析を用いたもので、手書きでParserを書く時に有効な手法のようです。
普通、自作言語を作る場合はyaccなどのパーサジェネレータを使って、文法のみを定義しますが、今回は1からparserを実装しています。
参考
パーサジェネレータというのは、バッカス・ナウア記法(BNF)を用いて文法などを記述し、parserを自動生成するプログラムのことです。
が、僕はそもそもパーサージェネレータの方を触ったことがないので、いまいちイメージが掴めていません・・。
Parserの種類
構文解析器は大きく分けて「トップダウン構文解析器」と「ボトムアップ構文解析器」に分けられます。
両方共にいくつか種類がありまして、例えば前者では「再帰下降構文解析」や「パックラット構文解析」などがあり、Pratt構文解析器はこの再帰下降構文解析に当たります。
Wikipediaに載っていたものを以下に掲載します。
トップダウン構文解析
再帰下降構文解析←PrattParserはこれ
LL法
末尾再帰構文解析
パックラット構文解析
ボトムアップ構文解析器
LR法
SLR法
LALR法
CLR法
GLR法
アーリー法
CYK法
思ってたより沢山の種類があって、圧倒されてしまいました。
一つ一つを知るのはまた別の機会にします・・。
興味がある方はwikiなどを参考にしてみてください。
参考
これも調べてる時に見つけたものですが、いくつかの種類の構文解析のアルゴリズムがビジュアル的にとてもわかりやすくまとめられているスライドを見つけたので、載せておきます。
Pratt Parserも載ってます。
参考
Pratt Parserのアルゴリズム
先ほどの例とコードの一部を切り取って、実際にどのように動いて木を作っていくのかを確認していきます。
例として先ほどの例の図のツリーの一部をパースする処理を順を追って見ていきます。
「2*3/4」という文字列から以下のようなツリーを作ります。
つまり、以下のような構造を持ったオブジェクトを作っていくことになります。
ParserはLexerが作ったTokenを一つずつ見ていき、順に処理をしていきます。
今回の実装では、今見てるTokenを
curToken 、その次のTokenを peekToken と呼び、Parser Objectのプロパティとして持っています。これを処理とともに進めていくことで解析していきます。
「2 * 3」のツリーを作る
1.式か式文かを判断する
まず最初にcurTokenは
2 を指しています。図の左下は関数のコールスタックになります。
長くなるので、重要じゃない部分は省きます。
最初に呼び出されるparseStatement()は、curTokenを見て3つに分類して、それぞれの処理を行います。
今は
curToken が 2 なので、ここでは一番下の、式文をparseする関数を呼び出します。
2."2"をオブジェクトに保存する
次にparseExpression()が呼び出されます。
これがだいぶ重要な処理で、再帰的に呼び出される関数になります。
この中でさらに数値をparseする関数が呼び出され、
2 の部分のオブジェクトを返し、leftに代入します。
2 が作られました。
これを持った状態でwhileループに来ます。
ここの条件式がめっちゃ重要なので、あとで説明します。
ここでは条件を満たし、ループの中に入ります。
3.whileループの中に入る
ループの中では、peekTokenを見て次の処理を実行します。
ここでは、peekTokenは
* です。
この中でnextToken()が呼ばれているので、見ているTokenを一つずらして次の処理に移ります。
4."*"をオブジェクトに保存する
この辺からPratt Parserの真髄に入っていきます。
* をオブジェクトに保存します。(上の矢印)
そして、Tokenを進め、さらに、parseExpression()を呼びます。
このparseExpression()は、図の右下のコールスタックの赤色のやつです。
つまりここで、再帰されたのです。
5.parseExpression 再び
今は、再帰呼び出しされたparseExpression()の中にいます。
さっきと同じように
3 をparseしてオブジェクトに保存します。
先ほどとの違いは、whileループには入らない点です。
そのまま
3 を返します。
6.1個めのparseExpressionに戻ってきた
これで、
2*3 の部分が完成しました。いやぁ、長いですね。まだ半分です。
もう忘れているかもしれませんが、今は一度目に呼び出されたparseExpression()のwhileループの中でした。
ここで、再びwhileループの一番上に戻ります。
ここでも、条件を満たすので、まだ抜けられません
早く
/4 の部分をやってしまいたいですが、一旦このwhileループの条件の部分を確認します。Tokenの優先順位つけ
実はこの部分がPratt Parserで最も大事な部分になります。
"+"、"("、"="など、コードの中では沢山の記号が出てきますが、これらの記号は数値などとの結びつきの優先度が異なります。
例えば、「1 + 2 * 3」という入力が合った時に、「(1 + 2) * 3」とするか、「1 + (2 * 3)」とするかで、答えが異なってきます。
これは、"+"よりも"*"の方が優先度が高いと定義されているので、後者のようにツリーが作られます。
今回の実装では、以下の列挙型でTokenの優先順位を決めています。
Nimも他の言語の列挙型と同じく、下に行くほど大きな数値が与えられます。
つまり、「Sum < Product」を評価すると
true が返ります。while文の条件式
さきほど何度かスルーしたwhile文の条件式を見てみます。
nimwhile precedence < self.peekPrecedence() and not self.peekTokenIs(SEMICOLON):
hogehoge...ここはandで２つの条件を判定しています。
１つ目は引数で得た優先順位とpeekTokenの優先順位を比較しています。
２つ目は単純に、peekTokenがセミコロンかどうかを見ています。
重要なのは１つ目の方で、ここで先ほどの列挙型を用いて定義した優先順位が使われるわけです。
記号同士の優先順位の強さを見て、周りの数字などがどちらに結びつくかを決定します。
「1 + 2 * 3」という入力で、「2」は両隣に「+」と「*」がいますが、結びつきの強さは
「+」<「*」 なので、「*」と結びつくことになります。
whileループの条件式の話に戻すと、引数で受け取った優先順位より、peekTokenの優先順位のほうが大きい場合に、ループの中に入ります。
続き 「/ 4」の部分を作る
さっきの続きです。やってることは同じです。
7.whileの中
whileの中でpeekTokenを見て、「/」の部分が実行されます。
見てるTokenを進め、「/」を作ります。
8.parseExpresson 再び再び
再びparseExpressionを呼び出して最後の
3 をparseします。この中では、while文の二つ目の条件、「次のTokenがセミコロンではない」を満たさないので、ループに入りません。
9.完成
最後に今まで作ってきた、「2*3」と「/」と「4」をガッチャンコします。
こうしてやっと、「2 * 3 / 4」をパースしてASTを作り終えることができました。
こんな感じで進めていきます。
再帰があるので解説が複雑になってしまいました。
Pratt Parserの解説記事
PythonとJSを用いた解説記事があったので載せておきます。
Pythonを用いた解説
JavaScriptを用いた解説
JSの解説記事のサンプルコードのリポジトリ。ちょっと文法が古い。
ちなみに、JavaScriptの方を書いているのはDouglas Crockfordという人で、Pratt Parserの理論を用いてJSLintを作った人です。
苦労したこと
GoのコードをNimに書き換えていく作業はLexerのときよりかなり大変でした。
というのも、Nimにはインターフェースがなく、この型に対するエラーにはどう対処したら良いんだ？？というのが続出したからです。
Nimのフォーラムで質問したりもしたのですが、あまりにもそういった「どうにもならない状態」に出くわす頻度が高すぎるので、設計がおかしいのでは疑い始めました。
具体的には、本の中では、Identや式や文でインターフェースをわけていますが、Nimの方では一つの列挙型の中に定義し、一つのオブジェクトPNodeの中で分岐させて各構造体を作っています。
やはり、ある言語でコードを書くときは、その言語の思想を知り、それに則って書いていく必要があるんだなと感じました。
最後に
長い記事を読むのはあまり好きじゃないので、長い記事も書かないようにしているのですが、長くなってしまいました。
Parserの種類や、パーサージェネレータ、文脈自由文法など、構文解析一つとっても奥深いんだなとびっくりしました。
この辺の再帰を使う部分は関数型言語だと書きやすいっぽいので、OCamlかHaskellあたりで書いてみたいです。
Lexer、Parserとできたので、次はEvaluatorを作っていきます。
実際に数値を計算したりする部分です。
ちなみに本でいうとまだ半分くらいです。
先は長い・・。
参考