Perlモジュールによる構文解析

適切なツールは作業を単純化し、文法の機能を拡張します

Perl の主要目標の 1 つはテキストの構文解析です。このチュートリアルでは、テキストの構文解析に使用する CPAN モジュールについて説明し、これらのモジュールをユーザー・プログラムで簡単に使用する方法を示します。適切なツールを使えば、コード・コメントの分析、既存の lex 文法の適用、その他多くの作業が簡単に行えるようになります。Teodor は、実際の業務上のプログラミングに目を向けながら、それぞれの作業について例を示してくれます。

Teodor Zlatanov (tzz@iglou.com)Gold Software Systems

Teodor Zlatanovは1999年にボストン大学を卒業し、コンピューター・エンジニアリングで学位を取得しています。1992年以来プログラマーとして働いており、Perl、Java、C、C++などの言語を使用してきています。関心を持っている領域としてはオープン・ソース作業、Perl、テキスト構文解析、3層のクライアント/サーバー・データベース・アーキテクチャー、Unixのシステム管理などです。助言や間違いの指摘を歓迎しています。連絡先はtzz@bu.eduです。



2000年 4月 01日

Perl は、テキスト分析を行うための優れた言語です。組み込み演算子が、テキストの検索、置き換え、パターン・マッチングなどの作業を簡単にしてくれます。Perl を学んだプログラマーは、よく独自のルーチンを作ってテキストやデータの構文解析を行います。好都合なことに、CPAN (Comprehensive Perl Archive Network の略。「参考文献」を参照) には大量のモジュールが集積記録されており、そのうちのいくつかは、ユーザーをテキスト分析やデータ分析という問題から解放してくれます。

Perl のモジュールによる構文解析、字句解析、および分析

Damian Conway の開発になる Parse::RecDescent は、テキストの字句解析と構文解析を行うための強力なツールです。Kim Ryan の開発になる Lingua::EN::Fathom は、ファイルやテキスト・ブロックを分析し、その入力についていろいろな統計を作成することができます。これらのツールについては、「参考文献」を参照してください。

Parse::RecDescent の弱点は、拡張性のある文法規則を使用し、詳細な字句解析や構文解析を行うため、スピードが多少遅いことです。このモジュールの使い方が悪いと、パフォーマンスが低下します。Parse::RecDescent の長所は、字句解析と構文解析に優れていることです。次のセクションでは、Parse::RecDescent の文法に移植された lex 文法について説明します。lex は、常に、自分の仕事を他のどのツールよりも立派にこなします。chef.pl スクリプト (「参考文献」を参照) は、chef.l lex 文法を使用するコンパイル済みの C プログラムよりもスピードは遅いですが、はるかに多くの処理を行うことができます。ツールについての正しい知識を持ち、自分のジョブに適合したツールを使用するようにしてください。


既存の lex 文法の適応

John Hagerman の開発になる Swedish Chef lex 文法は、単純なテキスト・フィルターの好例です。これも非常に面白い製品であり、最終試験の前夜など、コンピューター・サイエンスやコンピューター・エンジニアリング科の多くの学生たちを楽しませています。Parse::RecDescent モジュールを使って chef.l 文法を Perl に移植する例を示します (ただし、このモジュールは、このタスクにとって理想的な選択ではありません。Parse::Lex モジュールのほうがより適合しています)。このセクションは、Parse::RecDescent 構文作成の規則を紹介することを目的としており、状態の記憶、プロダクションのリジェクト、テキストの字句解析といったアクションを示すことにします。chef.pl スクリプトを自分で試してみるのを忘れないでください。病みつきになるかもしれません。

chef.pl スクリプトは、chef.l lex 文法をほとんどそのままコピーしたものです。始動時には、$niw 変数が 0 に設定されています。これは、多くの規則がそれを調べて、受け入れられるかリジェクトされるかを確認するからです。 $niw は「ワードに含まれていない(not in word)」ことを表し、構文解析プログラムがワードに含まれている場合は、1 に設定されています。Parse::RecDescent に対するディレクティブは、自己の中で指定されている変数が非ゼロであると、規則をリジェクトします。したがって、$niw = 0 は、ユーザーがワードに含まれていないことを意味する点に留意してください。

