Главная / ПрограммированиеСоздаём язык программирования → Лекция Я1. Язык арифметических выражений

Инфиксная запись выражений

В той записи выражений, к которой мы привыкли со школьной скамьи, знаки операторов ставятся между операндами: 1 + 2 * 3.

Данная запись гораздо сложнее в парсинге, чем префиксная или постфиксная.

Для обозначения порядка действий приходится использовать скобки и учитывать приоритет операций (умножение и деление выполняется перед сложением и вычитанием).

Ассоциативность операторов

Оператор в инфиксной записи называют «левоассоциативным», если череда операторов с одинаковым приоритетом группируется слева направо:

1 + 2 + 3 = (1 + 2) + 3

Умножение и деление — левоассоциативные операторы.

Оператор возведения в степень обычно принято определять правоассоциативным:

234 = 2(34), а не (23)4

Хотя в Ruby для возведения в степень используется **, а ^ используется для двоичного XOR.

В коде для возведения в степень часто используется знак ^: 2 ^ 3 ^ 4 = (2 ^ 3) ^ 4

Почему так сложно, если так просто?

Parenthesis lesson

«Маша» (слева) станет продавщицей, а «Вася» (справа) водителем. Навыком разбора инфиксных выражений они овладели за пару уроков и сразу в совершенстве.

Возникает закономерный вопрос — если у людей нет никаких проблем с парсингом инфиксных выражений (не зря же они стали основой математической записи), то почему у машин такие сложности?

Скорее всего, дело связано с некоторым аппаратным обеспечением, которым врождённо обладают люди, но которое довольно трудно смоделировать/сэмулировать на компьютере.

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

Или применяют остроумные хаки, как разработчики языка Fortran.

Или используют парсер-генераторы и сложные формальные грамматики (см. ниже).

Формальная грамматика инфиксных выражений

Для распознавания корректности инфиксного выражения подойдёт простая грамматика (BNF) следующего вида (далее называемая «наивная грамматика»):

<expression> ::=
  number
  | <expression> "+" <expression>
  | <expression> "-" <expression>
  | <expression> "*" <expression>
  | <expression> "/" <expression>
  | "-" <expression>
  | "+" <expression>
  | "(" <expression> ")"

Однако такая грамматика является неоднозначной, и разобранные с её помощью выражения не будут иметь корректный порядок операций (с учётом приоритета умножения и деления над сложением и вычитанием).

Учёт приоритета операций обычно отдаётся на откуп более сложным вариантам парсеров, позволяющим указать список приоритетов отдельно от основного блока правил вывода.

Однако, путём заметного усложнения правил вывода, можно добиться однозначности грамматики и корректного разбора выражений и без вспомогательных средств:

<expression> ::=
  <mul_or_div>
  | <expression> "+" <mul_or_div>
  | <expression> "-" <mul_or_div>

<mul_or_div> ::=
  <primary>
  | <mul_or_div> * <primary>
  | <mul_or_div> / <primary>

<primary> ::=
  number
  | "(" <expression> ")"