区分逻辑运算符和其他中缀运算符

Question

我正在尝试解析 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）？我不想走那条路，所以我希望我在某个地方犯了一个简单的错误。

完整代码是要点。

Answer 1

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

您发现了一个突出显示这一点的案例，但请考虑另一种情况：

1 = 1 or 2 = 2 and 3 =3

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

Answer 2

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

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

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

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

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

修复 searchCondition 解析器的一种方法是分解左手递归-side 表达式：

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)        

更新：
语法中也存在括号解析的问题，请参阅下面的评论。

Answer 3

为逻辑运算符创建单独的 OperatorPrecedenceParser 似乎已经解决了这个问题。

替换，并且 1 = 1 or (2 = 2 and 3 = 3) 解析正确。

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