※これはParserの作り方を真面目に解説する記事ではありません。
Perlと正規表現が好きな人間が、chabo-dslのコードを眺めながら「やっぱりPerlっていいな」と言っている記事です。

はじめに――Tokenizer、Parserはほとんど正規表現だからな～

chabo-dslのソースコードを眺めていると、ときどきこう思う。

「Tokenizer、Parserはほとんど正規表現だからな～。私はそれで良いと思うが……」

良いと思う。

むしろ、かなり良い。

世の中には「ちゃんとしたParser」を作ろうとすると、Lexerがあって、Parserがあって、ASTがあって、文法定義があって……と、だんだん大げさになっていく。

もちろん、それは正しい。

正しいのだが。

Perlを書いていると、横から正規表現がこちらを見ている。

「それ、s/// でよくない？」

……。

そこで負けてはいけない。

いや、負けてもいい。

chabo-dslは、だいたい負けている。

そして私は、それで良いと思う。

1. chabo-dslは「小さな言語」ではなく「正規表現の実験場」でもある

chabo-dslはPerlでゼロから実装したASTベースのDSLエンジンである。

Tokenizer、Parser、AST生成、Evaluator、スコープ管理、ユーザー定義関数、再帰などを持ちながら、本体はPODを含めても約750行程度に収まっている。日本語DSLについてはSugar.pmを差し替えれば別の言語風DSLも作れる構造になっている。

この「小ささ」は重要だ。

巨大なParser Generatorの世界に入ってしまうと、

文法
 ↓
Lexer
 ↓
Parser
 ↓
AST
 ↓
Evaluator

という立派な建築物ができる。

chabo-dslでは、もう少し雑である。

文字列
 ↓
正規表現
 ↓
もう少し正規表現
 ↓
AST
 ↓
評価

くらいである。

この「もう少し」がPerlなのである。

2. まず変数名から正規表現

Ast.pmには、こんな定義がある。

VAR_NAME => qr/[\p{L}_][\p{L}\p{N}_]*/u,

これだけである。

しかし、この一行にはchabo-dslの思想がかなり詰まっている。

[\p{L}_]

つまり、

文字、または _

から始まり、

[\p{L}\p{N}_]*

つまり、

文字、数字、_

が続く。

しかもUnicode対応。

だから日本語の変数名も、正規表現にとっては特別扱いではない。

金額
税込み
交差点
信号

も変数名になれる。

「日本語DSLだから日本語変数を特別にParserへ追加しよう」

ではない。

正規表現に、

「文字ってUnicodeだからね」

と言っておけば終わる。

このあたりが非常にPerlらしい。

3. 演算子まで正規表現になる

さらに面白いのがsetReOps()である。

$s->{ops} = join(
    '|',
    map { s/(\W)/\\$1/g; $_; }
    sort { length $b <=> length $a }
    (keys %$op, @_)
);

$s->{ops} = "(".$s->{ops}.")";

ここでは演算子テーブルから、演算子を認識するための正規表現を動的に作っている。

つまり、

+
-
*
/
%
==
!=
<=
>=
&&
||

などを一つずつParserに教えているわけではない。

演算子テーブルが、

my $op = getOp();

で増えれば、

正規表現も増える。

なんという怠惰。

いや、なんという自動化。

さらに、

sort { length $b <=> length $a }

で長い演算子を先に並べる。

これは重要だ。

例えば、

<=
<

があった場合、

を先に見つけてしまうと、

<=

が悲しいことになる。

そこで、

長いものから食べる。

Perlではこれができる。

Parser Generatorを導入するほどでもない。

正規表現を一行いじればいい。

4. 「日本語をParserに食わせる」のではなく「日本語を正規表現で甘やかす」

chabo-dslの日本語DSLを担当するのがSugar.pmである。

名前が良い。

Sugar。

つまり、本体のParserにいきなり日本語を食わせるのではなく、

先に甘くしておく。

日本語をchabo-dslの基本構文へ変換してしまう。

例えば、

もし信号が青か緑なら進んでも良い以外で

のような文を、

信号 == 青 || 信号 == 緑 ? 進んでも良い :

という構造へ持っていく。

その中心にあるのが、これ。

$text =~ s/
    もし(.+?)(?:なら|の場合|の時|時)(?:は)*(.+?)以外(?:(?:は|で))?
/
    my ($cond,$true) = ($1,$2);
    $cond = convert_condition($cond);
    "($cond) ? $true : "
