再帰降下型の解析Recursive-descent parsing

• これはParse::RecDescentも使っているやり方

  This is the method used by Parse::RecDescent too

• 考え方：ひとつひとつの文法規則を関数にする

  Idea: each grammar rule becomes a function

• expressionという関数の仕事は式を解析すること

  The job of the function expression is to parse an expression

• 成功したらその式のデータ構造を返す

  If it succeeds, it returns a data structure representing the expression

• 失敗したらundef

  If not, it returns undef

• こんな規則があるとする

  If you have a rule like this:

        expression → "(" expression ")" 
                    | term ("+" expression | nothing)

• ここではexpressionとtermという関数を使っている

  You have functions called expression and term

• まず、expressionで次のトークンが(か調べる

  expression looks to see if the next token is (

• そうなら自分を再帰呼び出ししたあとで、)を探す

  If so, it calls itself recursively, and then looks for the )

• 違った場合は、termでタームを探す

  Otherwise it calls term to look for a term

• termが失敗したらexpressionも失敗

  If term fails, expression does too

• 失敗しなかったら+記号と次の式があるか調べる

  Otherwise it looks to see if there's a + sign and another expression

Next

Copyright © 2007 M. J. Dominus