Fragments Of Time

Happiness only real when shared.

部落格搬移到 amobiz.github.io

部落格已搬移到 amobiz.github.io.

redirect to in seconds.

在 Blogger 上顯示 GitHub Ribbon

首先,到 GitHub Ribbons 挑選喜歡的配色,抄下其中 srcdata-canonical-src (非必要) 屬性。

在部落格的「版面配置」中,捲動到最後面,找到「新增小工具」,確認它是在「網誌文章」的後面,點選後,選擇「HTML/JavaScript」,然後插入下面程式碼:

<script>
//<![CDATA[
/* Add GitHub Ribbons */
(function(options) {
  var el, href, pos;

  if (location.pathname==='/') {
    href = options.home;
  }
  else {
    el = document.querySelector('*[data-forkme]');
    if (el) {
      href = el.getAttribute('data-forkme');
    }
  }
  pos = options.position || 'right';
  if (href) {
    el = document.createElement('div');
    el.innerHTML = '<a href="' + href + '"><img style="display: block; position: fixed; top: 0; ' + pos + ': 0; border: 0; background:none; border-radius:0; box-shadow:none; padding:0; z-index: 9999;" src="' + options.src + '" alt="Fork me on GitHub" data-canonical-src="' + options.canonicalSrc + '"></a>';
    el.style.cssText = 'padding:0; margin:0; background-color:none;';
    document.body.appendChild(el);
  }
})({
  home: 'https://github.com/amobiz',
  src: 'https://camo.githubusercontent.com/e7bbb0521b397edbd5fe43e7f760759336b5e05f/68747470733a2f2f73332e616d617a6f6e6177732e636f6d2f6769746875622f726962626f6e732f666f726b6d655f72696768745f677265656e5f3030373230302e706e67',
  canonicalSrc: 'https://s3.amazonaws.com/github/ribbons/forkme_right_green_007200.png',
  position: 'right'
});
//]]>
</script>

記得將最後面的 home 改為你自己的 GitHub 的個人頁面,並且分別填入剛剛抄下的 srcdata-canonical-srcsrccanonicalSrc 屬性中。彩帶預設放在右邊,如果挑選的彩帶必須放在左邊,則要加上 position: 'left' 屬性。

這樣設定之後,在部落格的首頁就會出現「Fork me on GitHub」的彩帶,點擊後會連到你的 GitHub 個人首頁。

預設在文章中不顯示彩帶。若要在文章中連到個人首頁或特定的專案,只要在文章的任意 HTML 標籤中,埋入 data-forkme 屬性,即可顯示彩帶:

<div data-forkme="https://github.com/amobiz/lazy-umd.js"></div>

Lazy-umd.js - 懶人 UMD (Universal Module Definition)

最近在整理過去寫的程式庫,想要統一支援 script loader,同時又很貪心地想要:

1.同時支援 AMD(RequireJS)、CommonJS(node.js) 及 browser,解決不同語法差異。
2.模組套用時,避免修改 script loader 程式碼的需要。

研究了一下,發現 Addy Osmani 已經寫了 UMD。UMD 可以滿足第一點,但是應該是為了避免 script loader 程式碼擁腫,所以套用的時候,一定要修改 script loader 的部分。所以我自己整理出兩種做法,放在 Github 供大家參考:

方法一、傳統的 factory 模式

(function(name, /* optional */deps, factory) {
    'use strict';

    /* global define, require, module, window */
    var i;

    // deps is not an array, means the module has no dependencies, and deps is a factory function.
    if (typeof deps === 'function') {
        factory = deps;
        deps = [];
    }

    // AMD(RequireJS)
    if (typeof define === 'function' && define.amd) {
        define(deps, factory);
    }
    // CommonJS(node.js)
    else if (typeof module !== 'undefined' && module.exports) {
        if (deps.length) {
            for (i = 0; i < deps.length; ++i) {
                deps[i] = require(deps[i]);
            }
        }
        module.exports = factory.apply(null, deps);
    }
    // Browser globals
    else {
        if (deps.length) {
            for (i = 0; i < deps.length; ++i) {
                deps[i] = window[deps[i]];
            }
        }
        window[name] = factory.apply(null, deps);
    }
})('MyModule', ['Promise'], function(Promise) {
    'use strict';

    return {
    };
});

模組的定義寫在後半段的 factory 方法中,然後當作參數傳遞給前面的 script loader 函數,控制權在 script loader 函數。這種寫法在語法上比較接近 RequireJS 的做法。

優點:

1.大量的程式庫都是採取與 UMD 類似的做法。容易了解。

缺點:

1.如果相依性較多,則會有很長的相依陣列,這是 RequireJS 原本就有的問題。
2.模組的主體定義在後面,強迫程式設計師先看到與模組無關的程式碼。
3.針對 RequireJS 而言,無法支援不匯出模組的 require() 函數。 (這其實不算缺點,畢竟就是要定義模組,讓模組能盡量支援各種不同的執行環境,才需要考慮 script loader 的相容性問題。一般應用程式通常執行環境早已確認。)

方法二、builder 串接語法模式

(function(module) {
    'use strict';

    module('MyModule')
    .require('Promise')
    .define(function(Promise) {
        return {
        };
    });

})(function(name) {
    'use strict';

    /* global define, require, module, window */
    var deps = [];

    // AMD(RequireJS)
    if (typeof define === 'function' && define.amd) {
        return {
            require: function(lib) {
                deps.push(lib);
                return this;
            },
            define: function(factory) {
                define(deps, factory);
            },
            run: function(script) {
                require(deps, script);
            }
        };
    }
    // CommonJS(node.js)
    else if (typeof module !== 'undefined' && module.exports) {
        return {
            require: function(lib) {
                deps.push(require(lib));
                return this;
            },
            define: function(factory) {
                module.exports = factory.apply(null, deps);
            },
            run: function(script) {
                script();
            }
        };
    }
    // Browser globals
    else {
        return {
            require: function(lib) {
                deps.push(window[lib]);
                return this;
            },
            define: function(factory) {
                window[name] = factory.apply(null, deps);
            },
            run: function(script) {
                script();
            }
        };
    }
});

這是模仿 https://github.com/voronianski/melchior.js 的做法。

在後半段先定義好 script loader,然後當作參數傳遞給模組定義函數,控制權在模組定義函數。

優點:

1.模組的主體定義在前面,避免與模組無關的程式碼的干擾。
2.相依模組的定義清晰易懂;若無相依也可以直接略掉 .require() 的呼叫。

缺點:

1.Script loader 部分的程式碼變得更為冗長。

題外話:melchior.js 為了避免在它的模組定義函數:body() 中重新宣告相依模組變數,選擇將相依模組變數都放到 global,如果採用的話需要多加注意。

將 SVN Local Repository 轉換為 Git Local Repository (Windows)

如果有舊專案使用 Subversion 管理程式碼,而且不是儲存在 svn server 上,而是使用 TortoiseSVN 的 create repository here 指令所建立的 repository。
或者是 server 已不復存在,只剩下 repository 目錄的備份,那麼可以試著使用本文介紹的方式,轉換為 git 格式。

首先,根據The Will Will Web | 介紹好用工具:SubGit ( 輕鬆將 SVN 專案移轉到 Git 的工具 )這一篇文章的介紹,可以將 svn server 的 repository 轉為 local git bare repositior。

再來,根據 StackOverflow 的 Converting a local svn repo dump to git 這一個回答,似乎沒有辦法直接讀取 local svn repository。所以,還是要先安裝 svn server 才行。

由於早先使用 TortoiseSVN 管理專案,所以本文決定還是以 TortoiseSVN 來介紹如何進行轉換。

安裝好 TortoiseSVNsubgit,設定好 subgit\bin 的 PATH 路徑後,就可以開始進行轉換。

以下假設 local repository 放在 C:\svn 目錄下,不需要是當初 repository 實際運作的目錄。另外,git 專案想放在 D:\workspace 目錄下。

1.在 cmd 模式下,先切換到該目錄下(cd/d D:\workspace)。

2.在檔案總管裡,在 C:\svn 目錄下點右鍵,點選 TortoiseSVN / Repo-browser,這會列出 local repository 中的所有專案。假設現在要轉換 editor 專案。進入該專案,看一下所有 checkin 的 Author 名稱,編輯 D:\workspace\authors.txt,設定好 svn 的作者名稱要如何對應 git 的作者名稱及 email,譬如:

svn-user1 = git-user1 <git-user1@gmail.com>
svn-user2 = git-user2 <git-user2@gmail.com>

3.回到 cmd,使用這個指令:

subgit import --non-interactive --authors-file authors.txt --svn-url file:///C:\svn\editor editor.git

就可以建立 D:\workspace\editor.git 目錄,裡面就是轉換成功的 git bare repository。
注意這裡的 file:///C:\svn\editor,其中 file:///C:\svn\ 是 local repository 所在目錄,而 editor 是專案名稱。editor.git 則是要匯出的 git bare repository 目錄名稱,在這裡是匯出到 D:\workspace\editor.git

這裡需要注意的是,即使專案名稱指定錯誤,subgit 仍然會顯示轉換成功。可參考第 5 步驟確認。

4.成功匯出之後,就可以將 git 專案 push 到 server:

git push --mirror https://remote.github.com/editor.git

5.或者要直接 clone 出來,建立 working repository:

git clone -l editor.git

這樣就會建立 D:\workspace\editor 專案目錄。
如果第 3 步驟發生錯誤,這裡的 clone 指令會提示:

warning: You appear to have cloned an empty repository.

6.如果還有其他專案需要轉換,重複上面 5 個步驟即可。

參考資料:
  1. The Will Will Web | 介紹好用工具:SubGit ( 輕鬆將 SVN 專案移轉到 Git 的工具 )
  2. Converting a local svn repo dump to git

Open Sourced my JavaScript Regular Expression Generator - RegexGen.js

RegexGen.js - JavaScript Regular Expression Generator

RegexGen.js is a JavaScript Regular Expression Generator that helps to construct complex regular expressions, inspired by JSVerbalExpressions.

The Problems

RegexGen.js tries to ease two problems.

  1. While creating a regular expression, it's hard to remember the correct syntax and what characters to escape.
  2. After done creating a regular expression, it's hard to read and remember what the regex do.

The Goals

