４．２ 再帰下降解析 （１）再帰下降解析とは ■再帰下降解析（Recursive Descent Parsing）

Presentation on theme: "４．２ 再帰下降解析 （１）再帰下降解析とは ■再帰下降解析（Recursive Descent Parsing）"— Presentation transcript:

1 ４．２ 再帰下降解析 （１）再帰下降解析とは ■再帰下降解析（Recursive Descent Parsing）
４．２　再帰下降解析 （１）再帰下降解析とは ■再帰下降解析（Recursive Descent Parsing） ①各構文要素（非終端記号）に対して１つの解析ルーチンを用意する。 ②各解析ルーチンの実行部は、その構文要素を左辺とする構文規則の右辺に対応する。 ③規則の右辺に現れる非終端記号は、対応する解析ルーチンの呼出しに相当する。 ④終端記号は、入力された記号が対応する記号であることを示す。 C, Pascal等で用いられている。 解析ルーチンの構造と構文図の対応が取れている。

2 （２）再帰下降解析の例 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(); }

3 再帰下降解析の例（その２） OP10::= *|/|% term::= unary | unary OP10 term term()
if(symbol==STAR || symbol=SLASH || (symbol == PERCENT) { input_symbol() term(); 　} } またはTail Recursion だから term() { unary(); while(symbol==STAR || symbol=SLASH || (symbol == PERCENT) { input_symbol() term(); 　} }

4 （３）再帰下降解析の特徴 ①構文規則の再帰的構造に対応して、お互いに再帰的に呼び出しあう。 ②解析における呼出し順序が解析木を表現する。
③構文図と解析ルーチンが対応している。 ④文脈自由文法に対してのみ適用できる。 ⑤どの文脈の自由文法に対しても正しく働くとは限らないが、構文規則の改良によって対処できる。

5 再帰下降解析でうまくいかない例 【正しく働かない例】左再帰（Left Recursion） A::= Aa | b
A → Aa → AAa → AAAa → (無限ループ） 【変更例】 　　A::= bA’ A’::= ε|aA’ A → bA’→ b A → bA’→ baA’→ ba　 A → bA’→ baA’→ baaA’　→　baa (bに続くn個のa)

6 二つ以上の可能性のある場合 ①先読みを行う（ただしうまくいかないこともある） ②左くくりだし（left factoring）を行う。
A::= B | C, B::=uD, C::=uE と書くことができるとき A::= uA’, A’::= D|E 【変更例】 　　if文::= if(式)文 | if(式)文 else 文 【変更例】 　　if文::= if(式)文　E 　　E::= ε | else 文