chapter0102_pratt

Top-Down Operator Precedence (TDOP), парсер Пратта. Те же простейшие выражения.

Ещё немного продолжим тему практичных, но чисто рукописных подходов парсером
Пратта (Vaughan Pratt, 1973). Прежде чем перейдём к реализации, несколько слов
об основной идее.
Возьмём ту же простую грамматику выражения с 5 операциями. Пока что пропустим
группировку скобками. Вырисовывается чёткое соотношение между приоритетами
операций в выражениях; "*" и "/" приоритетнее, чем "+" и "-"; "**"
приоритетнее их всех. Назначим им числа — 10 для "+" и "-", 20 для "*" и "/",
30 для "**". Числа-константы и идентификаторы можно считать ещё приоритетнее,
назначим им 100. (Замечание: можно было взять вместо них соответственно 1, 2,
3, 4 или 16, 95, 173, 888... важны только соотношения между ними, какое больше
и какое меньше.)

Тогда мы можем знать, что:

-> разбирая, что внутри участника цепочки операций сложения или вычитания,
мы можем быть уверены, что там нет ни одного элемента с приоритетом ниже 20;
-> разбирая, что внутри участника цепочки операций умножения или деления,
мы можем быть уверены, что там нет ни одного элемента с приоритетом ниже 30;
-> для возведения в степень — то же, но ни одного с приоритетом ниже 40.

Можно ли этим как-то воспользоваться? Например, сделать явный рекурсивный
вызов не "разобрать слагаемое", а "разобрать всё с приоритетом 20 и выше"?
Да, можно — как раз получится подход класса operator precedence.

Вторым принципиальным моментом в парсере Пратта является привязка действий к
найденным лексемам (идентификаторы, знаки операций и т.п. — дальше понятие
"лексемы" будет раскрыто шире). Это и удобно (привязку можно делать таблично и
меньше писать явного кода), и ограничивает: в разных случаях одни и те же
лексемы могут иметь разные свойства и назначенные действия (это мы не
учитываем различия между инфиксным и префиксным использованием), если есть
такие различия — надо как-то вводить контекст, возможно, меняя при этом
свойства лексем.

Функции, которые привязываются к лексемам, выполняют связанный с ними разбор
и обработку по сути описанных действий. Семантические действия (semantic
actions) дальше будут расписаны подробнее, но в примере с рукописным
рекурсивным парсером были вписаны в код (как «r <- r + r2;» в addsub); в
парсере Пратта они тоже вписываются в код (в его первой показанной тут
версии); в дальнейшем описании в основном будут отделяться от собственно
логики разбора.

В терминах Пратта есть два вида функций, назначаемых лексеме (привязываемых к
ней):

-> null denotation ("nud" в коде): что лексема делает сама по себе или как
  префикс операции;
-> left denotation ("led" в коде): что лексема делает, если слева от неё
выражение с более высоким приоритетом составляющих.

Null denotation мы будем использовать до введения префиксов только для
литералов и скобок, а вот left denotation будет активно применяться для
операций в выражении.  Можно было бы их (nud и led) переименовать в
apply_independent и apply_as_infix, но оставим как есть, добавив ещё
упоминаний в тексте.

Основная логика парсера описывается функцией, которая универсальна для любого
подвыражения (не делим на expression, addsub, muldiv, power...), зато получает
параметром ограничение приоритета, который ей разрешено выбрать из потока
символов обрабатываемого выражения (далее — входного потока). В терминах
Пратта этот параметр ограничения называется right binding power (rbp),
выбирать можно только те лексемы, у которых lbp выше этого rbp. Общая функция
парсинга выглядит так:

