解析は表現

Question

を括弧I持っているため、次のfsyacc文法（のわずかに変更された形式）SQL検索条件：

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 } 

私は（previous questionからいくつかの助けを借りて）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 

スカラー比較し、条件を検索し、すべてが同様に（ - >定数 - オープン括弧>中置演算子）を開始することができますが、基本的に最終的に遭遇したオペレータの種類によって区別されています。たとえば、orとヒットした場合、オープニングの括弧は条件全体に属し、左側の比較ではありません。これはバックトラッキングによって適切に処理されますか？その場合、複雑な式の解析中にどのように入力を消費しないようにすれば、どのように失敗するのですか？

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

Answer 1

メタ： FParsecタグがこの質問に対応していないのはなぜですか？

私はprevious questionページのコメントから自分自身を引用します：

入れ子のではなく、mutally再帰的な表現の文法括弧は、ここで少し厄介な構文解析を行います。問題は、パーザが特定の場所で開始括弧を見ると、括弧で囲まれた式が、scalarExpr、comparison、またはsearchConditionとして解析される必要があるかどうかはまだ分かりません。このような式を解析できるようにするには、角括弧を開いて角括弧を閉じる前に、構文解析プログラムのエラーを限定的に取り戻す必要があります。そのため、括弧で囲まれた式をあるサブ文法で仮解析し、 。

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に注釈を付ける必要があります。