スキップ変数が'' (空ストリング) に設定されているため、スペースを含め、すべての入力データはトークン・ディレクティブに入ります。また、chef 規則も\z で終わっており、これはストリングの終わりです。通常は\Z が使用されますが、これは Perl での改行とも一致することがあり、また入力データに含まれることもあります。

chef 規則: 文法は chef 規則で始まります。chef 規則は、ストリングの\z 終わりまで、多くのトークンと突き合わせられます。chef 規則のこれらの 2 つのエレメントは "プロダクション" と呼ばれます。すべての規則は、プロダクションで構成されていなければなりません。アクションをプロダクションの一部にすることができます。それは中括弧 {} でマークされ、Perl コードを含んでいます。これはどれとも一致しません。単に実行されるだけです。

トークン規則: トークン規則は、多少独断的ではありますが、chef.l 文法と突き合わせるように指定した任意の数値または数値列と突き合わせることができます。文法の対応を明確にするために、いくつかの例をあげて説明しましょう。

ワード/非ワード文字の基本的な文法定義は、以下のとおりです。
chef.pl: WC: /[A-Za-z']/
chef.pl: NW: /[^A-Za-z']/ 
chef.l:  WC  [A-Za-z']
chef.l:  NW  [^A-Za-z']

an 規則: 最も単純な規則は何にも依存しません。an 規則は、そのよい例です。つまり、'an' に出会うと、必ず'un' を印刷します。また、この規則は、$niw を 1 に設定します (これは、ユーザーがワードの中に含まれていることを示します)。

chef.pl: an: /an/ { $niw = 1; print 'un' }	
chef.l:  "an"		{ BEGIN INW; printf("un"); }

ax 規則: 次のより複雑な規則は ax 規則です。つまり、'a' が出てきて、その後にワード文字WC が続いていると、'e' を印刷します。...WC プロダクション構文は、a の後にワード文字が続いていなければならないことを意味していますが、突き合わせには消費されません。したがって、'aan' は、an および ax 規則で'eun' を作成します。この規則は、$niw を 1 (ワード内に含まれる) に設定します。

chef.pl: ax: /a/ ...WC { $niw = 1; print "e" } 
chef.l:  "a"/{WC}	{ BEGIN INW; printf("e"); }

en 規則: en 規則は、ax 規則とまったく同じように機能しますが、NW (非ワード) プロダクションが後に続くことが想定されています。つまり、'en' がワードの終わりになければなりません。

chef.pl: en: /en/ ...NW { $niw = 1; print "ee" }
chef.l:  "en"/{NW}	{ BEGIN INW; printf("ee"); }

ew 規則: ew 規則は、ユーザーがワード内にいるときにのみ正しく機能します。$niw が 0 の場合にユーザーがそれをリジェクトするのはそのためです。

chef.pl: ew:  /ew/ { $niw = 1; print "oo" }
chef.l:  "ew"	{ BEGIN INW; printf("oo"); }

i 規則: i 規則は、ユーザーがワード内に含まれていて、別のi がまだ存在していない場合にのみ正しく機能します。この規則は$i_seen を 1 に増やし、非ワード文字または改行が見える場合にのみ、$i_seen が 0 に戻されます。

chef.pl: i:   /i/ { $niw=1;$i_seen=1; print "ee" }
chef.l:  "i"	{ BEGIN INW; printf(i_seen++ ? "i" : "ee"); }

文の終わり規則: 任意の数の文の終わりマーカー[.!?] が、その後にスペースが付いて印刷され、その後にあの有名な (あるいは悪名高い、どちらでも好きなほうを取ってください) "Bork Bork Bork!" メッセージが続きます。実際の振る舞いは、オリジナルの chef フィルターから多少逸脱していますが、それは、わたしにはそのほうが好都合だからです (Bork メッセージは、いくらもらっても十分ということはありません)。$item[1] 構文は、スペースの突き合わせを行わないことを意味しています。なぜならば、スペースは Parse::RecDescent には$item[2] として認識されるからです。

chef.pl: end_of_sentence: /[.?!]+/ /\s+/
         { $niw = 0; $i_seen = 0;
           print $item[1] . "\nBork Bork Bork!\n" }
chef.l:  [.!?]$
         { BEGIN NIW;
           i_seen = 0;
           printf("%c\nBork Bork Bork!",
           yytext[0]);
         }

文法の動的な拡張

extend-grammar.pl スクリプトは、Parse::RecDescent モジュールと一緒に提供される demo_selfmod.pl スクリプトから展開されたもので、拡張可能な文法を提示します。初めの段階では、文法は 1 つの固有名 Ted だけで構成されています (余談ですが、これはすばらしい名前です)。名前規則は、1 ワード文字から n ワード文字まで突き合わせます (Perl の\w syntax によって異なります)。do_you_know 規則は、任意の数のスペースで分離されたワード "do you know" を、大文字小文字の任意の組み合わせで突き合わせます。このため Perl i 突き合わせ修飾子が役に立ち、簡単な概念を簡単に表現することができます。

proper_name: /Ted/
  name: /\w+/
  do_you_know: /do/i /you/i /know/i

拡張文法プロセス規則: このプロセス規則は、照会または定義で構成することができます。このいずれかが見つからなければ、この規則はメッセージをメイン・ループに入れます。

process: query | definition
... and later ...
while (<>)
{
 $parse->process($_)
   or print "Enter a query (do you know ...)"
            "or a definition (... exists)\n";
}

拡張文法照会規則: この照会規則はdo_you_know プロダクションからなり、その後に名前または固有名が続いています。名前の場合のアクションは、それが未認識であるというメッセージの印刷です。固有名 (proper_name 規則で定義されたもの) の場合のアクションは、それが既知であるというメッセージの印刷です。同じ名前の 2 つの規則は、2 つの代替プロダクションを持つ 1 つの規則と同等です。したがって、以下の定義は、

 query: do_you_know proper_name
           { print "I know " .
                   $item{proper_name} .
                   ",sure!\n"
           }
 query: do_you_know name
           { print $item{name} .
                   " does not exist in my little world",
                   ", sorry.\n"
           }

以下の定義と同等です。

 query: do_you_know proper_name
           { print "I know " .
                   $item{proper_name} .
                   ",sure!\n"
           }
        | do_you_know name
           { print $item{name} .
                   " does not exist in my little world",
                   ", sorry.\n"
           }

拡張文法定義規則: この拡張可能文法の真髄は定義規則です。名前の後に'存在する' が続いていれば、アクションは、proper_name の新規規則で構文解析プログラムを拡張します。文法を実行しながら、文法そのものを変更することができます。

definition: name /exists/i
         {
            $thisparser->Extend("proper_name: '$item{name}'");
            print "\"$item{name}\" is now a valid proper name\n";
         }

$thisparser は、文法アクションを実行する構文解析プログラムを示します。Extend に加え、Replace メソッドを使用して(たとえば、C の#ifdef ステートメントを考えてください) 規則の内容を変更することができます。

extend-grammar.pl でプレイするには (「参考文献」の全リストを参照)、単にそれを実行し、"do you know" または "exists" を入力してください。このほかのものは構文解析プログラムのプロセス規則によって突き合わせられないため、リジェクトされます。proper_name 規則は、既知の固有名 'Ted' で始まります。


読みやすくするための C/C++ ソース・コード・コメントの分析

stat-comments.pl スクリプト (「参考文献」のリストを参照) は、demo_decomment.pl スクリプトの文法を使用して、コメントを抽出するための C/C++ コードを構文解析します。demo_decomment.pl スクリプトは Parse::RecDescent モジュールと一緒に提供されます。

さらに、stat-comments.pl スクリプトは Lingua::EN::Fathom モジュールを使用して、Parse::RecDescent 文法によって構文解析されたコメントも分析します。

まず、stat-comments.pl は文法を作成します (スクリプトの終わりに配置された BEGIN ブロックの$Grammar 変数の中に)。この文法のプログラム規則は、その内部でテキストとして使用できるコード、コメント、およびストリングを持つハッシュ参照を戻します。残りの文法については、Parse::RecDescent のマニュアルを参照してください。(C 構文解析文法も、Java プログラムのソース・コードを処理します。)

次に、stat-comments.pl は、テキスト入力または、スクリプトの終わりに提供されているサンプル・データのいずれかを読み込み、コメントが入手されたかどうかをチェックします。$/undef に設定すると、すべての入力データが 1 度に$text に読み込まれ、改行が組み込まれます。

入力ループ、およびコメントが $/ の下にあるかどうかの検査;
my $text = @ARGV ? <> : ;
my $parts = $parser->program($text) or die "malformed C program";
# only work with comments of length > 0
die "No comments found in input" unless length $parts->{comments};

次に、stat-comments.pl はコメント・マークをピリオドに変換しますので、コメントはピリオドで分離されます。これは見やすくするためのものであり、最終統計にはあまり影響を与えません。最後に、Lingua::EN::Fathom オブジェクトが作成され、循環テキスト・ブロック (Text::Wrap を参照)が分析のためにそれに渡されます。このレポートは、次に、印刷されます。

stat-comments.pl の結論:
$parts->{comments} =~ s#//#. #g;
$parts->{comments} =~ s#/\*#. #g;
$parts->{comments} =~ s#\*/#. #g;
# we can now evaluate the comments (stored in $parts->{comments})
my $fathom = new Lingua::EN::Fathom; 
$fathom->analyse_block(wrap('', '', $parts->{comments}));
# voila, the readability report!
print($fathom->report);

stat-comments.pl スクリプトのポテンシャル・アプリケーションは、コードの品質管理です。きちんと文書化されたされたプログラムは保守が容易であるということは周知の事実であり、多くの企業がこうありたいと強く望んでいます。stat-comments.pl スクリプトは、良いコメントと悪いコメントを区別しません。しかしこのスクリプトは、プログラマーからきたコメントが簡潔すぎて分かりにくいか、冗長でくどいか、あるいはプログラマー以外の人が理解するには難しいかどうかをコード・マネージャーに知らせます。ご自分でそれを試してみてください。つまり、"We should raise..." で始まる長いコメント・ブロックを持つ stat-comments.pl と、それを持たないものとを実行し、統計に違いがあるかどうかを見るのです。明らかに、ソフトウェア・プロジェクト・マネージャーは、これらの統計を使用して効率を上げることができます。

stat-comments.pl スクリプトは、有用なソフトウェア・プロジェクト管理ツールですが、それは正しく使用した場合のみのことです。ファンクション・ポイントのカウントや 1 日当たりのコード行、その他ソフトウェア・プロジェクト・マネージャーが使用できる多くの統計データなどのように、stat-comments.pl によって作成される統計は、実際の作業を補完するものと見なすべきであり、実際の作業の本質と見なしてはなりません。多くの優れたプログラマーが劣ったコメントを作成し、多くの劣ったプログラマーが優れたコメントを作成します。重要なことは、こういったプログラマーたちの仕事のやり方を理解し、それのパターンと変化を認識することです。


最後の注意事項

今日使用できる Perl モジュールは、すべての構文解析作業を容易にすることができます。Parse::RecDescent のほかに、Parse::Lex、Parse::CLex、および Parse::Yapp も CPAN から使用できます。それらを調べて、どれがお客様の状態に最も適合しているかを確認してください。Parse::RecDescent は、このリスト中では最も柔軟性があり、最も強力なモジュールです。

よく使用される Parse::RecDescent の例については、Abigail による CPAN RFC::RFC822::Address を参照してください。Parse::RecDescent を使用しないと、RFC 822 電子メール・アドレスの統語の妥当性検査がほとんどできなくなりますが、これは、Perl の一般式の能力を使用しても同様です。

お客様が独自のツールを作成しようとすると、テキスト分析が難しくなります。CPAN Lingua モジュールは、任意のテキスト分析作業に能力と柔軟性を与えることができます。その他の多くの Lingua モジュールについては、CPAN Web サイト (「参考文献」を参照) をアクセスしてください。

この記事は、Perl コードの効果的な再使用方法を示しています。Parse::RecDescent モジュールと一緒に提供されるデモ・スクリプトは、ここに示した 3 つのスクリプトのうちの 2 つについての基盤を提供しました。Parse::RecDescent モジュールについては Damian Conway に感謝し、demo_decomment.pl スクリプトについては Helmut Jarausch、優れた Lingua::EN::Fathom については Kim Ryan、およびオリジナルの chef フィルター文法については John Hagerman に感謝します。

参考文献

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=227109
ArticleTitle=Perlモジュールによる構文解析
publish-date=04012000