LL(1)文法、字句解析、構文解析の感覚的説明
言語処理系についてのあいまいなことのまとめと整理
こんにちは、くりすぷです。今回は自分用にメモ。授業の言語処理は論理的にはわかるけど、感覚的には意味不明、わけわかめだから、整理。
字句解析と構文解析
「解析」はGoogle検索で出てきた一番上の定義だと
事柄を細かく分けて、組織的・論理的に調べること。
だけど、コンピュータ自体、秩序(組織)・論理的なので、
と整理できる。 かなり大雑把にいうと、ここでの解析は分類です。
LL(1)文法とはなんぞや
LL(1)文法とは下向き構文解析において最左導出によるアルゴリズム。
※これは定義ではなくインスタント説明です。詳細な定義についてはググりましょう。
ある文字列を生成規則に適用しまくってある文字列を作ることが導出なんだけど、最左導出というのがその適用の仕方がとりま左から適用していくよというやつです。下向き構文解析は下向きにもりもり構文木をつくっていく感じです。
余談
名称の由来の推測
LL(1)の由来は(少しググってもよくわからない、ググる気がなかったので推測)多分LanguageLeft(1)を略したものだと思います。１というのはググった結果、先読みしても良い文字数らしいです。 ソース はこちら。
その根拠は方法の名称には、人の名前か、あるいは、何がやりたいのか簡潔に示しているものなので、似たようなものにLR(1)法というのがあるんですが、そこから考えると、人名ではなさそう。それでいて、明らかにLとRとか、これは右と左の対応だよね、さらに、対象が言語だから、ということです。
個人的には語源というものは、よくわからないものについては、学者がこんな感じじゃねともっともらしい根拠を付けて説明していることも多々なので、生活レベルとしては自分に納得できる説明ができればいいかなと思っています。覚えやすさ重視。正しさなんてよくわからないからね。
余談終わり
LL(1)文法の中身
よくある言語の定義(文法、記号列)に加えて、First（終端、非終端記号含む文字列 → 終端記号）、Follow（非終端 → 終端）、 非終端 → 文字列という遷移ができるとき、Director(遷移に必要なもの、具体的には、非終端と終端 → 終端記号)が定義されていて、このDirector関数について条件があるんですが、それは、ある非終端記号に限定したとき、任意の遷移先に対して、Director関数を適用したとき、タブリがない、ということです。
さて、この関数は順に感覚的に説明すると、Firstが文字列を入力されたときその文字を遷移させていったとき文字列の一番左に来る可能性のある終端記号たちを返す関数、Followは入力の隣にくる終端文字を返す関数で、Directorは入力のように遷移させたときに一番左に来る可能性のある終端記号を返す関数です。
この情報から、先ほどのLL(１)文法に感覚的に特徴づけると、それは左から読むと誤解のない文法というわけです。読むというのは、解析で、誤解のないというのは、ダブりがないということです。
おしまい。
