本連載では第一線のPerlハッカーが回替わりで執筆していきます。今回のハッカーはPerl　5の字句解析器・構文解析器であるCompiler::Lexer/Parserを開発した五嶋壮晃さんです。Compiler::Lexer/Parserの開発で得られた知見をもとに、Perl 5がなぜ「Onlyperl can parse Perl」と言われているのかという謎に迫ります。また、言語処理系の字句解析器・構文解析器を開発する際の勘どころについてPerl 5の例を交えながら触れ、最後にCompiler::Lexer/Parserの応用例を紹介します。

構文解析器の役割とPerlとの関係

本節では言語処理系の基本的な構成や構文解析器の役割について触れ、筆者が開発しているCompiler::Lexer/Parserと、Perlコードの静的解析用途で広く利用されているPPIとの違いについて簡単に解説します。また、次節以降でさらに詳しく解説しますが、Perl 5の構文解析器を作ることがなぜ難しいのかについても触れます。

言語処理系の内部構成

Perl 5の構文解析器について説明する前に、言語処理系がどのようなしくみで動いているかを簡単に説明します。言語処理系の内部構成は、大きくは次の5つに分けることができます。

①字句解析器（Lexer）

入力されたソースコードを意味のある最小単位（トークン）に分割する

②構文解析器（Parser）

字句解析器によって得られたトークン列をプログラムで処理しやすいデータ構造に変換する。一般にはAST（Abstract Syntax Tree、抽象構文木）と呼ばれる木構造に変換する

③コード生成器（Code Generator）

ASTをトラバースしながら、OSや仮想マシンで実行可能な形式のコードを生成する。処理するものがOSであれば機械語となり、仮想マシンなら言語処理系独自のデータ構造となる

④最適化器（Optimizer）

コード生成器によって得られたコードを最適化し、より高速に実行できるコードに変換する

⑤仮想マシン（Virtual Machine）

言語処理系によっては、独自に実装された仮想マシンを積んでいるものがある。最適化器を通して得られたコード（独自のデータ構造になっている）を処理するための仮想CPUである

解説によっては、字句解析器と構文解析器をまとめて構文解析器と呼ぶ場合もありますが、本稿では分けて説明します。

仮想マシンと言うとJavaが有名ですが、PerlやRuby、Pythonなども仮想マシンを積んでいます。近年ではLLVM（Low Level Virtual Machine、低水準仮想マシン）という仮想マシンをモジュール化したプロジェクトも存在します。LLVMが解釈できるコードを生成すれば、コードを実行するために必要な処理はLLVMに任せることができるため、比較的簡単に言語処理系を開発できるようになりました。

構文解析器の役割

前項で少し触れましたが、LLVMの登場により、言語処理系を開発する際にバックエンドに当たる部分の実装を行わなくてもよい時代になりました。加えて、LLVMは高度な最適化器を持っており、簡単な設定を記述するだけでとても高速に動作します。つまり、新規に言語処理系を開発する場合だけでなく、既存の言語処理系をLLVMに対応させることで、とても高速に動作する処理系へとグレードアップさせることができるようになります。事実、さまざまな言語処理系でLLVM対応プロジェクトが立ち上がっています。最近では、Dropboxが発表したPyston（LLVMベースのPython）が有名です。

使い慣れた言語が今よりもずっと高速に動作するというのは夢のある話ですが、実現させるためには言語処理系側がASTを容易に生成・操作するためのAPIを提供している必要があります。有用なAPIを提供するためにはモジュール化された構文解析器が必要となりますが、RubyやGoといった言語がAPIを提供している一方、Perlには実用的なAPIが存在していませんでした。

また、プログラムを書く際に頻繁に利用するシンタックスハイライトやコード補完といった機能は、静的解析処理と呼ばれる、ソースコードを実行せずに解析した結果を用いて実現されています。精度の高い静的解析を行うにはASTを用いる必要があるため、構文解析器の存在が重要となります。

Compiler::Lexer/Parserの開発

そこで筆者が開発したのが、Perl 5の字句解析を行うCompiler::Lexerと、構文解析を行うCompiler::Parserです。これらのモジュールを使えばPerl 5のASTを容易に生成・操作できるようになり、LLVMや独自に実装したバックエンドとつなぎこめるようになります。また、シンタックスハイライトやコード補完、メトリクス測定といった静的解析にも用いることができます。

Compiler::Lexer/ParserとPPIの違い

現在、静的解析を行う際にPerlではPPIが広く利用されていますが、Compiler::Lexer/Parserとは具体的にどう異なるのでしょうか。

