Разбор выражений в скобках - PullRequest
Новая
       4

Разбор выражений в скобках

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

У меня есть следующая грамматика 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 }

Я заново реализовал ее в 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, но перенос константы или всего условия поиска в parens приводит к его сбою (как ни странно, оборачивание сравнения в parens работает).Вот пример, который терпит неудачу: 

Error in Ln: 1 Col: 8
(1 = 1 or 2 = 2)
       ^
Expecting: infix operator or ')'
: 8

Скаляр, условие сравнения и поиска могут начинаться одинаково (open paren -> constant -> infix operator), но в конечном итоге существенно различаются по типу операторавстречается.Например, если вы нажмете or, вы знаете, что открывающая скобка относится ко всему условию, а не к сопоставлению с левой стороны.Правильно ли это обрабатывается при возврате?Если это так, как бы вы потерпели неудачу - при синтаксическом анализе сложного выражения - таким образом, чтобы не потреблять никакого ввода?

Обработка необязательных скобок для скаляров, сравнений и условий поиска обрабатывается слева.рекурсия в грамматике fsyacc.Я понимаю, что это должно быть учтено в FParsec.Но из вышеприведенной ошибки я не могу себе представить, как избежать обширных возвратов в любом случае.

1 Ответ

3 голосов
/ 11 февраля 2012

Мета: Почему тег FParsec не работает по этому вопросу?

Я процитирую себя из комментариев на странице для предыдущего вопроса :

Вложенные, но не взаимно рекурсивные грамматики выражений делают паренсы здесь немного неприятными. Проблема в том, что когда анализатор видит открывающую скобку в определенных местах, он еще не знает, нужно ли разбирать выражение в скобках как 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, как предложил Стивен Свенсен. Однако вам нужно будет пометить AST местами источника, если вы хотите иметь возможность генерировать хорошие сообщения об ошибках после анализа.

...