StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POParsing parenthesized expressions
text
Body
copied!<p>I have the following fsyacc grammar for (a slightly modified form of) SQL search conditions:</p> <pre><code>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 } </code></pre> <p>I've re-implemented it in FParsec (with some help from a <a href="https://stackoverflow.com/q/9215975/162396">previous question</a>). Here are the relevant bits:</p> <pre><code>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 </code></pre> <p>This parses <code>1 = 1 or 2 = 2</code>, but wrapping a constant or the entire search condition in parens causes it to fail (oddly, wrapping a comparison in parens works). Here's an example that fails:</p> <pre><code>Error in Ln: 1 Col: 8 (1 = 1 or 2 = 2) ^ Expecting: infix operator or ')' : 8 </code></pre> <p>A scalar, comparison, and search condition may all start out similarly (open paren -> constant -> infix operator), but are essentially differentiated by the type of operator eventually encountered. For example, if you hit <code>or</code> you know the opening paren belongs to the entire condition and not the comparison on the left-hand side. Is this properly handled by backtracking? If so, how would you fail--while parsing a complex expression--in such a way that doesn't consume any input?</p> <p>Handling the optional parentheses for scalars, comparisons, and search conditions is handled by left recursion in the fsyacc grammar. I understand this needs to be factored out in FParsec. But from the above error, I can't imagine how to get away from extensive backtracking regardless.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload