４．２再帰下降解析（１）再帰下降解析とは ■再帰下降解析（Recursive Descent Parsing） ①各構文要素（非終端記号）に対して１つの解析ルーチンを用意する。 ②各解析ルーチンの実行部は、その構文要素を左辺とする構文規則の右辺に対応する。 ③規則の右辺に現れる非終端記号は、対応する解析ルーチンの呼出しに相当する。 ④終端記号は、入力された記号が対応する記号であることを示す。 C, Pascal等で用いられている。解析ルーチンの構造と構文図の対応が取れている。（２）再帰下降解析の例 While文::= while ( 式 ) 文 If (symbol == WHILE) { input_symbol(); if(symbol == LEFT_PARENTHESIS)input_symbol(); else error(); expression(); if(symbol == RIGHT_PARENTHESIS)input_symbol(); else error(); statement(); } 再帰下降解析の例（その２） OP10::= *|/|% term::= unary | unary OP10 term term() { unary(); if(symbol==STAR || symbol=SLASH || (symbol == PERCENT) { input_symbol() term(); } } またはTail Recursion だから term() { unary(); while(symbol==STAR || symbol=SLASH || (symbol == PERCENT) { input_symbol() term(); } } （３）再帰下降解析の特徴 ①構文規則の再帰的構造に対応して、お互いに再帰的に呼び出しあう。 ②解析における呼出し順序が解析木を表現する。 ③構文図と解析ルーチンが対応している。 ④文脈自由文法に対してのみ適用できる。 ⑤どの文脈の自由文法に対しても正しく働くとは限らないが、構文規則の改良によって対処できる。再帰下降解析でうまくいかない例【正しく働かない例】左再帰（Left Recursion） A::= Aa | b A → Aa → AAa → AAAa → (無限ループ）【変更例】 A::= bA’ A’::= ε|aA’ A → bA’→ b A → bA’→ baA’→ ba A → bA’→ baA’→ baaA’ (bに続くn個のa) → baa 二つ以上の可能性のある場合 ①先読みを行う（ただしうまくいかないこともある） ②左くくりだし（left factoring）を行う。 A::= B | C, B::=uD, C::=uE と書くことができるとき A::= uA’, A’::= D|E 【変更例】 if文::= if(式)文 | if(式)文 else 文【変更例】 if文::= if(式)文 E E::= ε | else 文