RegexGen.js is designed to achieve the following goals.

  1. The written codes should be easy to read and easy to understand.
  2. The generated code should be as compact as possible, e.g., no redundant brackets and parentheses.
  3. No more character escaping reguired (except '\', or if you use regex overwrite.)
  4. If the generated code is not good enougth, bad parts can be easily replaced directly in the written codes.

Getting Started

The generator is exported as a regexGen() function.

To generate a regular expression, pass sub-expressions as parameters to the regexGen() function.

Sub-expressions as parameters which are separated by comma are concatenated together to form the whole regular expression.

Sub-expressions can either be a string, a number, a RegExp object, or any values generated by the owned functions of the regexGen() function object, i.e., the regex-generator() as the following informal BNF syntax.

Strings passed into the regexGen(), the text(), the maybe(), the anyCharOf() and the anyCharBut() functions, are always escaped as necessary, so you don't have to worry about which characters to escape.

The result of calling the regexGen() function is a RegExp object.

The basic usage can be expressed as the following informal BNF syntax.

RegExp object = regexGen( sub-expression [, sub-expression ...] [, modifier ...] )

sub-expression ::= string | number | RegExp object | term

term ::= regex-generator() [.term-quantifier()] [.term-lookahead()]

regex-generator() ::= regexGen.startOfLine() | regexGen.endOfLine()
    | regexGen.wordBoundary() | regexGen.nonWordBoundary()
    | regexGen.text() | regexGen.maybe() | regexGen.anyChar() | regexGen.anyCharOf() | regexGen.anyCharBut()
    | regexGen.either() | regexGen.group() | regexGen.capture() | regexGen.sameAs()
    | regex() | ... (see regexGen.js for all termGenerator()s.)

term-quantifier() ::= .term-quantifier-generator() [.term-quantifier-modifier()]

term-quantifier-generator() ::= term.any() | term.many() | term.maybe() | term.repeat() | term.multiple()

term-quantifier-modifier() ::= term.greedy() | term.lazy() | term.reluctant()

term-lookahead() ::= term.contains() | term.notContains() | term.followedBy() | term.notFollowedBy()

modifier ::= regexGen.ignoreCase() | regexGen.searchAll() | regexGen.searchMultiLine()

Please check out regexgen.js and wiki for API documentations, and check out test.js for more examples.

Installation

If your are managing package dependencies with bower, your can install RegexGen.js using bower install command.

bower install git://github.com/amobiz/regexgen.js.git

Or you can just download the regexgen.js or regexgen.min.js, and put it to where your scripts located in your project.

Usage

The hard (but safe) way

Since the generator is exported as the regexGen() function.
Everything must be referenced from it.
To simplify the code, assign it to a short variable is preferable.

var _ = regexGen;

var regex = regexGen(
    _.startOfLine(),
    _.capture( 'http', _.maybe( 's' ) ), '://',
    _.capture( _.anyCharBut( ':/' ).repeat() ),
    _.group( ':', _.capture( _.digital().multiple(2,4) ) ).maybe(), '/',
    _.capture( _.anything() ),
    _.endOfLine()
);
var matches = regex.exec( url );

Mixin to global object

If you still feel inconvenient, and don't mind the global object being polluted,
use the regexGen.mixin() function to export all member functions of the regexGen() function object to the global object.

regexGen.mixin( window );

var regex = regexGen(
    startOfLine(),
    capture( 'http', maybe( 's' ) ), '://',
    capture( anyCharBut( ':/' ).repeat() ),
    group( ':', capture( digital().multiple(2,4) ) ).maybe(), '/',
    capture( anything() ),
    endOfLine()
);
var matches = regex.exec( url );

Use the with keyword

Or, if you don't use the strict mode with use strict keyword,
you can use the with keyword to refer to all member functions of the regexGen() function object.

with( regexGen ) {
    var regex = regexGen(
        startOfLine(),
        capture( 'http', maybe( 's' ) ), '://',
        capture( anyCharBut( ':/' ).repeat() ),
        group( ':', capture( digital().multiple(2,4) ) ).maybe(), '/',
        capture( anything() ),
        endOfLine()
    );
    var matches = regex.exec( url );
}

Examples

Simple Password Validation

This example is taken from the article: Mastering Lookahead and Lookbehind.

regexGen.mixin( window );
var regex = regexGen(
    // Anchor: the beginning of the string
    startOfLine(),
    // Match: six to ten word characters
    word().multiple(6,10).
        // Look ahead: anything, then a lower-case letter
        contains( anything().reluctant(), anyCharOf(['a','z']) ).
        // Look ahead: anything, then an upper-case letter
        contains( anything().reluctant(), anyCharOf(['A','Z']) ).
        // Look ahead: anything, then one digit
        contains( anything().reluctant(), digital() ),
    // Anchor: the end of the string
    endOfLine()
);

Generates:

/^(?=.*?[a-z])(?=.*?[A-Z])(?=.*?\d)\w{6,10}$/
Matching an IP Address

This example is taken from the book: Mastering Regular Expressions

regexGen.mixin( window );
var d1 = group( anyCharOf( '0', '1' ).maybe(), digital(), digital().maybe() );
var d2 = group( '2', anyCharOf( ['0', '4'] ), digital() );
var d3 = group( '25', anyCharOf( ['0', '5'] ) );
var d255 = capture( either( d1, d2, d3 ) );
var regex = regexGen(
    startOfLine(),
    d255, '.', d255, '.', d255, '.', d255,
    endOfLine()
);

Generates:

/^([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])$/
Matching Balanced Sets of Parentheses

This example is taken from the book: Mastering Regular Expressions

regexGen.mixin( window );
var regex = regexGen(
    '(',
    anyCharBut( '()' ).any(),
    group(
        '(',
        anyCharBut( '()' ).any(),
        ')',
        anyCharBut( '()' ).any()
    ).any(),
    ')'
);

Generates:

/\([^()]*(?:\([^()]*\)[^()]*)*\)/
Matching Balanced Sets of Parentheses within Any Given Levels of Depth

This example is taken from the book: Mastering Regular Expressions

regexGen.mixin( window );
function nestingParentheses( level ) {
    if ( level < 0 ) {
        return '';
    }
    if ( level === 0 ) {
        return anyCharBut( '()' ).any();
    }
    return either(
            anyCharBut( '()' ),
            group(
                '(',
                nestingParentheses( level - 1 ),
                ')'
            )
        ).any();
}

Given 1 level of nesting:

var regex = regexGen(
    '(', nestingParentheses( 1 ), ')'
);

Generates:

/\((?:[^()]|\([^()]*\))*\)/

Given 3 levels of nesting:

var regex = regexGen(
    '(', nestingParentheses( 3 ), ')'
);

Generates:

/\((?:[^()]|\((?:[^()]|\((?:[^()]|\([^()]*\))*\))*\))*\)/
Matching an HTML Tag

This example is taken from the book: Mastering Regular Expressions

regexGen.mixin( window );
var regex = regexGen(
    '<',
    either(
        group( '"', anyCharBut('"').any(), '"' ),
        group( "'", anyCharBut("'").any(), "'" ),
        group( anyCharBut( '"', "'", '>' ) )
    ).any(),
    '>'
);

Generates:

/<(?:"[^"]*"|'[^']*'|[^"'>])*>/
Matching an HTML Link

This example is taken from the book: Mastering Regular Expressions

regexGen.mixin( window );
var regexLink = regexGen(
    '<a',
    wordBoundary(),
    capture(
        anyCharBut( '>' ).many()
    ),
    '>',
    capture(
        label( 'Link' ),
        anything().lazy()
    ),
    '</a>',
    ignoreCase(),
    searchAll()
);
var regexUrl = regexGen(
    wordBoundary(),
    'href',
    space().any(), '=', space().any(),
    either(
        group( '"', capture( anyCharBut( '"' ).any() ), '"' ),
        group( "'", capture( anyCharBut( "'" ).any() ), "'" ),
        capture( anyCharBut( "'", '"', '>', space() ).many() )
    ),
    ignoreCase()
);

Generates:

/<a\b([^>]+)>(.*?)<\/a>/gi
/\bhref\s*=\s*(?:"([^"]*)"|'([^']*)'|([^'">\s]+))/i

Here's how to iterate all links:

var capture, guts, link, url, html = document.documentElement.outerHTML;
while ( (capture = regexLink.exec( html )) ) {
    guts = capture[ 1 ];
    link = capture[ 2 ];
    if ( (capture = regexUrl.exec( guts )) ) {
        url = capture[ 1 ] || capture[ 2 ] || capture[ 3 ];
    }
    console.log( url + ' with link text: ' + link );
}
Examining an HTTP URL

This example is taken from the book: Mastering Regular Expressions

regexGen.mixin( window );
var regex = regexGen(
    startOfLine(),
    'http', maybe( 's' ), '://',
    capture( anyCharBut( '/:' ).many() ),
    group( ':', capture( digital().many() ) ).maybe(),
    capture( '/', anything() ).maybe(),
    endOfLine()
);

Generates:

/^https?:\/\/([^/:]+)(?::(\d+))?(\/.*)?$/

Here's a snippet to report about a URL:

var capture = location.href.match( regex );
var host = capture[1];
var port = capture[2] || 80;
var path = capture[3] || '/';
console.log( 'host:' + host + ', port:' + port + ', path:' + path );
Validating a Hostname

This example is taken from the book: Mastering Regular Expressions

regexGen.mixin( window );
var regex = regexGen(
    startOfLine(),
    // One or more dot-separated parts . . .
    either(
        group(
            anyCharOf( ['a', 'z'], ['0', '9'] ),
            '.'
        ),
        group(
            anyCharOf( ['a', 'z'], ['0', '9'] ),
            anyCharOf( '-', ['a', 'z'], ['0', '9'] ).multiple( 0, 61 ),
            anyCharOf( ['a', 'z'], ['0', '9'] ),
            '.'
        )
    ).any(),
    // Followed by the final suffix part . . .
    either(
        'com', 'edu', 'gov', 'int', 'mil', 'net', 'org', 'biz', 'info', 'name', 'museum', 'coop', 'aero',
        group( anyCharOf( ['a', 'z'] ), anyCharOf( ['a', 'z'] ) )
    ),
    endOfLine()
);

Generates:

/^(?:[a-z0-9]\.|[a-z0-9][-a-z0-9]{0,61}[a-z0-9]\.)*(?:com|edu|gov|int|mil|net|org|biz|info|name|museum|coop|aero|[a-z][a-z])$/
Parsing CSV Files

This example is taken from the book: Mastering Regular Expressions

regexGen.mixin( window );
var regex = regexGen(
    either( startOfLine(), ',' ),
    either(
        // Either a double-quoted field (with "" for each ")
        group(
            // double-quoted field's opening quote
            '"',
            capture(
                anyCharBut( '"' ).any(),
                group(
                    '""',
                    anyCharBut( '"' ).any()
                ).any()
            ),
            // double-quoted field's closing quote
            '"'
        ),
        // Or some non-quote/non-comma text....
        capture(
            anyCharBut( '",' ).any()
        )
    )
);