/gex;

これを見て思う。

すごい。

そして、

ちょっと怖い。

そして、

美しい。

5. 正規表現で「日本語の揺らぎ」を吸収する

普通のプログラミング言語なら、

if

はifである。

終わり。

しかし日本語はそうはいかない。

なら
の場合
の時
時

など、似た意味を持つ表現が存在する。

そこでSugar.pmは、

(?:なら|の場合|の時|時)

と書く。

つまり、

「まあ、そのへん全部“なら”ってことで。」

という非常に柔軟な態度である。

日本語は曖昧だ。

だから正規表現も少し曖昧にする。

この組み合わせは、意外と相性が良い。

6. 比較演算子だって日本語になる

Sugar.pmには、こんな対応表がある。

my %jp_op = (
    '未満'   => '<',
    '以下'   => '<=',
    '超える' => '>',
    '以上'   => '>=',
    '等しい' => '==',
    '異なる' => '!=',
    '以外'   => '!=',
    'じゃない' => '!=',
    'でない' => '!=',
);

つまり、

金額が100以上

と書けば、

金額 >= 100

になる。

さらに論理演算子も、

my %jp_logical = (
    'で'     => '&&',
    'かつ'   => '&&',
    'か'     => '||',
    'または' => '||',
);

となっている。

だから、

信号が青か緑

は、

信号 == 青 || 信号 == 緑

へ変換される。

ここまで来ると、もはや正規表現は単なる「文字列検索」ではない。

小さな言語変換器である。

7. `s///gex`というPerlの魔法

個人的に好きなのは、この形式である。

s/
    パターン
/
    do {
        ...
    }
/gex;

gで全部探し、

eで置換文字列をPerlコードとして実行し、

xで正規表現を読みやすくする。

つまり、

正規表現
+
Perlコード
+
文字列変換

が一体化する。

これはもう、

「正規表現で置換しています」

というより、

「正規表現を入口にして小さなコンパイラを書いています」

に近い。

そしてPerlは、それを普通の構文として許している。

Perl、やはり恐ろしい。

8. Tokenizerとは何なのか

一般的な言語処理系では、

ソースコード
 ↓
Lexer
 ↓
Token列

と考える。

chabo-dslでは、もう少し現実的だ。

ソースコード
 ↓
adjust()
 ↓
item_split()
 ↓
Token列

そして、その途中で、

s/...

が大量に働く。

文字列を保護する。

空白を調整する。

演算子を分離する。

++や--を扱う。

括弧を考慮する。

つまり、

Tokenizerの仕事を正規表現と文字列操作で少しずつ片付けている。

Tokenizerを名乗るほど大げさなものではない。

しかし、やっていることはTokenizerである。

これは非常にchabo-dslらしい。

9. そしてParser `makeTree()`

Tokenizerを通過すると、いよいよASTである。

例えば、

2 + 3 * 4

は、

になる。

ここで重要なのは、

の優先順位が、

より高いこと。

Ast.pmでは演算子テーブルに、

+  -> 70
*  -> 80

のように優先順位が入っている。

そしてmakeTree()は、

一番優先順位の低い演算子を根にする。

という、とても素直な方法で木を作る。

つまり、

2 + 3 * 4

なら、

が根になる。

そして右側の

3 * 4

を再帰的に解析する。

結果、

+
├── 2
└── *
    ├── 3
    └── 4

になる。

Parserが「文法規則」を大量に持っているというより、

演算子と正規表現と再帰でASTまで持っていく。

潔い。

10. 三項演算子まで正規表現とASTの共犯

chabo-dslには三項演算子もある。

a ? b : c

これは普通に見える。

しかしParserからすると、

と

はセットである。

そのためmakeTree()では対応する:を探し、

という形にする。

ここでも「全部を一気に解析する巨大な文法規則」は登場しない。

小さなルールを積み重ねる。

そして、その小さなルールの足元には、

いつも正規表現がいる。

11. `split_eval()`という「カンマを見つけるだけなのに難しい」問題

DSLを書いていると、すぐに問題が発生する。

例えば、

func(a,b)

ならカンマで分割すればいい。

ところが、

func(a,[1,2,3])

ではどうする？

単純な、

split /,/

ではダメである。

さらに、

func(a,{x:1,y:2})

となったら？

ここでsplit_eval()は括弧・角括弧・波括弧の深さを追跡する。

