正規表現が苦手な人にも試してみてほしい、ABNF記法のパターンマッチング

2016/08/16

Lowell D. Thomas

8

Articles in this issue reproduced from SitePoint
Copyright © 2016, All rights reserved. SitePoint Pty Ltd. www.sitepoint.com. Translation copyright © 2016, KADOKAWA ASCII Research Laboratories, Inc. Japanese syndication rights arranged with SitePoint Pty Ltd, Collingwood, Victoria,Australia through Tuttle-Mori Agency, Inc., Tokyo

正規表現って使いこなせると便利だけど、書くのも読むのも大変…。そこで、ABNF記法で書けるapg-expというパターンマッチエンジンの使い方を紹介。正規表現と比べながら試してみて。

本記事はSebastian SeitzAlmir Bijedicが査読を担当しています。最高のコンテンツに仕上げるために尽力してくれたSitePointの査読担当者のみなさんに感謝します。

プログラマーにとって、ときどき何らかの形で正規表現を使うことは避けられません。多くの場合、パターン構文は難解でとっつきにくく思えます。この記事では、視覚的にいくぶん平易なABNFパターン構文で記述できる、RegExpの多機能な代替手段の新しいパターンマッチエンジンapg-expを紹介します。

簡単に比べてみる

Eメールアドレスの検証をしようとして、次のような表現に出くわしたことはないでしょうか?

