JavaScriptの「カバー文法」とは何か

皆さんこんにちは。この記事は2019新卒 エンジニア Advent Calendar 2019の6日目の記事です。新卒でもバイト経験何年という人たちがひしめく中、筆者が実務経験く無しでWeb業界に新卒で飛び込んだのが今年の4月のことでした。そんな思い出の年がもう1月もしないうちに終わってしまうのはとても感慨深いですね。

普段から業務でJavaScript（というかTypeScript）を使っている筆者ですが、今回はどちらかというと趣味で興味を持った内容について書いてみました。新卒ということなのでお手やわらかにお願いしたいところです。

この記事では、仕様書におけるJavaScriptの構文の定義に登場するカバー文法について解説します。

JavaScriptの文法はどのように定義されているか

JavaScriptは、その仕様がしっかりと定められている言語のひとつです。今どきは大抵の言語がOSSとして開発されているとはいえ、どこかの会社や非営利団体が音頭を取って言語の開発方針を決めていたり、実質的にコンパイラの動作によって言語が定義されていたりといった運用をされるものが多くあります。その一方で、JavaScriptには、JavaScriptがどのような言語かを定める仕様書が存在しています。

• ECMAScript® 2019 Language Specification

仕様書はJavaScriptの言語機能や動作を定めるものであり、JavaScriptへの機能追加は仕様書の改訂という形で行われます。この仕様書の管理を司るのが、ECMA Internationalという機関の中に存在するTC39という委員会です。この委員会にはいろいろな企業のメンバーが参加しており、どこか一つの企業が舵取りをしているというわけではありません（力が強い会社というのは多分あると思いますが）。

JavaScriptを実装する言語処理系（ブラウザとか）はこの仕様書を基準にして実装されており、「実装が仕様」と言わんばかりの言語たちとは一線を画しています（実際には仕様が正式リリースされる前に実装が先行するような仕組みになっているのですが）。

なお、仕様書にはECMAScriptという名前が書いてありますが、まあJavaScriptのことだと思って問題ありません。

そして、当然ながら、JavaScriptの文法を定義するのもやはり仕様書です。文法というのは、どのような文字列がJavaScriptプログラムとして受け入れられるかを定義したものです。

JavaScriptの文法は構文規則の集まりによって表現されています。例えばconst foo = bar + 3;というのはJavaScriptにおける正しい文ですが、これがなぜ正しい文なのかは次の表（あるいは木）で説明されます。

この表を上から読みつつ多少言葉で説明すると以下のようになります。

• const foo = bar + 3;はStatementListItemである。なぜなら、DeclarationはStatementListItemの一種であると定義されているから。
• const foo = bar + 3;はDeclarationである。なぜなら、LexicalDeclarationはDeclarationの一種であると定義されているから。

• const foo = bar + 3;はLexicalDeclarationである。なぜなら、LetOrConst, BindingList, ;が並んだものはLexicalDeclarationであると定義されているから。

  1. constはLetOrConstであると定義されている。
  2. foo = bar + 3 はBindingListである。LexicalBindingはBindingListの一種であると定義されているから。

• foo = bar + 3はLexicalBindingである。なぜなら、BindingIdentifierとInitializerが並んだものはLexicalBindingであると定義されているから。

  1. fooはBindingIdentifierである。なぜなら、IdentifierはBindingIdentifierであると定義されているから。
  2. = bar + 3はInitializerである。なぜなら、=とAssignmentExpressionが並んだものはInitializerであると定義されているから。

• bar + 3はAssignmentExpressionである。（以下略）

「定義されている」という言葉を多用しましたが、もちろんこれらの定義は仕様書に書いてあります。上の例に登場した定義の一部を仕様書 13.3.1 Let and Const Declarationsから画像で引用します。

一番上には「LetOrConst, BindingList, ;が並んだものはLexicalDeclarationである」という定義が書かれています。その次には、「LetOrConstとはletという文字列またはconstという文字列である」という定義が書かれています。以下も同様です。

なお、StatementListItemとかDeclarationとか、LetOrConstといった名前がたくさん登場しましたが、これらを総称して非終端記号と呼びます。どのような文字列がどの非終端記号に合致するかというのを定義するのが文法です¹。JavaScriptプログラム全体はScriptまたはModuleという非終端記号で表されます。正しいJavaScriptプログラムとは、JavaScriptの文法に照らしてScriptまたはModuleに当てはまるような文字列のことを言います（実際には後述のような追加のエラーチェックをくぐり抜ける必要がありますが）。