$depth++ if $_ =~ /[\(\[{]/;
$depth-- if $_ =~ /[\)\]\}]/;

if($_ eq $sep && $depth == 0){
    ...
}

つまり、

「カンマだけど、今は括弧の中だから無視。」

という判断をする。

正規表現だけでは全部解決しない。

しかし、

正規表現 + 深さカウンタ + 再帰

で解決できる。

ここが面白い。

正規表現万能論ではない。

正規表現を信頼している。

しかし、正規表現に無理をさせすぎない。

この絶妙な距離感。

12. Sugar.pmは「言語の方言」を作る装置

chabo-dslの面白いところは、Ast.pm自身は日本語を知らなくてもよいことだ。

日本語は、

Sugar.pm

に任せる。

Sugar.pmが、

日本語
 ↓
chabo-dsl構文

へ変換する。

だから本体は、

日本語DSL

ではない。

あくまで、

ASTエンジン

なのである。

READMEにも、

Sugar.pmを置き換えることで、他言語風のDSLを実装できます。

という思想が示されている。

これは結構重要だ。

Sugarは「日本語対応機能」ではない。

言語を甘くするための層なのだ。

英語にしてもいい。

関西弁にしてもいい。

古文にしてもいい。

極端な話、

おぬしが100以上ならば……

というDSLを作ってもいい。

Parserは知らない。

Sugarが知っていればいい。

13. 正規表現は「汚いコード」なのか

ここで少し真面目な話をする。

Parserを正規表現で書くと、

「それは保守性が悪い」

と言われることがある。

正しい。

複雑な文法を巨大な正規表現で全部解析しようとすると、だいたい地獄になる。

しかし、chabo-dslはそこを狙っていない。

正規表現で、

文字列の正規化

をする。

トークン候補を見つける

。

演算子を認識する

。

日本語構文を基本構文へ変換する

。

そして最後はASTに任せる。

つまり、

正規表現ですべてを解析する

のではない。

正規表現に向いている仕事を、正規表現にやらせる。

これなら、かなり健全だと思う。

14. 「Perlだからできる」ではなく「Perlだから楽しい」

chabo-dslの面白さは、実装技術そのものにもある。

例えば、

qr/[\p{L}_][\p{L}\p{N}_]*/u

を見るだけで、

「日本語変数名いけるな」

となる。

s/.../.../gex

を見ると、

「ここでちょっとした構文変換できるな」

となる。

