Subscribed unsubscribe Subscribe Subscribe

枕を欹てて聴く

香炉峰の雪は簾を撥げて看る

JavaScript Syntax探訪

JavaScript Programming


blogめったに書いてない... 2.5年で110件...

前々からJSのScannerを読んだりするのが楽しかったのですが, id:miya2000 さんからの「commentを削除するprogram」という話が出たときに, 結局JSのlexerというものは単体では生成できずParserと密着している(主にRegExpとRegExpとRegExpのせいです)ということがわかり, 自分でも書きたいという考えが浮かんできてC++でずっと書いていました. AST構築までできて, jqueryなどをparse成功 + json形式のtreeにシリアライズする程度になったのですが, せっかくなのでLLVMへのbridgeとか検討しています. LLVMおもしろいー.

Constellation/iv · GitHub

で, Constellation's gist: 387832 — Gist くらいなものが吐き出せるようになってます. ただpretty printしたのはpythonのsimplejsonで, 元は平べったく1行で書かれたJSONで吐き出されます.

C++で書いたものは, 地味にLLVM2.6以上とICUが必要だったりして手間がかかるので, JSにportingしたものをgithubにのっけています.

iv / js test

リアルタイムにASTが表示されておもしろいです. 演算子順序とか.

JSの妖精こと id:hasegawayosuke さんの 顔文字でJavaScript - 葉っぱ日記 のコードとか一応parseできます. ただ, C++からのそのままの部分は1字1字確認しているので大丈夫だと思うのですが, Lexerの正規表現あたりが若干不安...

で, Lexer / Parserを書いたときに, JSの文法がおもしろかったので.

Lexer

JSのlexerは思いのほか綺麗に作ることができます. また, JSにおいてはwhite spaceというものはほぼ存在しないものであるという風に解釈できます.(ただし, 一部を除く)

NumericLiteralの最後の文字

NumericLiteralは一般にそのまま解釈出来ると思います. しかし, これには少しだけ落とし穴があって, section 7.8.3にこう記述されています.

The source character immediately folloing a NumericLiteral must not be an IdentifierStart or DecimalDigit.

NumericLiteral終了直後の文字は, IdentifierStart(Identifierのはじめに来れる文字)もしくはDecimalDigitであってはいけない(これは正直Decimal Digit内に取り込めるので, まあない)という決まりで, 標準には丁寧に例まで示されます.

3in
is an error and not the two input elements 3 and in.

このため, NumericLiteralをparseするときは, 最後に次の文字がIdentifierStart or DecimalDigitでないことを確認する必要があります.
あと, 浮動小数点の解釈があり, 以下のものが認められています.

// 0.20
.20

NumericLiteralのparseにはDECIMAL, OCTAL, HEXの3つがあり, DECIMAL時にはFlaoting pointが存在するかどうかを確かめる必要が出てきます. このとき, PERIODがあると, 問答無用でfloating pointとするので,以下のような問題が出ます.

// これはerror
20.toString();

20.でfloatだと思い, その後数値が続かないので, NumericLiteral 20.として解釈され, NumericLiteralの直後にIdentifierStartであるtが来ているのでLexer時にsyntax errorと解釈されます.
つまりDECIMALじゃなければいいいので, これはokなのです.

// 問題なし
0x10.toString();

0x10がNumericLiteral, PERIODがきて(これはIdentifierStartでもDecimalDigitでもないのでNumericLiteralはparse成功), そしてIdentifier toStringがきて()と;がきます.
またこれも問題ないですね.

20.0.toString();
20..toString();

20.0の時点でfloating pointまで見終わっているので, DecimalDigitでないPERIODが来るとNumericLiteralは打ち切られます. その後valid なPERIODとIdentifier...という流れです.
2つめは, 20.の時点でNumericLiteralがvalidにparseされ, それにPERIOD, Identifierの流れなので, どちらも問題ありません.
ちなみに先頭に0が来るとOCTALとして解釈するので,

02.toString();

も大丈夫です. しかし, 8以上の物でDECIMALなものが来ると, OCTALは解釈をDECIMALに変更します, よってこれはダメです.

