生成規則って何ですか

はじめに

第8回 ECMA-262 Edition5.1読書会 - ECMA262-Edition5.1読書会 | Doorkeeper

こちらの本の読書会です。

初参加なわけですが、言語の仕様に触れるのはあまりない体験なので、わからない単語が結構多かったです。Node.jsのサンプルプログラムでなんとなく理解できたくらいで…

この記事は勉強会で僕が質問したこととその解答をまとめたものとなります。

生成規則

今回は11条を読んでいたわけですが、生成規則という言葉が随所に出てきており、それがあまり理解できなかったです。

生成規則は原著だとthe productionの訳で、普通に辞書を引っ張りだしたところで分かるはずもございません。なぜならプログラミング言語の実装周り全体の用語だからです。

生成規則については、以下のリンクが参考になります。

形式言語の構文と意味

Javaでコンパイラの基礎を理解する（4）：プログラム言語の文法はどうやって定義されるのか？ (1/2) - ＠IT

「左辺::=右辺」は生成規則（production rule）と呼ばれます。また、のように、「」で囲まれたものを非終端記号（nonterminal symbol）と呼びます。非終端記号からは新しい記号を生成できますから、各非終端記号については、生成規則を定義する必要があります。「0」や「1」のように、新しい記号を生成しないものは、終端記号（terminal symbol）と呼ばれます。終端記号は実際のソースコードで使用できる記号です。

生成規則が記事や文献によってthe productionだったりproduction ruleだったりするのはあまり気にしなくていいかなという感じです。言語の文法を知る上で生成規則

生成規則という言葉を知るためには、BNF記法(バッカス記法)について知る必要があります。なお、BNFは株の人ではありません。

バッカス・ナウア記法 - Wikipedia

BNF記法は文法を定義するメタ言語ですが、プログラミングの文法定義としてもよく使われます。 例えば、1けたの2進整数をBNF記法であらわすとこうなります。

<one-figure binary digit> ::= 0|1

ECMAScriptに限らずプログラミング言語の文法定義は、このBNF記法をベースにした書き方が多いようです。 ECMA仕様書の11条の冒頭には、このような記述があります。

PrimaryExpression:
  this
  Identifier
  Literal
  ArrayLiteral
  ObjectLiteral
  (Expression)

これはPrimaryExpressionの文法定義をあらわしたもので、BNF記法に直すと以下のようになるかと思われます。

 PrimaryExpression = this | Identifier | Literal | ArrayLiteral |
                     ObjectLiteral | (Expression) 

PrimaryExpressionとして指定できるのはthisやIdentifier等々…という考え方です。

まとめ

生成規則とは、「(文法を)生成(する)規則」ということになります。 上記のPrimaryExpressoinの例を見ると、PrimaryExpressionの文法を生成する規則はthisとかIdentifierとか…みたいな読み方になると思います。