Generates:

/(?:^|,)(?:"([^"]*(?:""[^"]*)*)"|([^",]*))/

為什麼我要開發 Regular Expression Generator - RegexGen.js

RegexGen.js is a JavaScript Regular Expression Generator that helps to construct complex regular expressions.

如同我在 Regular Expression 學習筆記 所說明的:「學習 regular expression 的關鍵,不在於記憶簡寫符號,而是對引擎匹配原理的掌握。」最佳的 regular expression 學習方法,就是先學習正則引擎的匹配原理。想要快速查閱重點的話,可以參考前三篇學習筆記: (1), (2), (3),如果有充足的時間的話,當然還是建議詳閱 Mastering Regular Expressions 這本書。

然而,畢竟正則表達式的語法相當緊湊,想要一眼看懂複雜的表達式,幾乎是不可能的。首先必須熟悉正則表達式的 meta-character (元字元),然後一步一步拆解。雖然有 RegexBuddy 這樣的軟體可以幫忙拆解,但即使能正確的拆解,也可能無法了解作者 (通常是自己) 原本的思考邏輯,或者要避免的問題。

如果使用的是 Perl 或 PHP 之類的程式設計語言,可以使用註解模式來撰寫 regular expression,這樣撰寫的時候,一方面可以直接將 sub-expression (子表達式) 一一拆解開來,方便辨識,另一方面可以寫上註解,說明該 sub-expression 的用途、考量的問題、使用的技巧等。

最後,就是正則表達式本身的 meta-character 的記憶問題。如果不是經常需要接觸 regular expression 的人,相信每隔一段時間要再回過頭來使用 regular expression 時,一定會有這樣的困擾:雖然已經熟悉引擎的匹配原理,但是要撰寫的時候,恐怕還是需要查表確認才行。另外,像要匹配 "]", "}" 字元時,其實不需要 escape (轉義)、以及在 character class (字元組)裡面,匹配 "^", "-" 字元的特殊使用技巧等,不查資料的話,應該很難記得住吧?

那麼,是不是可以重新設計 regular expression 的語法,讓它不要這麼不容易理解呢? 在讀過 Easy regular expressions with JSVerbalExpressions 這篇文章,見識到 JSVerbalExpressions 之後,我知道我事實上是可以重新設計 regular expression 的語法,只不過,並不是整個重新設計,而是經由程式產生器:一個能夠產出接近完整 regular expression 語法的產生器,能夠像人寫的一樣好,並且語法本身能夠一目瞭然。

這就是 RegexGen.js 了。RegexGen.js 的設計,謹守著下列目標:

  1. 寫出來的程式碼,應該易讀易懂。
  2. 產出來的程式碼,應該要像專家寫的一樣緊湊,不要為了產生器本身容易撰寫,而產出機械式程式碼。尤其是不要產出不必要的 {}()
  3. 不再需要手動對元字元進行轉義。(除了 \ 元字元本身。或者使用了表達式置換 (regex overwrite) 功能。)
  4. 如果產生器力有未逮,無法產生理想的子表達式,必須要能夠在語法中直接指定替代的子表達式。也就是表達式置換功能。

至於為什麼是 JavaScript? 雖然 C++, Java 都是我更熟悉的語言,但是自從開始接觸 JavaScript 之後,應該說,自從讀過 JavaScript: The Good Parts 之後,我覺得開始愛上這門輕巧簡單的程式語言了。

希望 JavaScript 版的 RegexGen 只是個開始,藉由它的 open source,由此拋磚引玉,吸引同好投入開發、除錯、改進、加強,甚至開發各種語言的 regular expression generator。

參考資料

  1. Mastering Regular Expressions 2.Learn, Create, Understand, Test, Use and Save Regular Expressions with RegexBuddy
  2. JSVerbalExpressions - JavaScript Regular expressions made easy
  3. Easy regular expressions with JSVerbalExpressions
  4. JavaScript: The Good Parts
  5. Regular Expression (JavaScript) 學習筆記 (1) - 原理篇 (上)
  6. Regular Expression (JavaScript) 學習筆記 (2) - 原理篇 (下)
  7. Regular Expression (JavaScript) 學習筆記 (3) - Informal BNF 語法
  8. Open Sourced my JavaScript Regular Expression Generator - RegexGen.js
  9. RegexGen.js - Github

Regular Expression (JavaScript) 學習筆記 (3) - Informal BNF 語法

Informal BNF of Regular Expression of JavaScript (語法篇)

能夠找得到的 regular expression 的 BNF 語法不太多,以下是自己整理的 JavaScript 的 regular expression 的非正式語法,是依照自己的理解與體會所整理出來的,一定有許多錯誤、遺漏以及命名不當的地方,但還是把它列出來,幫助自己快速複習目前已掌握的 regular expression 的完整語法。讀者如果發現有任何錯誤或是有更好的表示方式,請不吝多多指教。

<regex> ::= "/"  <sub-expression-set>  "/"  [ <modifier-set> ]

一個 regex (regular expression, 正則表達式) 是由一個 sub-expression-set (子表達式集合) 組成,前後以 "/" 字元包圍,可以添加 modifier-set (模式修飾子集合) 後綴,改變 regex 的行為。

<sub-expression-set> ::= <sub-expression>  |  <sub-expression> <sub-expression-set>

一個 sub-expression-set (子表達式集合),是由一個或多個 sub-expression (子表達式) 串接組成。

<sub-expression> ::=  [  <lookahead-set>  ]  <unit-expression>  [ <quantifier>  [ <quantifier-modifier> ]  ]   [  <lookahead-set>  ]

一個 sub-expression (子表達式) 是由一個 unit-expression (單元表達式) 組成。該單元表達式可以在後面緊接著可選的 quantifier (量詞) 及 quantifier-modifier (量詞修飾子)。在前後可添加 lookahead (順序環視表達式)。

其中,可選的量詞及環視表達式(註)作用於整個單元表達式上。

註:環視表達式事實上是獨立的表達式,不需依附在單元表達式上。請參考 unit-expression (單元表達式) 及 lookahead (順序環視表達式) 的說明。

<unit-expression> ::= <expression-construct>  |  <alternation-expression-group>  |  <group>  |  <back-reference>

一個單元表達式,可以是一個 expression-construct (表達式構成元素、不可分割的表達式)、一個 alternation-expression-group (群組多選結構表達式)、一個 group (群組表達式) 或一個 back-reference (反向引用)。

所謂單元表達式,是指其本身對外具有「不受侵害」的能力。所謂不受侵害,是指單元表達式與其它表達式以任何方式結合之後,不會改變單元表達式內部的表達式的意義。關於這個議題,一部分是與正則表達式本身的組成方式有關,另一部分則與 operator (運算元) 的 precedence (優先級別) 有關。

舉例來說,多選結構表達式,是以「|」元字元來區隔多個子表達式,譬如:「fat|cat|belly|your」。若在此表達式之後,緊接著想要匹配一個 "!" 字元,如果寫成這樣:「fat|cat|belly|your!」,那麼 "!" 字元就會與多選結構裡的子表達式「your」結合,成為「your!」。這是因為,「|」元字元的優先級別較低,低於普通字元的結合 (也就是 alternation (多選結構) 運算子的優先級別低於 sequence (表達式的結合) 運算子,請參考後面關於元字元的 precedence (優先級別) 的說明)。正確的寫法,應該是:「(fat|cat|belly|your)!」,或是使用非捕獲型群組:「(?:fat|cat|belly|your)!」。

由於正則表達式是以字元為匹配單位,能夠匹配一個字元的表達式,也就是 expression-construct (表達式構成元素、不可分割的表達式),就是最小的單元表達式。這些表達式都具有「不受侵害」的能力。

當多個 expression-construct 串連在一起,構成複雜的表達式時,若要確保整個表達式具有「不受侵害」的能力,譬如,以量詞為例,若要讓量詞作用於整個表達式上,就必須使用 group (群組表達式) 將整個表達式加以包裝區隔,使其成為單元表達式。否則,量詞將僅套用在整個表達式的最後一個 expression-construct 上。

舉例來說,「your」這個表達式本身,相較於以「|」元字元來區隔的多選結構表達式,如:「fat|cat|belly|your」,「your」在其中又可以視為一個獨立的子表達式。假設現在想對整個表達式添加量詞「?」,如果寫成這樣:「your?」,由於正則表達式是以字元為匹配單位,而量詞的優先級別又高於表達式的結合,這時候量詞將只作用於最後一個字元,上面的表達式實質上相當於:「(?:you)(?:r?)」;這時候,正確的寫法應該是:「(?:your)?」。

由上面的例子也可以看出,group (群組) 的元字元 "(""(?:"")" 具有極高的優先級別 ,任何表達式一旦以群組加以保護,即成為單元表達式。

注意:也許將 alternation-expression-group (群組多選結構表達式) 歸類為 group (群組表達式) 會比較好。但是考慮到當它是整個正則表達式中唯一的表達式時,其實可以省略群組括號,表達為 alternation-expression (多選結構表達式),也就是說,它又不必然一定是群組。為了不增加 BNF 的複雜性,所以將它放在這裡。請參考 alternation-expression-group (群組多選結構表達式) 的說明。

<lookahead-set> ::= <lookahead>  |  <lookahead>  <lookahead-set>

一個 lookahead-set (順序環視表達式集合) 是由一個或多個 lookahead (順序環視表達式) 組成。

<lookahead> ::= <positive-lookahead>  |  <negative-lookahead>

一個 lookahead (順序環視表達式),可以是 positive-lookahead (肯定型順序環視表達式) 或 negative-lookahead (否定型順序環視表達式)。

注意,lookahead (順序環視) 與 lookbehind (逆序環視) 合稱 lookaround (環視)。JavaScript 只支援 lookahead,不支援 lookbehind

嚴格來說,環視表達式是一個獨立的表達式,並不需要依附在單元表達式上。雖然環視表達式實際上不是直接作用在單元表達式上,但是依據其放置的位置,實際上會對單元表達式所要匹配的內容,起到不同的約束作用。所以在這裡把環視當作單元表達式的修飾詞來介紹。說明如下:

順序環視表達式置於單元表達式前方

順序環視表達式置於單元表達式前方時,由於環視表達式匹配成功後,引擎會回到開始之前的位置,然後繼續下一個表達式的匹配。也就是說,置於前方的順序環視表達式,與單元表達式,測試文本的起始位置相同,並且測試的內容有所重疊。換句話說,單元表達式主體所匹配的內容,必須同時、依序滿足順序環視表達式以及單元表達式的匹配條件。

另外,由於順序環視表達式只是對即將由單元表達式進行匹配的文本,進行額外的測試,並不會佔有字元;單元表達式才是真正的主體,負責實際上去 match (匹配並佔有) 文本。為了與 "match" 區分,我在這裡以 "contain" 來隱含「測試相同的內容但不佔有」這個意思。這樣,若以單元表達式為主體的觀點出發,將主體的匹配行為表達為 "match",將順序環視表達式的測試行為表達為 "contain"。可以把順序環視表達式的作用描述為:

對於肯定型順序環視表達式,單元表達式所要匹配 (matches) 的內容,必須同時吻合 (also contains) 肯定型順序環視表達式能夠匹配的內容。

對於否定型順序環視表達式,單元表達式所要匹配 (matches) 的內容,必須不含 (must not contains) 否定型順序環視表達式能夠匹配的內容。

順序環視表達式置於單元表達式後方

順序環視表達式置於單元表達式後方時,由於這個時候單元表達式主體已經匹配成功 (並佔有已匹配字元),順序環視表達式所要接續測試的內容,顯然不包含單元表達式已經匹配的內容,而是緊接在其後的內容。同時,由於順序環視表達式匹配失敗時,會先回到開始之前的位置,並且觸發一個回溯,這時候除非單元表達式主體還儲存有其它備選狀態 (譬如表達式是多選結構或具有量詞),可以嘗試不同選擇 (在多選結構的情形下),或仍保持匹配成功狀態可以讓順序環視表達式由不同的路徑開始嘗試 (在量詞的情形下)。否則,這個回溯將立即導致單元表達式主體匹配失敗,並回到上上個表達式 (如果有的話)。也就是說,即使在單元表達式匹配成功後,在其匹配內容後方接續的內容,如果無法滿足順序環視表達式的匹配條件,因為回溯的關係,會噵致該單元表達式失敗。

簡單的說,若置於單元表達式後方的順序環視表達式測試失敗,則單元表達式的匹配也算失敗。

同樣地,由於單元表達式才是真正的主體,負責實際上去 match (匹配並佔有) 文本,而順序環視表達式則不佔有字元,它所測試的內容,並不會被佔有。同樣為了與 "match" 有所區分,我在這裡以 "followed by" 來隱含「測試尾隨的內容但不佔有」這個意思。在這個情形下,可以把順序環視表達式的作用描述為:

對於肯定型順序環視表達式,單元表達式所要匹配 (matches) 的內容,必須跟隨著 (followed by) 肯定型順序環視表達式能夠匹配的內容。

對於否定型順序環視表達式,單元表達式所要匹配 (matches) 的內容,不可跟隨著 (not followed by) 否定型順序環視表達式能夠匹配的內容。

順序環視表達式匹配失敗時,其所「修飾」的單元表達式即匹配失敗

綜合以上順序環視表達式置於前方與後方兩部分的討論,可以得出這樣的結論:順序環視表達式匹配失敗時,其所「修飾」的單元表達式即匹配失敗。

當然,正則表達式是由許多子表達式構成,對於同一個順序環視表達式,位於其前方的單元表達式,可將其視為是 (not) followed by;位於其後方的單元表達式,則可將其視為是 (not) contains。哪個才是對的呢? 還是都對呢? 應該是根據表達式的目的來決定吧。

<positive-lookahead> ::= "(?="  <sub-expression-set>  ")"

一個 positive-lookahead (肯定型順序環視表達式),是由一個 sub-expression-set (子表達式集合) 組成,前後分別由 "(?=" 及 ")" 符號包圍。

對於肯定型順序環視表達式,其 sub-expression-set 必需匹配文本,才算匹配成功。

<negative-lookahead> ::= "(?!"  <sub-expression-set>  ")"

一個 negative-lookahead (否定型順序環視表達式),是由一個 sub-expression-set (子表達式集合) 組成,前後分別由 "(?!" 及 ")" 符號包圍。

對於否定型順序環視表達式,其 sub-expression-set 必需不匹配文本,才算匹配成功。

<group> ::= <capture-group>  |  <non-capture-group>

一個 group (群組表達式),可以是 capture-group (捕獲型群組) 或 non-capture-group (非捕獲型群組)。

unit-expression (單元表達式) 的說明,使用群組的主要目的之一,是要使群組內的整個表達式「不受侵害」,譬如量詞的使用。
另一個用途是捕獲子群組的內容,請參考 capture-group (捕獲型群組) 的說明。

<capture-group> ::= "("  <sub-expression-set>  ")"

一個 capture-group (捕獲型群組),是由一個 sub-expression-set (子表達式集合) 組成,前後分別由 "(" 及 ")" 符號包圍。

當正則表達式可以匹配文本內容時,會回傳整個匹配的內容。如果希望額外回傳其中的部分特定內容,可以將對應的子表達式使用捕獲型群組加以包圍。整個正則表達式可以使用多個群組,也可以巢狀套疊。回傳的順序,依照群組的左括號 "(" 出現的順序排列。

捕獲型群組所匹配的內容,可以在正則表達式中直接參照,請參考 back-reference
若要在 JavaScript 程式中參照捕獲型群組,可使用 $1, $2 對應,依此類推。

<non-capture-group> ::= "(?:"  <sub-expression-set>  ")"

一個 non-capture-group (非捕獲型群組),是由一個 sub-expression-set (子表達式集合) 組成,前後分別由 "(?:" 及 ")" 符號包圍。

使用非捕獲型群組,可以避免使用捕獲型群組時,引擎為了保留捕獲的內容,而在嘗試和回溯的過程中,不斷儲存和丟棄捕獲的內容所花費的時間,增進效率。缺點是會使正則表達式看起來更複雜。

<back-reference> ::= "\"  <number>

一個 back-reference (反向參照) 是由 "\" 字元緊接著一個數字組成。

JavaScript 對數字大小似乎沒有限制,即範圍為 1 ~ Number.MAX_VALUE。這也就是說,對於捕獲型群組的數量沒有限制。但是,在部分流派中,如 PHP,數字必須為 1 ~ 99 的任意數字。在 sed 中甚至只能是 1 ~ 9

反向參照的意義,是要匹配參照的捕獲型群組所捕獲的內容,也就是反向參照匹配的位置出現的內容,應該與捕獲型群組匹配的內容相同。通常用在內容必須成對出現,或重複多次的情況。

<expression-construct> ::= <raw-character>  |  <meta-character-escape>  |  <ascii-character-escape>  |  <unicode-character-escape>  |  <character-class-shorthand>  |  <character-class>  |  <negative-character-class>

一個 expression-construct (表達式構成元素、不可分割的表達式),可以是 raw-character (普通字元) 、 meta-character-escape (已轉義元字元)、ascii-character-escape (ASCII 跳脫字元)、unicode-character-escape (Unicode 跳脫字元)、character-class-shorthand (簡寫字元組)、character-class (字元組) 或 negative-character-class (排除型字元組)。

由於正則表達式是以字元為匹配單位,基本上,能夠匹配單一一個字元的表達式,就是不可分割的表達式。請參考 unit-expression (單元表達式) 的說明。

<raw-character> ::= any character that is not <meta-character>

一個 raw-character (普通字元),是任何不是 meta-character (元字元) 的字元。在 JavaScript 中,包含任意 Unicode 字元。

<meta-character> ::= "^"  |  "|"  |  "."  |  "*"  |  "+"  |  "-"  |  "?"  |  "\"  |  "["  |  "]"  |  "{"  |  "}"  |  "("  |  ")"  |  "$"

正則表達式的 meta-character (元字元),只有 "^"、"|"、"."、"*"、"+"、"-"、"?"、"\"、"["、"]"、"{"、"}"、"("、")" 及 "" 十五個字元。

注意到其中 "-"、"]" 及 "}" 三個字元。前兩個字元只有在它們位於沒有 escape (轉義) 的 "[" 字元之後,也就是在 character-class (字元組) 中,才成為元字元。而 "}" 字元只有當位於一個沒有轉義的 "{" 字元之後,也就是以 「{m,n}」形式存在,成為量詞時,才成為元字元。對於這三個字元,當要做為普通字元進行匹配時,在任何時候都沒有必要進行轉義。

另外,由於 JavaScript 使用 "/" 字元包圍的方式來表現正則表達式 literal。當使用這種語法時,必須在表達式內部對 "/" 字元進行轉義,也就是以「\/」的方式表示 "/" 字元。而當以字串形式表現正則表達式時,就不需要進行轉義。由於這是宿主語言的特性使然,因此不將 "/" 字元視為 meta-character (元字元)。

元字元的 precedence (優先級別)

根據 O'Reilly Learning Perl 3rd Edition, Chapter 8: More About Regular Expressions 這篇文章,列出了元字元的 precedence (優先級別) :

Group (群組字元):「()」、「(?:)」。
Quantifiers (量詞字元):「*」、「+」、「?」、「{,}」。
Anchors (錨定字元):「^」、「$」,包括「\b」、「\B」 (字詞邊界) 也在這個等級;sequence (序列),是指串接在一起的表達式,包括字元序列也是 (雖然 sequence 實際上沒有使用任何元字元)。
Alternation (多選結構):「|」。

<meta-character-escape> ::= "\"  <meta-character>

一個 meta-character-escape (已轉義元字元),是由 "\" 轉義元字元,緊接著一個 meta-character (元字元) 組成。
meta-character (元字元) 的說明,注意到當要做為普通字元進行匹配時,"-""]""}" 三個字元不需要進行轉義。

<character-class-shorthand> ::= "."  |  "\0"  |  "\b"  |  "\B"  |  "\d"  |  "\D"  |  "\f"  |  "\n"  |  "\r"  |  "\s"  |  "\S"  |  "\t"  |  "\v"  |  "\w"  |  "\W"  |  "\c" ["A"-"Z"]

一個 character-class-shorthand (簡寫字元組),表示匹配一個字元。

簡寫字元組通常用來表示一些常用的字元組,以縮短表達式的長度。或是用來表現一些不容易顯示、列印的字元,如空白字元、控制字元等。

如原理篇的前言所述,不需要花時間記憶這些簡寫符號。此項目使用灰色淡化處理的目的是特別要強調這一點。所以這裡也刻意不詳列每個簡寫符號的說明。詳細的說明請參考 Mozila Developer Network: Writing a Regular Expression Pattern

<ascii-character-escape> ::= "\x" <HH>

一個 ascii-escape-character (ASCII 跳脫字元),是由一個 "\x" 符號,加上 2 個 16 進位數字字元組成。

<unicode-character-escape> ::= "\u" <HHHH>

一個 unicode-escape-character (Unicode 跳脫字元),是由一個 "\x" 符號,加上 4 個 16 進位數字字元組成。

<character-class> ::= "["  <character-class-character-set>  "]"

一個 character-class (字元組) 是由一個 character-class-character-set (字元組字元集合) 構成。整個字元組前後分別以 "[" 及 "]" 字元符號包圍。

字元組的意義為,匹配若干字元之一,且僅匹配一個字元,該字元必須為 character-class-character-set (字元組字元集合) 所列舉的字元。

<negative-character-class> ::= "[^"  <character-class-character-set>  "]"

一個 negative-character-class (排除型字元組) 是由一個 character-class-character-set (字元組字元集合) 構成。整個排除型字元組前後分別以 "[^" 及 "]" 字元符號包圍。

排除型字元組同樣必須匹配一個字元,且僅匹配一個字元,該字元不可出現在 character-class-character-set (字元組字元集合) 所列舉的字元中。 要強調的是,排除型字元組並非不匹配字元,而是匹配一個未列出的字元。

<character-class-character-set> ::= <character-class-construct>  |  <character-class-construct>  <character-class-character-set>

一個 character-class-character-set (字元組字元集合),是由一個或多個 character-class-construct (字元組構成元素) 構成。

<character-class-construct> ::= <character-class-raw-character>  |  <character-class-range>  |  <character-class-shorthand>  |  <ascii-character-escape>  |  <unicode-character-escape>  |  <character-classes-meta-character-escape>

一個 character-class-construct (字元組構成元素),可以是 character-class-raw-character (字元組普通字元)、character-class-range (字元範圍)、character-class-shorthand (簡寫字元組)、ascii-character-escape (ASCII 跳脫字元)、unicode-character-escape (Unicode 跳脫字元) 或 character-classes-meta-character-escape (已轉義字元組元字元)。

<character-class-raw-character> ::= any character that is not <character-classes-meta-character>

一個 character-class-raw-character (字元組普通字元),是除了 character-classes-meta-character-escape (已轉義字元組元字元) 之外的任意字元。

<character-class-range> ::= <character-class-range-construct>  "-"  <character-class-range-construct>

一個 character-class-range (字元範圍),是由兩個 character-class-range-construct (字元範圍構成元素) 組成,中間以字元組元字元 "-" 連結。

字元範圍所能匹配的字元,是由起始字元所指定的字元碼,至結束字元所指定的字元碼,兩者之間所界定的連續範圍內的字元碼所對應的字元。包含起始字元及結束字元。

<character-class-range-construct> ::= <character-class-raw-character>  |  <ascii-character-escape>  |  <unicode-character-escape>

一個 character-class-range-construct (字元範圍構成元素),可以是一個 character-class-raw-character (字元組普通字元) 、一個 ascii-character-escape (ASCII 跳脫字元) 或一個 unicode-character-escape (Unicode 跳脫字元)。

<character-classes-meta-character-escape> ::=  "\"  <character-class-meta-character>

一個 character-classes-meta-character-escape (已轉義字元組元字元) ,是由一個 "\" 轉義字元,加上一個 character-classes-meta-character (字元組元字元) 構成。

<character-class-meta-character> ::= "-"  |  "]"  |  "\"  |  "^"

一個 character-classes-meta-character (字元組元字元),只能是 "-""]""\""^" 四個字元之一。

其中 "-""^" 字元,放在特定位置下,可以當作普通字元來匹配而不需要 escape (轉義):
"^" 字元,若不是第一個字元,即在「[ ... ^ ... ]」的情形下,可視為普通字元,可以不進行轉義。
"-" 字元,在以下兩種狀況,可視為普通字元,可以不進行轉義:
若出現在第一個字元或最後一個字元,即「[- ... ]」 、「[^- ... ]」、「[... -]」或 「[^ ... -]」的情況;
緊接在某個字元範圍,或 character-shorthand 之後出現,即「[a-c-def]」或「[\w-0-9]」的情況。
綜合上述,字元組若要匹配包含 "-""^" 字元時,
建議永遠將 "-" 放在字元組第一個字元,將 "^" 放在字元組最後一個字元。
這樣可以減少使用轉義字元,使正則表達式更清晰易懂。

參考:
What literal characters should be escaped in a regex?
How to escape square brackets inside brackets in grep

注意:上述兩篇參考文章提到 "]" 字元,若出現在第一個字元,即「[] ... ]」 或 「[^] ... ]」 的情況,可視為普通字元,可以不進行轉義。但在 JavaScript 似乎不是這樣,在 Chrome 下測試,並不支援。譬如:

/[]a-f]/.exec(']') // null
/[]]/.exec(']') // null

