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 レポジトリ




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

レポジトリ




2015年4月3日

SyncFiddleリニューアルしました

半年前に作った SyncFiddle を新しくしました。
(過去記事: JavaScriptが実行できるリアルタイムオンラインエディタ作ってみました)

SyncFiddle は、複数人とリアルタイムでコードが共有できるオンラインエディタです。
HTML, CSS, JavaScript が実行でき、他の人のコードやカーソル位置、選択範囲が同期されます。

URL は http://syncfiddle.net/ になりました。

SyncFiddleは現在ベータテスト中で無料で使えます(無料機能は予告なしに変わる可能性があります)。


今回ほとんど作りなおしましたが、既存の機能は基本的にそのままです。

機能とか

  • アクセスすると http://syncfiddle.net/xxxxxxxx のような新しい共有空間に飛ぶ
  • 飛んだ先は URLを共有しない限り基本的にプライベート
  • URLを共有して複数人で同時編集できる (Shareボタンから共有可能)
  • オンライン中のユーザー数とユーザー一覧(名前と色)がわかる
  • 自分の名前が編集可能
  • コードとカーソル位置、選択範囲がわかる
  • JavaScriptコンソールがある (コンソールは共有されない)
  • その時のHTMLコードを .html で保存できる (Exportボタン)
  • ブラウザで新しいウィンドウ開いて試してみるとわかりやすいかも

先日、リアルタイム・バックエンドサービスの Firebase を知って
これは SyncFiddle ぴったり!と思って作り直したくなってコツコツ進めていました。

技術的なこととか

もともと Backbone で作られていたので、そのまま引き継いで Backbone を使っています。
環境は webpack babel es6 で書いています。

バックエンド Firebase、エディタに CodeMirror の htmlmixed モードを使って、
Firepad という firebase が提供しているエディタを拡張して実装しています。

Firebase の Hacker Plan (FREE Plan) なので、最大接続数や容量がきついかもしれません。
Firebase にログインするとプランをアップグレードしろと真っ赤な表示で言われていますが、
一番安いプランでも個人で払えそうな額ではないので安くしてほしいです (Candle で月額 $49)。

SyncFiddle は JSFiddle などのサービス方向性からアイディアをもらっていますが、
音声通話などしながらリアルタイムに共有するにはきびしいのと、
そういったサービスが見つけられなかった (JavaScript の実行ができない) ので、
JavaScript が実行できる共有サービスとして作っています。

スクリプトの実行を自動的にやってしまうと どうかなと思い、
今のところユーザーの手で Run ボタンを押さない限り実行されないようになっています。

実行には iframe の sandbox 属性を使用しています。
origin を分けているので親 window は操作できないと思いますが、 もし問題あったら教えてください。

また、JSFiddle 等のサービスとはリアルタイム性として方向性が違い、
コードのログがいつまでも残ったところで意味はないのと、 容量スペースがあまりないので、
いまのところ ユーザー数 0 のまま一定時間経つと消えるようになっています。
(ベータテスト期間の状況で変わるかもしれません)
どちらかというとデザイン、レイアウトのほうがんばっていますが、
CSSはそこまで使いこなせてないです。作りながら調べつつ勉強になりました。
※ロゴ画像は poioq さんに作っていただきました、ありがとうございます。

おわりに

ちょっとしたツール的なものを作ることはよくありますが、
なかなか発展しなかったり止まってしまったりで、そういった継続力がほしいと思う日々です。
SyncFiddle はとても気に入っていて使える機会はあるので使いやすくしていきたいところ。
使ってみて不便な点とかアイディアとかありましたら教えてくれるとうれしいです。


Link: SyncFiddle

2015年2月17日

webpack babel-loaderを使ってES6でWebを書く

2015-11-21 babel presetsに合わせて更新
そろそろ ES6 で書きたいので環境メモを残しておきます。

はじめに

このエントリでは Node.js を使用してフロントエンドで ECMAScript 6th を書くことを目的にしています。
その際に babel を使います。
babel は grunt, gulp, browserify など多くのプラグインが提供されていますが、ここでは grunt を使っていきます。

以前は RequireJS でモジュール書いて r.js (1ファイルにまとめるやつ) でコンパイル(minify) てやってたのですが、
今回 webpackbabel-loader を使った ES6 環境で進めようと思います。

インストール

Node.js はすでにインストール済み前提とします。
まず適当なところにディレクトリを作って移動して npm init で package.json を作成します。
$ mkdir my_project
$ cd my_project
$ npm init
# いろいろ聞かれるけどとりあえずエンター連打

$ ls
package.json # できてること確認

ファイル構成

ファイル構成は以下のような感じです。
$ tree
.
├── package.json
├── Gruntfile.js        # これから作るgruntタスク
└── public              # 公開ディレクトリ
        ├── index.html  # これから作るhtml
        ├── js          # jsソースを置くディレクトリ
        └── assets      # コンパイル済みのjsなどを置くディレクトリ
まだ package.json しか作ってないので、public ディレクトリと、 その中に js, assets を作ります。

今回使うタスクランナーの grunt をインストールします (-g をつけてグローバルで)。
$ npm install -g grunt-cli

続いて grunt-webpack や grunt-contrib-uglify (圧縮),
grunt-contrib-watch (ファイルの更新を監視) などをインストールします。

