（1）はこちら 、（ 2）はこちら から。
構文解析器の作り方
（3）では、Compiler::Parserを開発する際に得た知見をもとに、構文解析器を開発するうえでの勘どころを説明します。
トークンをカテゴライズする
構文解析器のソースコードがシンプルになるか複雑になるかは、トークンを適切にカテゴライズできるかにかかっています。トークンどうしの共通点を見つけることができれば、木構造を生成するまでの過程が共通化され、見通しの良いソースコードにできます。もし処理が共通化できなければ、再帰処理を繰り返す過程でデバッグが困難になっていくことでしょう。このことは、構文解析器の開発が1回ではなかなか成功しない要因の一つになります（筆者自身、Compiler::Parserを開発するにあたって一度ソースを書きなおしています。PPIも一度書きなおしたそうです） 。
では、一度でトークンを適切にカテゴライズするにはどうすればよいでしょうか。作りなおしの原因は、一度作らないとどのトークンが同じ処理にまとめられるかを判断できないことに由来します。ですから、あらかじめ木構造のレイアウトを決め、各トークンがどのように木構造の中に配置されるかをイメージしながら開発することで、作りなおしを避けることができます。
これは自戒も込めてですが、トークンをカテゴライズする際には、できるなら自分一人で決定せず、ほかの開発者と相談しながら慎重に決定しましょう。他言語の実装を参考にすることも重要です。
「関心の分離」を意識する
構文解析器は言語処理系を実装するうえでも特にソースコードが複雑になりがちなコンポーネントです。そのため「関心の分離」を強く意識し、できる限り責務を分散させて開発します。そのうえで重要な考え方は、「 トークン列を一度にまとめない」ことです。一度とは、そのトークンがどうまとめられるかを、トークン列を最初から最後まで一周なめただけで決定することを指します。実装上は不可能ではありませんが、ソースコードの可読性が低下する原因になるため推奨しません。
Compiler::Parserでは複数のステップに分けてトークン列をまとめています。それぞれのステップを解説していきます。
①結合することで初めて意味を持つトークンを結合する
字句解析器でトークンに分解する際は、前後のコンテキストを意識せずに、最小単位の文字列を切り出します。たとえば、Compiler::Parser->newといった文字列は、「 Compiler」「 ::」「 Parser」「 ->」「 new」と分解されますが、「 ::」といったトークンはそれだけでは意味を成さないため、前後のトークンと結合する必要があります。
Compiler::Parserでは次のように、名前解決処理に関するトークンと、デリファレンス演算子の短縮表現に関してトークンの結合を行っています。
名前解決処理に関する結合例
Compiler::Parser->new
-> 'Compiler' '::' 'Parser' '->' 'new'# 字句解析の結果
-> 'Compiler::Parser' '->' 'new'# トークン結合後の結果デリファレンス演算子の短縮表現に関する結合例
scalar @$array_ref
-> 'scalar' '@$' 'array_ref' # 字句解析の結果
-> 'scalar' '@$array_ref' # トークン結合後の結果②トークン列を文単位にまとめる
トークンをまとめる際は、文・式・項・値という構造を意識することが重要です。
文（Statement ）は日本語の文章では「。」で区切られているように、それ自体で完結するまとまりです。Perl 5ではセミコロン（;）で区切られた単位と考えると理解しやすいと思います。ほかには「if文」「 for文」と呼ぶように、if () {}やfor (;;) {}も文とみなすことができます。
式（Expression ）は何らかの値を評価するまとまりを指します。たとえば1+1、print "hello"、$a && $bが該当します。
項（Term ）は式を構成する要素です。たとえば$array[0]や$hash{a}が該当します。
値（Value ）は項を構成する要素です。たとえば0やBareword、$aが該当します。
これらは文⊃式⊃項⊃値という包含関係があり、この構造を意識しながらトークンをまとめていきます。
まずはトークンを文の単位にまとめます。こうすることで、そのあとの処理をそれぞれの文単位で行うことができ、一度に考慮しなければいけない処理量を減らすことができます。
トークン列を文単位にまとめる
my $a = 1; print $a;
# 字句解析の結果
-> 'my' '$a' '=' '1' ';' 'print' '$a' ';'
# 「;」で文単位にまとめる
-> ['my' '$a' '=' '1' ';']['print' '$a' ';']※ []でくくった範囲が1つの文
③トークン列を式単位にまとめる
文単位にトークンをまとめたあとは、構文木をより容易に作成するために式単位にまとめる処理を行います。たとえば次のように式にまとめることができます。
トークン列を式単位にまとめる
my $a = sub { return 1; };
# 字句解析の結果を文単位にまとめる
-> [ 'my' '$a' '=' 'sub' '{'['return' '1' ';']'}' ';']
# さらに式単位に分割
-> [('my' '$a' '=' ('sub' '{'['return' '1' ';']'}')) ';']※ []でくくった範囲が1つの文、()でくくった範囲が1つの式
sub {}や、my $a = sub { }を式と判断し1つにまとめます。このあと、後述する括弧を補完する処理を行うことで、さらに式単位にまとめることが可能になりますが、この段階ではsub {}（ラムダ式）や(1+2)（明示的に括弧書きされている場合）などの自明なもののみを対象として式にまとめます。
④トークン列を項単位にまとめる
文・式とトークンをまとめたあとは、式を構成する要素の中でfunction_call() （関数呼び出し）や$array[0],$hash{key}（配列やハッシュアクセス） 、m|regexp|（正規表現）などを項としてまとめれば、ひとまずトークンをまとめる処理は終了となります。
括弧を補完する
Perlでは括弧などの記述を省略できます。省略記法で書かれたソースコードを適切に処理するためには、省略された記法を補って考えるほかありません。そこで、まとめられたトーク列を対象に、括弧が省略されなかったときと同じ評価順序になるよう、さらにトークンをまとめます。
括弧の省略処理の一番馴染み深い例は四則演算でしょう。① のコードは、構文解析器の中で② と解釈されます。
my $a = 1 + 2 * 3 + 4 / 2;
(my $a = ((1 + (2 * 3)) + (4 / 2)));
普段何気なく書いている処理であっても、裏側では多くの括弧がついて解釈されています。では、どのように括弧を補完していけばよいでしょうか。
括弧を補完することの意味は、式の評価順序を守るためです。1+2よりも2*3のほうが先に処理されなければなりません。そのため、演算子の評価順序をあらかじめ定義する必要があります。
perlopに従って解釈する
Perlでは、perlopに演算子の評価順序がまとめられており、日本語の記述はhttp://perldoc.jp/docs/perl/perlop.pod から参照できます。Compiler::Parserもperlopを参照して式の評価順序を決定しており、上記の例であれば次のように解釈して処理されます。
# 左からトークン列をなめて、「*」「/」が出てきたら
# 前後のトークンと併せてまとめる
my $a = 1 + (2 * 3) + (4 / 2);
↓
# 左からトークン列をなめて、「+」が出てきたら
# 前後のトークンと併せてまとめる
my $a = ((1 + (2 * 3)) + (4 / 2));
↓
# 左からトークン列をなめて、「my」が出てきたら
# あとのトークンと併せてまとめる
(my $a) = ((1 + (2 * 3)) + (4 / 2));
↓
# 右からトークン列をなめて、「=」が出てきたら
# 前後のトークンと併せてまとめる
((my $a) = ((1 + (2 * 3)) + (4 / 2));)
perlopでは解釈できないケースがある
しかしperlopを読み進めていくと、このやり方ではうまくいかない場面が登場します。次のようなケースです。
③ の正しい解釈は(!(defined($a+1)))となるはずですが、perlopにある規則に従って解釈すると次のようになってしまいます。
!defined $a + 1
# 名前付き単項演算子より先に右結合の単項演算子! を評価する
-> (!defined) $a + 1
# + 演算子を評価する
-> (!defined) ($a + 1)
-> 「式」「式」の組み合わせはありえないのでSyntax Error になる
つまり本来であれば、単項演算子である!を評価する前に、!演算子の対象となる項を決定しておく必要があるのですが、perlopの定義により、!演算子より+演算子のほうが評価順序があとなので、definedの引数を決定できません。その結果、「 項」としてdefined+引数をまとめることができず、上記のようなSyntax Errorになってしまいます。
Compiler::Parserでの対処
では、上記のような例にはどのように対応すればよいでしょうか。Compiler::Parserでは、名前付き単項演算子に関して次のように考え、対処しています。
名前付き単項演算子は、別な見方をすれば引数の数がわかっている組込み関数と同じように考えることができます。たとえばdefinedの場合、引数の数が1つでなければなりません。そこで、上記の例の(!defined) ($a+1)の結果を見た際に、definedの引数が空であることをおかしいと判断します。そのうえで、「 『 式』『 式』の組み合わせ」であり、かつ「最初の式の最後のトークンが名前付き単項演算子」であり、かつその演算子が「引数を1つとるもの」である場合には、上記の結果を修正して(!(defined($a+1)))と変更する処理を走らせています。
以上が括弧の補間処理のしくみの一部ですが、いかがだったでしょうか？ Perl 5の構文解析の複雑性をかいま見ることができたのではないかと思います。
構文解析器の応用例
前述したように構文解析器は、LLVMコードを生成するための橋渡しになったり、静的解析に使えたりと、さまざまな使い道が存在します。本節では、Compiler::Lexer/Parserを利用しているプロジェクトやモジュールをいくつか紹介します。
LLVMコードを生成する
本項では、Compiler::Lexer/Parserを用いてLLVMIR（LLVM Intermediate Representation 、LLVM中間表現）を生成する方法と、LLVM IRを用いた応用例を紹介します。LLVM IRとは、一言で言えばLLVMのためのDSL（Domain Specific Language 、ドメイン特化言語）です。LLVMは、LLVM IRを入力として自身の仮想マシンで実行したり、ネイティブコードを出力したりすることができます。
まずはLLVM IRを生成してみます。これは筆者が開発しているCompiler::CodeGenerator::LLVMを併用すれば簡単に行えます。
use Compiler::Lexer;
use Compiler::Parser;
use Compiler::CodeGenerator::LLVM;
my $code = do { local $/; <DATA> };
my $tokens = Compiler::Lexer->new->tokenize($code);
my $ast = Compiler::Parser->new->parse($tokens);
my $generator = Compiler::CodeGenerator::LLVM->new();
# LLVM IR を文字列として受け取る
my $llvm_ir = $generator->generate($ast);
__DATA__
print "hello world\n";
Compiler::Parserで作成したAST を、Compiler::CodeGenerator::LLVMのgenerateメソッドに渡すだけです。generateメソッドの戻り値はLLVM IRの文字列になっているので、そのままファイルに書き出したり、メモリに載せたまま別な処理に用いることもできます。
以降ではLLVM IRを用いた応用例としてCompiler::Tools::TranspilerとPerlMotionを紹介します。この2つはPerlコードをLLVM IRに落とすことで得られるメリットを端的に表すために筆者が開発したモジュールです。
Compiler::Tools::Transpiler
Emscripten という、LLVM IRを入力としてJavaScriptコードを生成するプロジェクトが存在します。Compiler::Tools::Transpiler は、Compiler::CodeGenerator::LLVMで生成したLLVM IRをEmscriptenに渡すことで、Perl to JavaScriptを実現しようと試みたものです。Emscriptenはまだ開発中のプロジェクトでありCompilerシリーズも開発中であるため、正確にPerlからJavaScriptに変換できるコードはまだ限られていますが、そう遠くない未来にPerlコードがブラウザ上で動く時代がくるかもしれません。
PerlMotion
PerlMotionは、iOS上でRubyコードを動かす技術であるRubyMotionのテクノロジをPerlでも再現できないかと思い挑戦したプロジェクトです。RubyMotionは、RubyコードをLLVM IRに変換し、それをネイティブコードに落とすことで、実行パフォーマンスを犠牲にすることなくRubyでiOSアプリケーションを書けるようにしたすばらしいプロジェクトです。同様にPerlにおいても、Compiler::CodeGenerator::LLVMを用いてLLVM IRに変換したコード上からCocoaフレームワークを呼び出せるようにしたことで、iOSアプリケーションを作成できるようになりました。PerlMotionはまだまだ開発中のプロジェクトであり、読者のみなさんのコントリビュートを待っています！
静的解析技術として利用する
本項では、Compiler::Lexer/Parserを静的解析技術として用いた応用例を紹介します。
Compiler::Tools::CopyPasteDetector
このモジュールは、Perlコードのコピー&ペーストを正確かつ高速に検出するために開発されたモジュールです。Compiler::Lexerをソースコードの解析エンジンとして利用しており、コピー&ペースト検出のロジックをXSで記述していることや、ネイティブスレッドを用いた解析にも対応していることから、とても高速に動作します。また、高品質なビジュアライザがある点も特徴です（図1 ） 。
図1 コピー&ペースト検出結果の表示例Perl::MinimumVersion::Fast
このモジュールは、@tokuhiromさんによって書かれたPerl::MinimumVersionの高速版です。解析エンジンにCompiler::Lexerが使われており、PPIを利用して書かれたPerl::MinimumVersionよりも30 倍近く高速化されているとのことです。このことは、PPIで記述された既存のモジュールをCompiler::Lexer/Parserを用いて書き直すことで高速化できることを示しており、数多くあるPPIで実装された静的解析モジュールの高速化が期待できるすばらしい例と言えるでしょう。
Perl::Lint
前号の本連載で川上大喜さん（@moznion）が解説していたPerl::Lintにも、Compiler::Lexer/Parserが使われています。このプロジェクトも、Compilerシリーズを用いて高速に静的解析を行う良い例です。
まとめ
第28回では、Compiler::Lexer/Parserを開発した際に得られた知見をもとに、言語処理系の構文解析器を実装するにあたっての勘どころを説明しました。また、Perl 5処理系の構文解析器を実装することがどうして難しいのかについても、実例を交えながら解説しました。本稿を読んで言語処理系の開発に興味を持った方がいらっしゃれば幸いです。
Compiler::Lexer/Parserはまだ開発中のプロジェクトであり、読者のみなさんのコントリビュートを心待ちにしています。直接の開発でなくとも、動かないコード例をGitHubのissueに登録してくださるだけでも歓迎ですので、ぜひよろしくお願い致します！
さて、次回の執筆者は横江直輔さん（zentooo）で、テーマは「Perlプログラマのためのstrace入門」です。お楽しみに。