<alternation-expression-group> ::= "(" <alternation-expression> ")"  |  "(?:"  <alternation-expression>  ")"

一個 alternation-expression-group (群組多選結構表達式),可以是捕獲型群組、或非捕獲型群組所包圍的 alternation-expression (多選結構表達式)。

注意,由於 alternation-expression (多選結構表達式) 的 "|" 元字元的 precedence (優先級別) 較低,也就是說,多選結構表達式本身不是單元表達式,不具「不受侵害」的能力 (參考單元表達式的說明)。所以,基本上,除非整個正則表達式的唯一表達式就是多選結構表達式,在這樣的情況下,多選結構表達式才不需要使用群組加以保護。否則,多選結構表達式都應該要以群組加以保護,表示為 alternation-expression-group (群組多選結構表達式)。

注意,由於上述特性,在盡量不增加整個 BNF 的複雜性的原則下,其它表達式的 BNF 都是參照群組多選結構表達式。但記住在前述例外情況下,可以不使用群組,而直接使用多選結構。

<alternation-expression> ::= <sub-expression-set>  "|"  <sub-expression-set>  |  <sub-expression-set>  "|"  <alternation-expression>

一個 alternation-expression (多選結構表達式),是由兩個以上的 sub-expression-set (子表達式集合) 構成,子表達式集合之間以元字元 "|" 分隔。

