top page > computer > programming > algorithm > parse > cfg.html
更新日:
文責: 重城良国

文脈自由文法

文脈自由文法とは

ウィキペディアの文脈自由文法の説明

構文解析の規則を表現する方法のひとつである。表現できる規則の範囲は正規文法より広く、文脈依存文法よりも狭い。ここらへんはウィキペディアのチョムスキー階層に詳しい。正規文法との大きな違いは、「くりかえし」よりも複雑な再帰的な表現が可能という点である。

対応するオートマトンはプッシュダウン・オートマトン。

文脈自由文法を一言で表現するならば「V -> w」。Vはある構造につけられた名前であり、wは構造やそれを構成する部品の列である。つまり、ある構造が他の構造や部品の列で表現できるということ。

バッカス・ナウア記法

ウィキペディアのバッカス・ナウア記法の説明

表記法にはいくつかの変種があり、オリジナルのBNF以外ではEBNFやABNFが有名である。EBNFではBNFの記法上のいくつかの問題を解決し、またオプションやくりかえしといった表現を追加している。ここでは以下の記法のみを使うことにする。

簡単な例

単純なくりかえし(正規文法の範囲)以上の再帰的な文法が定義できることの例として、aとbが同数ずつ並ぶような文字列を表現する文法を定義してみよう。この文法では、たとえば"ab"や"aaabbb"等が正しいとされる。

文法

AB = "a" , AB , "b" | ""

構文解析の例

aaabbbを構文解析してみよう。

  1. ABから始める
  2. ABは"a", AB, "b"となる
  3. そのABが"a", AB, "b"となる
  4. さらにそのABも"a", AB, "b"となる
  5. 今後は規則の右側を使ってABが""となる
  6. 最初のABをaaabbbに置き換えることができた

足し算、かけ算の例

文法

これらを使って変数x, y, zを使った足し算とかけ算の文法を表記してみよう。

  1. EXPRESSION = TERM | EXPRESSION , "+", TERM;
  2. TERM = FACTOR | TERM , "*" , FACTOR;
  3. FACTOR = VARIABLE | "(" , EXPRESSION, ")";
  4. VARIABLE = "x" | "y" | "z";

構文解析の例

x+y*zを解析してみよう。

  1. EXPRESSIONから始める
  2. 規則1の右側からEXPRESSION(1) , "+" , TERM(1)となる
  3. EXPRESSION(1)を規則1の左側でTERM(2)とする
  4. TERM(2)を規則2の左側でFACTOR(1)とする
  5. FACTOR(1)を規則3の左側でVARIABLE(1)とする
  6. VARIABLE(1)を規則4の左側で"x"とする
  7. TERM(1)を規則2の右側でTERM(3) "*" FACTOR(2)とする
  8. TERM(3)を規則2の右側でFACTOR(3)とする
  9. FACTOR(3)を規則3の左側でVARIABLE(2)とする
  10. VARIABLE(2)を規則4の真ん中で"y"とする
  11. FACTOR(2)を規則(3)の左側でVARIABLE(3)とする
  12. VARIABLE(3)を規則4の右側で"z"とする
  13. EXPRESSIONをx+y*zに置き換えることができた

「構文解析」トップへもどる

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics