2015年10月30日

ECMAScriptを正規表現で解く

最近、こつこつと Chiffon というECMAScriptのパーサを書き進めています。

この Chiffon の主な解析方法は正規表現です。
というのも、前に書いたJavaScriptコードをトークンに分解する正規表現が発端で、これを改良し、es6 にも対応させようとしています。

ECMA-262 の仕様を調べながらパーサを書いて、今まであまり知らなかったことがでてきたり、
いろんな構文パターンをテストしていくうちに、正規表現のミスや修正が必要なものがでてきました。

数値リテラル

数値リテラルにマッチする正規表現は 
/0(?:[xX][0-9a-fA-F]+|[0-7]+)|\d+(?:\.\d+)?(?:[eE][+-]?\d+)?|[1-9]\d*/g
でいいかと思っていましたが、
ECMA-262 11.8.3 Numeric Literals をあらためて見ると表現が足りないことに気付きます。

DecimalLiteral はドットから始まることができるので、.1 などにマッチする必要があります。
また、0x の他に BinaryIntegerLiteral (0bXXX)、OctalIntegerLiteral (0oXXX) があります。 

/0(?:[xX][0-9a-fA-F]+|[oO][0-7]+|[bB][01]+)|(?:\d+(?:[.]\d*)?|[.]\d+)(?:[eE][+-]?\d+)?|[1-9]\d*|0[0-7]+/g
現在はこの正規表現になっています。reffidleデモ

文字列リテラル

/'(?:\\.|[^'\\])*'/g
文字列リテラルにマッチする正規表現はこのパターンが有名です。
バックスラッシュでエスケープされたシングルクォート \' に対して正しくマッチします。

ただし、この正規表現は不完全で、改行にもマッチしてしまいます。
改行にはマッチしないが、バックスラッシュでエスケープされた改行にはマッチしたい。 

/'(?:\\[\s\S]|[^'\r\n\\])*'/g
この正規表現だと改行にマッチしなくなり、なおかつ 
'aaa\
bbb\
ccc'
のような、改行をバックスラッシュでエスケープした場合はマッチするようになります。

ただ、この正規表現にはまだ罠があります。
ECMA-262 11.3 Line Terminators では <CR><LF> の2文字で改行扱いされます。 
'aaa\
bbb\
ccc'
この改行コードが <CR><LF> だった場合、マッチに失敗してしまうのです。
\<CR>\<LF> と言った具合に、<CR><LF> の各文字の前にバックスラッシュがあればマッチすることになります。

<CR><LF> にも正しくマッチさせるには、単純に \\\r\n を追加して、 
/'(?:\\\r\n|\\[\s\S]|[^'\r\n\\])*'/g
この正規表現で改行コードに関しても正しくマッチします。refiddleデモ

※ECMA-262 11.3 Line Terminators は他にもありますが、この記事では簡略化しています。

正規表現リテラル

正規表現リテラルは以前こう書いていました。 
/\/(?!\*)(?:\\.|[^\/\r\n\\])+\/(?:[gimy]{0,4}|\b)/g

これは大抵の場合、正しくマッチしますが、
ECMA-262 11.8.5 Regular Expression Literals では文字グループ [...] 内に限りスラッシュ記号を直接書くことができます。 
/[/]/
このような正規表現リテラルに対しマッチに失敗してしまいます。

文字グループ内はバックスラッシュのエスケープなしでスラッシュ / を書けることを考慮し、
RegularExpressionFlags も g, i, m, u, y に直します。 
/\/(?![*\/])(?:\\[\s\S]|\[(?:\\[\s\S]|[^\]\r\n\\])*\]|[^\/\r\n\\])+\/(?:[gimuy]+\b|)/g
この正規表現で、確実に正規表現リテラルにマッチさせることができます。 refiddleデモ

ただし、ECMAScript には / や /= といった演算子があり、 正規表現リテラルじゃないものにまでマッチする可能性があります。 
var a = 1, b = 2, c = [1, 2], g = 2, i = 3;
a /= a / b / c[2/g] /i

