DSL / A short dip into language theory

DSL

言語理論を少しかじる †

一言要約 †

文法の観点から言語学を分類すると正規文法、文脈自由文法、文脈依存文法の3つに分類されるが、文脈自由文法はネストされたブロックを扱え、多くのプログラミング言語で採用されている。

要約 †

• 文法を分類する観点から、言語学を概観する。この分類の観点はチョムスキー階層と呼ばれる。

• 主なカテゴリーは正規文法、文脈自由文法、文脈依存文法の3つ。

• 正規文法は有限状態機械を使用するのに使われる点で重要だ。その実現方法が正規表現だ。

• 正規表現は少し使用するには複雑だが、難しいことをするには強力な方法だ

• 正規文法はネストされたブロックを使用できない点で問題を抱えている(ネストされたブロックを解析するには有限状態機械は使えない)

• ネストされたブロックを扱うには文脈自由文法が必要。

• プッシュダウン機械(スタックを持った有限状態機械)で実装される

• 多くのプログラミング言語は文脈自由文法を使用している

• すべての構文に対応しているわけではない(変数は使用する前に宣言しなければならない)

• 文脈依存文法は変数の宣言が階層の枝の外側で宣言できることに対応している

• ただし私たちは一般的な文脈依存パーサーの書き方を知らない

• ⇒ネストされたブロックを扱うには文脈自由文法を扱う必要がある
  • Delimiter Directed TranslationよりもSyntax Directed Translationを使うべき

• パーサージェネレータは使い慣れればわかりやすく、使いすぎることはない

• Syntax Directed Translationは伝統的に字句解析と構文解析に分けられる
  • 字句分析：有限状態機械で解析
  • 構文解析：プッシュダウン機械
  • 例外もあり。Antlrは両方ともプッシュダウン機械を使用。

• 新しいものとしてParsing Expression Grammar(PEG)がある
  • PEGは字句解析と構文分析を分離せず(読み取りなし解析とよばれる)、多くの状況で文脈自由文法よりも、より適しているようだ
  • ただまだ未成熟。

ファウラーへのフィードバック †

担当者のつぶやき †

全く不慣れな分野で勉強不足なので、理解が追いつかない。 http://kurt.scitec.kobe-u.ac.jp/~kikyo/lec/06/automaton/ とかで勉強すればいい？

みんなの突っ込み †