目的
再帰下降構文解析を通して、プログラミング言語がどのように解析されるのかの一端に触れ、未知の言語に対する恐怖を取り払います（大げさ）。BNF表現にも同時に触れ、いやいや便利だっなと感じます（人による）。
何が出来るの？
構文解析出来ます。おれおれ言語作れます。独自な設定ファイルのパーサやらが書けます。
なおここでは、構文解析器を作ってしまう便利なアレコレは使いません。
JavaScriptで書く意味
全く、これっぽっちも、ありません。比較的入りやすいと感じる人が多いのではないか、という程度の理由です。お好きな言語でどうぞ。
強いて言うなら、ブラウザ上でも簡単に動くのでなんだか夢が広がると言うのはあるでしょうか。例えば…「簡易SQL where句パーサとUIを組み合わせてなんだかリッチな検索条件設定を作ってみる」とかどうでしょう。
ちなみにここのコードは、基本的にnode(10.4.1)で実行して確認をしましたが、SafariのJavaScriptコンソールでも動いていましたので、お気軽にお試しいただけるのではと思います（差分でないコードからコピペすると楽です）。
1 + 2 = 3
まずは1 + 2という入力を受けたら3と返すものを考えます。例えばこんな感じですか。
let input = '1 + 2'
console.log(input, '=', expression(input))
あ、今そこでevalしようとした人。そういうんじゃないんです。空気を読んで10分間正座して下さい。
字句解析
構成要素をばらばらに分けるのを、字句解析と言います。最初なので、適当にごまかしましょう。
let tokenize = (str) => {
return str.split(/\s+/)
}
いや、これああしたらダメなんじゃ？みたいなことを即座に思いますが、考えなかったことにします。考えていません。正座しながら書いています。
構文解析
字句を文法定義に従って解析するのが構文解析です。ここでは、構文解析をしながら、評価（計算実行）も行います。
まあともかく、内容としては、+を見つけて、左右を足して、返せば良いだけの話です。
let expression = (str) => {
let tokens = tokenize(str)
let idx = 0;
let result = Number(tokens[idx++])
while ( tokens[idx++] === '+' ) {
result += Number(tokens[idx++])
}
return result
}
数字を足した後は、何もないか、もしくは+のオペレータであるかの二択です。オペレータならばその次を足すし、そうでないなら式の終わりもしくは文法違反で、いずれにしても終わりにします。
実行してみる
実行用のスクリプトは下記のようにしました。
let tokenize = (str) => {
return str.split(/\s+/)
}
let expression = (str) => {
let tokens = tokenize(str)
let idx = 0;
let result = Number(tokens[idx++])
while ( tokens[idx++] === '+' ) {
result += Number(tokens[idx++])
}
return result
}
let input = process.argv[2]
console.log(input, '=', expression(input))
step1.jsとか保存して、実行。
% node step1.js "1 + 2"
1 + 2 = 3
% node step1.js "1 + 2 + 3"
1 + 2 + 3 = 6
動いてそう！いや、まだ喜ぶところではないけど！
BNFにしてみる
BNFは言語の文法を表現するひとつの形式です。それで今回の素晴らしいおれおれ言語の文法を表現します。以下、この文章では拡張BNF（EBNF）を使います。
expression = number, { "+", number } ;
numberは何となく察してください。中括弧（{}）は「０回以上の繰り返し」です。「expressionは、numberをひとつと、+に続くnumberの0回以上の繰り返しである」と定義されています。
よく見ると、実際のコードとほとんど一緒ですよね。ひとつめを取り出して、以降'+'が見つかる限り繰り返す。
let result = Number(tokens[idx++]) // <- number
while ( tokens[idx++] === '+' ) { // <- { "+",
result += Number(tokens[idx++]) // <- number
} // <- }
再帰下降構文解析では、文法のBNF表現と実装がだいたい一緒になるようです。これは大変ありがたいことで、実装を見れば文法構造がわかるし、文法構造がわかれば実装のヒントになるというわけです。
1 + 2 - 3 = 0
引き算に対応してみましょう。こんなにも高度なことを楽々こなせる、人智をはるかに超えた言語ですね。バベル-17とでも名付けましょうか。いや止めておこう…。
BNF
今度は先にBNFを書いてみます。多分下記のようになります。
expression = number, { ("+"|"-"), number } ;
説明するのもアレな感じですが、要するに、「+」を「+か-」に変えただけです。
実装
BNFと実装は対応しているので、多分whileのループの内側あたりを変更すると良さそうですね。下記のようにしてみました。
let expression = (str) => {
let tokens = tokenize(str)
let idx = 0;
let result = Number(tokens[idx++])
while (tokens[idx] === '+' || tokens[idx] === '-') {
switch (tokens[idx++]) {
case '+':
result += Number(tokens[idx++])
break
case '-':
result -= Number(tokens[idx++])
break
}
}
return result
}
試してみると
% node step2.js "1 + 2 - 3"
1 + 2 - 3 = 0
どうやらちゃんと動きそうです。
- 1 + 2 - 3 = - 2
どうせなら符号にも対応していると良いのでは無いでしょうか。やってみましょう。
expression = ["+"|"-"], number, { ("+"|"-"), number } ;
角カッコ（[]）は「0回か1回」です。これまたexpressionの中に実装したら良さそうですね。いろんな方法が考えられますが、とりあえずこんなでどうでしょう。
let expression = (str) => {
let tokens = tokenize(str)
let idx = 0;
let result = 1
if (tokens[idx] === '+') {
idx++
}
else if(tokens[idx] === '-') {
result = -1
idx++
}
result *= Number(tokens[idx++])
while (tokens[idx] === '+' || tokens[idx] === '-') {
switch (tokens[idx++]) {
case '+':
result += Number(tokens[idx++])
break
case '-':
result -= Number(tokens[idx++])
break
}
}
return result
}
BNFがヒントになるので、あまり迷わずに実装出来ています。
リファクタリング
だんだんチェックしたい項目が増えました。今のうちに、テストしやすい用にリファクタリングでもしておきますか。
class MyLang {
constructor() {}
exec(str) {
return this.expression(str)
}
tokenize(str) {
return str.split(/\s+/)
}
expression(str) {
let tokens = this.tokenize(str)
let idx = 0;
let result = 1
if (tokens[idx] === '+') {
idx++
} else if (tokens[idx] === '-') {
result = -1
idx++
}
result *= Number(tokens[idx++])
while (tokens[idx] === '+' || tokens[idx] === '-') {
switch (tokens[idx++]) {
case '+':
result += Number(tokens[idx++])
break
case '-':
result -= Number(tokens[idx++])
break
}
}
return result
}
}
module.exports = MyLang
で、チェック用のコードはこんな。
let MyLang = require('./MyLang.js')
let lang = new MyLang()
let tests = [{
input: '1 + 2',
expect: 3
},
{
input: '1 + 2 + 3',
expect: 6
},
{
input: '1 + 2 - 3',
expect: 0
},
{
input: '- 1 + 2 - 3',
expect: -2
}
]
for (let test of tests) {
let result = lang.exec(test.input)
console.log(
result === test.expect ? '[OK]' : '[NG]',
test.input, '=', result
)
}
実行すると
% node step4/test.js
[OK] 1 + 2 = 3
[OK] 1 + 2 + 3 = 6
[OK] 1 + 2 - 3 = 0
[OK] - 1 + 2 - 3 = -2
あ、普通にnpmでテストモジュール使っていいですよ。単純にできるだけ予備知識なしで良いようにお手製にしているだけですから。
手元で実行するためのcalc.jsも書き換えておきます。
let MyLang = require('./MyLang.js')
console.log(process.argv[2], '=', new MyLang().exec(process.argv[2]))
1+2 = 3
では次に、1+2を解釈しましょう。そう、なんと驚くべきことに、上記のおれおれ言語は、すべての要素の間にスペースがないといけないのです！全く気付かなかったなぁ。
つまり、こんなテストが通って欲しいのですよね。
--- step4/test.js
+++ step5/test.js
@@ -17,6 +17,14 @@
{
input: '- 1 + 2 - 3',
expect: -2
+ },
+ {
+ input: '1+2',
+ expect: 3
+ },
+ {
+ input: '-1+2-3',
+ expect: -2
}
]
まあもちろん通らないわけですけど。
% node step5/test.js
[OK] 1 + 2 = 3
[OK] 1 + 2 + 3 = 6
[OK] 1 + 2 - 3 = 0
[OK] - 1 + 2 - 3 = -2
[NG] 1+2 = NaN
[NG] -1+2-3 = NaN
そうするとBNFなどがちょっと違うんじゃないかって話になりますが、明日から頑張りますので突っ込まないでください。気付いてた人はさらっと流して頂けると有り難いです。
字句解析を改良する
要するに字句解析で楽をしすぎたのが良くないのです。Cだったらあんなのないよ、まったく。
ちゃんと考えるなら、元の文字列をきちんと1文字ずつ取り出して、それがなんであるのかを一つずつ考えるのが良さそうです。ということで、まずは1文字ずつ取り出すためのものを用意しましょうか。
class MyBuffer {
constructor(str) {
this.str = str
this.idx = 0
}
exist() {
if (this.idx < 0) {
return false
}
if (this.str.length <= this.idx) {
return false
}
return true
}
read() {
return this.str.substr(this.idx, 1)
}
next() {
return this.str.substr(this.idx++, 1)
}
}
module.exports = MyBuffer
まあこんな風にカプセル化しなくても、普通にインデックスいじりながら出来ますが、案外インデックス操作が面倒になってくるものです。これは天才的な先見の明であって、散々苦労したからでは断じてありません。
さて次は、次の1文字からそれがなんであるか判定します。「次の1文字」だけからわかるのか、ということですが、現状の文法は「数字」「+」「-」くらいしかないですし、それ以外は全部いらないゴミなので、判定は簡単なものです。
let MyBuffer = require('./MyBuffer.js')
class MyLexer {
constructor(str) {
this.idx = 0
this.tokens = []
if (str) {
this.tokenize(str)
}
}
tokenize(str) {
this.tokens.splice(0)
let buf = new MyBuffer(str)
while (buf.exist()) {
if (/\d/.test(buf.read())) {
this.tokens.push(this.getlex_number(buf))
} else if (/[\+\-]/.test(buf.read())) {
this.tokens.push(this.getlex_symbol(buf))
} else {
buf.next()
}
}
return this.tokens
}
getlex_number(buf) {
let num = ''
while (/\d/.test(buf.read())) {
num += buf.next()
}
return Number(num)
}
getlex_symbol(buf) {
return buf.next()
}
exist() {
if (this.idx < 0) {
return false
}
if (this.tokens.length <= this.idx) {
return false
}
return true
}
read() {
return this.tokens[this.idx]
}
next() {
return this.tokens[this.idx++]
}
}
module.exports = MyLexer
バッファから1文字取り出して、数字だったらgetlex_numberに、+か-だったらgetlex_symbolに任せ、それ以外なら無視して次に進む。getlex_numberは、次が数字である限り繋げてから返す。getlex_symbolに関しては…手抜きですね。とりあえずはいいでしょう。
あとMyBufferにあるようなイテレーションを行うメソッドもつけておきました。先見の明ですよ。
これをMyLangに入れます。せっかくなので、インデックスをごちゃごちゃしているところもなくします。
let MyLexer = require('./MyLexer.js')
class MyLang {
constructor() {}
exec(str) {
return this.expression(new MyLexer(str))
}
expression(lexer) {
let result = 1
if (lexer.read() === '+') {
lexer.next()
} else if (lexer.read() === '-') {
result = -1
lexer.next()
}
result *= Number(lexer.next())
while (lexer.read() === '+' || lexer.read() === '-') {
switch (lexer.next()) {
case '+':
result += Number(lexer.next())
break
case '-':
result -= Number(lexer.next())
break
}
}
return result
}
}
module.exports = MyLang
なんだか立派になりましたが、実際はsplitがすごくなっただけなので、内容的には変わりありません。
% node step5/test.js
[OK] 1 + 2 = 3
[OK] 1 + 2 + 3 = 6
[OK] 1 + 2 - 3 = 0
[OK] - 1 + 2 - 3 = -2
[OK] 1+2 = 3
[OK] -1+2-3 = -2
無事テストも通った、と。
しかしふと考えると、解析途中で扱っているトークンの種類がわかっているんですよね。数字なのか、シンボル（ここでは演算子）なのか。
ここで文法上期待されているものが来ているかチェックができるし、この情報をトークンに足しておくと、実際の処理（トークンの種類判別）も綺麗になりそう！脱線しているので無視しますが、ぜひ余裕があったらやってみてください。
1 + 2 * 3 = 7
では話を戻して、そろそろ乗除を付け加えましょう。これ、電卓で計算してみて下さい。いち、たす、に、かける、さん…で答えは…9ですね！まあ普通の電卓だと9ですが、数式的には、かけ算のほうが優先順位が高いわけです。このあたりがどう表現されるのか。
BNF
パターン化してきたので先にBNFを見ましょう。ここは一工夫あります。
expression = ["+"|"-"], term, { ("+"|"-"), term } ;
term = number, { ("*"|"/"), number } ;
numberだったところをtermに変えて、termは乗除の文法を定義しています。expressionを評価しようとすると、加減算の前にtermの評価が必要になる…つまりtermのほうが優先順位が高い…というわけ。確かに先に計算されそうですね。
ではこんな感じで実装してみましょう。
字句解析
まずは字句解析で乗除の記号が通るようにしましょう。
--- step5/MyLexer.js
+++ step6/MyLexer.js
@@ -16,7 +16,7 @@
while (buf.exist()) {
if (/\d/.test(buf.read())) {
this.tokens.push(this.getlex_number(buf))
- } else if (/[\+\-]/.test(buf.read())) {
+ } else if (/[\+\-\*\/]/.test(buf.read())) {
this.tokens.push(this.getlex_symbol(buf))
} else {
buf.next()
getlex_symbolは手抜きで、通ってきた一文字をそのまま返しているだけですから、上記の通りシンボルの判定部分だけ変えればOKです。
構文解析
次はtermを実装してみましょう。
class MyLang {
// ...
term(lexer) {
let result = lexer.next()
while (lexer.read() === '*' || lexer.read() === '/') {
switch (lexer.next()) {
case '*':
result *= Number(lexer.next())
break
case '/':
result /= Number(lexer.next())
break
}
}
return result
}
}
加減算と同じパターンですね。もう一つ、加減算のほうはtermから値を得るようにしないといけません。
--- step5/MyLang.js
+++ step6/MyLang.js
@@ -15,15 +15,15 @@
result = -1
lexer.next()
}
- result *= Number(lexer.next())
+ result *= Number(this.term(lexer))
while (lexer.read() === '+' || lexer.read() === '-') {
switch (lexer.next()) {
case '+':
- result += Number(lexer.next())
+ result += Number(this.term(lexer))
break
case '-':
- result -= Number(lexer.next())
+ result -= Number(this.term(lexer))
break
}
}
}
数値を取り出していた部分をtermに任せるようにすれば良いだけです。BNFとも一致しますね。
後は実行あるのみ。
% node step6/test.js
[OK] 1 + 2 = 3
[OK] 1 + 2 + 3 = 6
[OK] 1 + 2 - 3 = 0
[OK] - 1 + 2 - 3 = -2
[OK] 1+2 = 3
[OK] -1+2-3 = -2
[OK] 1 + 2 * 3 = 7
動いてそうですね。素晴らしい。
1 + 2 * ( 3 - 4 ) = -1
調子に乗ってどんどん進みましょう。次は括弧つきです。もちろん括弧があると、優先順位が変わりますね。これはどうしましょうか。
BNF
以下のようにします。
expression = ["+"|"-"], term, { ("+"|"-"), term } ;
term = factor, { ("*"|"/"), factor } ;
factor = number | "(", expression, ")" ;
termで数値を取り出さずに、factorに任せます。factorでは、取り出した字句がnumberだったらそのまま使い、(だったらexpressionで評価します。
再帰的に定義されているので、括弧がいくつ重複していても、同じパターンで内側の評価が先に行われることになります。うまく出来ていますね。
では実装します。
字句解析
乗除と同様に、括弧も通すようにしましょう。
--- step6/MyLexer.js
+++ step7/MyLexer.js
@@ -16,7 +16,7 @@
while (buf.exist()) {
if (/\d/.test(buf.read())) {
this.tokens.push(this.getlex_number(buf))
- } else if (/[\+\-\*\/]/.test(buf.read())) {
+ } else if (/[\+\-\*\/\(\)]/.test(buf.read())) {
this.tokens.push(this.getlex_symbol(buf))
} else {
buf.next()
構文解析
factorを実装し、BNFに沿って入れ替えを行います。
class MyLang {
// ...
factor(lexer) {
if (lexer.read() === '(') {
lexer.next()
let result = this.expression(lexer)
if (lexer.read() === ')') {
lexer.next()
}
else {
console.log('Syntax Error! : unexpected charactor = ', lexer.read())
}
return result
}
else {
return lexer.next()
}
}
}
expressionで評価した後、次は閉じ括弧になっているはずなので、それを確認しています。閉じ括弧になっていないというのは括弧の対応が取れていないという意味なので、文法エラーです。おお、なんかちゃんと言語っぽいですね！
--- step6/MyLang.js
+++ step7/MyLang.js
@@ -31,14 +31,14 @@
}
term(lexer) {
- let result = lexer.next()
+ let result = this.factor(lexer)
while (lexer.read() === '*' || lexer.read() === '/') {
switch (lexer.next()) {
case '*':
- result *= Number(lexer.next())
+ result *= Number(this.factor(lexer))
break
case '/':
- result /= Number(lexer.next())
+ result /= Number(this.factor(lexer))
break
}
}
さてどうかな…。
% node step7/test.js
[OK] 1 + 2 = 3
[OK] 1 + 2 + 3 = 6
[OK] 1 + 2 - 3 = 0
[OK] - 1 + 2 - 3 = -2
[OK] 1+2 = 3
[OK] -1+2-3 = -2
[OK] 1 + 2 * 3 = 7
[OK] 1 + 2 * ( 3 - 4 ) = -1
[OK] ( 1 + 2 ) * ( 3 - 4 ) = -3
乗除の追加や括弧など、場合によっては面倒そうな文法追加も、結構スマートに出来ました。再帰おそるべし。
もうパターン化されているようなもので、指数も対数も三角関数も、その他自分の好きな組み込み関数も、やりたい放題ですよね。BNFに付け加えて、試してみてください。
まとめ
再帰下降構文解析は、BNFと実装が一致するのが利点の一つで、かなり機械的に実装ができます。しかも、処理内容としては「文字を取り出す」とか「インデックスを操作する」程度ですから、どんな言語を使っても書けそう。簡単なDSLであれば、ツールに頼らずともパパッと作れそうでしょう？
ただここで大切だと感じていることは、構文解析器の作り方ではなく、案外シンプルな方法の繰り返しで構文解析ができるという事実です。
こういうことを知っていると、ほかの言語を学習するときなどにも、きっと言語の動きの裏側がちょこっとだけ透けて見えて、気が楽になるのではないかなと思っています。
おまけ
上記のコードは以下で拾えます。