チョムスキー階層のさわり

ECMAScript を読んでいると、goal symbol や Context-Free Grammars といった語句が登場します。

これは「チョムスキー階層」(特に、その中の「文脈自由文法」、それを元にしたBNF(バッカス・ナウア記法))という概念の語句のようです。

全体を理解することはできていません。理解できた部分のみ備忘録として記事に残そうと思います。


文法とは何か(行われていることのイメージ)

この動画によると、以下の構造が定義されています。

  • 「言語(language)」-> 「記号(symbol)」と「記号に適用される規則」で成り立つ

    「記号に適用される規則」を「文法(grammar)」と呼ぶ

  • 「文法(grammar)」-> 「非終端記号(non-terminal)」を「終端記号(terminal)」に置き換える

例:Parseltongue(ハリー・ポッターの「蛇語」)

symbol:

  • 3つの終端記号: {s, sh, ss}

  • 3つの非終端記号: {snake, I, am}

grammar:

  • "I" -> "sh"

  • "am" -> "s"

  • "snake" -> "ss"

非終端記号を終端記号に変換

  • Nonterminal: "I am snake"

  • -> Nonterminal: "sh am snake"

  • -> Nonterminal: "sh s snake"

  • -> terminal: "sh s ss"

ここでの「文法(grammar)」といった用語は厳密に正確な用語でない可能性があります。

専門的に厳密に正確そうなのは、以下の語句です。

  • 「終端記号(terminal)」と「非終端記号(non-terminal)」

  • 左側に非終端記号・右側に終端記号で表記される「生成規則(production / production rule)」(上で言うところの「文法(grammar)」)

  • 解析・置き換えの開始位置である「開始記号(start symbol / goal symbol)」


ECMAScriptに出てくるワード

context-free grammar

日本語では「文脈自由文法」。複数の生成ルール(production)からなる。

「文脈自由」とは「Cの文脈では、A -> B」のような、文脈を考慮した変換を行わないということのよう。

※ECMAScript内では、文脈を考慮した production が存在する。ECMAScript全体のルールとして「文脈自由文法である」というよりは、単に「文脈自由文法とはなにか」を定義していると考えられる。

chain production

非終端記号 -> 1つの終端記号 + 0以上の非終端記号

言語学的には regular grammar(正規文法)と呼ばれるものが該当するはず。なぜ違う言い方をしているのか、意図は不明。

goal symbol

解析・置き換えのエントリーポイント。おそらく script か module

参考

@kohki_takatama
RUNTEQ 53期 Twitterなどは→potofu.me/ja/my/links