Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

Perl6Advent Calendar 2012

Day 5
@x19290(Hiroki Horiuchi)

grammar 超入門

Last updated at Posted at 2012-12-26

Perl 6 の売りの一つが、パーサーが超簡単に書けることです。

再帰的な汎用テキスト構造としての S 式

再帰的な汎用テキスト構造というと最近では XML や JSON などが盛んに使われていますが、昔から S 式というものもあって、今でも Lisp 系の言語で多用されています。

ここでは、Perl 6 の grammar を用いた構文解析の対象として、S 式の極小のサブセットを定義します。二度手間になるのを避けるため、いきなり Perl 6 の grammer 形式で定義します。これを読めば grammar の構文(ただしこれがすべてではない)と、ここで言う S 式の構文が一度にわかるでしょう。

sex1.p6
#!/usr/bin/env perl6

use v6;

grammar Sex::Grammar {...}
my $sex = ' ( S . ( E . X ) ) ';

sub MAIN(Bool :$dump = False)
{
	Sex::Grammar.parse($sex);
	if $dump {
		$/.perl.say;
	} else {
		$/.say;
	}
}

grammar Sex::Grammar
{
	token TOP { ^ <sex> $ }
	token sex { <symbol> | <cons> }
	token symbol { \w+ }
	rule cons { '(' <car> '.' <cdr> ')' }
	token car { <sex> }
	token cdr { <sex> }
}
  • Sex は、S 式 == S-expression の略です。
  • 内側の {...} 内には、Perl 6 の正規表現を書きます。
    • TOP {...} は必須です。
    • Perl 6 では、<...> を用いて他の正規表現が参照できます。
    • token の代わりに rule を使うと、空白込みでマッチするようになりますが、rule TOP {...} としても上手く行かないようです。

<sex> の具体例を挙げようと思いましたが、既に 3 日に Cons とか Symbol の出力を行っているのでやめます。あの出力形式が、ここでいう <sex> とほぼ一致します。

grammar だけを用いた構文解析

マッチオブジェクトのプリティプリント

ここで定義した Sex::Grammar だけを使って、実はかなりのことができます。

$ ./sex1.p6
｢ ( S . ( E . X ) ) ｣
 sex => ｢ ( S . ( E . X ) ) ｣
  cons => ｢ ( S . ( E . X ) ) ｣
   car => ｢S｣
    sex => ｢S｣
     symbol => ｢S｣
   cdr => ｢( E . X ) ｣
    sex => ｢( E . X ) ｣
     cons => ｢( E . X ) ｣
      car => ｢E｣
       sex => ｢E｣
        symbol => ｢E｣
      cdr => ｢X｣
       sex => ｢X｣
        symbol => ｢X｣

$/ に保持されたマッチオブジェクトを .say するだけで、その概略がわかるしかけです(余談ですが ｢｣ は、Unicode 化された半角かぎ括弧です。Larry Wall の日本語趣味がうかがえます)。

しかしこのマッチオブジェクトの正味を .perl を使って表示すると大変なことになります。

$ ./sex1.p6 --dump
Match.new(orig => " ( S . ( E . X ) ) ", from => 0, to => 19, ast => Any, list => ().list, hash => EnumMap.new("sex", Match.new(orig => " ( S . ( E . X ) ) ", from => 0, to => 19, ast => Any, list => ().list, hash => EnumMap.new("cons", Match.new(orig => " ( S . ( E . X ) ) ", from => 0, to => 19, ast => Any, list => ().list, hash => EnumMap.new("car", Match.new(orig => " ( S . ( E . X ) ) ", from => 3, to => 4, ast => Any, list => ().list, hash => EnumMap.new("sex", Match.new(orig => " ( S . ( E . X ) ) ", from => 3, to => 4, ast => Any, list => ().list, hash => EnumMap.new("symbol", Match.new(orig => " ( S . ( E . X ) ) ", from => 3, to => 4, ast => Any, list => ().list, hash => EnumMap.new()), )), )), "cdr", Match.new(orig => " ( S . ( E . X ) ) ", from => 7, to => 17, ast => Any, list => ().list, hash => EnumMap.new("sex", Match.new(orig => " ( S . ( E . X ) ) ", from => 7, to => 17, ast => Any, list => ().list, hash => EnumMap.new("cons", Match.new(orig => " ( S . ( E . X ) ) ", from => 7, to => 17, ast => Any, list => ().list, hash => EnumMap.new("car", Match.new(orig => " ( S . ( E . X ) ) ", from => 9, to => 10, ast => Any, list => ().list, hash => EnumMap.new("sex", Match.new(orig => " ( S . ( E . X ) ) ", from => 9, to => 10, ast => Any, list => ().list, hash => EnumMap.new("symbol", Match.new(orig => " ( S . ( E . X ) ) ", from => 9, to => 10, ast => Any, list => ().list, hash => EnumMap.new()), )), )), "cdr", Match.new(orig => " ( S . ( E . X ) ) ", from => 13, to => 14, ast => Any, list => ().list, hash => EnumMap.new("sex", Match.new(orig => " ( S . ( E . X ) ) ", from => 13, to => 14, ast => Any, list => ().list, hash => EnumMap.new("symbol", Match.new(orig => " ( S . ( E . X ) ) ", from => 13, to => 14, ast => Any, list => ().list, hash => EnumMap.new()), )), )), )), )), )), )), )), ))

