再帰下降型構文解析

• A.V.Aho, R.Sethi and J.D. Ullman, "Compilers - Principles, Techniques, and Tools", Addison-Wesley, 1986. 邦訳：原田賢一訳「コンパイラ 原理・技法・ツール I, II」, サイエンス社, 1990.
• 中田育男, 「コンパイラ(新コンピュータサイエンス講座)」, オーム社, 1995.
• 中田育男，「コンパイラの構成と最適化」，朝倉書店，1999.

再帰下降型構文解析の特徴

• 下向き構文解析＝解析木を根から下向きに作っていく解析方法
• 言語の定義がそのままプログラムになるので簡単
• ただし算術式は簡単には解析できない
• 本実験では算術式以外の部分の構文解析に用いる．

再帰下降型構文解析を行う際定義する文法上で注意すべき点

• 後戻り(back tracking)
• 左再帰性(left-recursion)

後戻り

S ::= aBd
B ::= b | bc

ここで，入力として abcd が来たとする．まず，a が S からの遷移の一番目の文字に一致するので，次に b について検討する．b は B からの遷移の左側に一致するので B を b と解釈して次の文字を読み込むと，入力は c だが文法上は次に d が来なければならないことになって，この文法に合わないことになる．そこで，再び B の評価に戻り，今度は B を bc と解釈する方を選ぶ．すると，最後の d も文法に一致して入力 abcd を受理する．ここでは B の解釈をやり直した．これを「後戻り」という．

構文解析での後戻りは，文法の中で後戻りの原因となっているもの（この場合には B に関するところ）に「くくりだし」と呼ばれる処理を行って文法を変更することでなくすことができることがある．

今回の実験では，後戻りの発生するような文法になっていた場合，文法は変更しないで再帰下降型構文解析のプログラムで対処する．つまり，「くくりだし」に相当する部分をプログラムで実現する．具体的には，共通部分の処理をまずしてしまってから分岐をするようにプログラムを作成すればよい．

左再帰性

A ::= Aa | b

左再帰性は除去アルゴリズムがあるのでそれにしたがって文法を変更すれば除去できる．

実験で行うこと

1. 自グループの定義した文法が後戻りが発生する文法であるかどうかチェックする．
   • もし後戻りが発生するような文法だったら，教員に知らせてください．原則としては，プログラムで対処します．
2. 自グループの定義した文法が左再帰性をもっているかどうかチェックする．
   • もし左再帰性を持っている文法だったら，文法を変更して対処してください．
3. 自グループが定義した文法にしたがって作成すべき関数の仕様を決定する．
4. 自グループが定義した文法にしたがってプログラムを書く（書き方解説）．

• 再帰下降型構文解析スライド
• 再帰下降型構文解析スライド2回目