本来なら webpack と grunt-webpack だけで済むっぽいですが、
非圧縮ファイルを確認したいときがあるので webpack で1ファイルにまとめてから uglify で圧縮します。
あえて非圧縮ファイルを残します。
$ npm install --save-dev grunt grunt-contrib-uglify grunt-contrib-watch
--save-dev オプションを指定して package.json の devDependencies に追加します。

それから webpack, babel-loaderをインストールします(1回でまとめてインストールしても同じです)。
$ npm install --save-dev grunt-webpack webpack babel-loader babel-preset-es2015

Gruntfile.js

プロジェクトのルート (package.json と同じ階層)に Gruntfile.js を作成します。
// Gruntfile.js
var webpack = require('webpack');

module.exports = function(grunt) {
  var pkg = grunt.file.readJSON('package.json');

  grunt.initConfig({
    // webpackの設定
    webpack: {
      build: {
        progress: true,
        entry: {
          // メインjsファイル (ここでは app.js とする)
          app: './public/js/app.js'
        },
        output: {
          // 出力ファイル (ここでは assets/js に出力)
          path: './public/assets/js',
          filename: 'bundle.js'
        },
        module: {
          loaders: [{
            // .jsに対してbabelを指定してES6で書けるようにする
            test: /\.js$/,
            exclude: /node_modules/,
            loader: 'babel',
            query: {
              presets: ['es2015']
            }
          }]
        },
        resolve: {
          // 読み込む際に拡張子を省略できるようにする
          extensions: ['', '.js']
        }
      }
    },
    // JS圧縮(minify)/最適化
    uglify: {
      options: {
        // Source Mapをつける
        sourceMap: true,
        sourceMapName: './public/assets/js/bundle.map'
      },
      build: {
        files: {
          // 出力ファイル: 元ファイル
          './public/assets/js/bundle.min.js': './public/assets/js/bundle.js'
        }
      }
    },
    // ファイルの変更/更新を監視
    watch: {
      js: {
        files: [
          // js/ 以下を再帰的に監視する
          './public/js/**/*.js',
        ],
        tasks: ['webpack', 'uglify']
      }
    }
  });

  grunt.loadNpmTasks('grunt-webpack');
  grunt.loadNpmTasks('grunt-contrib-uglify');
  grunt.loadNpmTasks('grunt-contrib-watch');

  // デフォルトタスクの登録
  grunt.registerTask('default', ['webpack', 'uglify']);
};

上のコードで Gruntfile.js に書き込んで保存します。

ES6でコードを書く

せっかくなので es6 modules を使って書いてみます。

public/jsapp.js を作成します。
// app.js
import * as math from './lib/math';

// Template Strings
var msg = `2π = ${math.sum(math.pi, math.pi)}`;
alert(msg);

続いて public/js/lib (lib ディレクトリを作成) に math.js を作成します。
// lib/math.js
export function sum(x, y) {
  return x + y;
}
export var pi = 3.141593;

publicindex.html を作成します。
<!-- index.html -->
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>webpack es6 babel-loader example</title>
<script src="assets/js/bundle.min.js"></script>
</head>
<body>
  <h1>webpack es6 babel-loader example</h1>
</body>
</html>

Build

各ファイルを作成したら grunt を実行してみます。
単に grunt と実行すると、default のタスクが実行されます。
$ grunt
...
Running "webpack:build" (webpack) task
...
Running "uglify:build" (uglify) task
...
>> 1 file created.

Done, without errors.
みたいに表示されれば成功です。

結果

index.html をブラウザで開くと、2π = 6.283186 とalertで表示されます。

出力

public/assets に以下の3つのファイルが作られています。
  • bundle.js : 非圧縮のファイル
  • bundle.map : Source Mapファイル
  • bundle.min.js : 圧縮済みのファイル

html 内では圧縮されたファイル assets/js/bundle.min.js を読み込んでいますが、
非圧縮の bundle.js を見ると変換されたコードも確認できます。

ファイルの変更を監視

毎回 grunt と入力するのも手間になるので、以降はファイルの変更を監視するようにします。
$ grunt watch
を実行すると、ファイルが更新される度に自動でタスクを実行してくれます。
Ctrl+C で中止できます。

babel-runtimeを含める

Promise などを使う場合、babel の runtime (polyfill) を含めるように指定します。
runtime を使う場合は babel-runtime のインストールが必要です。
$ npm install babel-runtime --save

Gruntfile.js の webpack loader を修正します。
// Gruntfile.js
  ...

    // webpackの設定
    webpack: {
      build: {
        ...
        module: {
          loaders: [{
            // .jsに対してbabel-loaderを指定してES6で書けるようにする
            test: /\.js$/,
            exclude: /node_modules/,
            // ランタイムを含めるよう指定する
            loader: 'babel-loader?experimental&optional=selfContained'
          }]
        },
        ...
      }
    },
  ...

runtime を含めると、それなりにサイズがあるので個別でライブラリ等を使うのもいいかもしれません。

Demo

今回作成した動作デモ:

Source

今回作成したソース:

おわりに

フロントエンド周りは移り変わりが激しいですが、安定したものを使っていきたいところです。
RequireJS 使った r.js の最適化は魅力的なのですが、 あらかじめひとまとめにする前提ってなると webpack が便利に感じます。
最近は CoffeeScript 書くことが多くて Coffee も楽しいなぁと思いつつ、 やっぱり ES6 で書けると嬉しいです (まだまだ勉強中…)。