// 8がきた時点で, OCTALからDECIMALへ解釈方式が変更される
028.toString();

また, white spaceは無視されるといいましたが, このとき, つまりIdentifierStart or DecimalDigitを調べるときには空白であればpassできます. よって, 以下の表記は可能なのです.

// これはダメ
20.toString();

// これは大丈夫
20 .toString();

// 空白が殆どの場合無視されるので(token間では)こんなのも可
20                                   .                                 toString              (       );

// これも大丈夫. なんかだんだんQuiz状態に...
20.                                   .     toString();
正規表現は文脈依存

これが一番困るのですが, 正規表現は以下のようなsyntaxでもって存在します.

/test/

しかし, 正規表現の初めの文字, /は演算子としても使われています. これが問題で, 実はlexerの時点ではどちらの意味なのかの解釈はできないです. 演算子が来れるところにきた/は演算子で, PrimaryExpressionの部分にきた/からはRegExpなのです.
よってJSのlexerでは, これを/までで解釈を止め, 演算子としてtokenを切り出します. そして, parserが見て, 演算子が来れるところで/を見たら演算子として解釈, RegExpのところで来たら, Parserから明示的にlexerに正規表現をparseするよう命令を出します.

ちなみに, コメントもこれを使いますね. これは問題ないのでしょうか?

// コメント
/*
 * これもコメント
 */

