初めまして。最近、コンパイラの学習を始めた初心者です。よろしくお願いいたします。
ある文献には、「BNF表記は文脈自由文法を表す」と書かれています。これは、BNF表記が表す文法と文脈自由文法が等価と文字通り理解していいものなのでしょうか?(つまり、BNF表記された文法は全て文脈自由文法で、文脈自由文法は全てBNF表記で表すことができる、ということなのかです。)
また文脈“自由”文法があるのであれば、文脈“依存”文法というもの存在するのでしょうか?
以上2点につきまして、ご回答よろしくお願いいたします。
No.1ベストアンサー
- 回答日時:
形式言語理論ネタですね.
BNF表記といってもいくつかの変種があるのですが, いずれにしても
<なんか> ::= 記号列
という形で
「左辺にあるのは (<なんか> であらわされる) 非終端記号が 1個だけ」
であることに変わりはありません. で, 書き換え規則がこのように「非終端記号があったらその周辺には無関係に置き換えていい」となっている文法のことを文脈自由文法といいます. なので, BNF表記で書けるものは文脈自由文法で表現できます.
もちろん「文脈依存文法」も存在します. 例えば「aaaabbbb のように a と b が同じ数だけ並ぶ」ものが文脈自由文法であらわされるように, 「aaabbbccc のように a, b, c が同じ数だけ並ぶ」ものは文脈依存文法で表現できます (が文脈自由では書けない).
ただ, 文脈依存はあんまり研究されていないかもしれない.
早速のご回答ありがとうございます。
自分なりにまとめますと、
・BNF表記は文脈自由文法を表現している。
・したがってBNF表記で表される文法は文脈自由文法
となり、BNFと文脈自由文法は等価であることがわかりました。
文脈自由文法を表記するためにBNFを使うわけですね。
文脈依存文法も存在するとのことですが、あまり研究されていないとのことなのですね。プログラミング言語の表現には文脈自由文法でカバーできるからでしょうね。
以上、ご教示ありがとうございます。
No.2
- 回答日時:
ん~, 文脈依存文法は立ち位置が微妙だから....
もっと弱い正規文法や文脈自由文法はいろんなところで使われています. 正規文法は「正規表現」という名前でさまざまに現れていますし, 今どきのプログラム言語は構文的に「だ~いたい」文脈自由文法で規定されています.
逆に, もっと強い句構造文法はチューリング機械と等価であり, 計算理論とからんで研究されていると思います.
これにたいして文脈依存は.... 一応「FORTRAN の構文は文脈依存文法で書ける」というのは聞いたことがありますが, そもそも FORTRAN の構文はこの辺をあまり考えずに作っていたような気もします. 構文が「見てもよくわからん」のが敗因だと思う.
確かに今時のプログラミング言語は、文脈自由文法に若干の(構文木の曖昧さを避けるための)付帯規則から成り立っていますよね。
FORTRANの文法が文脈依存文法で表現できるというのは初耳でした。FORTRANは「空白を読み飛ばす」という規則のために字句解析が一筋縄でいかないのは直感的に分かっていましたが…。FORTRANコンパイラを作るのはなかなかに難しいということでしょうね。
重ね重ねご回答ありがとうございます。
No.3
- 回答日時:
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のサブセットから始めるのが無難ですね。
示唆に富んだご回答ありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 英語 提示した結果構文が非文となる理由について 1 2022/07/25 12:22
- システム科学 オートマトン、文脈自由文法の問題 2 2023/07/12 23:19
- 英語 仮定法と直接法の共存する文での使い分けの文法事項等について 1 2023/07/04 09:19
- WordPress(ワードプレス) Wordpressの記事URLを自由に決めたい 3 2022/06/02 12:05
- Perl perlのプログラミング 部分入れ替えの方法 1 2022/10/11 22:26
- 英語 仮主語の「to be+名詞」の和訳について 4 2022/05/07 14:49
- 英語 Targeting titanium surfaces with improved antimicr 1 2022/07/13 09:50
- 日本語 日本語文法 5 2023/06/28 22:10
- Word(ワード) Wordの目次作成についてです。 卒業論文で目次を作ることになりました。 本文は「見出し」の機能を使 1 2023/01/17 11:26
- 日本語 意味とは何か、どこにあるのか? 16 2022/04/09 11:44
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
司法予備試験の基礎固めの段階...
-
「ちまちま」を使用した前向き...
-
マリオに出てくるような無限階...
-
どうして大人になると勉強しな...
-
戦争に召集されたら、どうしま...
-
本屋さんがこれだけ閉店してい...
-
食塩水の濃度の計算について 「...
-
人種と機能性食品
-
ドル円相場が158円を付けたGW前...
-
誰に産まれるかで決まったしま...
-
女じゃダメなんですか?
-
INFP-aとINFP-tの違いを教えて...
-
学校でなにか悩んでいることが...
-
百人一首
-
危険物乙4の燃焼範囲の計算問...
-
勉強法について 先輩方に質問で...
-
世の中の実践的なことを色々学...
-
人気はあるけど自分は好きでは...
-
太陽の光はセロトニンを活性化...
-
5歳から高校生までそろばん教室...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
誰でもと誰もがとの文法的な違い
-
「不能」と「没能」
-
ということになる
-
チョムスキーの文法って難しい...
-
島崎藤村「まだあげ初めし前髪...
-
「言う」の過去形敬語を第三者...
-
不通に形容詞の連体形の「き」...
-
--つもりでいます
-
日本語の乱れ、「ら抜き言葉・...
-
高校古典の教え方について
-
「聞ける」と「聞こえる」は意...
-
日本語に文法ってあるの
-
「その客観性のなさがお前の悪...
-
高一の文法についてです。 (死...
-
及第点と合格点の違い
-
上は 以上は からには それぞれ...
-
更級日記「門出」の品詞分解を...
-
食べられるについて。
-
漢文の文法について教えてくだ...
-
日本語文法について質問です 使...
おすすめ情報