Отличие логического от других инфиксных операторов - PullRequest
Новая
       64

Отличие логического от других инфиксных операторов

2 голосов
/ 09 февраля 2012

Я пытаюсь разобрать условия поиска 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 backtrack, понимая, что это не инфиксный оператор, возврат1 как полный скаляр и узнайте, что он разбирает левую часть условия, к которому присоединяется логический оператор or.

Вместо этого он, кажется, продолжает предполагать, что 1 начинает более сложное скалярное выражение, возможно, с использованием инфиксного оператора.

Есть ли проблема с кодом или есть решение для синтаксического анализа AND / OR как инфиксных операторов (используя тот же OperatorPrecedenceParser)?Я бы предпочел не идти по этому пути, поэтому я надеюсь, что где-то допустил простую ошибку.

Полный код находится в гисте.

Ответы [ 3 ]

4 голосов
/ 09 февраля 2012

Я думаю, что в конечном итоге вы обнаружите, что вам нужно рассматривать 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)?

2 голосов
/ 10 февраля 2012

Ваш синтаксический анализатор останавливается после первого уравнения, потому что комбинатор choice searchCondition применяет анализатор первого аргумента comparison к входным данным и в случае успеха просто возвращает результат синтаксического анализатора аргумента.Затем вы получите сообщение об ошибке, потому что filter не может выполнить синтаксический анализ eof после searchCondition.

. Комбинаторы 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)

Обновление: В грамматике также есть проблема с анализом паренов, см. Комментарии ниже.

1 голос
/ 10 февраля 2012

Создание отдельного 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) правильно разобрать.

...