2

SQL検索条件（のわずかに変更された形式）について、次のfsyacc文法があります。

scalar_expr:
    | ID                                    { Identifier($1) }
    | constant                              { Constant($1) }
    | unary_op scalar_expr                  { Unary($1, $2) }
    | scalar_expr binary_op scalar_expr     { Binary($2, $1, $3) }
    | LPAREN scalar_expr RPAREN             { $2 }

search_condition:
    | search_condition OR search_condition  { Or($1, $3) }
    | search_condition AND search_condition { And($1, $3) }
    | scalar_expr comparison scalar_expr    { Comparison($2, $1, $3) }
    | LPAREN search_condition RPAREN        { $2 }

FParsecで再実装しました（前の質問の助けを借りて）。関連するビットは次のとおりです。

let binOpp = OperatorPrecedenceParser()
let scalarExpr = binOpp.ExpressionParser
binOpp.TermParser <- 
  [ constant 
    id
    between lparen rparen scalarExpr ]
  |> choice

// binary/unary ops added here

let comparison = 
  let compareExpr = pipe3 scalarExpr compareOp scalarExpr (fun l op r -> Comparison(op, l, r))
  between lparen rparen compareExpr <|> compareExpr

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()
searchConditionRef:= 
  chainl1 comparison (andTerm <|> orTerm)        
  <|> between lparen rparen searchCondition

これは解析し1 = 1 or 2 = 2ますが、定数または検索条件全体を括弧でラップすると失敗します（奇妙なことに、比較を括弧でラップすると機能します）。失敗する例を次に示します。

Error in Ln: 1 Col: 8
(1 = 1 or 2 = 2)
       ^
Expecting: infix operator or ')'
: 8

スカラー、比較、および検索条件はすべて同じように開始できますが（open paren-> constant-> infix演算子）、最終的に遭遇する演算子のタイプによって本質的に区別されます。たとえば、ヒットしたor場合、オープニングパレンは条件全体に属し、左側の比較ではないことがわかります。これはバックトラックによって適切に処理されていますか？もしそうなら、入力を消費しないような方法で、複雑な式を解析しているときに、どのように失敗しますか？

スカラー、比較、および検索条件のオプションの括弧の処理は、fsyacc文法の左再帰によって処理されます。これはFParsecで考慮に入れる必要があることを理解しています。しかし、上記のエラーから、私は、それにもかかわらず、大規模なバックトラックから逃れる方法を想像することはできません。

4

1 に答える 1

3

Meta： FParsecタグがこの質問で機能しないのはなぜですか？

前の質問のページのコメントから自分自身を引用します：

ネストされているが相互に再帰的ではない式の文法により、ここでの括弧の解析は少し厄介になります。問題は、パーサーが特定の場所で開き角かっこを検出したときに、括弧で囲まれた式をscalarExpr、comparisonまたはとして解析する必要があるかどうかをまだ認識していないことsearchConditionです。このような式を解析できるようにするには、角かっこを開いた後、角かっこを閉じる前に、パーサーエラーの限定的なバックトラックを導入する必要があります。これにより、パーサーは、括弧で囲まれた式を1つのサブ文法で暫定的に解析し、必要に応じて、別の文法で再度解析できます。 。

let tryBetweenParens p = lparen >>? (p .>>? rparen)

let opp = OperatorPrecedenceParser<_,_,_>()
let scalarExpr = opp.ExpressionParser
opp.TermParser <- choice [constant; id; tryBetweenParens scalarExpr]

// ... 

let comparison = // doesn't currently allow chained comparisons ( e.g. 1 = 2 = 3)
    let compareExpr = pipe3 scalarExpr compareOp scalarExpr (fun l op r -> Comparison(op, l, r))
    compareExpr <|> tryBetweenParens compareExpr

// ...

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

完全なコードはhttp://pastebin.com/i7JFJWJEで入手できます。

括弧で囲まれた（トップレベルの）式がリーフ項が有効なすべての場所で有効である通常の式文法では、文法の1つの場所で親を処理するだけでよいため、解析は明らかに簡単です。OperatorPrecedenceParserスティーブン・スウェンセンが示唆したように、これは単一を使用するための別の議論です。ただし、解析後に適切なエラーメッセージを生成できるようにする場合は、ASTにソースの場所で注釈を付ける必要があります。

于 2012-02-11T12:07:12.953 に答える