自前のプログラムで、マッチオブジェクトを直接プリントしてみる

マッチオブジェクトの構造は 4 日、汎用の関数でダンプしてみました。ここでは別のプログラムを書いて表示してみましょう。この際、もとのテキストで (、) だったのを «、» にしてみましょう。

sex2.p6
#!/usr/bin/env perl6

use v6;

grammar Sex::Grammar {...}
my $sex = ' ( S . ( E . X ) ) ';
Sex::Grammar.parse($sex);
sex :sex($/);
say '';

grammar Sex::Grammar
{
# sex1 と同じ
}

sub sex(:$sex!)
{
	my $sexex = $sex<sex>;
	sexex(:$sexex);
}

multi sub sexex(:$sexex! where $sexex.keys[0] eq 'symbol')
{
	print $sexex<symbol>;
}

multi sub sexex(:$sexex! where $sexex.keys[0] eq 'cons')
{
	my $sex = $sexex<cons>;
	print '«';
	sex :sex($sex<car>);
	print ' . ';
	sex :sex($sex<cdr>);
	print '»';
}

$ ./sex2.p6
«S . «E . X»»

アクション

grammar では、アクション (actions) と呼ばれるクラスを書いて .parse() の動作をカスタマイズすることができます。アクションは普通のクラスで、grammar に登場した正規表現と同じ名前のメソッドを書いておくと、パーサーがそこを通ったときにフックされます。試しにトレースを取ってみましょう。

sex3.p6
#!/usr/bin/env perl6

use v6;

grammar Sex::Grammar {...}
class Sex::Actions {...}
my $sex = ' ( S . ( E . X ) ) ';
my $actions = Sex::Actions;
Sex::Grammar.parse($sex, :$actions);

grammar Sex::Grammar
{
# sex1 と同じ
}

class Sex::Actions
{
	method TOP($junk) { &?ROUTINE.say; }
	method sex($junk) { &?ROUTINE.say; }
	method symbol($junk) { &?ROUTINE.say; }
	method cons($junk) { &?ROUTINE.say; }
	method car($junk) { &?ROUTINE.say; }
	method cdr($junk) { &?ROUTINE.say; }
}

$ ./sex3.p6
symbol
sex
car
symbol
sex
car
symbol
sex
cdr
cons
sex
cdr
cons
sex
TOP

これを見る限りフックメソッドは、一つの正規表現のパースが 終了 するタイミングで呼ばれているようです。

最初筆者は、これらのフックメソッドを使ってマッチオブジェクトの直接プリントができないかと考えたのですが、この順番だと無理ですね。<cons> のプリントは、まず ( をプリントして、<car> と <cdr> を再帰的にプリントして、) をプリントしなければなりませんが、フックメソッドは .car() が呼ばれ、.cdr() が呼ばれ、最後に .cons() が呼ばれるので、( のプリントが間に合いません。

アクションを使った定石的な構文解析

Lisp オブジェクト

S 式の内部表現は、しばしば Lisp オブジェクトと呼ばれます。ここでの極小 S 式に対応する Lisp オブジェクトをクラスで定義してみましょう……と言いたいところですが、これも 3 日に完成しています。

S 式を読んで Lisp オブジェクトを組み立てる

以下では、Actions の .symbol() や .cons() メソッドで Symbol や Cons を生成して、$mo.ast と差し替えています。この差し替えを行うのがマッチオブジェクトの .make() メソッドで、method make($ast) { $!ast = $ast; } くらいの意味です。全部 .make() すると $/.ast にトップレベルの Lisp オブジェクトが得られるはずです。

アクションのメソッドのパラメーター名は、習慣的に $/ としますが、このように任意の名前を付けることもできます。パラメーター名を $/ にしたときは特別に、$/.make($ast) が make $ast と書けたり、$/<key> の代わりに $<key> と書けたりします。

sex4.p6
#!/usr/bin/env perl6

use v6;
use Symbol;
use Cons;

grammar Sex::Grammar {...}
class Sex::Actions {...}
my $sex = ' ( S . ( E . X ) ) ';
my $actions = Sex::Actions;
Sex::Grammar.parse($sex, :$actions);
print $/.ast, "\n";

grammar Sex::Grammar
{
# sex1 と同じ
}

class Sex::Actions
{
	method TOP($mo) # match object.
	{
		$mo.make($mo<sex>.ast);
	}

	method sex($mo)
	{
		$mo.make($mo.values[0].ast);
	}

	method symbol($mo)
	{
		$mo.make(Symbol.new($mo.Str));
	}

	method cons($mo)
	{
		$mo.make(Cons.new($mo<car><sex>.ast, $mo<cdr><sex>.ast));
	}
}

$ perl6 -I../a.streams sex4.p6
(S . (E . X))

出力ロジックとデータ構造がセットで作れるので、sex2 の場合よりもプリント処理がきれいに書けていることがわかります。いやいや、プリント処理は既に 3 日の段階で完成していました。ここでは S 式をパースして Lisp オブジェクトを生成しただけです。

sex2 の方法だと、新しい型の式が追加されるたびに multi sub sexex() を書き加える必要があって、一つの中心的なソースファイルに対する変更が避けられません。今回の方法だと、型の追加 == クラスの追加であり、出力処理はそのクラスの .str-on()、.gist-on() を定義することで行えます。

2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?