スキップしてメイン コンテンツに移動

Perl 5 to 6 - (似非)XMLのグラマー

ラベル:

これはMoritz Lenz氏のWebサイトPerlgeek.deで公開されているブログ記事"Perl 5 to 6" Lesson 20 - A grammer for (pseudo) XMLの日本語訳です。

原文はCreative Commons Attribution 3.0 Germanyに基づいて公開されています。

本エントリにはCreative Commons Attribution 3.0 Unportedを適用します。

Original text: Copyright© 2008-2010 Moritz Lenz

Japanese translation: Copyright© 2011 SATOH Koichi

注記: XMLに関する用語の誤用(「整形式」と「妥当」を混同しているなど)がありますが、あくまで例なので原文通りに残しています。

NAME

"Perl 5 to 6" Lesson 20 - (似非)XMLのグラマー

SYNOPSIS

grammar XML {
    token TOP   { ^ <xml> $ };
    token xml   { <text> [ <tag> <text> ]* };
    token text {  <-[<>&]>* };
    rule tag   {
        '<'(\w+) <attributes>*
        [
            | '/>'                 # 空タグ
            | '>'<xml>'</' $0 '>'  # 開始タグと終了タグ
        ]
    };
    token attributes { \w+ '="' <-["<>]>* '"' };
};

DESCRIPTION

これまでの連載記事の焦点はPerl6言語であり、実装状況は気にしていませんでした。 これが空想上の言語でないことを示すため、またグラマーの能力を証明するために、このレッスンでは基本的なXMLを解析する、Rakudoで実行できるグラマーの開発をお見せします。

Rakudoの入手とビルドはhttp://rakudo.org/how-to-get-rakudoの指示にしたがって自分で行って下さい。

XMLの概念

私たちの用途の範囲ではXMLは非常に単純です: プレーンテキストと入れ子になったタグから成り、タグは属性を持つことがあります。 妥当なXMLであると(あるいはそうでないと)解析させたいテストケースをちょっとだけ用意しました:

my @tests = (
    [1, 'abc'                       ],      # 1
    [1, '<a></a>'                   ],      # 2
    [1, '..<ab>foo</ab>dd'          ],      # 3
    [1, '<a><b>c</b></a>'           ],      # 4
    [1, '<a href="foo"><b>c</b></a>'],      # 5
    [1, '<a empty="" ><b>c</b></a>' ],      # 6
    [1, '<a><b>c</b><c></c></a>'    ],      # 7
    [0, '<'                         ],      # 8
    [0, '<a>b</b>'                  ],      # 9
    [0, '<a>b</a'                   ],      # 10
    [0, '<a>b</a href="">'          ],      # 11
    [1, '<a/>'                      ],      # 12
    [1, '<a />'                     ],      # 13
);

my $count = 1;
for @tests -> $t {
    my $s = $t[1];
    my $M = XML.parse($s);
    if !($M  xor $t[0]) {
        say "ok $count - '$s'";
    } else {
        say "not ok $count - '$s'";
    }
    $count++;
}

これは「良い」XMLと「悪い」XMLのリスト、そしてXML.parse($string)を呼び出してテストを走らせる小さなスクリプトです。 言語全体にマッチするルールはTOPという名前にする約束になっています。

(テスト1で分かるように単一のルートタグを必須にしていませんが、この制限を追加するのは些細なことです)

グラマーの開発

XMLのキモは当然タグの入れ子構造ですから、まず2番目のテストに着目することにしましょう。 テストスクリプトの先頭に以下のコードを置いて下さい:

grammar XML {
    token TOP   { ^ <tag> $ }
    token tag   {
        '<' (\w+) '>'
        '</' $0   '>'
    }
};

それからスクリプトを実行します:

$ ./perl6 xml-01.pl
not ok 1 - 'abc'
ok 2 - '<a></a>'
not ok 3 - '..<ab>foo</ab>dd'
not ok 4 - '<a><b>c</b></a>'
not ok 5 - '<a href="foo"><b>c</b></a>'
not ok 6 - '<a empty="" ><b>c</b></a>'
not ok 7 - '<a><b>c</b><c></c></a>'
ok 8 - '<'
ok 9 - '<a>b</b>'
ok 10 - '<a>b</a'
ok 11 - '<a>b</a href="">'
not ok 12 - '<a/>'
not ok 13 - '<a />'

つまりこれは一対の開始タグと終了タグのペアを解析する単純なルールであり、妥当でない4つのXMLをきちんと排除できています。

1番目のテストも同様に簡単に通るように、次のコードを試して下さい:

grammar XML {
    token TOP   { ^ <xml> $ };
    token xml   { <text> | <tag> };
    token text  { <-[<>&]>*  };
    token tag   {
        '<' (\w+) '>'
        '</' $0   '>'
    }
};

(<-[...]>は否定形の文字クラスだったことを思い出して下さい)

それから実行します:

$ ./perl6 xml-03.pl
ok 1 - 'abc'
not ok 2 - '<a></a>'
(残りはさっきと同じ)

どうして2番目のテストは動かなくなったのでしょう? その理由はRakudoが最長トークンマッチをまだ実装しておらず、順番にマッチングを行っているからです。 <text>は空文字列に(つまりいつでも)マッチするので、<text> | <tag>は<tag>とのマッチングを試しません。選択肢の順番を入れ替えると動きます。

しかし我々はプレーンテキストかタグだけを適当にマッチさせたいのではなく、両者のランダムな組合わせをマッチさせたいのでした:

token xml   { <text> [ <tag> <text> ]*  };

([...]はキャプチャしないグループであり、Perl5の(?: ...)と同様です)

いやはや驚くことに、これは最初の2つのテストを両方とも通過します。

3番目のテスト.<ab>foo</ab>ddは開始タグと終了タグの間にテキストがあるので、次はこれを受理しなければいけません。 しかしタグの間に出現できるのはテキストに限らず任意のXMLで在り得るので、<xml>を単に呼ぶことにしましょう:

token tag   {
    '<' (\w+) '>'
    <xml>
    '</' $0   '>'
}

./perl6 xml-05.pl
ok 1 - 'abc'
ok 2 - '<a></a>'
ok 3 - '..<ab>foo</ab>dd'
ok 4 - '<a><b>c</b></a>'
not ok 5 - '<a href="foo"><b>c</b></a>'
(残りはさっきと同じ)

これで属性(href="foo"のやつ)に集中することができます:

token tag   {
    '<' (\w+) <attribute>* '>'
    <xml>
    '</' $0   '>'
};
token attribute {
    \w+ '="' <-["<>]>* \"
};

しかしこれでは新しいテストを通過できるようにはなりません。その原因はタグ名と属性の間にある空白です。 \s+や\s*を色んな場所に加える代わりに、tokenをrule(:sigspace修飾子を暗黙的にセットします)に切り替えることにします:

rule tag   {
    '<'(\w+) <attribute>* '>'
    <xml>
    '</'$0'>'
};
token attribute {
    \w+ '="' <-["<>]>* \"
};

これで残るテストは最後の2つになりました:

ok 1 - 'abc'
ok 2 - '<a></a>'
ok 3 - '..<ab>foo</ab>dd'
ok 4 - '<a><b>c</b></a>'
ok 5 - '<a href="foo"><b>c</b></a>'
ok 6 - '<a empty="" ><b>c</b></a>'
ok 7 - '<a><b>c</b><c></c></a>'
ok 8 - '<'
ok 9 - '<a>b</b>'
ok 10 - '<a>b</a'
ok 11 - '<a>b</a href="">'
not ok 12 - '<a/>'
not ok 13 - '<a />'

これらは/で閉じられた入れ子になっていないタグを含んでいます。rule tagにこれを追加するのは何の問題もありません:

rule tag   {
    '<'(\w+) <attribute>* [
        | '/>'
        | '>' <xml> '</'$0'>'
    ]
};

全テストが通るようになりました。やった、はじめて作ったグラマーはちゃんと動きます。

さらなるハッキング

グラマーで遊ぶのは遊び方を読むよりずっと楽しいので、これから実装できるものの例を挙げておきます:

  • &amp;のような実体参照を含むことができるプレーンテキスト
  • XMLタグ名が数字で開始して良いのかどうか分かりませんが、現在のグラマーはこれを許しています。必要ならXMLの仕様書を調べてグラマーを改造するのも良いでしょう
  • <![CDATA[ ... ]]>を含むことができるプレーンテキスト。このXML風タグは無視され、<のような文字はエスケープする必要がありません
  • <?xml version="0.9" encoding="utf-8"?>のようなXML宣言を許容し、すべてを包含する単一のルートタグを要求する本物のXML(テストケースをいくつか修正する必要があります)
  • マッチオブジェクト$/を再帰的に走査することでXML用のプリティプリンタを実装できます(これは生半可にはいきません; いくつかRakudoのバグを回避しなければいけないかも知れませんし、キャプチャも新しく導入する必要があるかも知れません)

(解答をこのブログのコメント欄に書かないで下さい; 他の人にも楽しませてあげましょう;-)

ハッキングを楽しんで下さい。

MOTIVATION

強力だし、楽しい

SEE ALSO

正規表現はS05で詳細に規定されています: http://perlcabal.org/syn/S05.html

正規表現とグラマーの動作している(!)例を、Perl6で書かれたWikiエンジンであるNovember projectでもっと見つけることができます。http://github.com/viklund/november/をご覧下さい。

コメント

コメントを投稿

このブログの人気の投稿

Perl 5 to 6 - コンテキスト

2011-02-27: コメント欄で既に改訂された仕様の指摘がありました ので一部補足しました。 id:uasi に感謝します。 これはMoritz Lenz氏のWebサイト Perlgeek.de で公開されているブログ記事 "Perl 5 to 6" Lesson 06 - Contexts の日本語訳です。 原文は Creative Commons Attribution 3.0 Germany に基づいて公開されています。 本エントリには Creative Commons Attribution 3.0 Unported を適用します。 Original text: Copyright© 2008-2010 Moritz Lenz Japanese translation: Copyright© 2011 SATOH Koichi NAME "Perl 5 to 6" Lesson 06 - コンテキスト SYNOPSIS my @a = <a b c> my $x = @a; say $x[2]; # c say (~2).WHAT # Str() say +@a; # 3 if @a < 10 { say "short array"; } DESCRIPTION 次のように書いたとき、 $x = @a Perl5では $x は @a より少ない情報—— @a の要素数だけ——しか持ちません。 すべての情報を保存しておくためには明示的にリファレンスを取る必要があります: $x = \@a Perl6ではこれらは反対になります: デフォルトでは何も失うことなく、スカラ変数は配列を単に格納します。 これは一般要素コンテキスト(Perl5で scalar と呼ばれていたもの)及びより特化された数値、整数、文字列コンテキストの導入によって可能となりました。無効コンテキストとリストコンテキストは変更されていません。 特別な構文でコンテキストを強制できます。 構文 コンテキスト ~stuff 文字列 ?stuff 真理値 +stuff ...
2 件のコメント
続きを読む

Perl 5 to 6 - サブルーチンとシグネチャ

これはMoritz Lenz氏のWebサイト Perlgeek.de で公開されているブログ記事 "Perl 5 to 6" Lesson 04 - Subroutines and Signatures の日本語訳です。 原文は Creative Commons Attribution 3.0 Germany に基づいて公開されています。 本エントリには Creative Commons Attribution 3.0 Unported を適用します。 Original text: Copyright© 2008-2010 Moritz Lenz Japanese translation: Copyright© 2011 SATOH Koichi NAME "Perl 5 to 6" Lesson 04 - サブルーチンとシグネチャ SYNOPSIS # シグネチャなしのサブルーチン——Perl5風 sub print_arguments { say "Arguments:"; for @_ { say "\t$_"; } } # 固定引数の型指定付きシグネチャ sub distance(Int $x1, Int $y1, Int $x2, Int $y2) { return sqrt ($x2-$x1)**2 + ($y2-$y1)**2; } say distance(3, 5, 0, 1); # デフォルト引数 sub logarithm($num, $base = 2.7183) { return log($num) / log($base) } say logarithm(4); # 第2引数はデフォルトを利用 say logarithm(4, 2); # 明示的な第2引数 # 名前付き引数 sub doit(:$when, :$what) { say "doing $what at $when"; } doit(what => 'stuff', when => 'once'); # ...
コメントを投稿
続きを読む

Project Euler - Problem 27

問題 しばらく止まってましたが今日から再開。 原文 Considering quadratics of the form: n 2 + an + b, where |a| < 1000 and |b| < 1000 Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0. 日本語訳 |a| < 1000, |b| < 1000 として以下の二次式を考える (ここで|a|は絶対値): n 2 + an + b n=0から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数a, bの積を答えよ. 解答 最大探索範囲は-999 <= a <= 999、-999 <= b <= 999なので、およそ4,000,000通りの係数の組合せを試すことになります。組合せ毎に数列を生成して、それが素数か判定するわけですからたまりません。簡単な検討を加えて範囲を絞りましょう。 与えられた二次式をf(n)とおくと、f(0) = b、f(1) = a + b + 1です。 f(n)が長さ2以上の素数列を生成するならこれらは素数ですから、次のことがいえます： bは素数である a + b + 1は素数である b = 2のとき、aは偶数である それ以外のとき、aは奇数である 素数判定関数 is_prime には同じ引数が与えられることがよくあるのでメモ化しています。 #!/usr/bin/perl use strict; use warnings; use feature qw/say/; sub prime_seq_len($$) { my ($coeff_a, $coeff_b) = @_; my $len = 0; my $n = 0; $len++, $n++ while is_prime($n * ($n + $coeff_a) ...
2 件のコメント
続きを読む

Perl 5 to 6 - ツイジル

これはMoritz Lenz氏のWebサイト Perlgeek.de で公開されているブログ記事 "Perl 5 to 6" Lesson 15 - Twigils の日本語訳です。 原文は Creative Commons Attribution 3.0 Germany に基づいて公開されています。 本エントリには Creative Commons Attribution 3.0 Unported を適用します。 Original text: Copyright© 2008-2010 Moritz Lenz Japanese translation: Copyright© 2011 SATOH Koichi NAME "Perl 5 to 6" Lesson 15 - ツイジル SYNOPSIS class Foo { has $.bar; has $!baz; } my @stuff = sort { $^b[1] <=> $^a[1]}, [1, 2], [0, 3], [4, 8]; my $block = { say "This is the named 'foo' parameter: $:foo" }; $block(:foo<bar>); say "This is file $?FILE on line $?LINE" say "A CGI script" if %*ENV.exists('DOCUMENT_ROOT'); DESCRIPTION いくつかの変数にはツイジルという第2のシジルがあります。これは基本的にはその変数が「普通」ではないということです。違いはいくつかあり、例えばスコープの違いなどです。 オブジェクトのパブリックな属性とプライベートな属性がそれぞれ . と ! というツイジルを持つことは既に紹介しました; それらは通常の変数ではなく self に結びつけられています。 ツイジル ^ はPerl5で例外的に扱われていたケースを一般化します。次のように書けます # 注意: Perl5のコードです sort ...
コメントを投稿
続きを読む

Project Euler - Problem 18

問題 原文 Find the maximum total from top to bottom of the triangle 日本語訳 三角形を頂点から下まで移動するとき、その最大の合計値を求めよ。 解答 動的計画法 を使ってボトムアップで簡単に解くことができる問題です。 簡単のため、小さい三角形で考えることにします： 0: j 1: h i 2: e f g 3: a b c d 2行目の各点を頂点として、2行の小さい三角形が作れることが分かります。 上の例で言えば、(e, a, b)と(f, b, c)、(g, c, d)の3つです。 (e, a, b)の頂点eから末端（a、b、c、dのいずれか）に移動したとき、その数値の合計は最大でe + max(a, b)となります（maxは最大値を選ぶ関数）。同様に他の2つもf + max(b, c)、g + max(c, d)と表せます。 これらをE、F、Gとおくことにして、例を次のように書き換えます： 0: j 1: h i 2: E F G (h, E, F)からなる三角形の最大値はH = h + max(E, F)、(i, F, G)からなる三角形のそれはI = i + max(F, G)です。 Eは「頂点eから末端に至る経路の最大値」で、FやGも同様ですから、HとIは「頂点h（やi）から末端に至る経路の最大値」となります。 これを先ほどと同様に置き換えて： 0: j 1: H I 頂点jから末端に至る経路の最大値はJ = j + max(H, I)となり、これが解です。 #!/usr/bin/perl use strict; use warnings; use feature qw/say/; use List::Util qw/max/; my @rows = map { [ split /\s+/ ] } <DATA>; until (@rows == 1) { my $curr_row = $rows[-2]; my $bigger_branch; for (my $i = 0; $i < @$curr_row; $i++) { $bigger_branch = ma...
3 件のコメント
続きを読む