「コンパイラ」第9回

• 実施日: 2007-06-13(水) 1限
• 内容: LL(1)文法（FOLLOW()関数、判定法）、構文解析プログラム
• 配布資料5.3節、5.4節（5.5節は時間の都合で割愛）

前回に引き続きLL(1)文法の説明を行い、最後にLL(1)文法に対する予測型構文解析プログラムの概略を説明しました。前回説明したFIRST()関数に比べて、FOLLOW()関数は、どういうものか、なんのために必要か、ややつかみにくいかと思います。そのため、かなり時間をかけて説明をしました（その結果、プログラムの説明の時間がなくなってしまいました…）。

講義で使った例（配布資料を作成した後に考えた例なので、資料には載っていません）を再掲します。

S→aAB, A→b|c|ε, B→d

このような文法に対して、終端記号列adの構文解析を考えてみます。最初の文字aを読んで、SをaABに展開します（Sの子節点にa, A, Bを作成して解析木を成長させる）。次の文字dを読んで、Aを展開しようとしますが、A→b|c|εについて、FIRST(b), FIRST(c), FIRST(ε)のいずれにもdは含まれません。では構文解析は失敗なのか…というと、そうではなく、Aをεに展開し、さらにBをdに展開すると、成功します。この例から分かるように、FIRST()関数だけでは、次に出現し得る終端記号を列挙し切れない場合があるわけです。これがFOLLOW()関数を導入する理由です。

FIRST()関数、FOLLOW()関数、LL(1)文法かどうかの判定は、是非自分で手を動かして計算してみて下さい。

次回から意味解析に入ります。