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))

但是一旦我尝试使用逻辑运算符加入两个比较，例如"1 = 1 or 2 = 2"，它无法解析

Ln 中的错误：1 Col：7
1 = 1 或 2 = 2
         ^
预期：输入结束或中缀运算符
：7

我希望它将1错误之前的错误解析为标量表达式，并在or回溯时意识到它不是中缀运算符，1作为完整的标量返回，并识别它正在解析由逻辑运算符连接的条件的左侧or。

相反，它似乎继续假设1开始一个更复杂的标量表达式，可能涉及中缀运算符。

代码有问题，还是将AND/解析OR为中缀运算符的解决方案（使用相同的OperatorPrecedenceParser）？我宁愿不走那条路，所以我希望我在某个地方犯了一个简单的错误。

完整的代码在要点上。

4

3 回答 3

4

我认为最终你会发现你需要用优先规则来对待and和or作为中缀运算符，因为这正是它们的本质，也是包括 fparsec 和 fsycc 在内的大多数解析器具有处理它们的特殊功能的原因（即通过优先级和关联性解决歧义规则）。

您发现一个案例突出了这一点，但请考虑另一个案例：

1 = 1 or 2 = 2 and 3 =3

应该解析为(1 = 1 or 2 = 2) and 3 = 3or1 = 1 or (2 = 2 and 3 = 3)吗？

于 2012-02-09T18:34:49.683 回答
2

您的解析器在第一个等式之后停止，因为 的choice组合器searchCondition将第一个参数解析器comparison应用于输入，并且成功后仅返回参数解析器的结果。然后您会收到一个错误，因为无法filter解析.eofsearchCondition

和组合子不实现最长匹配规则，并且它们choice不会在出错后回溯，如教程中所述。所以你的解析器不能工作。<|>searchCondition

另一个问题是您的searchCondition解析器是左递归的，因为第二个和第三个choice参数将尝试searchCondition再次应用而无需之前消耗任何输入。左递归会导致堆栈溢出。

类似地，<|> scalarExpr在定义末尾opp.TermParser添加是不必要的，并且可能导致无限递归。

当您将左递归解析器语法转换为 FParsec 时，您需要消除左递归。

修复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 = 3并1 = 1 or (2 = 2 and 3 = 3)正确解析。

于 2012-02-09T23:14:35.230 回答