多選結構表達式表示匹配任意子表達式。在 JavaScript 中,匹配的測試順序,是依照子表達式列舉的順序。

注意,"|" 元字元的 precedence (優先級別) 較低,所以多選結構表達式不是單元表達式。請參考 alternation-expression-group (群組多選結構表達式) 及 unit-expression (單元表達式) 的說明。

<quantifier> ::= "?"  |  "+"  |  "*"  |  "{"  <quantifier-lower-bound>  ","  <quantifier-upper-bound>  "}"

一個 quantifier (量詞),是由一個 "?" 、 "*" 或 "+" 簡寫元字元構成,或者以 { lower, upper } 的完整形式表示。

量詞的作用類似於英文文法中的副詞。在英語中,副詞用來修飾動詞。
而在正則表達式中,量詞用來描述其所修飾 (作用) 的表達式必須匹配的次數。
每個量詞皆有匹配次數的下限及上限限制,分別如下:

? : 表示可有可無。亦即,匹配 0 至 1 次。
* : 表示可有可無,且不限定上限。亦即,匹配 0 至無限次。
+ : 表示一定要存在,但不限定上限。亦即,匹配 1 至無限次。
{ m, n } : 表示下限為 m,上限為 n,其中 m、n 為自然數 (或說包含 0 的正整數)。如果只有下限,可以簡寫如: { m, };如果下限與上限一致,可以簡寫如: { m }。JavaScript 不支援只有上限的縮寫形式: { , n },必須表達為 { 0, n }

注意:標準量詞是匹配優先的。

<quantifier-lower-bound>, <quantifier-upper-bound> ::= <number>

在量詞的完整形式中,上限與下限必須是自然數 (包含 0 的正整數)。

<quantifier-modifier> ::= "?"

一個 quantifier-modifier (量詞修飾子),是由一個 "?" 元字元表示。

當標準量詞附加了量詞修飾子,匹配的行為由匹配優先轉為忽略優先。

注意: 事實上,並沒有量詞修飾子這種說法。JavaScript 中的標準量詞 (匹配優先),分別為 ?*+{m,n}。其對應的忽略優先版本,分別為 ??*?+?{m,n}?

注意: 量詞有三種:greedy (貪婪) 匹配優先量詞、lazy (懶惰) 忽略優先量詞,以及 possessive (佔有) 佔有優先量詞。JavaScript 不支援佔有優先量詞。多數支援占有優先量詞的流派,使用 "+" 字元來表示,即其對應的占有優先版本,分別為 ?+*+++{m,n}+。佔有優先量詞與匹配優先量詞相同,都是匹配優先,差別在於佔有優先量詞一旦匹配字元,便不再釋放。主要的使用時機是在匹配失敗時,減少不必要的回溯所導致的絕不可能匹配的無謂嘗試,最佳化引擎的匹配速度。

<modifier-set> ::= <modifier>  |  <modifier> <modifier-set>

一個 modifier-set (模式修飾子集合),是由一個或多個 modifier (模式修飾子) 組成。

<modifier> ::= "g"  |  "i"  |  "m"  |  "y"

一個 modifier (模式修飾子),可以是 "g""i""m""y" 之一的一個字元。

意義分別如下:

g : Global search. 預設情形下,只找出文本中第一個匹配的部分。開啟 global search 模式後,會找出文本中的所有匹配的部份。

i : Case-insensitive search. 忽視文本中的字元大小寫。(尚不清楚 JavaScript 是否支援忽視 Unicode 字元的大小寫。)

m : Multi-line search. 預設情形下,元字元 "^""$" 分別匹配整個文本的開頭與結尾。當文本中含有斷行符號,由斷行符號區隔出多行內容時,為使 "^""$" 分別匹配文本中每行的開頭與結尾,可以開啟多行搜尋模式。

y : Sticky search. 如果未開啟 global search 模式,也不開啟 sticky search 模式的情況下,每次由 JavaScript 對同一文本啟動正則表達式搜尋時,都只會由文本的開頭開始進行匹配,所以總是找到第一個匹配結果。開啟 sticky search 模式後,每次由 JavaScript 對同一文本啟動正則表達式搜尋時,都會由上一次搜尋的結束位置,也就是所謂目前位置開始進行匹配。(注意:這是 Firefox 才有的功能。)

參考資料

  1. BNF
  2. 找到的 regular expression 的 BNF 語法
  3. PHP: preg_replace - Manual
  4. StackOverflow: Circumvent the sed backreference limit \1 through \9
  5. O'Reilly Learning Perl 3rd Edition, Chapter 8: More About Regular Expressions
  6. Mozila Developer Network: Writing a Regular Expression Pattern
  7. What literal characters should be escaped in a regex?
  8. How to escape square brackets inside brackets in grep
  9. Regular Expression (JavaScript) 學習筆記 (1) - 原理篇 (上)
  10. Regular Expression (JavaScript) 學習筆記 (2) - 原理篇 (下)