Compiler::Lexer/Parserは、筆者が世界一高速に動作するYet Another Perlを目指して開発したgperlという処理系で使われている字句解析部分・構文解析部分をベースに開発しました。そのため、初めから静的解析で用いるために開発されたPPIとは目的が異なります。特に、Compiler::Parserの目的はコード生成可能なASTを生成・操作するためのAPIを提供することであり、静的解析は副産物にすぎません。

また、Compiler::Lexer/Parserはメンテナンス性を損なわない範囲で高速に動作することも目的としており、メインの処理はすべてC++で実装しています。Perl本体よりも高速に動作することを目指して開発しているため、Pure Perlで開発されたPPIとは実行速度が大きく異なります。

try/catch構文を解析対象にした場合のPPIとCompiler::Parserの違い

上述した両者の違いを具体的に説明するために、次のようなコードをPPI、Compiler::Parserそれぞれに入力します[1]⁠。

use Try::Tiny;
my $result = try {
    my $response = do_something;
    return $response;
} catch {
    warn 'throw exception';
};

use PPI;
use PPI::Dumper;
my $document = PPI::Document->new(\$source_code);
PPI::Dumper->new($document)->print;

use Compiler::Lexer;
use Compiler::Parser;
use Compiler::Parser::AST::Renderer;
my $lexer = Compiler::Lexer->new;
my $tokens = $lexer->tokenize($source_code);
my $ast = Compiler::Parser->new->parse($tokens);
Compiler::Parser::AST::Renderer->new->render($ast);

try/catch構文は、正しく解釈するならばtry(sub {},catch(sub {}))となりますが、PPIではtryはBareword[2]と解釈され、あとに続くblock構文もtry関数の引数として処理されません。これは静的解析器としては正しい挙動（Try::Tinyの中身を読まないため、tryが関数なのかわからない）ですが、正確な解析結果がほしい場合には好ましくありません。

一方Compiler::Parserでは、tryは関数と認識され、そのあとのblock構文とcatch{}が引数として処理されます。この違いは、Compiler::Parserが出力しようとする結果が、コード生成可能なASTであるために生じています。執筆時点（2014年7月）でのCompiler::Parserのバージョン（0.0.9）では再帰的なモジュール探索をサポートしていないため、PPI同様Try::Tinyのソースは読みません。ですが、コード生成可能なASTを生成するために、Bareword+block構文の場合は、プロトタイプ定義で(&;@)と定義された関数と判断して解析します。

このように、PPIでは解析結果を保留にする場合でも、Compiler::Parserでは結果を得ることができます。しかし、実際にはプロトタイプ定義を読まなければ解析できない処理も存在するため、すべての場合で正確な結果を得ることはできません。そのため次期バージョンでは、再帰的にモジュールを読み込むオプションを設け、解析精度を高めようと考えています。

なぜPerl 5の構文解析器は作ることが難しいのか

Perl 5の構文解析はなぜ難しいのでしょうか。

よく言われるのは、BEGINブロックなどを用いることで、コンパイルフェーズにもかかわらず振る舞いを変更できるという点です。このため、コンパイルフェーズに関数の再定義などが可能となり、その定義によっては構文解析の解釈自体を変更できます。このことは、究極的には実行系が存在しないと正しい構文解析が行えないことを意味し、静的解析が不可能なことを示しています。ただし、実際にはメンテナンス性が大きく低下する原因になるため、コンパイルフェーズにおける振る舞いの変更によって構文解析結果を変更するアプリケーションは筆者の知るかぎりありません。

ほかにもPerl 5の構文解析を困難にしている要因があります。多数の省略記法を許容し、プロトタイプ定義によって関数の引数の解釈を変更できる点などです。代表的な省略記法には次のようなものがあります。

• リファレンスをつなげてアクセスする際の「->」の省略
• ブロック中の最後の文における「;」の省略
• 名前付き単項演算子やプロトタイプ定義のある関数の括弧の省略

これらはいずれも処理系開発者の負担を重くする原因となっています。特に括弧の省略記法は構文解析ミスを起こしやすく、対応には注意が必要です。詳しくは「括弧を補完する」で後述します。

また、プロトタイプ定義によって関数の引数の解釈を変更できるというのは、言い換えれば、プロトタイプ定義を参照しなければ構文解析すらまともに行えないことを意味します。場合によっては、字句解析すら行えないこともあります。これについては次節で詳しく解説します。

ほかにも、正規表現のデリミタの種類が多過ぎることや、ヒアドキュメントの処理なども字句解析器・構文解析器開発の障害となり得るでしょう。

次節からは、実際に字句解析器・構文解析器を開発する際に必要となる知識や考え方について解説していきます。

＜続きの（2）はこちら。＞