$depth += () = $_ =~ /[\[\{]/g;

を見ると、

「おお、そう来たか」

となる。

そして、

$text =~ s/.../.../gex;

が連続すると、

「また正規表現でやってるよ」

と思いながら、

ちょっと嬉しくなる。

これがPerlである。

15. 正規表現を愛する者には、`$1`が友達に見えてくる

例えばSugar.pmでは、

my ($cond,$true) = ($1,$2);

とする。

正規表現のキャプチャ。

$1。

$2。

初心者には、

「なんでこんなところに$1がいるんだ」

となる。

Perlを書き続けると、

「ああ、$1ね」

となる。

さらに進むと、

「このパターンなら$1と$2で十分だな」

となる。

そして最終段階では、

「名前付きキャプチャにしようかな……いや、$1でいいか」

となる。

ここまで来れば立派なPerl使いである。

16. `quotemeta`と「正規表現に食わせるものを正規表現から守る」

動的に演算子から正規表現を作るなら、

+
*
?
[
]
(
)

などの正規表現メタ文字を、そのまま食わせてはいけない。

そこで、

s/(\W)/\\$1/g

としてエスケープする。

これは小さい処理だが、とても大事だ。

正規表現は強力だ。

だからこそ、

何を正規表現として解釈させ、何をただの文字として扱うのか

をこちらが決めなければならない。

正規表現を愛するとは、

正規表現に何でもやらせることではない。

正規表現の機嫌を取ることである。

17. 日本語DSLの裏側で起きていること

例えばREADMEには、こんな日本語DSLの例がある。

青=1;緑=2;赤=3;黄=4;
信号=黄;
ans{交差点}= もし信号が青か緑ならすすめ以外で、
              もし信号が黄なら注意以外は止まれ。

これが最終的には、

交差点:注意

という結果になる。

表面だけ見ると、

日本語でプログラムを書いている。

しかし内部を見ると、

日本語
 ↓
Sugar.pm
 ↓
正規表現による変換
 ↓
chabo-dsl構文
 ↓
Tokenizer
 ↓
AST
 ↓
Evaluator
 ↓
結果

となっている。

つまり、

日本語の下に正規表現がいる。

さらにその下にASTがいる。

さらにその下にPerlがいる。

一番下まで掘るとPerlがいる。

怖い。

18. Parserは「賢い」のではなく「しつこい」

chabo-dslのParserを眺めていると、もう一つ気付くことがある。

Parserが賢いというより、

しつこい。

括弧があれば外してみる。

演算子を探してみる。

優先順位を比較してみる。

右結合か調べる。

三項演算子なら:を探す。

左側を再帰する。

右側を再帰する。

また演算子を探す。

また再帰する。

そして最後に、

AST

ができる。

Parserの仕事とは、

「賢く理解すること」

ではないのかもしれない。

「理解できるまで分解し続けること」

なのかもしれない。

そして、その分解作業のかなりの部分を、

正規表現が黙々と担当している。

19. だから私は「これで良いと思う」

chabo-dslを見て、

「もっとちゃんとしたParserにしたら？」

と言われるかもしれない。

もちろん、それもできる。

Lexerを独立させてもいい。

文法をBNFにしてもいい。

Parser Generatorを使ってもいい。

AST Builderを別クラスにしてもいい。

それはそれで面白い。

でも、chabo-dslには今の形だからこその魅力がある。

文字列
 ↓
正規表現
 ↓
少し加工
 ↓
また正規表現
 ↓
Token
 ↓
AST
 ↓
Perl

この距離の近さ。

コードを書いた本人が、

「ここで文字列をこう切って……」

と考えながら、そのまま実装できる。

これは小さな言語処理系を作るうえで、とても楽しい。

そして何より、

Perlである。

20. 正規表現は「黒魔術」ではない

正規表現はしばしば黒魔術と言われる。

確かに、

s/
    もし(.+?)(?:なら|の場合|の時|時)(?:は)*(.+?)以外(?:(?:は|で))?
/
    ...
/gex

などを見ると、

初見の人は一歩後ずさるかもしれない。

しかし、よく見るとやっていることは単純だ。

「もし」で始まる
 ↓
条件を取る
 ↓
「なら」などを探す
 ↓
真の場合を取る
 ↓
「以外」を探す
 ↓
条件式へ変換する

つまり、

正規表現は黒魔術ではない。

ただし、

Perlの正規表現は黒魔術になりやすい。

これは認めよう。

21. 「正規表現でParserを書く」という遊び

言語処理系を作るというと、

Lexer
Parser
AST
Semantic Analysis
Code Generation

という壮大な世界を想像する。

しかし、最初の一歩は、

$text =~ s/...

でもいい。

そこから、

my @tokens

が生まれ、

makeTree()

が生まれ、

readTree()

が生まれる。

そして気がつくと、

1 + 2 * 3

が、

になっている。

この瞬間が楽しい。

言語処理系は難しい。

でも、

小さく作れば、Perlと正規表現だけでもちゃんと「言語」が立ち上がる。

chabo-dslは、その実験場である。

22. 最後に――Perl愛、正規表現愛

chabo-dslのコードを見ると、

qr//

があり、

s///

があり、

split //

があり、

$1
$2

があり、

/g
/e
/x

がある。

そして、その先にASTがある。

これは偶然ではない。

Perlの、

「文字列をちょっと加工したい」

という欲望と、

正規表現の、

「文字列なら俺に任せろ」

という自信と、

ASTの、

「最後は俺が木にしてやる」

という落ち着きが、

なんとなく噛み合ってしまった結果である。

だから、

「Tokenizer、Parserはほとんど正規表現だからな～。私はそれで良いと思うが……」

である。

良い。

むしろ、

それがchabo-dslなのだ。

巨大なParserを作るのではなく、

小さな正規表現を一つずつ積み重ねる。

日本語を甘くし、

演算子を見つけ、

文字列を守り、

括弧を追い、

最後にはASTを作る。

そしてASTが計算する。

正規表現
    ↓
文字列
    ↓
Token
    ↓
AST
    ↓
計算

たったこれだけ。

でも、その「たったこれだけ」の中に、

Perlが好きな人間の、

「これ、正規表現でいけるんじゃない？」

という、あの危険な好奇心が詰まっている。

そして一度それを始めると、

$text =~ s/...

を書いた瞬間、

もう後には戻れない。

――それで良いと思う。

Perlだから。

正規表現だから。

そして、

chabo-dslだから。