じつは正規表現では最初の文字に*が来ることができません. また, 正規表現は最低でも一文字の正規表現文字を要求します. これは section 7.8.5 RegularExpressionFirstCharが省略可能でなく, *や\や/や[を許さないとして記述されています.

RegularExpressionFirstChar ::
RegularExpressionNonTerminator but not * or \ or / or [
RegularExpressionBackslashSequence
RegularExpressionClass

よって以下のような正規表現はそもそも許されていません.

// 正規表現としての//はダメ
//

// これもダメ
/*/

よって/が来て, / or *がきた時点で, 演算子でも正規表現でもなく, コメントであると即座に判断することができます.

メントスキップ

コメントはどう解釈されるのでしょうか.
まず, SingleLineCommentには最後の改行は含まれません.

function test() {
  return// これでなにもかえさないよー.
  "unreachable";
}
console.assert(test() === undefined);

が,

function test() {
  return "unreachable";
}
console.assert(test() === undefined); // failure

なんて解釈されると困るからです. これは自動セミコロン挿入(Automatic Semicolon Insertion)に抵触しないようにするためで, 意外と改行は重要なわけです.

MultiLineCommentが改行を含む場合, 以下のように解釈されます. section 7.4です.

Comments behave like white space and are discarded except that, if a MultiLineComment contains a line terminator character, then the entire comment is considered to be a LineTerminator for purposes of parsing by the syntactic grammar.

改行があればLineTerminatorひとつに変換されるとあります. これは実は, こう動くことを定義していたりします.

function test() {
  return/*
  * ここはコメント
  */"val";
}

これ, 実はECMA262的には

function test() {
  return
  "val";
}

これと等価で, test() === undefinedでなければいけません. Automatic Semicolon Insertionによってreturnのあとにセミコロンが入るからです. しかしながら, V8とかで試してもらえるとわかるのですが, "val"が返ってきます. これについては, V8のscannerにコメントが有り,

If we have reached the end of the multi-line comment, we
consume the '/' and insert a whitespace. This way all
multi-line comments are treated as whitespace - even the ones
containing line terminators. This contradicts ECMA-262, section
7.4, page 12, that says that multi-line comments containing
line terminators should be treated as a line terminator, but it
matches the behaviour of SpiderMonkey and KJS.

という話で, SpiderMonkeyとKJS(今のJavaScriptCore)の挙動にあわせましたとあります. 互換性の話.
自分の書いているlexerでは互換性とかまったく気にしていないので, 普通にreturn undefined解釈します. 上のJS ASTを見るもので試してもらえれば.

自動セミコロン挿入

JSの深淵, 自動セミコロン挿入です. これは, JSのBNFをみるとあれなのですが, returnなどのあとには, 省略不可能な形でセミコロンがあります. しかしながら, lexerの段階で, ある規則に従ってセミコロンを挿入した上であのBNFに通されるわけです.

ここらへんの実装, JavaScriptCoreなんかはわかりやすく, 規則通りにセミコロンを追加します. JavaScriptCoreはparser部分にBNFを使っているので, 余り融通が効かないためLexer部分できちんとセミコロンを突っ込んでおいておかないといけないわけです.
V8はそこはぶった切っていて, return終わりなど, セミコロンが自動挿入されるかもしれない場所でセミコロンがない場合, セミコロン自動挿入することができるかをparser側からlexerに聞いて調べて, できるならpass, できなければsyntax errorになります. こっちのほうがcost低そうです. ただ, Parserを手書きする分出来ることではあります. あと, parserとlexerが密結合になってしまいますが, 正規表現の時点でもう分割不可能なものですから, 別に問題なさそうです.

Keyword

IdentifierかKeywordなのか. この判断はIdentifierをscanしたときに行います. JSでのporting時には単純にhashにいれてあるかどうかをみていたのですが, C++となると話が少し違います. ここらへんは実装によってかなり違います.

SpiderMonkeyは長さをとり, それからif / else / switchで分岐しています.
jsで雰囲気だけお伝えすると,

switch (size) {
  case 3:
    // var int ...
    if (str[0] == 'v' && str[1] == 'a' && str[2] == 'r')
      //...
}

見たいな感じです.

JavaScriptCoreは超わかりやすいです. jsで雰囲気だけ(ry

var keyword = KEYWORD[str];

V8は, 状態遷移マシンを使っています. KeywordMatcherというもので, Identifierとして一字確定するたびに, KeywordMatcherに入力し, KeywordMatcherの状態が遷移していきます.
例えば, caseだと,

  • c入力
    • 状態がcに
  • a入力
    • 状態がcaに
  • s入力
    • 状態がcasに
  • e入力
    • 状態がcaseに

見たいな感じです. もちろん,

  • c入力
    • 状態がcに
  • b入力
    • cb状態は存在しないのでFailに

という風に状態を外れたときはFailになり, keywordではないという判断がでます.

Parser

さて長々とLexerの話をしたところで, つぎにParseの話. JavaScriptはまた非常に構文がきれいなので, Parseもそんなに難しくないです. いくつかのはまりポイントを紹介.

Statements

Statementsにはザーッと羅列されていますが, 気になる点はBlockなんかどうでしょうか.
Statementは基本的にはじめの1 tokenで判断することができます(labelとexpression statementを除く)つまり,

{
  ok: "test"
}

は, ObjectLiteralでもなんでもないです. {がStatementできたとたん, Blockが始まり, BlockはStatementsを取るので, ok:でLabelledStatementと解釈, その後ExpressionStatementの"test"が来て, 自動セミコロン挿入が来て, Block終了です. これはStatementのContextで{が来ると即座にBlock解釈するためです. この間JS Quizで間違えまくりました.

var i = {
  ok: "test"
}

これはAssignExpressionが来るところなので, ObjectLiteralとして解釈されます.

あと, Statementは基本的にはじめの1 tokenで解釈できるので非常に心温まるのですが, 唯一解釈できないもの, それがLabelledStatementとExpressionStatementです.

LabelledStatement
  : IDENTIFIER ':' Statement
ExpressionStatement
  : Expression ';'

はじめの1 tokenでIdentifierがきた時に, さてどちらかなーという話で. IdentifierだってExpressionととれるんですねー. これはV8など他のEngineでは以下のような手順を踏みます.

  1. まず, tokenがIdentifierでなければExpressionStatementであるとして切る
  2. Expressionだという目論見で(IdentifierだってExpressionととれるので成功するはず)Reduceする
  3. Reduce結果のExpressionが単一のIdentifier Literalであり, かつ次のtokenがCOLON ( : )である場合, これはLabelledStatementである
  4. 違うならExpressionStatementとしてReduceする.

例えば,

test()

となっていたとき, testの段階ではlabelかexpressionかわからないので, まずExpressionとしてReduceします. この場合, test()でFunctionCallになりますから, 単一のIdentifierではないので, その場合はExpressionStatementです.

このように, いったんExpressionとしてReduceして, Identifierならーというやり方でもって解釈します. 難しいですね.

LeftHandSide

いくつかのものはReference型でないと(JS的に)Validでない演算子があります. Increment / Decrementなんてそうです. Increment / Decrement演算子がかかっているExpressionが, LeftHandSide, つまり代入される側(左辺), JS的にはReference型として正しい表現かどうかが問われるのです.

var i = 10;
i++;// valid

i = 20;// i is Valid LeftHandSide Expression

10++;// invalid

ということです. 10 = 20というものが無理なのを考えてもらえればわかりやすいかも. このように対象の値がLeftHandSideであるかどうかという解釈がIncrement/Decrement演算子には必要になってきます.
ちなみに, LeftHandSideに来れるのは,

var i = 10;// Identifier
window["ok"] = 10;// PropertyAccess

です.
Increment / DecrementがUnaryOperationとしてきたとき, targetがIdentifier / PropertyAccessであるかどうかを判別して, 異なっていた場合, 「ReferenceError : Invalid left-hand side expression」であるというerrorを出します. これはAST状態ですでに判別できるので, 実行時ではなくParse時に判別することが可能です.

RegExp Parse側

正規表現のParse側です. Operatorが来るところで, / か /= がきたときは, 単に演算子としてReduceします. 一方, PrimaryExpressionのところできた場合は, /=の場合EqualがあるのかないのかをboolあたりでLexerに伝えつつ, LexerにRegExpをScanするように伝えます.
このため, JSではLexerですべてtoken列にしてからそれをParserに与えるというやり方はできません. LexerとParserが協調しながら動作する必要があるのです.
できるやり方が考案されました, See Tim Disney (disnetdev) -- How to read macros

new constructor

深淵その2. new周りです. そんな難しくないだろうと思ったらところがどっこい. なぜなら, newは

var i = new Array;

最近のJS Engineだとnew Array()みたいに()を入れなくても通るように作らないといけません...

var i = new func();

は, constructorとしてfuncを取り, 引数0でnewするのであって, func()で返って来る関数をconstructorとしてnewするのではないわけです. ここらへんが絶妙に演算子の順序が絡みます. funcをparseするときに, ()までreduceしないようにして, funcをconstructorとしてreduceして, new func ()の3つでconstructor callとしてreduceしなければいけないのです.

var i = new func()();

は, func()がconstructorになるのではありません. new func()でconstructor callとして, そのconstructされたobjectが関数呼び出し()でcallされ, その戻り値がiに代入されるのです. つまり以下と等価です.

var i = (new func())();

関数の戻り値をconstructorにするには明示的に演算子順序を与える必要があります.

var i = new (func())();

まずnewがきたら, 次の表現を()を含まない分まで再帰的に解釈する必要があります. 再帰的ですが, しかし()は一番外側までとっておいてあげなければいけません. newで一度入った後のParseに関してfunction callは許さない(明示的に括弧で順序を指定されない限り. 指定された場合は, IdentifierじゃなくてFunctionCallとしてExpressionで処理すればいいです)というやり方で行けば問題ないです.

var i = new new func();

は,

var i = new (new func)();

です.

まとめ

JSのLexer / Parserを書くと, 新しい発見やいろんなものが見えてきて非常に面白かったです. IdentifierStartに数値を許さないのは, 一文字目でNumericLiteralとの区別をつけたいのだろうなとか, 正規表現一文字目に*や/がこれないのはコメントと区別するため, むしろコメントと区別しないように*とかの記号を一文字目にこれない意味にしたのかなーなどいろいろ考えることができました.
ASTまでできてるので, 後は適当にfunctionを並べる風に書いたらcomment削除はできると思います. やったね!
あと, 非常にアレな副産物というか, 特典として, 演算子の結合順序が空で並べられるようになりました. お得ですね.