Главная / ПрограммированиеСоздаём язык программирования → Лекция Я3. Префиксная запись (S-expressions)

Префиксная запись

Префиксная запись знаменита, пожалуй, благодаря популярности Lisp и порождённого им семейства языков программирования.

Префиксное выражение также называют «символическое выражение» (symbolic expression), «S-выражение» (S-expression), SEXP.

В префиксной записи знак операций ставится перед операндами, а всё выражение заключается в скобки. 1 + 2 * 3 превращается в

(+ 1 (* 2 3))

Абстрактное синтаксическое дерево

Префиксную запись можно рассматривать как прямуюлинейную текстовую запись (раскладку) дерева.

Вышеприведённое выражение можно прочитать так:

  • (+ 1 ...) — дерево с узлом +, левым листом 1, и некоторым правым листом (раскрывается на следующем шаге)
  • (* 2 3) — дерево с узлом *, левым листом 2, и правым листом 3

Итого имеем:

Ast

Дерево префиксного выражения (+ 1 (* 2 3))

Вообще говоря, то же самое дерево соответствует и инфиксному выражению 1 + 2 * 3. Но из инфиксной формы записи по сути того же выражения построить дерево гораздо сложнее, а из префиксной оно получается тривиально и прямолинейно.

Префиксное выражение удобно хранить в виде стандартной структуры данных — списка. Например, в Ruby следующим образом можно сохранить данное выражение:

[:+, 1, [:*, 2, 3]]

Получается, префиксная запись в своём роде «триедина»:

  • текстовое представление;
  • графическое представление;
  • представление в языке программирования (списком/массивом).

Из любой заданной из данных трёх формы тривиальным образом можно получить остальные две.

Поэтому префиксные выражения являются удобной формой представления/хранения абстрактного синтаксического дерева.

Ну а программы на Lisp-подобных языках сравнительно просты в парсинге.

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

Грамматику префиксного выражения (BNF) с четырьмя основными арифметическими операциями можно записать следующим образом:

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

<operator> ::= "+" | "-" | "*" | "/"

Естественный язык и типология порядков слов

Yoda prefix

«Назван должен быть твой страх, перед тем как изгнать его ты сможешь.»

Конечно, если бы разработчики фильма немного интересовались лингвистикой (в отличие от пресловутого Star Trek, который породил несколько сложных искусственных языков типа клингонского, в Star Wars в качестве инопланетных языков использовалась просто словесная окрошка), то предложение звучало бы так:

Перед тем как сможешь изгнать его ты, должен быть назван твой страх

Получилось бы префиксное выражение:

(перед_тем_как
  (сможешь
    (изгнать его ты)
  )
  (должен_быть
    (назван твой страх)
  )
)

Глагол на первом месте, а его референты следом. Ключевой предикат (типа временной связки «перед») перед своими аргументами.

Порядок слов является важным вопросом в изучении естественных языков.