実際に与えられた入力文字列がどの非終端記号に当てはまるかを特定するのがパースという作業です。上記のような定義を見ると分かる通り、非終端記号は生の文字列（終端器号）や別の非終端記号の組み合わせによって定義されています。

全てのJavaScriptプログラムは、仕様書に書かれた膨大な文法・非終端記号の定義によって全て説明し尽くすことができるのです。

JavaScriptの文法における「曖昧性」

文法にはいろいろな分類が知られています。例えばLL(1)やLR(1)などです。この(1)というのは文字列をパースする際に先読みが1文字（あるいは1トークン）必要であるという意味です。(0)なら先読みが不要、(2)なら2文字の先読みが必要ということになります。

JavaScriptの文法が正確にどのようなクラスに属するのかについては、筆者には確実なことが言えないので言及を避けようと思います。しかし、JavaScriptの文法定義を眺めると、1トークンの先読みでパースできるように定義されているように見えます。そして、仕様書では、1トークンの先読みでパースできないような規則を「曖昧である」と呼んでいるように見えます（cf. 5.1.4 The Syntactic Grammar）。

例えば、const foo = bar + 3;については先読みなしでパースできます。パーサーの気持ちになって考えてみましょう。パーサーは前から順番にトークンを読んでいきます。

1. 最初にconstを読んだ時点でこれはLetOrConstであることが確定します（constは予約語であるため、そういう名前の変数であるなど他の可能性はありません）。
2. 次にfooを読みます。このような普通の変数名っぽいものはIdentifierになります。constの次である（次はLexicalBindingが来るはず）ことも加味するとこれはBindingListの中のBindingIdentifierであることも確定します。
3. 次に読んだ=も、LexicalBindingの中のInitializerの最初の=であることは明らかです。
4. 次のbarはIdentifierになります。このIdentifierがどのような役割かはまだ分かりません。
5. +を読んだ時点で今AdditiveExpressionの真ん中にいることが明らかになります。これにより、先ほどのbarがAdditiveExpressionの左のAdditiveExpressionであることが明らかになります。
6. 次の3はNumericLiteralになります。
7. 最後に;を読んだ時点でAdditiveExpressionの右に位置するMultiplicativeExpressionは3のみであることが明らかになります。

実は、この一連の処理においては先読みが発生していません。4において「Identifierがどんな役割なのかまだ分からない」というシチュエーションもありましたが、「Identifierである」という結論自体はその場で下すことができています。先読みが必要になるというのは、「barがIdentifierである」というような結論すらその場で下すことができない（全く異なる複数の可能性が存在してしまう）シチュエーションを指しています。

JavaScriptの文法に存在する曖昧性

JavaScriptの文法は、前節で説明したような「曖昧性」が存在しないように作られているようです。1トークンの先読みまでは許容しますが、それでも曖昧性が解消できない構文は存在しないというのが原則です。

しかし、実はその原則が破られる場合が存在します。そのひとつがアロー関数です。

アロー関数は(foo) => { console.log(foo); }のような構文です。これは関数を作る式であり、この例の場合は「引数fooを受け取ってconsole.log(foo);を実行する関数」になります。

アロー関数では引数一覧を( )で表しますが、これが問題です。次の2つの文を見比べてみましょう。

const v1 = (foo) => { console.log(foo); };
const v2 = (foo);

この2つの文はどちらも妥当な文です。そして、=の右が(foo)まで同じです。

しかし、この2つの文における(foo)の役割は全く異なります。1つ目の文ではアロー関数の引数部分であるのに対し、2つ目の文では変数fooを括弧で囲んだものです。2つ目の文はconst v2 = foo;と同じ意味ですね。

ここで問題となるのは、この2つの文の区別は1トークンの先読みでは無理である、すなわち（前節で述べた意味で）曖昧であるということです。