func expression(rbp):

  // Входное условие: тут выражение, причём непустое (гарантируется вызывающей
  // стороной).
  // Входной поток разбит лексическим анализом на лексемы, есть текущая
  // лексема, которая анализируется парсером.
  t <- взять текущую лексему;

  // Применить назначенную null denotation.
  // Функция-обработчик должна пропустить из входного потока всё, что
  // отработала.
  // nud своя для каждой лексемы; записываем это в объектном стиле — t.nud()
  // значит "вызвать ту nud(), которая назначена для t".
  advance_token(); // пропустить лексему и прочитать следующую
  v <- t.nud();

  // Цикл помогает реализации типичной левоассоциативной операции.
  // В цикле, пытаемся определить, можем ли мы ещё добавить что-то к
  // текущему значению, не выходя за пределы ограничений по приоритету.
  while (true) {

    // Тут возможно наткнуться на конец ввода. Можно этот случай
    // проверять и отрабатывать отдельно, но чаще оформляют конец ввода
    // как отдельную лексему с приоритетом меньше любого другого в выражении.
    // В любом случае, если конец ввода, просто выходим из цикла.
    t <- взять текущую лексему;
    if (t.lbp <= rbp) {
      break; // Дальше не обрабатываем. Текущая лексема не пропускается!
    }

    // Лексему надо пропустить в любом случае; вынесем это действие сюда.
    advance_token(); // пропустить лексему и прочитать следующую

    // Выполняется та led(), что назначена для t. Замещаем текущее значение.
    v <- t.led(v);
  }
  return v;
}

Кроме назначения функций nud и led на каждую лексему, тут было введено
left binding power (почему left — вопрос терминологии алгоритма, примем как
данное). Для нашего примера с выражениями оно равно:
-> "+", "-" — 10
-> "*", "/" — 20
-> "**" — 30
-> идентификатор, число-константа — 100 (хотя, как уже сказано, можно было что
назначить угодно выше 30)

Null denotation для простейшего варианта определяются только для
идентификатора и числа-константы, и выполняют отдачу или значения переменной,
или собственно константы. Для остальных лексем их имеет смысл определить в
генерацию ошибки парсинга (например, "a+*2" должно дать ошибку). Где эти
лексемы будут вводиться как унарные действия (для "+", "-") — переопределим
позднее.

Теперь сами left denotation. Пример реализации для "+":

func "+".led(v) {
  v2 <- expression(10);
  return v + v2;
}

словами: выбираем продолжение, у которого приоритеты всех лексем строго больше
10 (это будет включать в себя: "*", "/", у которых 20; "**", у которого 30;
константы чисел, приоритет 100; и так далее). Выполняем операцию с левой и
правой частью — сложение. Отдаём результат.

Аналогично (не приводим) будет для остальных операций: "-" — 10 и вычитание;
"*" — 20 и умножение; "/" — 20 и деление;
но: "**" — 29 и возведение в степень. Для "**" вызывается expression(29),
а не expression(30).

func "**".led(v) {
  v2 <- expression(29);
  return pow(v, v2);
}

Это даёт, что в правой части будет допускаться и
возведение в степень (lbp = 30), но не умножение (lbp = 20). Реализация
отношения к рекурсии в алгоритме Пратта такая же, как в рукописном парсере:
левая рекурсия превращается в цикл, правая остаётся рекурсией.

(Вместо 29 тут можно было бы писать 20, если нет промежуточных уровней между
20 и 30. А если их придётся добавить? Именно для возможности такого добавления
в будущем мы и брали интервал 10 между значениями. В целых числах, >29
эквивалентно >=30, но то же неверно для 20, если нет гарантии отсутствия
значений от 21 до 29.)

Теперь реализуем скобки. Так как они являются принудительным изменением логики
интерпретации приоритетов, то они и должны форсировать другую логику. Для
этого определяем null denotation:

func "(".nud() {
  v <- expression(0);
  // Пропустить лексему и подготовить следующую,
  // но выдать ошибку, если текущая была чем-то другим, чем закрывающая скобка
  advance_token(")");
  return v;
}

и определить lbp: для "(" — открывающей круглой скобки — 101, 1000 или любое
значение выше любых приоритетов прочих операций (но не обязательно выше, чем у
atom, как константа или идентификатор); для ")" — закрывающей круглой скобки —
наоборот, 0, -1000... — в общем, ниже, чем у любой другой операции — она
должна ограничивать отработку expression() для любых операций.

