「コンパイラ」第8回

• 実施日: 2007-06-06(水) 1限
• 内容: 構文解析(1) …文脈自由文法との関係、LL(1)文法（概要、FIRST()）
• 配布資料あり（第5章）

前回までお話した文脈自由文法を基に、構文解析の話を始めました。構文解析には大きく分けて下向き構文解析と上向き構文解析がありますが、この講義では下向き構文解析、しかもその特殊な場合である予測型構文解析についてのみ扱います。

文脈自由文法は導出を繰り返すことで終端記号列を得る仕掛けであり、一方構文解析はトークン列（終端記号列）を順次読んで解析木を得る処理です。両者は関係ありそうで関係なさそう、というように見えます。一つの解釈としては、導出により得られた記号列（文形式）を先頭から順次入力記号列と照合していき、その過程で解析木を作っていく、というものが考えられます。この講義では、この解釈に基づいて文脈自由文法と下向き構文解析を結びつけました。この解釈に従えば、予測型構文解析は、導出の際、どの規則を用いて非終端記号の展開を行うかが一意に決められるような下向き構文解析であり、対象とする文脈自由文法には制限があります。このような文法の一つがLL(1)文法です。

ある文法がLL(1)であるかどうかは機械的に判断することができます。その手法で用いられる考え方がFIRSTとFOLLOWです。今回はまずFIRSTについてお話しました。注意しなければならない点は、文脈自由文法では、非終端記号からεが導出される（つまり非終端記号から終端記号列が全く生成されない）ことがある、ということです。この事を念頭に置いて、FIRSTやFOLLOWの求め方、LL(1)文法の判定を読んで下さい。