^[\w!#$%&'*+/=?^_`{|}~-]+(?:\.[\w!#$%&'*+/=?^_`{|}~-]+)*@(?:[A-Z0-9-]+\.)+[A-Z]{2,6}$

パターンマッチエンジンは由緒正しい作業ツールです。優れた設計の、よく練られた正規表現で、動作も抜群です。それなら使わない手はありませんね。

さて、みなさんが正規表現のエキスパートでしたらなにも問題はありません。でもそうでない人にとって、正規表現とは次のように考えているのかもしれません。

  • 読みにくい
  • 書くのはもっと難しい
  • 管理が大変である

長い歴史を持つ正規表現の構文は、プログラマーが毎日使う多くのツールや言語に深く浸透しています。

とはいえ、同じくらい古くから存在してきた代替構文があります。その構文はインターネット技術仕様の執筆者やユーザーの間ではとてもポピュラーで、正規表現のすべての機能を備えています。それにもかかわらず、JavaScriptプログラミングの世界ではほとんど使われていません。その構文とは、IETFRFC 5234RFC 7405で定義される「Augmented Backus-Naur Form(拡張バッカスナウア記法)」、つまりABNFです。

同じEメールアドレスがABNFではどうなるかご覧ください。

email-address   = local "@" domain
local           = local-word *("." local-word)
domain          = 1*(sub-domain ".") top-domain
local-word      = 1*local-char
sub-domain      = 1*sub-domain-char
top-domain      = 2*6top-domain-char
local-char      = alpha / num / special
sub-domain-char = alpha / num / "-"
top-domain-char = alpha
alpha           = %d65-90 / %d97-122
num             = %d48-57
special         = %d33 / %d35 / %d36-39 / %d42-43 / %d45 / %d47 
                / %d61 / %d63 / %d94-96 / %d123-126

確かにコンパクトとは言えませんが、HTMLやXMLのように、人間にも機械にも判読できるように設計されています。ワイルドカード検索パターンについてのひととおりの知識さえあれば、おそらく「簡単な英語」で、なにを言っているのかをだいたい読み取れるでしょう。

  • Eメールアドレスは、ローカルパートとドメインパートが@で区切られるものとして定義されています
  • ローカルパートは、あとに任意のドットで区切られた単語が来る1単語です
  • ドメインは、あとに単一のトップドメインが来る、ドットで区切られた1つ以上のサブドメインです
  • ここでははっきり分からないものの、推測できることは以下のとおりです
    • 単独のワイルドカード記号*は「0回以上」、1*は「1回以上」、2*6は「2回から6回まで」の繰り返しを表します
    • 選択肢は/で区切られます
    • %dは10進文字コードと文字コードの範囲を定義します
    • たとえば、%d35#とASCII10進数字の35を表します
    • %d65-90は、A-Zの範囲の任意のアルファベットとASCII10進数字の65~90を表します

例1では、このEメールアドレスについて、RegExpとapg-expを比較しています。

apg-expは、RegExpのルック&フィールを備え、しかもABNF構文を使ってパターンを定義するように設計されたパターンマッチエンジンです。以降で、以下の点を詳しく説明します。

  • アプリにapg-expを組み込む方法
  • ABNF構文の簡単なガイド
  • apg-expの使用例
  • 次なるステップとして、さらなる詳細な説明と、高度な使用例

インストールと起動:導入方法

npm

Node.js環境で作業する場合、プロジェクトのディレクトリから次のコードを実行します。

npm install apg-exp --save

これで、コードからrequire()を使ってapg-expにアクセスできます。

例を見てください。

var ApgExp = require("apg-exp");
var exp = new ApgExp(pattern, flags);
var result = exp.exec(stringToMatch);

GitHub

リポジトリのクローンをプロジェクトのディレクトリに作成して、GitHubからコードのコピーを取得できます。

git clone https://github.com/ldthomas/apg-js2-exp.git apg-exp

または、コードをzip形式でダウンロードできます。

page.htmlに組み込んだところです。

<!-- optional stylesheet used in tutorial examples -->
<link rel="stylesheet" href="./apg-exp/apgexp.css">
<script src="./apg-exp/apgexp-min.js"></script>

<script>
  var useApgExp = function(){
      var exp = new ApgExp(pattern, flags); 
      var result = exp.exec(stringToMatch);
      /* do something with the result */
  }
</script>

CDN

RawGitを使えば、GitHubのソースからCDNでディレクトリの作成もできます。ただし、アップタイムもサポートも保証されないことについて「no uptime or support guarantees」の部分(というよりFAQ全体)を必ず読んでください。

この記事のすべての例に次のコードが使われています。

<link rel="stylesheet"
 href="https://cdn.rawgit.com/ldthomas/apg-js2-exp/89c6681798ba9e47583b685c87b244406b18a26d/apgexp.css">
<script
 src="https://cdn.rawgit.com/ldthomas/apg-js2-exp/c0fc3adac954a6f6ad6f265fd2f8f06f68001e10/apgexp-min.js"
 charset="utf-8"></script>

ここに挙げられているファイルはMaxCDNサーバーにキャッシュされており、テストとしては利用可能期間中ずっと無料で使用できますが、プロジェクトに使う場合は、保証付きでアクセスできるようにapgexp-min.jsapgexp.cssのコピーを自分のサーバーに置き、アプリケーションに最適な方法でページにインクルードすることをお勧めします。

ABNFの簡単なガイド

ABNFはフレーズを記述する構文で、フレーズとは文字列のことです。先ほどのEメールの例のように、複雑なフレーズを分解していくつかの単純なフレーズのまとまりにできます。フレーズの定義には書式があります。

name = elements LF

要素を抜粋した表を次に示します(完全版のガイドはSABNFで確認してください)。

要素定義説明/例
name規則名(英数字 + ハイフン、注1を参照)
%d32単一の文字コード文字コードの10進値
%d97.98.99文字コードの文字列abc
%d48-57文字コード範囲0~9の任意のASCII数字
“abc”大文字・小文字を区別しない文字列またはABCなど
%s”aBc”大文字・小文字を区別する文字列aBcのみ(「%d97.66.99」と記述した場合と同じ)
space2要素の連結%d97 %d98 (= ab)
/2つの選択肢を区切る%d97 / %d98 (= aまたはb)
*element要素の0回以上の繰り返し(注2を参照)
(elements)グループ化し、単一の要素として扱う(注3を参照)
[elements]選択的グループ化[%d97] %d98(abまたはb)
%^入力文字列の先頭空のフレーズのときのみ位置にマッチ
%$入力文字列の末尾空のフレーズのときのみ位置にマッチ
&element要素の先読み現在の文字列の直後に要素が来ることが条件
!element要素の否定先読み現在の文字列の直後に要素が来ないことが条件
&&element要素の後読み現在の文字列の直前に要素が来ることが条件
!!element要素の否定後読み現在の文字列の直前に要素が来ないことが条件
\name規則名“name”の後方参照“name”に関して見つかった先行のフレーズにマッチ
;commentコメントコメントは;(セミコロン)で始まり、行末まで継続する

注1:規則名は必ず英字で始まり左詰めとします。続く行は必ずスペースかタブで開始します。最初の規則は、マッチするフレーズやパターン全体を定義します。それ以降の規則は、フレーズ全体の中で名前付きのサブフレーズ(または名前付きのキャプチャ)を定義します。

注2:繰り返しの一般的な書式はn∗mで、最小n回、最大m回の繰り返しを定義します。0~m回の繰り返しを∗mnの上限なしの繰り返しを∗nn∗nをnのみとするなど、簡易表記もできます。

注3:選択と連結で想定通りの反応を維持するためには、グループ化が大切です。連結は、選択よりも強くバインドします。次のように記述した場合、

phrase1 = elem (foo / bar) blat LF
phrase2 = (elem foo) / (bar blat) LF
phrase3 = elem foo / bar blat LF

phrase1ではelem foo blatまたはelem bar blatにマッチしますが、phrase2phrase3ではどちらもelem fooまたはbar blatにマッチします。注意しながら、ぜひグループ化を使用してください。

apg-expの使用例

アプリにapg-expをインクルードし、パターン構文の記述の基本が分かったところで、さっそくお楽しみのコーナー、apg-expの使用例に入っていきます。

次には、構築オブジェクトの詳細を書きました。サンプルを理解するために、必要に応じて参照できます。エラーハンドリングのこともスキップしますが、パターンエラーが出た場合、コンストラクタがApgExpError例外オブジェクトを投げることを覚えておいてください。このオブジェクトには、フォーマットされたパターンエラー表示用の、使い勝手のいい2つの関数が含まれています。try/catchブロックは次のようになります。

try {
  var exp = new ApgExp(pattern, flags);
  var result = exp.exec(stringToMatch);
  if (result) {
    // do something with results
  } else {
    // handle failure
  }
} catch(e) {
  if (e.name === "ApgExpError") {
    // display pattern errors to console
    console.log(e.toText());
    // display pattern errors to HTML page
    $("#errors").html(e.toHtml());
  } else {
    // handle other exceptions
  }
}

電話番号

電話番号はフォーム確認のよくある課題で、基本を実践するにはもってこいです。電話番号のように見える形式で10桁の数字が入力されたことを、the North American Plan(北米電話番号計画)や international numbers(国際電話番号)について細かいことを気にせずに知りたいと思う場合がありますよね。

「丸カッコ(または数字で始まり、0~3個の非数文字によって3桁、3桁、4桁に区切られたブロックがある」とリクエストすれば大丈夫です。この方法は一般的で大半の普通のフォーマットに十分通用し、しかもエリアコード(市外局番)、オフィスコード(市内局番)、加入者番号を、再フォーマットできるキャプチャグループとしてとらえるという特定の目的にかなっています。

ABNFで記述すると、次のようになります。

phone-number = ["("] area-code sep office-code sep subscriber
area-code    = 3digit                       ; 3 digits
office-code  = 3digit                       ; 3 digits
subscriber   = 4digit                       ; 4 digits
sep          = *3(%d32-47 / %d58-126 / %d9) ; 0-3 ASCII non-digits
digit        = %d48-57                      ; 0-9

例2でこのコードを実行しています。また、電話番号のフォーマットの変更もできます。

例3では、パターン構文を編集して、期待されるエラーメッセージを表示しています。

RegExp構文も、難しくはありません。例4では並べて比較できます。

\(?(\d{3})\D{0,3}(\d{3})\D{0,3}(\d{4})

日付

今度は少しレベルアップして、日付のマッチングでapg-expとRegExpを比較するとどうなるか説明します。

日付のフォーマット要件は次のとおりです。

mm/dd/yy or mm/dd/yyyy
dd/mm/yy or dd/mm/yyyy
mm, 1-12 or 01-12, i.e. with or without leading zero
dd, 1-31 or 01-31, i.e. with or without leading zero
yy, 00-99
yyyy, 1900-1999 or 2000-2099

mm/dd/yyyyのフォーマット自体は難しいものではありませんが、数字の範囲が狭まったことが、レベルアップした点です。ABNFでの記述は次のようになります。

date     = %^ (mm-first / dd-first) %$
mm-first = mm "/" dd "/" yyyy   ; month before day
dd-first = dd "/" mm "/" yyyy   ; day before month
dd       = "0" digit1           ;    01-09
         / ("1"/"2") digit      ; or 10-29
         / "3" %d48-49          ; or 30-31
         / digit1               ; or 1-9
mm       = "0" digit1           ;    01-09
         / "1" %d48-50          ; or 10-12
         / digit1               ; or 1-9
yyyy     = ("19" / "20") 2digit ; 1900-1999 or 2000-2099
         / 2digit               ; or 00-99
digit    = %d48-57              ; 0-9
digit1   = %d49-57              ; 1-9

コメントがそのまま内容の説明になっています。ddmmyyyyの部分で、最短の選択肢が連続していることに注目してください。「最短の選択肢が連続」はとても重要です。なぜなら、apg-expは選択肢に対して常に「最初のマッチが優先」というアプローチを適用するからです。左から右に選択され、ひとたびマッチする部分が見つかると、残りの選択肢は無視されてしまいます。ですから、パターンが1つまたは2つの数字にマッチする可能性がある場合、2桁のパターンを「最初」とすることが必要になるのです。

上とまったく同じアプローチに従って、ddmm[yy]yyを選択肢のパターンに分割してから結合し、完全な日付にするRegExp構文は、次のようになります。

^(?:((?:0[1-9])|(?:1[0-2])|(?:[1-9]))/((?:0[1-9])|(?:(?:1|2)[0-9])|(?:3[0-1])|(?:[1-9]))|((?:0[1-9])|(?:(?:1|2)[0-9])|(?:3[0-1])|(?:[1-9]))/((?:0[1-9])|(?:1[0-2])|(?:[1-9])))/((?:19|20)?[0-9][0-9])$

筆者はRegExpのエキスパートではないので、もっと短く書く方法があるのかもしれません。でも、これが動作するコードの1例です。例5で比較できます。アクセスして、実行してみてください。

入れ子になったペア(())を再帰でマッチングする

最後に、丸カッコ、大カッコなどの、入れ子になったペアをマッチングする方法を紹介します。入れ子のペアのマッチングはパターンマッチングでとても重要な課題であるにもかかわらず、RegExpではできません。丸カッコのペアのマッチについて、次のABNFコードを参照してください。

P = L P R / L R
L = "("
R = ")"

規則Pがそれ自体の定義の中に含まれていることに注目してください。これを「再帰」と言います。正規表現エンジンは種類によっては再帰に対応しており、RegExpツールの中にもある程度の再帰機能を持つものがある一方で、JavaScript用のRegExpは、再帰にまったく対応していません。上の例では丸カッコとマッチングさせるためにLRが使われていますが、「L」と「R」が同じものにマッチしないようにさえすれば、この部分に別の文字を使ってもかまいません。

例6で再帰のおもしろい例を見てください。

入れ子になったペアのマッチングについての話を終える前に、apg-expを使った2つの役立つ実例を紹介します。

例6で、入れ子になったペアをマッチングする方法とかぎカッコの中にテキストを入れる方法を見ました。「開き大カッコ{にカーソルを乗せると、対応する閉じ大カッコ}がハイライトされる」というようなプログラムを書くとしたら、と考えてみてください。

例7にこの課題の答えがあります。stickyモード(先頭固定)についての理解が必要です。

入れ子になったペアの最後の例です。これまで、すでにブロック内でコメントされている、ということを示すだけのために、HTMLの大きなブロックにコメントを入れる必要を感じたことはありませんか? いらいらしますよね? インターネットで「HTMLのコメントの入れ子問題」を検索してみればその気持ちが分かるでしょう。例8で、使える解決策を1つ紹介します。

注意:この解決方法を試すためには、少し背伸びしてresult.rulesオブジェクトとglobalモードについて理解する必要があります。

最後に

終わりにまとめとして、フォーム検証の全体例がどのようなものかを見ていきます。

一般に、新しいアカウントを作成する場合、ユーザー名、Eメールアドレス、パスワード、パスワードの確認を求められます。ユーザー名は、ASCII文字、ハイフン、ピリオドで3~32文字とします。パスワードは必ず8~12文字で、英大文字・英小文字・数字をそれぞれ1つ以上含むものとします。

このフォームでは、無効な入力があると、続行する前にその上の部分に文章でエラーメッセージを表示します。例9にまとめてあります。

ライブラリのAPI

この項では、これまでに挙げた例を理解するために必要な情報を載せることを目指しました。とはいえ、たくさんの高度な機能を使うには構文解析理論のさらに深い理解が必要です。こうした点については、「高度な」コメントとして示しています。

入力引数

ApgExpとするapg-expコンストラクタは、4つの引数を取ります。

  • pattern
    • string:前のセクションに書かれているSABNFパターン構文*
    • object:インスタンス化されたAPG parserオブジェクト(高度なオプション)。
  • flags:string:"gyud"の文字のいずれか
    • g – globalモード:すべてのパターンマッチの繰り返し(例8参照)
    • y – stickyモード:exp.lastIndexでマッチを固定(例7参照)
    • u – Unicodeモード:stringではなくinteger文字コード配列で結果を返す
    • d – debugモード:高度なオプション―APG traceオブジェクトをエクスポーズ
  • nodeHits: integer > 0:デフォルト値=Infinity:マッチングのアルゴリズムを"nodeHits"ステップに限定し、壊滅的なバックトラッキングから保護
  • treeDepth: integer > 0:デフォルト値=Infinity:マッチングパーサーのツリーの深さを制限

*たとえば、入力文字列に使用する英数字の名前とマッチさせる構文は次のとおりです。

var pattern = "alphanum = alpha *(alpha / num)\n"
            + "alpha = %d65-90 / %d97-122\n"
            + "num = %d48-57\n";

プロパティとメソッド

構築済みオブジェクトexpは、それ自体に16のプロパティと14のメソッドを持ちます。

プロパティ説明
astobject(高度: APG Abstract Syntax Tree ( APG 抽象構文木)オブジェクト)
debugbooleandebug フラグ d が設定済みの場合に真、それ以外は偽となる
flagsstringflags 引数の再フォーマットされたコピー
globalbooleanglobal フラグ g が設定済みの場合に真、それ以外は偽となる
inputstring/array(*)入力文字列のコピー
lastIndexinteger(**) でマッチングの試行を開始する文字インデックス
leftContextstring/array(*)マッチしたパターンのプレフィックス
lastMatchstring/array(*)マッチしたパターン(=result[0])
nodeHitsinteger入力値(実際の値で result.nodeHits を参照)
rightContextstring/array(*)マッチしたパターンのサフィックス
rulesobjectresult.rules を参照。最後にマッチしたフレーズだけをここに保持
sourcestring入力 SABNF パターン構文。 String
stickybooleansticky フラグ y が設定済みの場合に真、それ以外は偽となる
traceobject(高度: APG trace オブジェクトを参照) debug フラグが偽の場合 undefined となる
treeDepthinteger入力値(実際の値で result.treeDepth を参照)
unicodebooleanUnicode フラグ u が設定済みの場合に真、それ以外は偽となる

注1unicodeフラグがtrueの場合、integer文字コードの配列となり、それ以外ではstringとなります。

注2:ユーザーはここに任意の値を自由に設定できます。パターンマッチは常にこのインデックス値で開始します。マッチング試行後、使用と値はglobalモードとstickyモードの影響を受けます。例7例8を参照してください。

メソッド引数説明
defineUdt(name, func)string, function高度: SABNF の UDT 関数で使用される。
exclude([string])規則名の配列result.rules オブジェクトから除外された規則名のリスト
exec(str)stringstring でのパターンマッチの試行
include([string])規則名の配列result.rules オブジェクトに排他的に含まれる規則名のリスト
maxCallStackDepth()noneコールスタックの深さの上限を返す
replace(str, repl)string, string または functionパターンをstrでマッチングし、 replで置換する
sourceToHtml()none入力パターンを HTML 形式で返す
sourceToHtmlPage()none入力パターンを完全な HTML ページで返す
sourceToText()none入力パターンを ASCII 文字形式で返す
split(str[, limit])string, integerパターンマッチで入力文字列を分割する
test(str)stringパターンマッチが見つかった場合trueを返し、それ以外ではfalseを返す(例9参照)
toHtml()noneこのオブジェクトのプロパティを HTML 形式で返す
toHtmlPage()noneオブジェクトのプロパティを完全な HTML ページとして返す
toText()noneオブジェクトのプロパティを ASCII 文字形式で返す

resultオブジェクト

パターンマッチが成功すると、7つのプロパティと3つのメソッドを持つresultオブジェクトで結果を返します。

var result = exp.exec(str);
プロパティ説明
[0]string/array(*)マッチしたパターン
inputstring/array(*)入力文字列のコピー
indexintegerマッチしたパターンの最初の文字のインデックス
lengthintegerマッチしたパターンの文字数
nodeHitsintegerマッチングに必要な解析ステップの実際の数
rulesobject(名前付きキャプチャ)名前付き規則 (***) のそれぞれについてマッチしたすべてのフレーズの配列
treeDepthintegerマッチング中に到達した解析ツリーの深さの実際の最大値

注3:例 result.rules["name"][i] = {phrase: string/array, index: integer}例8参照)。

メソッド引数説明
toHtml()noneHTML 形式でプロパティを返す
toHtmlPage()none完全な HTML ページとしてプロパティを返す
toText()noneASCII 文字形式でプロパティを返す

次なるステップ

ここではapg-expライブラリとABNFとはどんなものか、これらがいかにRegExpに勝るとも劣らないかを、ちょっとだけでも知ってもらえる程度の、最小限の内容にとどめました。しかし、できることはもっともっとたくさんあります。パターンマッチングのスキルをさらに磨きたい人やちょっと冒険してみたい人は、さらに高度な例完全版のユーザーガイドを参考にしてください。

(原文:An Alternative to Regular Expressions: apg-exp

[翻訳:新岡祐佳子]
[編集:Livit

Copyright © 2016, Lowell D. Thomas All Rights Reserved.

Lowell D. Thomas

Lowell D. Thomas

JavaScriptの愛好家でアメリカ フロリダ州、ガルフコースト在住です。C/C++、Java、PHP、フロントエンドデータベース、Webサイトのバックエンド、通信プロトコル、パーサー(構文解析)、パーサージェネレーターで30年以上の経験があります。余暇には、ハードボイルドの探偵小説を読んだり、アウトドアで写真を撮るのが好きです。

Loading...