Perl Hackers Hub

第28回 Perlの構文解析器の作り方と応用例(3)

この記事を読むのに必要な時間:およそ 4.5 分

(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+1print "hello",$a && $bが該当します。

項(Termは式を構成する要素です。たとえば$array[0]$hash{a}が該当します。

値(Valueは項を構成する要素です。たとえば0Bareword$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 …③

の正しい解釈は(!(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の構文解析の複雑性をかいま見ることができたのではないかと思います。

著者プロフィール

五嶋壮晃(ごしままさあき)

2012年株式会社ミクシィに入社後,開発者のための開発などを行うたんぽぽGに所属。

その後投資事業本部に移り,株式会社ノハナの開発サポートとして,アプリ開発やシステム開発などを幅広く担当している。

一方,趣味で高速なYet Another Perlであるgperlを開発しており,他にもPerl 5の字句解析器・構文解析器であるCompiler::Lexer/ParserやPerlでiOSアプリを書けるようにするPerlMotionなどのプロダクトを開発中。インフラからアプリ開発まで幅広くカバーできるエンジニアを目指し,精進の日々をおくっている。

Blog:http://goccy54.hatenablog.com/

コメント

コメントの記入