f# - 解析括号表达式

Question

对于 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 中重新实现了它(在 previous question 的帮助下)。以下是相关位:

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 页面上的评论中引用自己的话。 :

嵌套但不相互递归的表达式语法使括号在这里解析有点讨厌。问题是当解析器在某些位置看到左括号时，它还不知道括号中的表达式是否需要解析为 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 获得

对于通常的表达式语法，任何带括号的(顶级)表达式在叶项有效的任何地方都有效，解析显然更简单，因为您只需要在语法中的一个地方处理括号。这是仅使用单个 OperatorPrecedenceParser 的另一个论点。 ，正如斯蒂芬斯文森所建议的那样。但是，如果您希望能够在解析后生成良好的错误消息，则必须使用源位置对 AST 进行注释。