구문 분석은 표현

Question

을 괄호 나는이에 대해 다음 fsyacc 문법 (약간 수정 양식) SQL 검색 조건 :

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 } 

I의 (a previous question에서 약간의 도움으로) FParsec에서 다시 구현했습니다. 여기서 중요한 비트이다 :

는

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에서 이것을 고려해야 할 필요가 있음을 이해합니다. 그러나 위의 오류에서, 나는 상관없이 광범위한 backtracking에서 벗어나는 방법을 상상할 수 없습니다.

Answer 1

메타 : 왜이 질문에 FParsec 태그가 작동하지 않습니까?

나는 previous question의 페이지에 코멘트에서 자신을 인용합니다 :

중첩하지만 mutally 재귀 표현 문법은 괄호 여기에 약간 불쾌한 구문 분석합니다. 문제는 파서가 특정 위치에서 여는 괄호를 볼 때 괄호 안에 표시된 표현식을 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을 사용하는 또 다른 주장입니다. Stephen Swensen이 제안했습니다. 그러나 구문 분석 후에 좋은 오류 메시지를 생성하려면 AST에 소스 위치를 주석으로 추가해야합니다.