다른 중온어 연산자와 논리 구분

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 골 : 7
1 = 1 또는 2 = 2
     ,583,210        ^
기대 :
입력 또는 이항 연산자의 끝 : 그것은 스칼라 식과 오류 전에 or 철수 타격시 1 파싱 예상 7

는 그것을 아닌 것 실현 중위 연산자 인 경우 1을 완전한 스칼라로 반환하고 논리 연산자 or에 의해 조인 된 조건의 왼쪽 부분을 파싱하는 것으로 인식합니다.

대신에, 더 복잡한 스칼라 표현식을 시작할 가능성이 있다고 가정합니다. 아마도 중위 연산자를 포함 할 수 있습니다.

코드에 문제가 있습니까? AND/OR을 삽입 연산자로 구문 분석하는 솔루션입니까 (동일 OperatorPrecedenceParser 사용)? 나는 그 길을 가고 싶지 않아, 나는 어딘가에서 간단한 실수를하기를 바라고있다.

complete code은 요지입니다.

Answer 1

나는 그것이 그들이 정확히 무엇이며 fparsec 및 fsyacc 등 대부분의 파서를 처리 할 수있는 특수 기능이 이유 때문에 당신이 우선 순위 규칙과 중위 연산자로 and 및 or을 치료하는 데 필요 찾을 궁극적으로 생각하는 (즉, 우선 순위 및 연관성 규칙을 통해 모호성 해결).

이 강조 표시 한 경우를 찾았지만, 또 다른 고려했습니다

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

논리 연산자에 대해 별도의 OperatorPrecedenceParser을 작성하면 문제가 해결 된 것으로 보입니다.

내가 제대로

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) 구문 분석과

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 

를 교체했다. searchCondition의 choice 콤비가 입력에 첫 번째 인수 파서 comparison을 적용하고 성공을 단순히 인수 파서의 결과를 반환하기 때문에

Answer 3

귀하의 파서는, 최초의 식 후 중지합니다. filter은 searchCondition 다음에 eof을 구문 분석하지 못하므로 오류가 발생합니다.

choice 및 <|> 콤비는 하지는 가장 긴 일치 규칙을 구현 않으며 tutorial에 설명 된대로 그들은하지 철수 오류 후 을한다. 따라서 귀하의 searchCondition 파서는 작동하지 않습니다.

또 다른 문제는 searchCondition 파서가 왼쪽에서 순환되는, 두 번째와 세 번째 choice 인수가 이전에 어떤 입력을 사용하지 않고 다시 searchCondition을 적용하려고하기 때문에입니다. 왼쪽 재귀는 스택 오버플로를 발생시킵니다.

마찬가지로, opp.TermParser 정의 끝에있는 <|> scalarExpr을 가지면 무한 재귀가 발생할 수 있습니다.

왼쪽 재귀 구문 분석기 문법을 FParsec로 변환 할 때 왼쪽 재귀를 제거해야합니다. 문법에서 :

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)   

업데이트 searchCondition 파서를 해결하기 위해

한 가지 방법은 왼쪽 측의 발현을 고려하는 것입니다 파렌스 구문 분석에도 문제가 있습니다. 아래 주석을 참조하십시오.