Scalaでの再帰構造の解析

Question

単純なSQLのような文字列を解析できるパーカーをscalaで構築しようとしています。私は基本的な機能を備えており、次のようなものを解析できます。

select id from users where name = "peter" and age = 30 order by lastname

しかし、ネストされたクラスとクラスを解析する方法、つまり

select name from users where name = "peter" and (age = 29 or age = 30)

私の 'combinedPredicate'の現在の制作は次のようになります。

def combinedPredicate = predicate ~ ("and"|"or") ~ predicate ^^ {
  case l ~ "and" ~ r => And(l,r)
  case l ~ "or" ~ r => Or(l,r)
}

それ自体でcombinedPredicateプロダクションを再帰的に参照しようとしましたが、スタックオーバーフローが発生しました。

ところで、私はここで実験しています... ansi-99仕様全体を実装していません;）

Answer 1

まあ、何らかの形で再帰を区切る必要があります。この場合、これを行うことができます：

def combinedPredicate = predicate ~ rep( ("and" | "or" ) ~ predicate )
def predicate = "(" ~ combinedPredicate ~ ")" | simplePredicate
def simplePredicate = ...

つまり、再帰するには、最初に文字を受け入れる必要があるため、オーバーフローがスタックすることはありません。これは重要な部分です。最初に文字を受け入れない限り再帰が発生しないことを常に保証すると、無限再帰に陥ることはありません。もちろん、無限の入力がない限り。 ：-）

Answer 2

発生しているスタックオーバーフローは、おそらく左再帰言語の結果です。

def combinedPredicate = predicate ~ ...
def predicate = combinedPrediacate | ...

Scala 2.7のパーサーコンビネーターは再帰降下パーサーです。再帰降下パーサーは、最初に出会ったときの終端記号がどのようなものかわからないため、これらの問題を抱えています。 Scala 2.8のpackratパーサーコンビネーターのような他の種類のパーサーではこれに問題はありませんが、メソッドの代わりに lazy val を使用して文法を定義する必要があります：

lazy val combinedPredicate = predicate ~ ...
lazy val predicate = combinedPrediacate | ...

代わりに、左再帰を回避するために言語をリファクタリングすることもできます。あなたが私に与えている例から、この言語で括弧を要求することは問題を効果的に解決するでしょう。

def combinedPredicate = predicate ~ ...
def predicate = "(" ~> combinedPrediacate <~ ")" | ...

現在、より深いレベルの再帰は、解析された別の括弧に対応しています。かっこが足りなくなったときに、さらに深く再帰する必要はないことを知っています。

Answer 3

演算子の優先順位の解決策について読んだ後、次のことを思いつきました：

  def clause:Parser[Clause] = (predicate|parens) * (
            "and" ^^^ { (a:Clause, b:Clause) => And(a,b) } |
            "or" ^^^ { (a:Clause, b:Clause) => Or(a,b) } )

  def parens:Parser[Clause] = "(" ~> clause  <~ ")"

Wichは、おそらく@Danielが書いたものを書く別の方法です;）