BNF表記と文脈自由文法の関係について

初めまして。最近、コンパイラの学習を始めた初心者です。よろしくお願いいたします。

ある文献には、「BNF表記は文脈自由文法を表す」と書かれています。これは、BNF表記が表す文法と文脈自由文法が等価と文字通り理解していいものなのでしょうか？（つまり、BNF表記された文法は全て文脈自由文法で、文脈自由文法は全てBNF表記で表すことができる、ということなのかです。）

また文脈“自由”文法があるのであれば、文脈“依存”文法というもの存在するのでしょうか？

以上2点につきまして、ご回答よろしくお願いいたします。

No.1 ベストアンサー 回答者： Tacosan 回答日時： 2010/02/18 23:01

形式言語理論ネタですね.

BNF表記といってもいくつかの変種があるのですが, いずれにしても
<なんか> ::= 記号列
という形で
「左辺にあるのは (<なんか> であらわされる) 非終端記号が 1個だけ」
であることに変わりはありません. で, 書き換え規則がこのように「非終端記号があったらその周辺には無関係に置き換えていい」となっている文法のことを文脈自由文法といいます. なので, BNF表記で書けるものは文脈自由文法で表現できます.
もちろん「文脈依存文法」も存在します. 例えば「aaaabbbb のように a と b が同じ数だけ並ぶ」ものが文脈自由文法であらわされるように, 「aaabbbccc のように a, b, c が同じ数だけ並ぶ」ものは文脈依存文法で表現できます (が文脈自由では書けない).
ただ, 文脈依存はあんまり研究されていないかもしれない.

この回答へのお礼

早速のご回答ありがとうございます。

自分なりにまとめますと、
・BNF表記は文脈自由文法を表現している。
・したがってBNF表記で表される文法は文脈自由文法
となり、BNFと文脈自由文法は等価であることがわかりました。
文脈自由文法を表記するためにBNFを使うわけですね。

文脈依存文法も存在するとのことですが、あまり研究されていないとのことなのですね。プログラミング言語の表現には文脈自由文法でカバーできるからでしょうね。

以上、ご教示ありがとうございます。

お礼日時：2010/02/19 11:34

No.3 回答者： Tacosan 回答日時： 2010/02/19 23:23

FORTRAN で問題になるのは

1. 「空白を読み飛ばす」+「字句解析と構文解析が渾然一体となった処理」
2. 予約語が存在しないこと
3. 全く同じ形なのに意味が変わりうる
くらい, かな.
1 についていえば, 今時の言語だと「まず字句解析を行い, その後で構文解析」という順序があります. つまり字句解析の時点では構文解析の都合は無視できます. しかし FORTRAN では「構文解析がきちんとできるように字句解析しなければならない」という縛りがあり, 具体的にはたとえば
DO 10 I=1, 10
DO 10 I=1. 10
という 2つの文をそれぞれ
DO 10 I = 1 , 10
DO10I = 1.10
と字句解析しなきゃならないのが問題です.
2 は, まあそのまま. C なら「if って書いてあるから if文だ」って感じで構文解析できるんだけど FORTRAN ではそうもいかない.
3 では
F(X) = 3*X+5
とあるときにこれだけでは配列なのか文関数なのかが区別できない. もちろん意味解析すればいいんだけど.
1, 2 の理由で文脈自由にならないんじゃないかな. さすがに FORTRAN は処理系を作ろうと思ったことがないからわからんけど....

この回答へのお礼

FORTRANの解析に関して、詳しい説明ありがとうございます。
様々な理由でFORTRANコンパイラを作るのは難しそうですね。

実はFORTRAN処理系を作るのも（遠い先の話ですが）夢でして、その時にはGNUのgfortranのソースを眺めることになりそうです。（苦笑）
まずは素直に作れるCのサブセットから始めるのが無難ですね。

示唆に富んだご回答ありがとうございました。

お礼日時：2010/02/19 23:44

No.2 回答者： Tacosan 回答日時： 2010/02/19 13:24

ん～, 文脈依存文法は立ち位置が微妙だから....

もっと弱い正規文法や文脈自由文法はいろんなところで使われています. 正規文法は「正規表現」という名前でさまざまに現れていますし, 今どきのプログラム言語は構文的に「だ～いたい」文脈自由文法で規定されています.
逆に, もっと強い句構造文法はチューリング機械と等価であり, 計算理論とからんで研究されていると思います.
これにたいして文脈依存は.... 一応「FORTRAN の構文は文脈依存文法で書ける」というのは聞いたことがありますが, そもそも　FORTRAN の構文はこの辺をあまり考えずに作っていたような気もします. 構文が「見てもよくわからん」のが敗因だと思う.

この回答へのお礼

確かに今時のプログラミング言語は、文脈自由文法に若干の（構文木の曖昧さを避けるための）付帯規則から成り立っていますよね。

FORTRANの文法が文脈依存文法で表現できるというのは初耳でした。FORTRANは「空白を読み飛ばす」という規則のために字句解析が一筋縄でいかないのは直感的に分かっていましたが…。FORTRANコンパイラを作るのはなかなかに難しいということでしょうね。

重ね重ねご回答ありがとうございます。

お礼日時：2010/02/19 14:15