Regular Expression (JavaScript) 學習筆記 (2) - 原理篇 (下)

前言

上一篇介紹了正則引擎的基本功能與原理,接下來介紹功能更為強大的 lookaround (環視)。

Lookaround (環視) 不會佔用匹配字元

有時候,要匹配的文本主體,需要滿足的條件不只一個;或者,需要對上下文進行多重約束。

然而,對於一般的表達式而言,一旦文本匹配成功,便會由表達式所佔有;也就是說,同一段文本,絕不可能同時由兩個表達式所匹配。

另一方面,有時候,需要確保匹配的文本主體不含特定的內容,但是這個特定的內容,不是一個單一字元。在單一字元的情況下,我們可以使用否定型字元組來處理。但是在多重字元的情況下,卻很難使用一般的表達式辦到。

在這樣的需求下,許多新的 flavor (流派) 開始支援 lookaround (環視) 的功能。

對於環視表達式,最重要的特性就是,它們不會 consume (吃掉) 任何字元:不論匹配結果是否成功、不論是肯定型還是否定型、不論是順序還是逆序,引擎都會回到開始匹配前的原點,並且丟棄所有匹配的內容以及過程中儲存的備選狀態。在此之後,引擎才會根據環視表達式的匹配成功與否,進行下一個動作:當匹配成功時,引擎由目前位置繼續下一個表達式的匹配;當匹配失敗時,引擎回溯 (請參考前面回溯的說明) 到上一個儲存點 (這是由上一個表達式所儲存),繼續由上一個表達式儲存的下一個選擇進行嘗試 (或繼續回溯到上上個表達式)。

(環視使用的是一種擴展的 NFA:NFA-λ (也叫做 NFA-ε 或有 ε 移動的 NFA),它允許轉換到新狀態的變換不消耗任何輸入符號。)

可以這樣想像,lookaround (環視) 就像是站在原地不動,向前或向後觀望。依照環視檢視文本的方向,可以區分為 lookahead (順序環視) 和 lookbehind (逆序環視)。

Lookahead (順序環視)

Lookahead (順序環視),或稱為「順向環視」、「向前環視」,顧名思義是在原地向前看的意思。也就是先偷看還沒看過的內容,確認是否符合預期,只有在接下來的內容能夠滿足指定條件的前提下,才繼續由下一個表達式、由目前位置開始後續的測試。(注意這裡的「前」,是 ahead 的意思,是指對引擎而言,擺在引擎前方尚未測試過的文本。與中文「先前」,previous 的意思不同。由於在中文裡,ahead 與 previous 的翻譯都有「前」的意思,但是實際上方向卻完全相反,為避免混淆,建議使用「順序環視」,以強調環視測試文本的方向與引擎測試文本的方向,兩者之間的關係。)

順序環視表達式的語法為:

肯定型:

(?=expression)

否定型:

(?!expression)

其中,對於肯定型順序環視表達式,其子表達式必需匹配文本,才算匹配成功。對於否定型順序環視表達式,其子表達式必需不匹配文本,才算匹配成功。 (請參考後面 BNF 語法的說明)

Lookbehind (逆序環視)

Lookbehind (逆序環視),或稱為「逆向環視」、「向後環視」,顧名思義是在原地往後看的意思。也就是由目前位置回頭測試文本。只有在目前位置之前的內容能夠滿足指定條件的前提下,才繼續由下一個表達式、由目前位置開始後續的測試。(注意這裡的「後」,是 behind 的意思,是指對引擎而言,擺在引擎後方已經測試過的文本。與中文「後續」,next 的意思不同。由於在中文裡,behind 與 next 的翻譯都有「後」的意思,但是實際上方向卻完全相反,為避免混淆,建議使用「逆序環視」,以強調環視測試文本的方向與引擎測試文本的方向,兩者之間的關係。)

逆序環視表達式的語法為:

肯定型:

(?<=expression)

否定型:

(?<!expression)

其中,對於肯定型逆序環視表達式,其子表達式必需匹配文本,才算匹配成功。對於否定型逆序環視表達式,其子表達式必需不匹配文本,才算匹配成功。 (請參考後面 BNF 語法的說明)

注意,JavaScript 只支援 lookahead,不支援 lookbehind。這裡特意列出以完整說明 NFA 引擎的正則表達式的能力。

注意:順序環視表達式所允許的子表達式,在多數的流派中都沒有特殊限制。而JavaScript 不支援的 lookbehind (逆序環視表達式),通常限定子表達式的匹配長度必須固定。

匹配的文本主體需要滿足多重條件

針對本節開頭所描述的問題,當要匹配的文本主體,需要滿足的條件不只一個時,可以將順序環視表達式置於用來匹配主體的表達式的前方。或者將逆序環視表達式置於其後方。像這樣:

(?=lookahead-expression-1)(?!lookahead-expression-2)(main-expression)

(main-expression)(?=lookbehind-expression-1)(?!lookbehind-expression-2)

譬如,下面的表達式,來自於 Mastering Lookahead and Lookbehind 這篇文章,用來檢查密碼是否符合規範:

/^(?=.*?[a-z])(?=.*?[A-Z])(?=.*?\d)\w{6,10}$/

其中:

\w{6,10}」 就是匹配主體,要求匹配文本必須是英數字或底線,包含最少 6 個字元,最多 10 個字元。
(?=.*?[a-z])」 是肯定型順序環視,要求匹配的文本中,必須含有小寫的英文字母。
(?=.*?[A-Z])」 是肯定型順序環視,要求匹配的文本中,必須含有大寫的英文字母。
(?=.*?\d)」 是肯定型順序環視,要求匹配的文本中,必須含有數字字母。

注意,其中「.*?」是前面介紹過的忽略優先量詞,意思是,先忽略,直接匹配後面的表達式。若後面的表達式匹配失敗,再回過頭來由「.」匹配一個任意字元,然後又繼續嘗試匹配後面的表達式。在這裡的效果,就是不斷地測試文本是否含有後面的表達式指定的字元,直到測試成功 (匹配),或抵達文本的結尾,然後失敗 (不匹配)。由於這裡都是肯定型

整個表達式,意義就是:匹配 6 到 10 個英數字或底線字母,其中必須包含大寫英文字母、小寫英文字母、數字字母至少各一個字元。

匹配文本的上下文需要滿足指定條件

當要匹配的內容,必須出現在特定的字元之後。

由於 JavaScript 不支援 lookbehind,這裡只列出 Mastering Regular Expressions 一書 66 頁的 Perl 語言的範例,該範例利用逆序環視來為數值加上每三位數出現一次的 "," 逗號,使數值的位數更容易分辨:

$text =~ s/(?<=\d)(?=(\d\d\d)+(?!\d))/,/g;

基本原理就是,添加逗號時必須由個位數開始計算,每三位數添加一個逗號。實際上,要插入逗號的「位置」是,左邊有數字 (上文),右邊的數字的個數正好是 3 的倍數 (下文)。以下讓我們一步一步來看建構的過程:

要找出個位數,先要找出一整串數字,因為這整串數字最右邊的數字就是個位數字。由此導出「\d+」。
由於要每三位數添加一個逗號,這串數字至少要含有三位數,少於三位數就不需要添加逗號了。由此導出「\d\d\d」。
但是這樣一來,超過三位數的數字,匹配到的就會是最高位數開始往右算的三個數字,而不是由個位數往左算的三個數字。譬如 "12345" 這串數字,匹配到的將是 "123" 而不是 "345"。仔細想想個位數有什麼特別的地方呢? 就是它的右邊 (下文) 沒有數字。這時候第一個否定型向前環視登場了,我們可以使用「(?!\d)」來保證右邊沒有數字,也就是確保匹配的是由個位數往左算的三個數字。由此導出的是「(\d\d\d)(?!\d)」。
由於每三位數都要添加一個逗號。因此應該是「(\d\d\d)+(?!\d)」。
由於要添加逗號的位置,是位於連續三位數的左邊的「位置」,上述的表達式卻會吃掉字元,因此需要使用順序環視來進行測試,以保持位置不變。由此導出「(?=(\d\d\d)+(?!\d))」。
同上,找到的這個「位置」,它的左邊 (上文) 也必須有數字。否則,這表示已經到達整串數字的最高位數,那麼這個「位置」也不需要添加逗號。這時候,就必須使用肯定型逆序環視表達式,來確保這個位置的左邊確實有數字存在。由此導出「(?<=\d)(?=(\d\d\d)+(?!\d))」。
上面的表達式,一次只會匹配一個「位置」(在數值字串所有需要插入逗號的位置的最左邊那個)。同時字串中可能包含多個數值字串,必須全部處理。所以必須使用 global search,找出所有的數值字串的適當「位置」。由此導出「/(?<=\d)(?=(\d\d\d)+(?!\d))/g」。
配合 Perl 語言提供的功能,可以在以上每個找到的「位置」,插入 "," 逗號。由此導出「$text =~ s/(?<=\d)(?=(\d\d\d)+(?!\d))/,/g」。

書中也指出,可以使用捕獲型群組,來模擬逆序環視:

$text =~ s/(\d)(?=(\d\d\d)+(?!\d))/$1,/g;

這裡最前面的「(\d)」捕捉的,正是上面第 6 點提到的肯定型逆序環視表達式捕捉到的那個數字字元,所以使用置換功能來插入逗號時,必須包含該字元,所以取代字串為「$1,」。

另外,舉個簡單的例子,若需要匹配 $9999 這樣的字串,又不想包含前面的 "$",只想要取得數值字串時,可以使用下列表達式:

/(?<=$)\d+/

同樣,若不使用逆序環視,可以使用:

/$(\d+)/

這裡與前面插入逗號的例子相反,捕捉的是數值字串本身,所以「$1」代表的就是我們所要的結果。

確保匹配的文本主體不含特定內容

到這裡應該很清楚了,這個情況可以使用否定型順序環視來實現。

這裡引用 Mastering Regular Expressions, 167 頁的例子,用來匹配一個 HTML 中,完整的 <b></b> 標籤。

首先,若使用匹配優先量詞,「<b>.*</b>」,非常有可能會匹配到 "<b> ... </b> ... <b> ... </b>" 這樣的結果。
使用忽略優先量詞,「<b>.*?</b>」,仍然有可能匹配到 "<b> ... <b> ... </b>" 這樣的結果。
由這一點可以知道,忽略優先量詞並不是排除型字元組的多字元版的完美替代方案。