実際、前から順番にトークンを読むことを考えると、const v =まで読んだという前提のもとでも、次の(が「アロー関数の引数一覧の始まりの括弧」なのか、それとも「グルーピングの括弧」なのか分かりません。また、1文字先読みしても無理です（それどころか、任意の定数個の先読みでもこれは不可能です）。

JavaScriptの新機能を議論するときには「文法の曖昧性」は大きな問題であり、曖昧性を持つ文法を導入するのは極力避けられます。それにもかかわらず、アロー関数はその利便性や構文の分かりやすさを天秤にかけて、曖昧性を受け入れるほうを取ったことになります。

ちなみに、曖昧性が実際に問題になった例として、TypeScriptに搭載されたパーサーの例を紹介します。これはまだオープンなissueであり、ものすごく曖昧な入力をパーサーに与えることでパースに非常に時間がかかってしまうというものです。回避することはできるかもしれませんが（Babelなどがどうやっているのか調べるとよいと思いますが残念ながら未検証です）、いずれにせよ何らかの工夫が求められるものであり、曖昧性が実際にパーサーの実装者に負担を与えることが分かります。

• Nested series of assignments takes ~quadratic time to parse

カバー文法による曖昧性の対処

やっとカバー文法が話に登場します。前節ではJavaScriptの文法が（先読み1でパースできないという意味での）曖昧性を抱えていることを示しましたが、実は実際の仕様書における文法定義では、カバー文法というものを使って曖昧性を半ば無理やり回避しています。この手法を紹介するのが本記事のメインのテーマです。

いきなりキーとなる非終端記号を紹介します。それはCoverParenthesizedExpressionAndArrowParameterListです（仕様書から画像で引用）。

見ると分かる通り、この終端器号は( )で囲まれた何かの構文を表すようです。詳細は省きますが、実はこの終端器号は「グルーピングの構文としての( )」と「アロー関数の引数リストとしての( )」の両方をカバーする定義になっています。

これにより、(を見かけたらとりあえず「CoverParenthesizedExpressionAndArrowParameterListの始まりの括弧である」と判定すれば間違いがありませんので、前述の曖昧性が形式上は消えていることになります。

実際、グルーピングの構文に対応するものとしてCoverParenthesizedExpressionAndArrowParameterListはPrimaryExpressionであるという定義が存在しています。また、アロー関数の構文に関しても、ArrowFunction非終端記号が CoverParenthesizedExpressionAndArrowParameterList => ConciseBody という並びから作れることが定義されており、アロー関数の引数部分がCoverParenthesizedExpressionAndArrowParameterListで表現されていることがわかります。

カバー文法と実際の構文のギャップ

上で説明したCoverParenthesizedExpressionAndArrowParameterListを愚直に受け入れると、例えば以下のようなものが妥当なプログラムとしてパースしうるということになります。

(1+2) => 3

実際、これは以下のようにパースできます。

問題の本質は、カバー文法は本来異なる2つの構文を無理やり同一視するものであるという点にあります。このため、カバー文法を用いた場合、本来パースできるべきではない誤ったプログラムがパースできてしまうという問題が発生します。

この問題に対しては、仕様書はSupplemental Syntaxを用いて対処しています。例えばアロー関数に対しては次のSupplemental Syntaxが定義されています（14.2 Arrow Function Definitionsから画像で引用）。

Supplemental Syntaxの言っていることは、「CoverParenthesizedExpressionAndArrowParameterListに該当するものがアロー関数の一部として現れたらそれを念の為パースし直して( UniqueFormalParameters )に当てはまるかどうかをチェックする」ということです。( UniqueFormalParameters ) はアロー関数の引数の( )部分の構文を正確に表しており、これに合わないもの（上の(1+2) => 3のようなもの）はこのチェックで弾かれて晴れて文法エラーとなります。

これで、なんとか曖昧性を回避しつつ構文が定義できました。ただ、「再パース」とかいう荒業を用いたものになっています。

愚直にこの通りにパーサーを実装した場合、同じ部分を何度もパースすることになるため最悪の場合入力の長さ$N$に対して$O(N^2)$くらい時間がかかりそうです。おや、先ほど紹介したTypeScriptのissueにquadratic （二次）と書いてあったような……？²

• Nested series of assignments takes ~quadratic time to parse（再掲）

なお、グルーピングの( )構文の側にも同様にsupplemental syntaxが定義されています。こちらはEarly Errorという仕組みを用いて文法エラーが定義されています。これは、パースには成功したものの妥当ではないというようなプログラムを弾くための仕様書上の仕組みです。

まとめ

この記事ではJavaScriptの構文に潜む（1トークン先読みでパースできないという意味での）“曖昧性”と、言語仕様におけるワークアラウンドとしての「カバー文法」について解説しました。

ここでは代表例としてアロー関数の場合を紹介しましたが、他にもカバー文法の例がいくつかあります。気になる方は仕様書をcoverとかで全文検索してみましょう。

この記事ではあくまで言語仕様がどうなっているかに絞って解説したので、実際のパーサーの実装がどうなっているかといったことには触れませんでした。そういった内容について補足してくださる方や記事を書いてくださる方は大歓迎です。

いやあ、実際の実装に目も向けず理想（言語仕様）ばかり追い求めているのがいかにも右も左もわからない新卒という感じの記事でしたね。この記事は2019新卒 エンジニア Advent Calendar 2019の6日目の記事でした。明日もお楽しみに。