Неоднозначная грамматика при анализе булевых выражений с помощью Peg.js

Question

Я пишу парсер, который генерирует абстрактное синтаксическое дерево из булевых выражений.

Я следующий Peg.js грамматику, которая поддерживает ^ и ∨, как & и | соответственно:

start 
    = operation 

// optional whitespace 
_ = [ \t\r\n]* 

operation "operation" 
    = "("? _ left:(operand/operation) _ operator:operator _ right:(operand/operation) _ ")"? 
    { 
    return { 
     operation: operator, 
     between: [ left, right ] 
    }; 
    } 

operator "operator" 
    = operator:["&"|"|"] 
    { 
    return operator; 
    } 

operand "operand" 
    = operand:[a-z] 
    { 
    return { operand: operand }; 
    } 

Он успешно разбирает выражения, как a & b и a & (b | c), однако он терпит неудачу, если выражение начинается с операции :

(a | b) & c 
Line 1, column 8: Expected end of input but " " found. 

Выражение распознается корректно, если я окружаю его круглыми скобками:

((a | b) & c) 

Я думаю, что Peg.js только принимает (a | b) как операцию, вместо операнда родительской операции, таким образом, не видя при & c.

Что мне не хватает?

Answer 1

В правиле вашей операции указано, что скобки необязательны, но один из них не обеспечивает соблюдение других правил. Например, успешно обрабатывается (a & b.

Вам нужно разбить его на более мелкие части. Отдельные правила для and и or должны позволить приоритету оператора выполнять свой трюк.

Попробуйте это:

start 
    = sentence 

sentence 
    = orSentence 

orSentence 
    = lhs:andSentence __ '|' __ rhs:orSentence { return { operation: '|', between: [lhs, rhs] }; } 
/andSentence 

andSentence 
    = lhs:primarySentence __ '&' __ rhs:andSentence { return { operation: '&', between: [lhs, rhs] }; } 
/primarySentence 

primarySentence 
    = '(' _ sentence:sentence _ ')' { return sentence; } 
/operand 

operand 
    = operand:[a-z] { return { operand: operand }; } 

_ "optionalWhiteSpace" 
    = whiteSpace * 

__ "mandatoryWhiteSpace" 
    = whiteSpace + 

whiteSpace 
    = [ \t\n\r]+