2

Treetop を使用して、やや再帰的なパーサーを作成しようとしています。式は数値にすることも、式の加算にすることもできるので、次のように書きました。

grammar Language
  rule expression
    "(" _ expression _ ")" / addition / integer 
  end

  rule addition
    expression _ "+" _ expression
    /
    expression _ "-" _ expression
  end

  rule integer
    '-'? _ [0-9]+
  end

  # space
  rule _
   ' '*
  end
end

それはうまくいきません。何かを解析しようとすると、「SystemStackError: スタック レベルが深すぎます」という例外が発生します (スタック オーバーフロー! イェイ!)。理由はありますか？Treetop でこのような再帰的な定義を指定する正しい方法は何ですか?

4

1 に答える 1

2

あなたの文法は左再帰的です。つまり、 aexpressionはすぐに anadditionになり、次に an expressionetc になる可能性があり、パーサーを無限ループに陥らせます。

代わりに次のようなことを試してください (未テスト! ):

grammar Language

  rule expression
    addition
  end

  rule addition
    multiplication (_ [+-] _ multiplication)*
  end

  rule multiplication
    unary (_ [*/%] _ unary)*
  end

  rule unary
    "-"? _ atom
  end

  rule atom
    number / "(" _ expression _ ")"
  end

  rule number
    float / integer
  end

  rule float
    [0-9]+ "." [0-9]+
  end

  rule integer
    [0-9]+
  end

  rule _
    ' '*
  end

end
于 2011-07-13T09:39:15.810 に答える