chabo-dslを支えるPerl正規表現テクニック――Tokenizer、Parserはほとんど正規表現だからな～

※これは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

は、

      +
     / \
    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()では対応する:を探し、

      ?
     / \
    a   :
       / \
      b   c

という形にする。

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

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

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

いつも正規表現がいる。

---

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

が、

7

になっている。

この瞬間が楽しい。

言語処理系は難しい。

でも、

小さく作れば、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だから。