Объединить подобные конструкции в рекурсивных правилах

Question

Это для парсера в Jison, но я думаю, то же самое относится и к Bison.

У меня есть правило, которое имеет определение для выражения.

expr
    : NUMBER -> { type: "number", value: $1 }
    | "(" expr ")" -> $2
    | expr "+" expr -> { type: "+", left: $1, right: $3 }
    | expr "-" expr -> { type: "-", left: $1, right: $3 }
    | expr "*" expr -> { type: "*", left: $1, right: $3 }
    | expr "/" expr -> { type: "/", left: $1, right: $3 }
    ;

В той же грамматике у меня также есть правило для "выражения фильтра", которое также поддерживает "параметры".

filterExpr
    : NUMBER -> { type: "number", value: $1 }
    | PARAM -> { type: "param", name: $1 } /* parameter */
    | "(" filterExpr ")" -> $2
    | filterExpr "+" filterExpr -> { type: "+", left: $1, right: $3 }
    | filterExpr "-" filterExpr -> { type: "-", left: $1, right: $3 }
    | filterExpr "*" filterExpr -> { type: "*", left: $1, right: $3 }
    | filterExpr "/" filterExpr -> { type: "/", left: $1, right: $3 }
    ;

Это работает, но когда я добавляю операторы, я должен изменить оба определения. Есть ли способ объединить общую часть "expr" и "filterExpr" в грамматике?

Answer 1

Сам Javascript (официально ECMAScript, определенный в ECMA-262) описывается с использованием расширения BNF, которое позволяет дополнять правила булевыми квалификаторами ("параметры" на языке стандарта). Это имеет именно тот эффект, который вы ищете, и это явно упрощает представление несколько сложной грамматики языка. Полное объяснение расширений BNF можно найти в разделе 5.1.5 (Грамматическая нотация) стандарта; в итоге, параметры могут передаваться с левой стороны на нетерминалы с правой стороны, или они могут быть явно установлены или не установлены для терминалов RHS; кроме того, они могут использоваться для фильтрации возможных производств на основе либо наличия, либо отсутствия параметра. (Есть пример в конце этого поста.)

Это конкретное расширение BNF не добавляет никакой генеративной мощности к BNF; любое его использование можно механически исключить, просто перечисляя возможности. К сожалению, я не знаю ни одного генератора грамматики, который бы реализовывал этот формализм (хотя, безусловно, возможно, что некоторые реализации Javascript содержат собственный генератор синтаксических анализаторов).

Для ваших целей было бы легко предварительно обработать вашу грамматику jison, чтобы реализовать нечто очень похожее. Действительно, было бы относительно легко предварительно обработать файл грамматики бизонов, но это проще с jison, потому что вы можете вычислить грамматику программно и передать ее jison как объект JSON. Эта функция недостаточно документирована, но руководство Jison содержит достаточно примеров, чтобы ее можно было легко использовать. Смотрите, например, раздел CommonJS.

---

Как и было обещано, вот выдержка из грамматики ECMA-262, в которой показано использование этого расширения BNF:

IdentifierReference может быть квалифицирован двумя возможными логическими определителями (Yield а также Await) приводя к четырем возможностям. Это всегда может быть Identifier; это может быть ключевое слово yield только если не квалифицирован с Yield атрибут или ключевое слово await только если не квалифицирован с Await,

IdentifierReference[Yield, Await]:
    Identifier
    [~Yield]yield
    [~Await]await

Таким образом, эта единственная строфа эквивалентна четырем нетерминалам, которые могут быть созданы механически:

IdentifierReference: Identfier | yield | await
IdentifierReference_Yield: Identifier | await
IdentifierReference_Await: Identifier | yield
IdentifierReference_Yield_Await: Identifier

Вот как это применяется: Expression может быть квалифицировано тремя атрибутами, через которые все проходят (?Yield) к нетерминалам с правой стороны.

Expression[In, Yield, Await]:
    AssignmentExpression[?In, ?Yield, ?Await]
    Expression[?In, ?Yield, ?Await] , AssignmentExpression[?In, ?Yield, ?Await]

yield Выражение допускается только в вариантах AssignmentExpression квалифицированный с Yield:

AssignmentExpression[In, Yield, Await]:
    ConditionalExpression[?In, ?Yield, ?Await]
    [+Yield]YieldExpression[?In, ?Await]

Наконец, пример с явными параметрами. В производстве для GeneratorMethod, Yield явно указано для PropertyName производство (что мешает yield от распознавания в качестве идентификатора в списке параметров) и GeneratorBody определяется как FunctionBody с Yield (с учетом yield выражения и запрещающие yield в качестве идентификатора) и без Await (не позволяя await выражения, но позволяющие await быть идентификатором).

GeneratorMethod[Yield, Await]:
    * PropertyName[?Yield, ?Await] ( UniqueFormalParameters[+Yield, ~Await] ) { GeneratorBody }

GeneratorBody:
    FunctionBody[+Yield, ~Await]

Большая часть вышеуказанной сложности требуется по требованию обратной совместимости: поскольку программы, написанные для более ранних версий JS, возможно, использовали yield а также await в качестве имен переменных эти ключевые слова зарезервированы только в синтаксическом контексте, который не был доступен в более ранних версиях. (Это слишком упрощенное, но детали этого вопроса выходят за рамки.)