7

単純な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仕様全体を実装していません;）

4

3 に答える 3

11

さて、再帰は何らかの形で区切らなければなりません。この場合、これを行うことができます：

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

したがって、再帰するには、最初に文字を受け入れる必要があるため、スタック オーバーフローは発生しません。これは重要な部分です。最初に文字を受け入れないと再帰が起こらないことを常に確認していれば、無限再帰に陥ることはありません。もちろん、無限の入力がある場合を除きます。:-)

于 2009-11-26T11:35:32.683 に答える
7

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

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

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

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

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

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

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

于 2009-11-27T04:51:16.930 に答える
0

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

  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  <~ ")"

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

于 2009-11-26T19:23:35.160 に答える