パーサジェネレーターLIME入門

LIMEとは？

C#の演算子オーバーロードを使ったパーサジェネレーターです。
https://github.com/ryu-shizumi/LIME

当記事投稿時ではできたてホヤホヤ、2018年12月にできたばかりです。

Language-Integrated-Matching-Evaluator (言語 統合 一致 評価器)
の頭文字を繋いでLIMEという名称ですが、覚えやすさ重視で柑橘類のライムと同じ綴りになるようにした「こじつけ」でもあります。

入力支援のあるSQLとしてLINQがあるように、入力支援のある正規表現を作ってみようというのがLIME開発の契機です。
作っている内に機能が正規表現を超え、パーサジェネレーターと呼べるくらいに達しました。

LIMEの特徴と性能は？(初心者は読み飛ばし可)

●インラインパーサジェネレーター
●BNFっぽく書ける。
●ボトムアップ型なので左再帰性の問題が発生しない。
●LR(∞)相当の表現力を有するのでC++パーサでも記述できる。
●線形時間で動作する。

動作原理に関しては単独で記事を設けるつもりなので今回は説明しません。

この記事の難易度

C#言語の基本が分かっていれば読めるくらいに記すつもりです。
小難しい専門用語は出ないはずです。そもそも著者自身が専門用語を知りません。

まずは初歩的な例から始めます

using LIME;

//(中略)

Matcher Rahmen = ("醤油"._() | "みそ"._() | "豚骨"._()) + "ラーメン"._();

これで変数Rahmenは

醤油ラーメン
みそラーメン
豚骨ラーメン

の３種類の文字列に一致する検索パターンになります。
検索パターンを使う場合は以下の様になります。

using LIME;

//(中略)

Matcher Rahmen = ("醤油"._() | "みそ"._() | "豚骨"._()) + "ラーメン"._();
Match match = Rahmen.Search("美味しい醤油ラーメンを食べよう");
Console.WriteLine(match.ToString());

Searchの引数として与えた"美味しい醤油ラーメンを食べよう"の中からRahmenを検索する処理になります。
標準出力には "醤油ラーメン" が出力されます。

次からはLIMEを構成する要素を順に説明していきます。

_()関数

文字列型・文字型の拡張メソッドとしてLIMEが提供する関数で、
文字列型・文字型を Matcher型(後述)に変換します。
LIMEの演算子オーバーロードはMatcher型に定義してあるのでMatcher型を作らない事には話が始まりません。

Matcher型

マッチャーが検索パターンの最小単位であり、マッチャーを演算子で結合して複雑なマッチャーを構築できます。
先の例の通り、Matcher型を演算した結果もMatcher型です。

+ 演算子

マッチャー同士を連結します。
文字列型同士が + で連結できるように、マッチャー同士の連結も + で可能です。

| 演算子

複数のマッチャーを併記して「どれかに合致する」を表現します。
| 演算子は + よりも演算の優先順位が低いので、普通は | 演算子は丸括弧と共に使います。

Matcher Rahmen = "醤油"._() | "みそ"._() | "豚骨"._() + "ラーメン"._();

のように丸括弧を忘れてしまった場合は + 演算子が優先されてしまうので、

醤油
みそ
豚骨ラーメン

の３種類の文字列に一致する検索パターンになってしまいます。

マッチャーは文字・文字列とも演算できる

先程の例は説明の為に文字列を全て_()関数でマッチャーに変換していましたが、
左辺か右辺のいずれかがマッチャーであれば文字・文字列との演算が可能です。

Matcher Rahmen = "醤油"._() + "ラーメン"._();

Matcher Rahmen = "醤油"._() + "ラーメン";

Matcher Rahmen = "醤油" + "ラーメン"._();

上記のいずれの演算でも変数Rahmenの値は同じになります。
| 演算子も + 演算子と同様に文字・文字列との演算が可能です。

Matcher Rahmen = ("醤油"._() | "みそ"._()) + "ラーメン";

Matcher Rahmen = ("醤油"._() | "みそ") + "ラーメン";

Matcher Rahmen = ("醤油" | "みそ"._()) + "ラーメン";

("醤油"._() | "みそ"._())の部分がMatcher型と評価されるので、文字列型の "ラーメン" との演算が可能になります。

Times()メソッド

繰り返しを表現可能です。

Matcher Person = 'ゲ'._().Times(3) + "の鬼太郎";

この例では

ゲゲゲの鬼太郎

に一致する検索パターンになります。
引数に渡したint型の3は繰り返し回数です。

繰り返し回数の下限と上限を指定する実装もあります。

Matcher Person = 'ゲ'._().Times(0, 4) + "の鬼太郎";

この例では

の鬼太郎
ゲの鬼太郎
ゲゲの鬼太郎
ゲゲゲの鬼太郎
ゲゲゲゲの鬼太郎

の５種類に一致する検索パターンになります。

Times()メソッドは繰り返し回数の指定に加えてデリミタも指定できます。

Matcher Person = 'ゲ'._().Times(3, "◆"._()) + "の鬼太郎";

この例では

ゲ◆ゲ◆ゲの鬼太郎

に一致する検索パターンになります。

Matcher Person = 'ゲ'._().Times(0, 4, "◆"._()) + "の鬼太郎";

この例では

