こんにちは、開発担当の福満です。
このエントリでは、URI の正規表現について扱います。
ある程度正常に動作する URI 正規表現は簡単に作れそうですが、URI の仕様には色々な要素が含まれていて、完全なものを作るのは中々難しそうです。
今回、なるべく完全に動作させるために URI の ABNF をほぼそのまま実装して正規表現を生成するコードを書いてみたので、そのご紹介をします。
URI の定義
URI は RFC3986 によって定義されています。
上記文書内に、文法が ABNF で掲載されているので、それを忠実に実装してみます。
Appendix A. Collected ABNF for URI
https://tools.ietf.org/html/rfc3986#page-49
Expression
ABNF は 「名前 = 定義」になっています。それを Expression というクラスで表現することにします。
static abstract class Expression {
protected String abnfDisplayName() {
return null;
}
public abstract String regexp();
public abstract String abnf();
}
regexp() で正規表現文字列を出力します。
ABNF の各行に対応する Expression を実装すれば、URI 正規表現を出力できるようになるはずです。
また、検証用に ABNF の出力を行うためのメソッドも定義しています。
繰り返し
繰り返し表現が多用されていますので、それを処理するクラスも実装します。
static abstract class RepeatExpression extends Expression {
private Expression mExpression;
public RepeatExpression( Expression expression ) {
mExpression = expression;
}
protected abstract String regexpRepeat();
protected abstract String abnfRepeat();
@Override
public String regexp() {
return mExpression.regexp() + regexpRepeat();
}
@Override
public String abnf() {
String s = mExpression.abnfDisplayName();
if ( TextUtils.isEmpty(s)) {
s = mExpression.abnf();
}
return abnfRepeat() + s;
}
}
static class RepeatExpressionAsterisc extends RepeatExpression {
public RepeatExpressionAsterisc(Expression expression) {
super(expression);
}
@Override
protected String regexpRepeat() {
return "*";
}
@Override
protected String abnfRepeat() {
return "*";
}
}
static class RepeatExpressionCount extends RepeatExpression {
private int mCount;
public RepeatExpressionCount(Expression expression, int count) {
super(expression);
mCount = count;
}
@Override
protected String regexpRepeat() {
return String.format( "{%d}", mCount);
}
@Override
protected String abnfRepeat() {
return String.format( "%d", mCount);
}
}
...
グルーピング
表現の結合や OR(“/”) による選択などは GroupedExpression として定義します。
サブクラスで、expressionList() 実装して使用します。
abstract static class GroupedExpression extends Expression {
private boolean mUseParen;
public GroupedExpression( boolean useParen ) {
mUseParen = useParen;
}
protected abstract Expression[] expressionList();
protected abstract String regexpDelimiter();
protected abstract String bnfDelimiter();
protected boolean reverse() {
return false;
}
@Override
public String regexp() {
Expression[] expressions = expressionList();
StringBuilder sb = new StringBuilder();
sb.append("(");
List<Expression> list = Arrays.asList(expressions);
if ( reverse() ) {
Collections.reverse( list );
}
Iterator<Expression> itr = list.iterator();
while ( itr.hasNext() ) {
Expression exp = itr.next();
sb.append( exp.regexp() );
if ( itr.hasNext() ) {
sb.append( regexpDelimiter() );
}
}
sb.append(")");
return sb.toString();
}
...
}
結合と OR は区切り文字が違うだけなので、サブクラスでその差分を実装します。
abstract static class GroupedExpressionConcat extends GroupedExpression {
public GroupedExpressionConcat(boolean useParen) {
super(useParen);
}
public GroupedExpressionConcat() {
super(false);
}
@Override
protected String regexpDelimiter() {
return "";
}
@Override
protected String bnfDelimiter() {
return " ";
}
}
abstract static class GroupedExpressionOr extends GroupedExpression {
public GroupedExpressionOr(boolean useBnfParen) {
super(useBnfParen);
}
public GroupedExpressionOr() {
super(false);
}
@Override
protected String regexpDelimiter() {
return "|";
}
@Override
protected String bnfDelimiter() {
return " / ";
}
}
文字列
文字列のみの単純な表現は StringExpression とします。
正規表現上エスケープが必要な文字はエスケープして渡します。
static class StringExpression extends Expression {
protected String mExpression;
public StringExpression(String expression) {
mExpression = expression;
}
@Override
public String abnf() {
return quotedString( excludeBackSlash( mExpression ) );
}
@Override
public String regexp() {
return mExpression;
}
}
ABNF の各行の実装
あとは ABNF の各行を実装していきます。
例えば、ABNF の一番下の行 sub-delims の実装は下記のようになります。
// ABNF: sub-delims = "!" / "$" / "&" / "'" / "(" / ")" / "*" / "+" / "," / ";" / "="
static class SubDelimsExpression extends GroupedExpressionOr {
@Override
protected Expression[] expressionList() {
return new Expression[] {
new StringExpression("\\!"),
new StringExpression("\\$"),
new StringExpression("\\&"),
new StringExpression("\\'"),
new StringExpression("\\("),
new StringExpression("\\)"),
new StringExpression("\\*"),
new StringExpression("\\+"),
new StringExpression("\\,"),
new StringExpression("\\;"),
new StringExpression("\\=")
};
}
@Override
protected String abnfDisplayName() {
return "sub-delims";
}
}
例外的な処理
dec-octet = DIGIT / %x31-39 DIGIT / “1” 2DIGIT / “2” %x30-34 DIGIT / “25” %x30-35
上の行を、そのままの順序で正規表現に翻訳すると、以下のようになります。
([\x30-\x39]|([\x31-\x39][\x30-\x39])|(1[\x30-\x39]{2})|(2[\x30-\x34][\x30-\x39])|(25[\x30-\x35])
マッチングが成功する場合に於いて、正規表現の最長マッチは “|” を超えての検査を行わず、最初の [\x30-\x39] でマッチしたら以降の表現をテストしないようで、一部の URI が正常に検出されない問題がありました。
例えば、http://192.168.200.77:3000/ を含むテキストに対してマッチングを行うと http://192.168.200.7 が検出されてしまいます。
これは dec-octet が前方の候補ほど文字数が短く記述されていることが問題でしたので、dec-octet のみ reverse() メソッドを実装して正規表現を逆順で出力するようにしています。
正規表現の生成
全ての ABNF 行の実装が完了したら正規表現の生成を行います。
public static String generate( String concreteSchemeExpression) {
URIExpression uri = new URIExpression(concreteSchemeExpression);
return uri.regexp();
}
public static String generate() {
return generate( "https?");
}
スキームが何でもありだと、想定外のものがマッチしてしまうことが多かったので、スキーム指定を可能にして、実際の使用時は HTTP / HTTPS 固定にしました。
下記が生成した正規表現です。
URI 正規表現（HTTP / HTTPS 固定）
(https?\:((\/\/(((([a-zA-Z]|[\x30-\x39]|\-|\.|\_|\~)|(\%[0-9a-fA-F][0-9a-fA-F])|(\!|\$|\&|\'|\(|\)|\*|\+|\,|\;|\=)|\:)*\@)?((\[(((([0-9a-fA-F]{1,4}\:){6}(([0-9a-fA-F]{1,4}\:[0-9a-fA-F]{1,4})|(((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39]))))|(\:\:([0-9a-fA-F]{1,4}\:){5}(([0-9a-fA-F]{1,4}\:[0-9a-fA-F]{1,4})|(((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39]))))|([0-9a-fA-F]{1,4}?\:\:([0-9a-fA-F]{1,4}\:){4}(([0-9a-fA-F]{1,4}\:[0-9a-fA-F]{1,4})|(((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39]))))|((([0-9a-fA-F]{1,4}\:){0,1}[0-9a-fA-F]{1,4})?\:\:([0-9a-fA-F]{1,4}\:){3}(([0-9a-fA-F]{1,4}\:[0-9a-fA-F]{1,4})|(((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39]))))|((([0-9a-fA-F]{1,4}\:){0,2}[0-9a-fA-F]{1,4})?\:\:([0-9a-fA-F]{1,4}\:){2}(([0-9a-fA-F]{1,4}\:[0-9a-fA-F]{1,4})|(((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39]))))|((([0-9a-fA-F]{1,4}\:){0,3}[0-9a-fA-F]{1,4})?\:\:[0-9a-fA-F]{1,4}\:(([0-9a-fA-F]{1,4}\:[0-9a-fA-F]{1,4})|(((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39]))))|((([0-9a-fA-F]{1,4}\:){0,4}[0-9a-fA-F]{1,4})?\:\:(([0-9a-fA-F]{1,4}\:[0-9a-fA-F]{1,4})|(((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39]))))|((([0-9a-fA-F]{1,4}\:){0,5}[0-9a-fA-F]{1,4})?\:\:[0-9a-fA-F]{1,4})|((([0-9a-fA-F]{1,4}\:){0,6}[0-9a-fA-F]{1,4})?\:\:))|(v[0-9a-fA-F]{1,}\.(([a-zA-Z]|[\x30-\x39]|\-|\.|\_|\~)|(\!|\$|\&|\'|\(|\)|\*|\+|\,|\;|\=)|\:){1,}))\])|(((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39])\.((25[\x30-\x35])|(2[\x30-\x34][\x30-\x39])|(1[\x30-\x39]{2})|([\x31-\x39][\x30-\x39])|[\x30-\x39]))|(([a-zA-Z]|[\x30-\x39]|\-|\.|\_|\~)|(\%[0-9a-fA-F][0-9a-fA-F])|(\!|\$|\&|\'|\(|\)|\*|\+|\,|\;|\=))*)(\:[\x30-\x39]*)?)(\/(([a-zA-Z]|[\x30-\x39]|\-|\.|\_|\~)|(\%[0-9a-fA-F][0-9a-fA-F])|(\!|\$|\&|\'|\(|\)|\*|\+|\,|\;|\=)|\:|\@)*)*)|(\/((([a-zA-Z]|[\x30-\x39]|\-|\.|\_|\~)|(\%[0-9a-fA-F][0-9a-fA-F])|(\!|\$|\&|\'|\(|\)|\*|\+|\,|\;|\=)|\:|\@){1,}(\/(([a-zA-Z]|[\x30-\x39]|\-|\.|\_|\~)|(\%[0-9a-fA-F][0-9a-fA-F])|(\!|\$|\&|\'|\(|\)|\*|\+|\,|\;|\=)|\:|\@)*)*)?)|((([a-zA-Z]|[\x30-\x39]|\-|\.|\_|\~)|(\%[0-9a-fA-F][0-9a-fA-F])|(\!|\$|\&|\'|\(|\)|\*|\+|\,|\;|\=)|\:|\@){1,}(\/(([a-zA-Z]|[\x30-\x39]|\-|\.|\_|\~)|(\%[0-9a-fA-F][0-9a-fA-F])|(\!|\$|\&|\'|\(|\)|\*|\+|\,|\;|\=)|\:|\@)*)*)|)(\?((([a-zA-Z]|[\x30-\x39]|\-|\.|\_|\~)|(\%[0-9a-fA-F][0-9a-fA-F])|(\!|\$|\&|\'|\(|\)|\*|\+|\,|\;|\=)|\:|\@)|\/|\?)*)?(\#((([a-zA-Z]|[\x30-\x39]|\-|\.|\_|\~)|(\%[0-9a-fA-F][0-9a-fA-F])|(\!|\$|\&|\'|\(|\)|\*|\+|\,|\;|\=)|\:|\@)|\/|\?)*)?)
検証
実装したクラスが構造的に ABNF と一致するか検証するために、ABNF からコメントや余分なスペース、改行等を除いたテキストファイルを用意しておき、 下に掲載したコード中の createAbnfText() メソッドで出力してファイルに保存し、DIFF ツールで比較しました。
さいごに
コードは下に置きますので、ご自由にお使いください。拡張子は .txt に変更しています。（ファイル冒頭にライセンスが記載されています。）
今回ご紹介したアプローチは複雑な正規表現を作る必要がある時に応用可能かと思いますので、参考にしていただけたら幸いです。
フェンリルのオフィシャル Twitter アカウントでは、フェンリルプロダクトの最新情報などをつぶやいています。よろしければフォローしてください！
関連記事
