Смещение / уменьшение грамматики зубров, обработка факториалов наряду с другими унарными операторами - PullRequest
Новая
       7

Смещение / уменьшение грамматики зубров, обработка факториалов наряду с другими унарными операторами

0 голосов
/ 06 июня 2018

Я слоняюсь с зубрами, когда читаю книгу об этом, и я работаю над простым инфиксным калькулятором, где я использую грамматику для определения приоритета, а не %left/%right и порядок таких объявлений.

Большинство калькуляторов зубров, которые я видел, имеют факториал как функцию, а не как оператор, поэтому эти примеры не помогли.

В настоящее время у меня есть: 

 15 calclist:
 16   | calclist expr EOL { printf(" = %d\n", $2); }
 17   | calclist EOL { /* nada */ }
 18   ;
 19 expr:
 20     term
 21   | expr '+' term { $$ = $1 + $3; }
 22   | expr '-' term { $$ = $1 - $3; }
 23   ;
 24 term:
 25     factor
 26   | term '*' factor { $$ = $1 * $3; }
 27   | term '/' factor { $$ = $1 / $3; }
 28   ;
 29 factor:
 30     '|' factor { $$ = $2 > 0 ? $2 : -$2; }
 31   | '-' factor { $$ = 0 - $2; }
 32   | '(' expr ')' { $$ = $2; }
 33   | '(' expr ')' '!' { $$ = factorial($2); }
 34   | NUMBER '!' { $$ = factorial($1); }
 35   | NUMBER
 36   ;

Линии33 и 34 кажутся слишком многословными.Я чувствовал, что правильный способ сделать это - заменить 33/34 на: 

33   | factor '!' { $$ = factorial($1); }

Но затем я получаю конфликты сдвига / уменьшения с помощью операторов отрицания / значения абс, что имеет смысл, когда я смотрю на calc.output файл, созданный с помощью bison -v.

Есть ли более чистый способ сделать это, поддерживая грамматику expr / term / factor, которая определяет приоритет оператора?Или мое рабочее решение - лучшее, что я могу сделать, учитывая мои ограничения (наложенные самостоятельно или иным образом).

1 Ответ

0 голосов
/ 06 июня 2018

Что означает -2!?Если вы добавите factor: factor '!', тогда вы создадите неоднозначность, потому что вы можете проанализировать ее как - <factor: 2 !> или <factor: - 2> !, которые, очевидно, семантически отличаются.[Примечание 1]

Я думаю, что нормальным пониманием было бы то, что постфиксные операторы, такие как ! , имеют приоритет над любым префиксным оператором, так что естественная интерпретация -2! как -(2!) должнаприменяться[Примечание 2]

Таким образом, должен существовать уровень приоритета, который связывает более тесно, чем унарные префиксные операторы.И каждый раз, когда вы вводите новый уровень приоритета, вам нужно вводить новый соответствующий нетерминал (если вы не используете декларации предшествования; подробности и примеры см. В руководстве по бизонам).

Это приводит к: 

expr:
    term
  | expr '+' term { $$ = $1 + $3; }
  | expr '-' term { $$ = $1 - $3; }
  ;
term:
  factor
  | term '*' factor { $$ = $1 * $3; }
  | term '/' factor { $$ = $1 / $3; }
  ;
factor:
    postfix
  | '|' postfix { $$ = $2 > 0 ? $2 : -$2; }
  | '-' postfix { $$ = 0 - $2; }
  ;
postfix:
    postfix '!'  { $$ = factorial($1); }
  | '(' expr ')' { $$ = $2; }
  | NUMBER
  ;

Примечания

  1. (-2)! может быть или не быть семантической ошибкой, но не похоже, что есть вероятность сделать ее синтаксической ошибкой, поскольку синтаксис не может знать, что может быть (3-5)!.Семантически, если бы нужно было обобщить факториал для гамма-функции Эйлера, это было бы значимо для отрицательных чисел, при условии, что Г отрицательного целого числа бесконечно.Но это полное отступление.

  2. В таких языках, как C, которые имеют постфикс ++, это правило также нормально;-x++ означает -(x++).Чаще всего префиксный оператор в этом случае будет *.

...