の鬼太郎
ゲの鬼太郎
ゲ◆ゲの鬼太郎
ゲ◆ゲ◆ゲの鬼太郎
ゲ◆ゲ◆ゲ◆ゲの鬼太郎

の５種類に一致する検索パターンになります。

デリミタはMatcher型、文字型、文字列型のいずれかを指定します。

_01() _0Max() _1Max()

よく使う回数指定は専用メソッドがあります。
_01() は０回か１回です。
_0Max() は０回から最大回数です。デリミタの指定も可能です。
_1Max() は１回から最大回数です。デリミタの指定も可能です。

文字コードの範囲を指定してマッチャーを生成する

文字型にTo()という拡張メソッドを用意してあります。

// 数字１文字
Matcher Numeric = '0'.To('9');

// 大文字１文字
Matcher UpperCaseAlphabet = 'A'.To('Z');

// 小文字１文字
Matcher LowerCaseAlphabet = 'a'.To('z');

// 数字か大文字か小文字１文字
Matcher WordChar = Numeric | UpperCaseAlphabet | LowerCaseAlphabet ;

組み込みマッチャー

文字列先頭・文字列末尾・単語区切りといった文字の組み合わせで表現できない状況に一致するマッチャーを、組み込みマッチャーとして用意してあります。

LIME.BuiltInMatcher.Begin は文字列先頭に一致するマッチャーです。
LIME.BuiltInMatcher.End は文字列末尾に一致するマッチャーです。
LIME.BuiltInMatcher.WordBreak は単語区切りに一致するマッチャーです。

using static LIME.BuiltInMatcher;

//(中略)

Matcher Curry = Begin + "カレーライス" + End;

この場合、文字列全体がカレーライスの６文字の場合にのみ一致として認められます。
C#6.0からの機能「using static」を使えば「LIME.BuiltInMatcher」を略記できます。

Notプロパティ

「○○に一致しないマッチャー」を返します。
'0'.To('9') は数字に一致しますが、'0'.To('9').Not は数字以外に一致します。
'A'.To('Z') は大文字に一致しますが、'A'.To('Z').Not は大文字以外に一致します。
'a'.To('z') は小文字に一致しますが、'a'.To('z').Not は小文字以外に一致します。
('\r'._() | '\n') は改行文字に一致しますが、 ('\r'._() | '\n').Not は改行以外に一致します。
Begin は文字列先頭に一致しますが、 Begin.Not は文字列先頭以外に一致します。
End は文字列末尾に一致しますが、 End.Not は文字列末尾以外に一致します。
WordBreak は単語区切りに一致しますが、 WordBreak.Not は単語区切り以外に一致します。

Notプロパティは、長さ１文字 か 長さ０文字 のマッチャーのみに定義されています。

以上で正規表現と同等性能を表現する要素が出揃いました。

EmptyMatcher

正規表現では処理できない「入れ子構造」に対応する為のマッチャーです。
プログラミングのソースコードを解析するような用途では必須となります。
これは正規表現を超える唯一の機能であり、LIMEの最後となる機能です。
このマッチャーの解説は後ほど行います。

要素は以上、後は慣れです

実用的な例で慣れてもらいましょう。

整数

// マイナス記号
Matcher Minus = '-'._();

// 数字
Matcher Numeric = '0'.To('9');

// 整数値
Matcher IntegerValue = '0' | (Minus._01() + '1'.To('9') + Numeric._1Max());

「0」か「先頭に0を許さない非ゼロ」という事以外は特筆すべき事は無いかと思います。

実数

整数の定義に小数部と指数部を追加して実数を作ってみます。

// ゼロで始まっても良い整数値
Matcher Numerics = Numeric._1Max();

// 小数部
Matcher RealPart = '.' + Numerics;

// 正負の符号
Matcher Sign = Minus | '+';

// 指数部
Matcher ExponentPart = ('e'._() | 'E') + Sign._01() + Numerics;

// 実数値
Matcher RealNumber = IntegerValue + RealPart._01() + ExponentPart._01();

識別子

// 数字１文字
Matcher Numeric = '0'.To('9');

// アルファベット１文字
Matcher Alphabet = 'A'.To('Z') | 'a'.To('z');

// 識別子
Matcher Identifier = (Alphabet | '_') + (Alphabet | '_' | Numeric)._0Max();

プログラミング言語の識別子は数字以外で始まるのが一般的です。

文字列リテラル(C言語方式)

Matcher DoubleQuote = '"'._();

Matcher Cr = '\r'._();
Matcher Lf = '\n'._();
Matcher CrLf = Cr + Lf;
Matcher LineChar = (Cr | Lf).Not;

Matcher StringLiteral = '"' + ( ('\\' + LineChar) | ('\\'._()|'"').Not).0Max() + '"';

ダブルクォート + 文字の連続 + ダブルクォート、という定義は疑問の余地は無いでしょう。
問題は逆スラッシュ(Windowsでは円記号)でエスケープされた文字の扱いです。
逆スラッシュ(Windowsでは円記号)と後続の１文字を合わせて１文字扱いとしています。

今回はここまで。次回以降では後回しにしていたEmptyMatcherを使った「入れ子構造」を解説する予定です。

2018/12/24追記

続きができました。
パーサジェネレーターLIME入門その２(二項演算式にマッチさせる)