Left denotation для скобок _пока что_ должен выдавать ошибку (далее будем
использовать его для вызова функции).

Примера полного кода пока не будет — он будет после добавления префиксных
операций.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Добавление префиксных операций (в рукописный и парсер Пратта).

В предыдущих примерах не было того, что умеют все реальные языки:
отрицание (negation) значения; например, нельзя было написать -a, можно было
только 0-a. Аналогично обычно добавляют унарный плюс; для чисел его
результатом является то же самое число.

Грамматику со введением унарных операций назовём "Грамматика 2".

Для рукописного парсера введём новую грамматическую категорию unary. В функции
power(), заменяем

-  r <- atom();
+  r <- unary();

сама unary будет:

func unary() {
  if (next token is "-") {
    skip "-";
    return -unary();
  }
  if (next token is "+") {
    skip "+";
    return unary();
  }
  return atom();
}

Это поддерживает не только "-a", но и какое-нибудь "--a" (если не конфликтует
с "--" для декремента, о чём будет дальше; если конфликтует — разделяем
пробелами: "- -a"; как быть с пробелами, тоже будет дальше, в подробностях
лексического анализа, пока они пропускаются перед лексемами).

См. test_mtdp_ml_gr02 — полный пример ручного нисходящего парсера для
грамматики 2.

То же самое для Пратта делается через определение nud() для плюса и минуса:

func "-".nud() {
  return -expression(30); // 30 потому что выбираем выше, чем power
}

func "+".nud() {
  return expression(30);
}

(Напоминаем, что уровень lbp не влияет на применение null denotation: влияет
только факт наличия соответствующей лексемы во входном выражении.)

См. test_pratt_ml_gr02 — полный пример парсера Пратта для выражений с числами
в этой грамматике.

Однако, результат приобретает свойства, которые могут оказаться неожиданными.
Например, -2**2 парсится как (-2)**2, что равно 4, а некоторые ожидают, что
это будет -(2**2), равное -4, потому что это лучше соответствует их ожиданиям
от математической записи -2². Это характерно именно для операции возведения в
степень, не для прочих операций. (Хотя при F-делении возможно и неожиданное
понимание выражений типа -13/4; не будем тут углубляться в это.) Это отражено,
например, в Python, где ради этого специально сформирована грамматика:

m_expr ::=  u_expr | m_expr "*" u_expr | m_expr "//" u_expr |
            m_expr "/" u_expr | m_expr "%" u_expr;
u_expr ::=  power | "-" u_expr | "+" u_expr | "~" u_expr;
power ::=  primary ["**" u_expr];

(Цитируется по версии языка 2.7; в 3.* тут расширено элементами за пределами
данного курса. Primary — расширение нашего atom, см. следующую главу. Пока
что считайте его синонимом для atom.)
знак "::=" соответствует простому ":" в наших описаниях грамматик.
То есть там унарные операции типа "отрицание" размещены до возведения в
степень. Это тоже допустимый вариант — но его надо учитывать при написании
программ на таком языке.

Также тут интересно, что вариант Python определяет показатель в операции
степени как u_expr, которое имеет меньший приоритет, чем power. Ранее у нас
переход к менее приоритетным грамматическим конструкциям мог выполняться
только через указание последних в скобках. Оно будет работать даже в парсере
Пратта с его прямой завязанностью на приоритеты, это практически показано, но
далее надо будет доказать корректность этого построения.

Грамматика 3: версия с описанными выше изменениями.

Для самостоятельной работы: исправьте код для рукописного парсера и для
парсера Пратта под такое расположение унарных операций (минус и плюс). По
завершению сравните с test_pratt_ml_gr03 и с его отличиями от
test_pratt_ml_gr02 (воспользуйтесь командой "diff -u" для удобного показа).

// vim: set tw=78 et :