使用否定型順序環視,就可以安全地排除多重字元:

/<b>(?:(?!<\/?b>).)*<\/b>/

(這裡的「(?: ... )」代表非捕獲型群組。請參考後面 BNF 語法的說明。)

注意,在這個例子裡,"<b>""</b>" 同時是必須包含的內容 (也就是做為標籤的邊界符號),同時又是 "<b>""</b>" 標籤之間的內文 (對 JavaScript 而言,就是 innerHTML) 中不可出現的內容 (否則找到的就不是一個獨立的標籤了)。因此,這裡的否定型順序環視表達式,必須與「.」元字元,一同由「*」量詞一起修飾。也就是說,在開頭的「<b>」表達式匹配完之後,在匹配內文時,必須逐字元檢視,確認該字元起始的文本,不是 "<b>""</b>",如果不是,就可以把該字元視為內文,由「.」匹配。否則,一旦遭遇 "<b>""</b>",否定型順序環視表達式匹配失敗,導致「*」量詞回溯到上一個儲存位置,也就是 "<" 之前的位置,然後「*」量詞結束 (並成功) 匹配 (記住「*」量詞可以匹配 0 次)。接著,再由「<\/b>」繼續匹配。

完全排除特定內容

有一個簡化的特別情況,如果要排除的內容本身,不需要以任何形式存在於要匹配的內容中,也就是單純要加以排除時,其實有更快速的方法,就像前面的檢查密碼範例一樣,只是這裡使用的是否定型順序環視表達式:

/^(?!.*?hede).*$/

這裡的 "hede" 是要排除的字串。其中「.*?」是前面介紹過的忽略優先量詞,意思是,先忽略,直接匹配後面的表達式,也就是「hede」。若後面的表達式匹配失敗,再回過頭來匹配一個任意字元,然後又繼續嘗試匹配後面的表達式。在這裡的效果,就是環視表達式不斷地測試文本是否含有 "hede" 字串,若抵達文本的結尾都沒有發現 "hede" 字串,則否定型順序環視表達式匹配成功。於是,引擎又回到原點,也就是文本的開始位置,然後由「.*」匹配優先量詞,直接匹配到字串尾端。匹配成功。

這個表達式的效率,在最差的情形下,都比 /^(?:(?!hede).)*$/ 快上一倍以上。可以參考 jsfiddle.net 這裡的比較結果,以及我在 StackOverflow 的回答。

小結

到這裡,正則引擎最重要的功能與原理都介紹完畢了。記得在學習時,可以搭配查閱 非正式 BNF 語法 快速掌握正則表達式的語法。

參考資料

  1. NFA-λ (也叫做 NFA-ε 或有 ε 移動的 NFA)
  2. Mastering Lookahead and Lookbehind
  3. Mastering Regular Expressions 一書 66 頁的 Perl 語言的範例
  4. Mastering Regular Expressions, 167 頁
  5. jsfiddle.net
  6. StackOverflow
  7. Regular Expression (JavaScript) 學習筆記 (1) - 原理篇 (上)
  8. Regular Expression (JavaScript) 學習筆記 (3) - Informal BNF 語法

Regular Expression (JavaScript) 學習筆記 (1) - 原理篇 (上)

前言

過去初學 regular expression 時,看了許多入門教學及參考資料,但多數資料幾乎都只是將一些表達式符號一一列出,然後再舉一些無關緊要的範例,以為這樣就可以弄懂 regular expression 了。做為初學者,看到這麼多的表達式符號,就以為 regular expression 很難學。直到看了 Mastering Regular Expressions 這本書,才知道其實是被誤導了。雖然 regular expression 提供了許多簡寫符號,但是大多數的簡寫符號多半只是為了縮短表達式的長度,這些簡寫符號只要在使用的時候查一下,實際使用過就可以熟悉了,根本不需要特別花時間記憶。其實學習 regular expression 的關鍵,不在於記憶簡寫符號,而是對引擎匹配原理的掌握。

正則表達式

正則表達式是強大、極富彈性、高效的文本處理工具。

其通用的模式表示法,具有如同迷你程式語言般的功能,賦予使用者描述和解析文本的能力。配合上特定工具提供的支援,正則表達式能夠添加、移除、分離 (isolate)、疊加 (fold)、插入 (spindle) 和截斷 (mutilate) 各類型的文本和數據。

完整的正則表達式是由兩類不同的字元構成,特殊字元是由 *, +, ?, ^ 之類的字元構成,稱為 metacharacters (元字元),其餘的字元稱為 literal (文本字元) 或是 normal text characters (普通文字字元)。可以把 metacharacters 想像為程式語言中的 operator (運算子),而 literal 則是 operand (運算元)。(事實上,literal 本身也應該算是 operator: literal 中的每個字元,都代表必須匹配一個字元,而且是逐字元匹配。)

完整的正則表達式是由如上述的小的建構模塊單元組成。每個單獨的建構模塊都很簡單,過它們能夠以無窮多種方式組合,要將它們結合起來實現特殊目標,則必須依靠經驗。

歷史

正則表達式的源起,是代數學上的 regular sets (正則集合)。
代數學家 Stephen Cole Kleene 發明了一套簡潔的表示正則集合的方法,稱為 regular expressions (正則表達式)。

Stephen Cole Kleene 的正則表達式,使用的是 Deterministic Finite Automaton (DFA, 確定性有限狀態自動機),是一種不使用回溯的有限狀態機。是真正數學意義上的正則集合。

而由 Perl 語言所引領風潮的正則表達式,包括 JavaScript,所採用的正則引擎則屬於 Nondeterministic Finite Automaton (NFA, 非確定性有限狀態自動機) 引擎。這種引擎實際上已經不是數學意義上的正則表達式了。Mastering Regular Expressions 的作者 Jeffrey E. F. Friedl 將這種引擎比擬為「燃油引擎」,意思是它跟正統的 DFA 引擎相比,更難掌控,但威力強大,如果控制得宜,可以做到 DFA 引擎做不到的功能。 (簡單地說,可以玩出更多花樣。)

NFA 引擎匹配基本原理

這裡介紹的匹配原理,是以描述程式處理邏輯的方式說明,不涉及數學公式。以下文章在內文中提到正則表達式時,會以「expression」的方式表示,在提到文本以及匹配的文本時,會以 "literal" 的方式表示。

由文本的起始位置開始,逐字元測試、匹配整個正則表達式

NFA 引擎進行匹配時,是以字元為單位,
由文本的起始位置,事實上是第一個字元之前的位置,開始嘗試匹配。
由此位置,逐字元測試整個正則表達式能匹配文本的各種可能性。

若由當前位置所進行的各種可能性的嘗試都失敗時,
則引擎將捨棄當前位置所鄰接的字元,向前推進到文本的下一個字元之前的位置
由此位置,繼續測試整個正則表達式能匹配文本的各種可能性。

在引擎找到匹配結果前,必須在文本的所有位置上重複上述過程。
過程中,一旦其中任何一種可能性能夠通過整個正則表達式的測試,則整個正則表達式匹配成功。

若引擎推進到最後一個字元後面的位置,在此位置的各種嘗試仍告失敗,
則整個正則表達式匹配失敗。

由上可知,當引擎宣告匹配失敗時,引擎必然嘗試了所有的可能性。
所以必須注意當匹配失敗時,可能會有的效率問題。

優先選擇最前端的匹配結果 (The Match That Begins Earliest Wins)

由於 NFA 引擎是由文本的起始位置,逐字元測試整個正則表達式,
同時,在不斷嘗試的過程中,一旦其中任何一種可能性能夠通過測試,則整個正則表達式匹配成功。
因此,只要正則表達式能匹配成功,則其必定是在所有可能結果的最前端。

譬如,下例的匹配結果,是 "belly",而不是 "fat"

 "The dragging belly indicates your cat is too fat".match( /fat|cat|belly|your/ ); // [ "belly" ]

(這裡的 「fat|cat|belly|your」代表多選結構。由「|」所分隔的任一表達式,如果能成功匹配文本,即代表該多選結構成功完成匹配。請參考後面 BNF 語法的說明。)

雖然「fat」出現在多選結構中的第一項,但引擎在測試完所有的可能性之前,絕不會向前推進,略過當前字元。引擎會逐字元測試整個正則表達式的所有可能性,過程中不斷失敗,然後向前推進。直到當引擎推進到『^ belly』這個位置時,此時,可選結構中的「belly」通過測試,因此正則表達式測試成功,匹配結果為 "belly"

標準匹配量詞是匹配優先的 (The Standard Quantifiers Are Greedy)

除了直接指定簡單的匹配字元文字 (literal),正則表達式也能指定要匹配的內容的重複次數,這就是 quantifier (量詞) 的作用。

標準匹配量詞有 +, ?, *, {m,n}。(詳見後面 BNF 語法的說明)

使用量詞來約束子表達式時,進行嘗試的次數是存在下限和上限的。
而標準匹配量詞總是希望獲得最長的可能匹配。
也就是說,它們總是嘗試匹配盡可能多的字元,直到匹配上限為止。
這正是它的名字 greedy (貪婪) 的由來。

譬如:

 "Subject: Hi there".match( /Subject: (.*)/ );     // [ "Subject: Hi there", "Hi there" ]

 "Subject: Hi there".match( /Subject: (.*)(.*)/ ) // [ "Subject: Hi there", "Hi there", "" ]

(這裡的 「.」代表匹配任意字元;
*」代表前面的字元,也就是這裡的「.」,可以匹配最少 0 次,最多無限次;
()」代表要將匹配的內容,另外捕捉、儲存下來。
請參考後面 BNF 語法的說明。)

第一個例子,唯一的「(.*)」匹配 "Subject: " 之後的全部內容: "Hi there"
第二個例子,第一個「(.*)」仍然匹配 "Subject: " 之後的全部內容: "Hi there"。 而第二個「(.*)」則匹配到空內容 ""

這是因為「*」量詞是匹配優先的,所以第一個「(.*)」會盡可能匹配所有可以匹配的字元,
由於「.」代表匹配任意字元,所以「(.*)」會匹配 "Subject: " 之後的所有的字元,直到整個文本結束。
即使在第二個例子中,存在有兩個「(.*)」,第一個「(.*)」仍然會嘗試匹配所有的字元,直到文本結束。
由於此時再無其它可匹配字元,第一個「(.*)」匹配結束,由第二個「(.*)」開始嘗試匹配。
在此情況下,第二個「(.*)」將首先從文本的最後一個字元後面的位置開始進行測試。
這時候雖然已經沒有字元可以匹配了,但由於「*」量詞可以匹配最少 0 次,所以,第二個「(.*)」成功匹配到空字元 ""
整個表達式匹配成功。

