Как вы абстрагируете какое-то выражение для BNF? - PullRequest
Новая
       6

Как вы абстрагируете какое-то выражение для BNF?

0 голосов
/ 24 июля 2011

Например: 

waldo:=fern+alpha/-beta^gamma;

Приведенное выше арифметическое выражение может быть абстрагировано этим BNF (может быть некоторое отличие от стандартного BNF, но давайте пока проигнорируем его): 

AEXP = AS $AS ;

AS = .ID ':=' EX1 ';' ;

EX1 = EX2 $( '+' EX2 / '-' EX2 ) ;

EX2 = EX3 $( '*' EX3 / '/' EX3 ) ;

EX3 = EX4 $( '^' EX3 ) ;

EX4 = '+' EX5 / '-' EX5 / EX5 ;

EX5 = .ID / .NUMBER / '(' EX1 ')' ;

.END

Но абстракция EX1~EX5 не настолько интуитивна для меня (я не совсем понимаю, как они создавались в первую очередь)

Есть ли какие-либо шаги, которые необходимо соблюдать при нормализации таких выражений?

1 Ответ

1 голос
/ 24 июля 2011

Вы можете перевести эту запись в EBNF напрямую.

Присвоение имен категориям EX1-EX5 не является редким способом указания приоритета оператора. На самом деле это хороший IMHO, особенно в некоторых языках с 15 или более уровнями приоритета, как в C и C ++. :)

Вы можете переименовать их в выражение, термин, фактор, первичный и т. Д. (Или любые другие термины, которые имеют для вас смысл).

ДОПОЛНЕНИЕ

Если вам нужен перевод вышеперечисленного в более традиционный EBNF, вот как я бы это сделал: 

AEXP => AS+
AS   => id ':=' EX1 ';'
EX1  => EX2 (('+' | '-') EX2)*
EX2  => EX3 (('*' | '/') EX3)*
EX3  => EX4 ('^' EX3)*
EX4  => ('+'|'-')? EX5
EX5  => id | number | '(' EX1 ')'

Я использую '*' для нуля или более, '+' для одного или нескольких и '?' по желанию. Я думаю, это довольно круто, как здесь обрабатывается приоритет операторов.

ADDENDUM 2:

Обратите внимание: похоже, что правило для EX3 неверно. Теперь так, как есть, вы можете разобрать деревья вот так 

                  EX3
                   |
     +---+----+----+----+---------+
     |   |    |    |    |    |    |
    EX4  ^   EX3   ^   EX3   ^   EX3
            / | \               / | \
         EX4  ^  EX3         EX4  ^  EX3

Так что написание a^b^c^d^e^f может означать a^(b^c)^d^(e^f). Но на самом деле есть и другие способы сделать это дерево. Грамматика неоднозначна.

Похоже, что разработчик грамматики хотел сделать оператор ^ правоассоциативным. Но чтобы сделать это, правило должно было быть 

EX3 => EX4 ('^' EX3)?

Теперь грамматика перестала быть неоднозначной. Посмотрите, как происходит вывод a^b^c^d^e^f: 

          EX3
         / | \
      EX4  ^  EX3
             / | \
          EX4  ^  EX3
                 / | \
              EX4  ^  EX3
                     / | \
                  EX4  ^  EX3
                         / | \
                      EX4  ^  EX3

Теперь a^b^c^d^e^f можно ТОЛЬКО анализировать как a^(b^(c^(d^(e^f))))

Альтернатива состоит в том, чтобы переписать правило как EX3 => EX4 ('^' EX4)* и добавить побочное правило, гласящее: «ВНИМАНИЕ, каретка является правой ассоциативной».

...