このようなコードに対して誤ったマッチをしてしまいます。

もし JavaScript に否定後読み (?<!...)、もしくは肯定後読み (?<=...) があったらいけそうな気がしますが、 おそらく解決できないでしょう。 
if (1) /a/
や 
if (((a||b)&&c)||d) /a/.test('a') ? ... : ...
などのように if, while, for, with などが前にある場合、括弧を超えて判断する必要があるからです。

ECMAScript の正規表現リテラルにマッチする正規表現は、少なくとも JavaScript の正規表現では100% 確実には無理なので、
Chiffon では正しいマッチかどうかバックトラックして判断しています。

テンプレートリテラル

テンプレートリテラルの正規表現は、 
/`(?:\\[\s\S]|[^`\\])*`/g
このパターンは、バッククォートからバッククォートまで ` ... ` バックスラッシュのエスケープも考慮してマッチします。 refiddleデモ

テンプレートリテラルは、
ECMA-262 11.8.6 Template Literal Lexical Components にあるように、改行 (LineTerminatorSequence) が含まれます。

しばらくはこの正規表現で問題ないと思っていたのですが、
テンプレートリテラルの Expression 部分 ${ ... } には、
その中にさらにテンプレートリテラルが書けるので、これを表現するのは正規表現の再帰が必要になり、無理ではないかと思っています。
そこで Chiffon では、有限ではあるものの、ある程度のネストを考慮して、 
/`(?:\\[\s\S]|\$\{(?:\\[\s\S]|[^{}\\]|\{(?:[^{}]*(?:\{[^{}]*\})?)*\})*\}|[^`\\])*`/g
このような正規表現になっています。refiddleデモ

このパターンは、${ から } までを別でマッチさせて、 ある程度の深さまでなら正しく扱えるようになっています。
ただし再帰パターンは JavaScript では書けないため、 
` ${
      `${
           `${
                1 + 1
             }`
       }`
   }
`
ここまでの深さまでマッチしますが、 
` ${
      `${
           `${
                `${
                     1 + 1
                 }`
             }`
       }`
   }
`
これ以上になるとマッチに失敗します。

ただ、通常ここまで深くなるテンプレートリテラルを書かないと思うので、そこまで問題視していません。

<!--, --> でコメントになる

ECMA-262 B.1.3 HTML-like Comments をみると、 <!-- や --> がコメント扱いになることがわかります。 詳しい仕様まではあまり一般的ではないように思いますが、 
var a = 1, b = a<!--a;
console.log(b); // 1
b の値は false ではなく 1 になります。

<!-- 以降がコメント扱いされているため、 
var a = 1, b = a<!--a;
b = a で終わってしまっています。

また、 --> に関しては、 <!-- から --> の間がコメントになるのではなく、 それ以降の行末までがコメントになります。 
var a = 1;
--> a = 2;
console.log(a); // 1
上のコードは --> a = 2 がコメントになり、1 が console.log されます。

--> は、大雑把に言うと行頭にない場合コメントになりません。 
var a = 1, b = a-->a;
console.log(b); // true
上のような場合はコメント扱いされません。

Identifier に UnicodeEscapeSequence が使える

ECMA-262 11.6 Names and Keywords によると、 IdentifierName に UnicodeEscapeSequence が使えます。

今までせいぜい数えられるくらいしか出会ってないのと、使う機会もないものですが、 
\u0074\u0079\u0070\u0065\u006F\u0066 \u307B\u3052
これをコンソールで実行すると 'undefined' と結果が返ると思います。 
typeof ほげ
やってることは上のコードと同じです。 Identifier を \uXXXX もしくは \u{XXXX} で表すことができます。
部分的に表すこともできるので、typeof ほ\u3052 でも同じです。 
var \u307B\u3052 = 1;
console.log(ほげ); // 1
非ASCII文字が含まれるソースコードを、ASCIIのみにしたい時などに使えます。

RegExp.prototype.exec から string.match(regex) で高速化

Chiffon はもともと、RegExp#exec を使って、 
var m;
while ((m = re.exec(source)) != null) {
  // ...
}
といったやり方で字句解析してたのですが、
これがなかなか遅いので、どうにかならないかとあれこれ試して、 
var m = source.match(re);
正規表現リテラルに g フラグをつけて、String#match を使ったら、約250% 速くなりました。
いくらビルトインメソッドとはいえ exec はループで回すとなると扱いが難しいです。



なんとなく書き始めた Chiffon ですが、
ECMA-262 の仕様を知るいいきっかけになってくれています。
まだ tokenizer (字句解析) までの実装で厳密なパーサではないですが、日々進めていこうと思ってます。

Chiffon レポジトリ




投稿者 時刻: 19:08 0 コメント コメントを投稿する
このエントリーをはてなブックマークに追加
ラベル: , , ,

2015年10月11日

ECMAScriptのParser/Tokenizer(字句解析)をJavaScriptで書きました

ECMAScript のコードを字句解析するコンパクトなパーサーライブラリ、chiffon.js を書きました。
chiffon.min.js は、3KB ほどのサイズです(v1.2.0 現在)。

特徴

  • ライブラリのファイルサイズが軽い
  • ECMAScript6 の仕様 を元にしてる
  • 解析結果が esprima のtokenize結果と同じになる
  • esprima ほど厳密ではない(構文エラーあっても解析を続けるなど)
  • 速度は esprima と同じくらいかちょっと速い
  • 正規表現で解析してる

Chiffon はとにかくファイルサイズが軽いのが特徴です。
正規表現で一発解析してて、その正規表現が少し長くなっちゃってるため、これ以上なかなかファイルサイズが削れないです。
構文エラーなどあってもエラーを吐かずに解析を続けます。
esprima ほど厳密ではないものの、ほとんどは esprima と同じ結果になります。
Parser と言ってますが、いまのところ Tokenize(字句解析) してるだけなので、厳密には Parser とは言わないのかもしれません。

使い方

ブラウザの場合:

<script src="chiffon.js"></script>
または、 
<script src="chiffon.min.js"></script>
Chiffon というオブジェクトがグローバルに定義されます。

Node.js の場合:

npm install chiffon

var Chiffon = require('chiffon');

bower:

bower install chiffon

tokenize

ECMAScriptのコード文字列をトークン化します。 
var tokens = Chiffon.tokenize('var a = 1');
console.log(tokens);
/*
[ { type: 'Keyword',    value: 'var' },
  { type: 'Identifier', value: 'a' },
  { type: 'Punctuator', value: '=' },
  { type: 'Numeric',    value: '1' } ]
*/

返される結果のトークン名リスト:

  • Comment
  • LineTerminator
  • Template
  • String
  • Punctuator
  • RegularExpression
  • Numeric
  • UnicodeEscapeSequence
  • Identifier
  • Null
  • Boolean
  • Keyword

※多少変化する可能性があります。最新の情報はこちらを参考ください
※JavaScript AST は現在サポートされてません。

Options

  • comment : trueにするとCommentトークンを残します (default=false)
  • lineTerminator : trueにするとLineTerminatorトークンを残します (default=false)

untokenize

tokenize() で返されたトークンを文字列に戻します。 
var tokens = Chiffon.tokenize('var a = 1');
var code = Chiffon.untokenize(tokens);
console.log(code); // 'var a=1'

minify

JavaScriptのコードを minify します。 
var min = Chiffon.minify('var a = 1 + 1; // comment');
console.log(min); // var a=1+1;

minify は以下のような感じで単純に実装されてます。 
function minify(code) {
  return untokenize(tokenize(code));
}

Demo

レポジトリ




投稿者 時刻: 23:34 0 コメント コメントを投稿する
このエントリーをはてなブックマークに追加
ラベル: , , ,
登録: 投稿 (Atom)