匹配優先量詞 (以及後面提到的忽略優先量詞) 總想獲得全局匹配 (Greediness and Laziness Always Favor an Overall Match)

前面的例子,剛好第二個「(.*)」可以匹配 0 個字元,所以整個正則表達式可以匹配成功。
然而,如果在包含匹配優先量詞的表達式之後,還有其它表達式,並且期望獲得至少一個字元的匹配,
是否該表達式就會匹配失敗呢?

為了成功匹配整個正則表達式,為了使匹配優先量詞後續的表達式也能匹配 (然後才能使整個正則表達式成功匹配),
有時候引擎必須要求量詞表達式將已經匹配的字元再交還 (吐) 出來,
這個過程叫做 relinquish (放棄)unmatch (交還)
(其實這只是 backtracking (回溯) 的一個特例,詳見後面 backtracking 的說明。)

譬如:

 "Subject: Hi there".match( /(.*): (.*)/ );            // [ "Subject: Hi there", "Subject:", "Hi there" ]

 "Subject: Re: Hi there".match( /(.*): (.*)/ );     // [ "Subject: Re: Hi there", "Subject: Re:", "Hi there" ]

首先,因為「*」量詞是匹配優先的,所以兩個例子中的第一個「(.*)」會嘗試匹配所有的字元,直到文本結束。
由於此時再無其它可匹配字元,第一個「(.*)」匹配結束,由下一個表達式「:」開始嘗試匹配。
由於此時已達文本結束位置,再無其它字元可以匹配,
而引擎知道前一個量詞表達式實際上不需要匹配全部的字元即可滿足匹配條件,
此時引擎會要求前面的量詞表達式交還已匹配的最後一個字元,讓後續的表達式嘗試匹配。
在這兩個例子中,此時將交還最後一個 "e",並且由 "e" 前方的位置開始嘗試匹配,即:『Subject: Hi ther ^ e』。
由於「:」無法匹配 "e",匹配失敗。
此時引擎會繼續要求前面的表達式交還已匹配的最後一個字元,讓後續的表達式繼續嘗試匹配。
此過程一直重複,直到交還 ":" 字元時,此時,第一個例子所在的位置是『Subject ^ : Hi there』,
而第二個例子所在的位置是『Subject: Re ^ : Hi there』。
此時,「:」成功匹配,接下來由第二個「(.*)」開始嘗試匹配。
*」量詞是匹配優先的,所以第二個「(.*)」匹配剩餘的所有字元。
所有的表達式匹配完成,整個表達式匹配成功。

忽略優先量詞是忽略優先的

在前面的第二個例子裡,兩個「*」量詞分別匹配到 "Subject: Re:""Hi there"
如果我們期望的結果是: "Subject:""Re: Hi there" 呢。
由於匹配優先量詞的特性,使得處理這樣的問題變得複雜而困難。
為此,部分 flavor (流派),包含 JavaScript,提供了所謂忽略優先量詞。

忽略優先量詞有 +?, ??, *?, {m,n}?。(請參考後面 BNF 語法的說明。)

對,就是標準匹配量詞再加個 「?」。

忽略優先量詞的特性,與標準匹配量詞相反,是忽略優先的,也就是總是嘗試匹配盡可能少的字元
這正是它的名字 lazy (懶惰)reluctant (厭惡) 的由來。

譬如:

 "Subject: Re: Hi there".match( /(.*?): (.*)/ );     // [ "Subject: Re: Hi there", "Subject", "Re: Hi there" ]

由於忽略優先量詞總是嘗試匹配盡可能少的字元,「(.\*?)」首先決定略過匹配 (或者說,匹配 "")。
接下來,「:」嘗試匹配 "S" 字元,匹配失敗。
於是引擎又回到「(.\*?)」,「(.\*?)」只好「勉強」匹配了一個字元 "S",然後又交給下一個表達式繼續嘗試匹配。
當然,「:」嘗試匹配 "u" 字元又匹配失敗了。
於是引擎又回到「(.\*?)」,「(.\*?)」再匹配一個字元,然後又交給下一個表達式繼續嘗試匹配。
如此不斷重複,直到「(.\*?)」匹配到 "t" 為止。
接著,「:」嘗試匹配 ":" 字元,終於匹配成功了。
於是又接著嘗試下一個表達式「」空白字元表達式也成功匹配了文本空白字元。
然後是「(.\*)」,這是匹配優先量詞,所以,匹配到文本結束,成功匹配。
於是,整個正則表達式成功匹配。
我們也成功取得第一個 ":" 之前的文本,以及之後 (其中包含了第二個 ":") 的全部文本。

這裡可以看到,如果由文本的同一個位置開始,存在多個可能的匹配結果時,
匹配優先量詞總是匹配最長的結果;忽略優先量詞總是匹配最短的結果。

事實上,匹配優先與忽略優先量詞,兩者的唯一差異,在於嘗試匹配的路徑的次序不同。
匹配優先量詞總是先嘗試最長的結果;忽略優先量詞總是先嘗試最短的結果。

Backtracking (回溯)

NFA 引擎最重要的性質是,它會依序處理各個子表達式或組成元素,
在遇到需要在兩個 (或多個) 成功的可能中進行選擇時,
它會選擇其一,同時記住 (儲存) 另一個,以備稍後可能的需要。

選擇什麼

需要做出選擇的情形,包括量詞 (決定是否嘗試另一次匹配)
和多選結構 (決定選擇哪個多選分支,留下哪個稍後嘗試)。

對於量詞而言,在做選擇的時候,如果需要在「進行嘗試」和「跳過嘗試」之間做選擇,
對於匹配優先量詞,引擎會優先選擇「進行嘗試」,但在嘗試之前,先儲存目前位置以及「跳過嘗試」的選項;
而對於忽略優先量詞,在滿足匹配數量下限前,行為與匹配優先量詞一致。
滿足下限之後,會選擇「跳過嘗試」,但在跳過之前,先儲存目前位置以及「進行嘗試」」的選項。
(所以匹配優先量詞總是匹配最長的結果;忽略優先量詞總是匹配最短的結果。)

對於多選結構而言,在做選擇的時候,多數的 FNA 引擎,包括 JavaScript,會依序處理在表達式中的多選分支。
基本做法就是,將多選分支依反向次序,連同文本當前位置儲存起來,然後由第一個多選分支開始進行測試。
(所以對於從同一個位置開始的文本,如果存在多個分支可以同時匹配,則總是排在前面的多選分支獲得匹配。)

不論選擇哪一途徑,如果它能夠匹配成功,而且正則表達式的餘下部分也成功了,匹配即告完成。
如果正則表達式中餘下的部分,最終匹配失敗,引擎會知道需要回溯到之前做出選擇的地方,選擇其它備用分支繼續嘗試。

回溯到哪裡

而當強制回溯發生時,引擎總是回到最後儲存的選擇項目。實際運作方式即為 LIFO (Last In First Out, 後進先出),如同堆疊般運作。

對於匹配優先量詞,引擎會退回到「進行嘗試」之前的位置 (等於就是 unmatch 一個字元) ,
如果這個退回動作,會導致匹配的字元少於量詞要求匹配的下限,則量詞匹配失敗,引擎必須退回更早的儲存位置 (由其它表達式儲存的位置) 。否則,量詞仍然處於匹配成功的狀態,引擎又推進到下一個表達式,嘗試匹配這個被 unmatch 的字元。

對於忽略優先量詞,引擎會退回到當初「跳過嘗試」之前儲存的位置 (其實就是當前位置),由量詞「進行嘗試」匹配一個字元。
若這個字元無法匹配,則量詞匹配失敗,由於退回此狀態之前的後續表達式也已經失敗,所以整個表達式匹配失敗。
如果個字元匹配成功,則量詞匹配成功,在達到匹配數量上限之前,量詞又面臨到「進行嘗試」和「跳過嘗試」的選擇,
忽略優先量詞再次選擇「跳過嘗試」,同時儲存目前位置以及「進行嘗試」」的選項,然後向引擎報告匹配成功。
引擎則繼續推進到下一個表達式,嘗試匹配下一個字元。

對於多選結構而言。需要回溯的時候,只要依循 LIFO 原則,將儲存的狀態取出,即可依照多選分支列舉的先後順序依序處理。

這樣,藉由選擇路徑和回溯,引擎最終會嘗試表達式的所有可能途徑 (或者是匹配完成之前需要的所有途徑)。

小結

到這裡,已經介紹完了正則引擎的基本功能與原理。在學習時,可以多看看現成的範例,了解專家們在構造正則表達式的過程中如何思考。譬如 Regular Expression Cookbook 裡,就有相當多的範例。另外,搭配查閱 非正式 BNF 語法,可以更快掌握正則表達式的完整功能。

下一篇文章,將介紹更強大的功能:lookaround (環視)。

參考資料

  1. Stephen Cole Kleene
  2. Deterministic Finite Automaton
  3. Nondeterministic Finite Automaton
  4. Mastering Regular Expressions, 3rd Edition
  5. Regular Expressions Cookbook, 2nd Edition
  6. Regular Expression (JavaScript) 學習筆記 (2) - 原理篇 (下)
  7. Regular Expression (JavaScript) 學習筆記 (3) - Informal BNF 語法

整合 Maven 與 Yeoman, 學習筆記(5) - 使用 build-helper-maven-plugin 支援多 src 目錄

使用 build-helper-maven-plugin 支援多 src 目錄

對於一些較複雜的專案, 為了明確區分不同類型的 source code, 要求將它們分別放在專屬的目錄下. 譬如將 model, view, controller 分開來放. Maven 預設的 maven-compiler-plugin 只允許單一 source 目錄, 因此無法支援這樣的設定. 這時候, 就可以利用 build-helper-maven-plugin 來支援多 src 目錄 (不過官方並不推薦使用這種方法):

<!-- multi src dir support -->
<plugin>
    <groupId>org.codehaus.mojo</groupId>
    <artifactId>build-helper-maven-plugin</artifactId>
    <version>1.8</version>
    <executions>
        <execution>
            <id>add-source</id>
            <phase>generate-sources</phase>
            <goals>
              <goal>add-source</goal>
            </goals>
            <configuration>
                <sources>
                    <source>src/main/rs-app/services</source>
                    <source>src/main/rs-app/domain</source>
                    <source>src/main/rs-app/resources</source>
                </sources>
            </configuration>
        </execution>
    </executions>
</plugin>
參考資料: