スカラーの再帰構造を解析する

Question

私は単純なSQLのような文字列を解析できるスカラーのパーサを構築しようとしています。私が働いて基礎を持っているし、何かに解析することができます

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 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が書いたもの書くだけで、別の方法である。）

Answer 3

スタックオーバーフローします」経験して再おそらく左再帰的な言語の結果である：

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

スカラ2.7でパーサコンビネータは、再帰下降構文解析されています。再帰的降下パーサは、ターミナルシンボルが最初にそれに遭遇したときにどのように考えられないので、これらに問題があります。

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

を代わりにあなたがリファクタリングができ、：あなたがそうのように、lazy valの代わりの方法を使用して文法を定義する必要がありますけれどもスカーラ2.8のpackratのパーサコンビネータのようなパーサの他の種類は、これで何の問題もありません再帰を避けるための言語。あなたが私に与えている例から、この言語でかっこを必要とすると、問題を効果的に解決できます。

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

ここで、より深いレベルの再帰は、解析された別の括弧に対応します。カッコが足りなくなったときに、より深く再帰する必要はないことがわかります。