2

SQL検索条件を解析しようとしていますが、パーサーが論理（AND、OR）を他の中置演算子と区別するのに問題があります。私はそれらを異なるノードとして解析しています（おそらくそれを行うのは難しいです）が、評価フェーズを単純化します。関連するコードスニペットは次のとおりです（必要に応じてさらに含めることができます）。

let opp = OperatorPrecedenceParser<_,_,_>()
let scalarExpr = opp.ExpressionParser
opp.TermParser <- constant <|> id <|> between lparen rparen scalarExpr <|> scalarExpr

//infix operators added here

let comparison = //(e.g., 1 < 2)
  let compareExpr = pipe3 scalarExpr compareOp scalarExpr (fun l op r -> Comparison(op, l, r))
  between lparen rparen compareExpr <|> compareExpr

let andTerm = pstringCI "and" .>> ws
let orTerm = pstringCI "or" .>> ws

let searchCondition, searchConditionRef = createParserForwardedToRef()
searchConditionRef := 
  [ comparison 
    pipe3 searchCondition andTerm searchCondition (fun l _ r -> And(l, r))
    pipe3 searchCondition orTerm searchCondition (fun l _ r -> Or(l, r))
    between lparen rparen searchCondition ]
  |> choice

let filter : Parser<_,unit> = ws >>. searchCondition .>> eof

"1 = 1"正しく解析しますComparison (Eq,Constant (Int32 1),Constant (Int32 1))

しかし、論理演算子を使用して2つの比較を結合しようとすると、たとえば、次"1 = 1 or 2 = 2"のように解析できません。

Lnのエラー：1列：7
1=1または2=2
         ^
期待：入力の終わりまたは中置演算子
：7

1エラーの前をスカラー式として解析し、orバックトラックを押すと、中置演算子ではないこと1を認識し、完全なスカラーとして戻り、論理演算子で結合された条件の左側を解析していることを認識しますor。

1代わりに、おそらく中置演算子を含む、より複雑なスカラー式が始まると仮定し続けるようです。

コードに問題がありますか、または（同じを使用して）中置演算子としてAND/を解析するための解決策はありますか？私はそのルートに行きたくないので、どこかで単純な間違いを犯したことを望んでいます。OROperatorPrecedenceParser

完全なコードは要点です。

4

3 に答える 3

4

and最終的には、優先順位ルールを使用して中置演算子として扱う必要があると思います。これorは、fparsecやfsyaccを含むほとんどのパーサーがそれらを処理するための特別な機能を備えている（つまり、優先順位と結合性によってあいまいさを解決する）理由です。ルール）。

これを強調する1つのケースを見つけましたが、別のケースを検討してください。

1 = 1 or 2 = 2 and 3 =3

またはとして解析する必要があります(1 = 1 or 2 = 2) and 3 = 3か1 = 1 or (2 = 2 and 3 = 3)？

于 2012-02-09T18:34:49.683 に答える
2

choiceのコンビネータがsearchCondition最初の引数パーサーcomparisonを入力に適用し、成功すると引数パーサーの結果を返すため、パーサーは最初の方程式の後で停止します。その後、のfilter解析に失敗するため、エラーが発生します。eofsearchCondition

チュートリアルで説明されているように、choiceと<|>コンビネータは最長一致ルールを実装せず、エラー後にバックトラックしません。したがって、パーサーは機能しません。searchCondition

もう1つの問題は、2番目と3番目の引数が以前に入力を消費せずに再度適用しようとするsearchConditionため、パーサーが左再帰的であるということです。左再帰はスタックオーバーフローにつながります。choicesearchCondition

同様に<|> scalarExpr、定義の最後にあるopp.TermParserことは不要であり、無限の再帰につながる可能性があります。

左再帰パーサー文法をFParsecに変換するときは、左再帰を排除する必要があります。

パーサーを修正する1つの方法searchConditionは、左側の式を除外することです。

let andTerm = stringCIReturn "and" (fun l r -> And(l, r)) .>> ws
let orTerm = stringCIReturn "or" (fun l r -> Or(l, r)) .>> ws

let searchCondition, searchConditionRef = createParserForwardedToRef()

do searchConditionRef:=
    let comparisonTerm =
        comparison <|> between lparen rparen searchCondition

    pipe2 comparisonTerm (many ((andTerm <|> orTerm) .>>. comparisonTerm)) 
          (fun l opRList -> 
                List.fold (fun l (op, r) -> op l r) l opRList)

またはさらに簡単：

do searchConditionRef:= 
    chainl1 (comparison <|> between lparen rparen searchCondition)
            (andTerm <|> orTerm)

更新： 文法には、parensの構文解析にも問題があります。以下のコメントを参照してください。

于 2012-02-10T10:42:51.383 に答える
1

論理演算子用に別の演算子を作成するとOperatorPrecedenceParser、修正されたようです。

交換しました

let andTerm = pstringCI "and" .>> ws
let orTerm = pstringCI "or" .>> ws

let searchCondition, searchConditionRef = createParserForwardedToRef()
searchConditionRef := 
  [ comparison 
    pipe3 searchCondition andTerm searchCondition (fun l _ r -> And(l, r))
    pipe3 searchCondition orTerm searchCondition (fun l _ r -> Or(l, r))
    between lparen rparen searchCondition ]
  |> choice

と

let condOpp = OperatorPrecedenceParser()
let searchCondition = condOpp.ExpressionParser
condOpp.TermParser <- (attempt comparison) <|> between lparen rparen searchCondition <|> searchCondition
condOpp.AddOperator(InfixOperator("or", ws, 1, Assoc.Left, fun l r -> Or(l, r)))    
condOpp.AddOperator(InfixOperator("and", ws, 2, Assoc.Left, fun l r -> And(l, r)))

(1 = 1 or 2 = 2) and 3 = 31 = 1 or (2 = 2 and 3 = 3)正しく解析します。

于 2012-02-09T23:14:35.230 に答える