Запрещение ненужных внешних скобок в BNF C -граммаре - PullRequest
Новая
       92

Запрещение ненужных внешних скобок в BNF C -граммаре

0 голосов
/ 15 апреля 2020

Это продолжение этого вопроса, который я задавал ранее о BNF C -грамме для логики высказываний c. Я понял, что он работает с круглыми скобками согласно определению, но теперь я хотел бы расширить грамматику для работы без круглых скобок, однако с уловкой: никакие ненужные внешние скобки не допускаются.

Например, atomi c предложение a должно быть разрешено, но (a) не должно быть распознано. Предложение (a => b) & c также должно быть разрешено, но не ((a => b) & c), и так далее. Последний пример подчеркивает необходимость паретезирования. Уровни приоритета:

  1. эквивалентность <=> и значение =>,
  2. соединение & и дизъюнкция |
  3. отрицание - и
  4. атомов.

Чем выше уровень, тем раньше он будет проанализирован.

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

IFF     .   L     ::=   L   "<=>" L1  ;
IF      .   L     ::=   L   "=>"  L1  ;
AND     .   L1    ::=   L1  "&"   L2  ;
OR      .   L1    ::=   L1  "|"   L2  ;
NOT     .   L2    ::=       "-"   L3  ;
NOT2    .   L2    ::=       "-"   L2  ;
P       .   L3    ::=   Ident         ;

_       .   L     ::=   L1            ;
_       .   L1    ::=   L2            ;
_       .   L2    ::=   L3            ;
_       .   L3    ::=   "(" L ")"     ;

Теперь возникает вопрос, как мне не разрешить внешние скобки, допуск которых вызван последним правилом L3 ::= "(" L ")";? Это строго необходимо для того, чтобы разрешить скобки внутри выражения, но это также допускает их по краям. Думаю, мне нужно какое-то дополнительное правило для устранения неоднозначности, но как это может быть?

Эта грамматика также приводит к примерно 6 конфликтам уменьшения / уменьшения, но разве они не являются неизбежными в рекурсивных определениях?

1 Ответ

3 голосов
/ 15 апреля 2020

Вы можете сделать это, просто запретив форму в скобках на верхнем уровне. Это требует написания иерархии приоритетов другим способом, чтобы распространить ограничение по иерархии. Далее суффикс r указывает на то, что производство «ограничено» и не является скобкой.

Я также исправил конфликты уменьшения / уменьшения, исключив одно из производств NOT. См. Ниже.

(Надеюсь, я правильно понял BNF C. Я написал это в бизоне и впоследствии попытался преобразовать синтаксис.) 

_       .   S     ::=   L0r             ;

IFF     .   L0r   ::=   L0 "<=>" L1     ;
IF      .   L0r   ::=   L0 "=>"  L1     ;

AND     .   L1r   ::=   L1 "&"   L2     ;
OR      .   L1r   ::=   L1 "|"   L2     ;

NOT     .   L2r   ::=       "-"   L2    ;
ID      .   L2r   ::=   Ident           ;                                            

PAREN   .   L3    ::=   "(" L0 ")"      ;

_       .   L0r   ::=   L1r             ;
_       .   L1r   ::=   L2r             ;

_       .   L0    ::=   L0r             ;
_       .   L1    ::=   L1r             ;
_       .   L2    ::=   L2r             ;

_       .   L0    ::=   L3              ;
_       .   L1    ::=   L3              ;
_       .   L2    ::=   L3              ;

( Редактировать : я изменил правила IFF, IF, AND и OR, удалив ограничение (r) из первых аргументов. Это позволяет правилам сопоставлять выражения, начинающиеся с круглых скобок, без сопоставления синтаксис PAREN.)

Если вы также хотите запретить избыточные внутренние скобки (например, ((a & b))), вы можете изменить правило PAREN на 

PAREN   .   L3    ::=   "(" L0r ")"     ;

, что приведет к L0 правило не нужно.

Вариант, который использует меньшее количество единиц продукции, можно найти в ответе от @ IraBaxter до Грамматика для выражений, которая запрещает внешние скобки .

Примечание:

Эта грамматика также приводит к примерно 6 конфликтам уменьшения / уменьшения, но разве они не являются неизбежными в рекурсивных определениях?

Нет, рекурсивные грамматики могут и должны быть однозначным. Сокращение / уменьшение конфликтов не являются неизбежными и почти всегда указывают на проблемы в грамматике. В этом случае они являются результатом избыточных производств для унарного оператора NOT. Наличие двух разных нетерминалов, которые оба могут принять "-" L3, очевидно, приведет к неоднозначности, а неоднозначности всегда приводят к конфликтам синтаксического анализа.

...