Выражения. Формы записи
A + B), перед ними (префиксная + A B) или после них (постфиксная A B +).
Постфиксная форма знаменита под именем обратной польской записи (ОПЗ): ей не нужны ни скобки, ни правила приоритета, и она вычисляется машиной за один проход.
Читать дальше
Про рождение бесскобочной записи есть известная байка. Лукашевич печатал свою работу на старой немецкой пишущей машинке, у которой было не две, а три клавиши переключения регистров: строчные буквы и знаки препинания, прописные буквы, а также все скобки и специальные символы. Машинка с грохотом заедала при каждом переключении регистра.
Вместо того чтобы мучиться с третьим регистром, Лукашевич изобрел запись, которой скобки не нужны вовсе: привычную схему "операнд, оператор, операнд" он заменил на "оператор, операнд, операнд". Обычная запись A + B превратилась в + A B.
Спустя полвека идея логика пережила второе рождение: обратная польская запись оказалась идеальной для стековых машин. На ней работали инженерные калькуляторы Hewlett-Packard, язык Forth и принтерный язык PostScript, а компиляторы до сих пор приводят выражения именно к такому виду.
Выражения. Формы записи. Проблема линейной записи
Выражение по своей природе нелинейно и рекурсивно: внутри выражения сидят подвыражения, внутри них - свои подвыражения. Но записываем мы его в строку, то есть линейно. Поэтому приходится вводить искусственные правила приоритета операций (сначала умножение, потом сложение) и использовать скобки для преодоления неоднозначности.
Для человека скобки привычны, а вот для компьютера они - источник неудобств. Классический процессор (машина фон Неймана) выполняет команды одну за другой, строго последовательно. Скобка же означает: "отложи операцию, которую начал, и сначала посчитай вот это". Вычисление приходится прерывать, запоминать отложенное и возвращаться к нему позже, а для этого нужны дополнительные структуры данных. В классических учебниках это свойство называют фон-неймановской нежелательностью скобочных структур.
Три формы записи выражений
Место знака операции относительно операндов и определяет форму записи:
- Инфиксная форма: знак операции стоит между операндами:
A + B. Это привычная математическая запись, но именно ей нужны скобки и правила приоритета. - Префиксная форма (польская запись): знак операции стоит перед операндами:
+ A B. Скобки не нужны: каждая операция сама говорит, что берет два следующих операнда. - Постфиксная форма (обратная польская запись, ОПЗ): знак операции стоит после операндов:
A B +. Скобки также не нужны.
Обратите внимание: в бесскобочных формах порядок операндов A B C сохраняется, меняется только положение знаков операций. Почему форм ровно три и как все они получаются из одного источника, покажет следующий урок: это три обхода дерева выражения.
Чем хороша бесскобочная запись
Постфиксная запись (ОПЗ) имеет феноменальную ценность для информатики: она вычисляется за один проход слева направо с использованием классического стека. Именно к такому виду любой компилятор (включая C и Python) сводит ваш код перед генерацией машинных инструкций.
Для машины фон Неймана это идеальный формат: уже не формула, а готовая линейная последовательность действий. Читая ОПЗ слева направо, процессор никогда не откладывает операцию "на потом" и не возвращается назад - каждый символ обрабатывается ровно один раз.
Показать теорию
В теории компиляторов есть класс методов разбора, основанный на грамматиках простого предшествования. Идея такая: для каждой пары соседних лексем можно заранее вычислить отношение предшествования. Знак < означает "справа начинается более приоритетная конструкция, продолжаем читать", знак > - "конструкция слева закончилась, пора сворачивать". Эти отношения сводятся в матрицу предшествования и записываются правилами вида:
; отношения предшествования:
T+ -> T>+ ; слагаемое T закончилось, перед знаком + можно сворачивать
*( -> *<( ; после * идет скобка: сначала нужно разобрать ее
; правила свертки (продукции грамматики, вывернутые наизнанку):
<a> -> F ; операнд превращается в множитель
<T*F> -> T ; произведение сворачивается в слагаемое
$$ ->. YES! ; все свернулось: выражение синтаксически правильноеРазбор превращается в чередование двух действий: сдвиг (читаем строку дальше) и свертка (участок между < и > заменяем на символ грамматики). Если в конце вся строка свернулась в единственный символ выражения между ограничителями $...$, выражение построено правильно.
Самое неожиданное: этому методу не нужны ни стек, ни рекурсия. Целиком его можно записать как нормальный алгоритм Маркова: выражение кладется на ленту в виде строки $(((a+a)*a+a*a)+((a+a)*a+a*a))$, а весь разбор - это последовательность формальных подстановок "найди подстроку - замени". Дойдя до конца, алгоритм печатает YES!, если цепочка допускается грамматикой (сама грамматика в примере взята из классического учебника Ахо по теории компиляции).
Это фундаментальный факт: синтаксический разбор сводится к чисто строковым заменам. Попробовать такие подстановки вживую можно в нашем интерпретаторе нормальных алгоритмов Маркова.
Коротко: главное
- Форма записи определяется местом знака операции: инфиксная - между операндами, префиксная (польская) - перед ними, постфиксная (обратная польская, ОПЗ) - после них.
- Скобки и правила приоритета нужны только инфиксной форме. Префиксная и постфиксная записи однозначны сами по себе.
- Скобки неудобны для последовательной машины фон Неймана: они заставляют откладывать операции и возвращаться назад.
- ОПЗ - готовая линейная последовательность действий: вычисляется за один проход слева направо с помощью стека. Именно к ней компиляторы сводят выражения.
- Бесскобочную запись изобрел логик Ян Лукашевич в 1920-х годах, задолго до компьютеров.
Проверьте себя
В какой форме записано выражение + A * B C?