Eyes, JAPAN Blog > お手軽な構文解析

お手軽な構文解析

mima

この記事は1年以上前に書かれたもので、内容が古い可能性がありますのでご注意ください。

D

少し込み入ったコーディングをしていると、たまに構文解析が必要な状況になることがあります。

大抵の場合、正規表現で解決できますが(例えば、文字列内のIPアドレス表記の部分を抜き出すなど)、そうでない複雑な場合もあります。

そんな時に、EBNFから構文解析器を生成するライブラリなどを使って事前に構文解析器を生成して構文解析するのもいいですが、少し手間がかかります。

今回は、そんな時に使えるであろう、お手軽にEBNFから構文解析器を作る方法を紹介します。

というわけで、

exp = digit [ op ]
op = "+" exp
digit = '0' | '1' | '2' | '4' | '5' | '6' | '7' | '8' | '9'

という、一桁の数字の足し算を実際に計算する構文解析器をD言語で作ってみます。

まず、Resultという構造体を以下のように作ります。

struct Result{
    bool success = false; // パーサが成功したかどうか
    int value; // パースした値
    string rest; // 入力の残り
}

一つのパーサはひとつの関数として定義します。そのとき、関数はResult型の値を返します。

import std.conv;

Result exp(string input){
Result res;
// digitを呼ぶ
Result r1 = digit(input);
// digitが失敗したらexpも失敗する
if(!r1.success){
return res;
}
res.value = r1.value;
res.rest = r1.rest;
// opを呼ぶ
Result r2 = op(res.rest);
// opはあってもなくてもいいので、成功した時だけ足す
if(r2.success){
res.value += r2.value;
res.rest = r2.rest;
}
return res;
}

Result op(string input){
Result res;
// 入力の一文字目が ‘+’ じゃなかったら失敗
if(input[0] != ‘+’){
return res;
}
// exp を呼ぶ
Result r = exp(input[1..$]);
res.success = r.success;
res.value = r.value;
res.rest = r.rest;
}

Result digit(string input){
Result res;
// 入力の一文字目が数字なら成功
if(‘0’ <= input[0] && input[0] <= '9'){ res.success = true; res.value = to!int(input[0] - '0'); res.rest = input[1..$]; } return res; } [/cpp] と、EBNFの通りに書いてみます。 すると、 [cpp] exp("1+2+3+4") [/cpp] が10になってくれます。 今回はかなり簡単な例を紹介しましたが、もう少し複雑になっても同様の方法で構文解析器を関数として作れます。 構文解析器が必要な状況に遭遇したら、ぜひ試してみてください。

Comments are closed.