chapter0101_mtdp

Вводное
Рекомендуется базовый курс программирования и знание Python и C/Java/C#
(одного из трёх на выбор).
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Интуитивное введение и рукописный нисходящий парсинг. Простейшие выражения.

С ходу начнём с реального примера — вычисление выражений из целых чисел, 4
действий арифметики, плюс возведение в степень. Это типовой пример, с которого
начинается практически любое обучение теме грамматик. Нарисуем правила — пока
что без всякой математической основы за ними, на чистой интуиции. Правила
будут поданы "готовыми", но обдумайте их при чтении; далее станет яснее,
почему они такие.

"Грамматика 1":

expression: addsub (0.1); // корневое правило
addsub: muldiv (1.1) | addsub "+" muldiv (1.2) | addsub "-" muldiv (1.3);
muldiv: power (2.1) | muldiv "*" power (2.2) | muldiv "/" power (2.3);
power: atom (3.1) | atom "**" power (3.2);
atom: number (4.1) | "(" expression ")" (4.2);

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

Слово number понимаем как реализуемые чем-то внешним — целое число (без знака).

Рассмотрим выражение: "3+4*5". Нетрудно убедиться, что оно имеет единственный
вариант соответствия этим правилам:
альтернатива 1.2 делит на "3" (addsub) и "4*5" (muldiv);
"3" также по последующим правилам является muldiv (по 1.1), power (по 2.1),
atom (по 3.1) и number (по 4.1);
похожим образом, "4*5" сначала по 2.2 делится на "4" как muldiv и "5" как
power... и точно так же мы спускаемся, хоть и по более коротким путям, к
number (по 4.1).

Эти правила не позволяют понять выражение "3+4*5" как "3 сложить с 4 и
полученное умножить на 5", потому что левая сторона от знака "*" может быть
только muldiv, а это не допускает подвыражений с "+", если не вводить скобки
(правило 4.2). Если ввести скобки, получится выражение "(3+4)*5", в котором
чётко видна группировка. Такого объяснения, хоть и достаточно неформального,
достаточно, чтобы понять, как работают приоритеты операций в таких правилах.

По таким правилам — предполагая, что в них нет внутренних противоречий — уже
можно составлять рукописные рекурсивные нисходящие (top-down) парсеры. Но тут
есть один важный логический переход с участием понятия "левосторонняя
рекурсия" (или просто "левая рекурсия"), который пока молча реализуем, а потом
обсудим. Псевдокод разбора с вычислением значения выражения будет выглядеть
так:

func expression() {
  return addsub(); // 0.1
}

// addsub, левоассоциативные сложение и вычитание
func addsub() {
  r <- muldiv(); // 1.* общее
  do {
    continuing <- false;
    if (next token is "+") { // 1.2
      skip "+";
      r2 <- muldiv();
      r <- r + r2;
      continuing <- true;
    }
    if (next token is "-") { // 1.3
      skip "-";
      r2 <- muldiv();
      r <- r - r2;
      continuing <- true;
    }
  } while (continuing);
  return r;
}

// muldiv, с точностью до операций и следующего уровня грамматики
// совпадающая с addsub
func muldiv() {
  r <- power(); // 2.* общее
  do {
    continuing <- false;
    if (next token is "*") { // 2.2
      skip "*";
      r2 <- power();
      r <- r * r2;
      continuing <- true;
    }
    if (next token is "/") { // 2.3
      skip "/";
      r2 <- power();
      r <- r / r2;
      continuing <- true;
    }
  } while (continuing);
  return r;
}

// power, правоассоциативная, в отличие от базовых арифметических операций
// (предыдущие addsub и muldiv)
func power() {
  r <- atom(); // 3.* общее
  if (next token is "**") { // 3.2
    skip "**";
    r2 <- power();
    r <- r ** r2;
  }
  return r;
}

// atom: две альтернативы для проверки
func atom() {
  if (next token is number) { // 4.1
    return parse_and_skip_number();
  }
  if (next token is "(") { // 4.2
    skip "(";
    r <- expression();
    skip ")"; // скобка обязана быть, иначе генерируем ошибку
    return r;
  }
}

Многие пункты в этом псевдокоде будем раскрывать по ходу дальнейшего
изложения, пока что следует его читать максимально интуитивно. (Также тут
отсутствуют целые "слои" логики типа обработки ошибок разбора.) Но некоторые
моменты лучше объяснить прямо сейчас.

1. После двух косых черт идут комментарии до конца строки (стиль C++).

2. Знак "<-" означает присвоение тому, что слева от него, значения справа от
него — то есть с момента выполнения этого оператора закреплённое значение
заменено на новое. Далее будет обсуждение такого выбора. Он аналогичен ":=" в
Pascal, "=" в C, C++, Java, C#...

3. Мы оперируем понятиями типа "next token is какая-то сущность
(последовательность символов)", это обычно относят к понятиям "лексического
анализа". Лексический анализ устроен, будет разбираться дальше, пока условно
введём термин "лексема" (для английского традиционно принято token), не
формализуя его; у нас тут лексемами будут знаки операций, числа-константы и
идентификаторы (где используются). Причём "*" — лексема, и "**" — лексема, а
не две лексемы "*". Неоднозначности разбора тут не будет. Например:
"3+44*555" разбирается как последовательность лексем: "3", "+", "44",
"*", "555".

(В "Книге дракона" разделяют lexeme как элемент входного потока и token -
соответствующее ему внутреннее представление в виде, например, числа — кода
типа лексемы, и приложенных данных. Но это разделение не обязательно, если
понятен контекст. Пример вполне допустимого token, но очень сомнительного
как lexeme — это знак end-of-input, EOI в нашем коде разбора.)

Также отметим, что нам надо заглядывать вперёд и не всегда результаты этого
заглядывания забирать сразу — то есть в алгоритм заложен предпросмотр.
(Например, для выхода из muldiv() нам надо убедиться, что дальше идёт не "*" и
не "/".) Это общий момент для почти всех парсеров; исключения редки и
ограниченны.

4. Операции сложения, вычитания, умножения, деления левоассоциативны. Не
только "a+b+c" разбирается как "(a+b)+c" — это ещё не столь принципиально — но
"a-b-c" должно быть разобрано как "(a-b)-c", а не как "a-(b-c)" — последнее
даст просто неверный результат в значимых случаях.

Исходный список правил нельзя напрямую перевести в код для случая левой
ассоциативности операций и, соответственно, левосторонней рекурсии правил.
Если мы из addsub() вызовем снова addsub() в надежде, что когда-нибудь оно не
пойдёт дальше в рекурсию и остановится... увы, так не работает. Поэтому
вариант, который показан, переводит рекурсию в цикл. (В общем случае не всегда
так легко получится, но тут пример специально прост.)

В разных типах парсеров бывают проблемы и у левосторонней рекурсии, и у
правосторонней, и решаются они в каждом типе парсера по-своему. Перевод в цикл
— один из простых рабочих методов.

5. В отличие от четырёх арифметических операций, операция "**"
правоассоциативна. Это сделано намеренно, потому что иначе нет смысла в
определении многоуровневого возведения в степень: так как (a**b)**c равно
a**(b*c), левая ассоциативность "выхолащивает" смысл в ассоциативности этой
операции вообще. В правилах в начале главы это определяется через альтернативу,
что power может быть atom "**" power.

Для правоассоциативной "**" и правосторонней рекурсии мы оставили
явную рекурсию в коде — так удобнее. И, опять же, парсеры различаются по тому,
каких подходов в каком из них требует правая ассоциативность.

6. Некоторые критикуют подобный стиль ручного написания за то, что с ним
слишком много ненужных вызовов других функций. Например, для "a+b*c" для
компоненты "a" есть addsub(), который вызывает muldiv(), тот дальше power(),
тот дальше atom()... особенно это было важно во времена слабых компьютеров
с ограниченными возможностями рекурсии. Есть технологии, которые исправляют
это — дальше посмотрим на operator precedence подходы в лице TDOP; ну и,
обычно, автоматические построители парсеров на основе заданной грамматики
генерируют выходной код без подобной избыточности.

7. В некоторых традициях вместо термина atom применяется primary. Мы тоже
вначале следовали этому, но потом из-за того, что при введении индексации и
вызова функции весь старый primary переносится в atom, решили применить
понятие atom с самого начала описания.

(Конец списка комментариев по отдельным моментам)

Говоря в общем, следует сказать, что ручные нисходящие парсеры сейчас являются
основной технологией для практического применения в случае популярных языков,
в которые вложено много усилий. Например, они практически применяются в C/C++
(Clang), C# (Roslyn), Java, Go... Но они неинтересны как для массовой
практики, которая склоняется к использованию средств генерации кода по
описанию грамматики, и неинтересны для теории — не в том смысле, что не дают
научно интересных результатов (хотя и в этом тоже), а в том, что для
практических инструментов генерации качественного оптимального кода по
описанию грамматики требуется глубокая теоретическая проработка.  Мы ещё будем
возвращаться к этой теме несколько раз.

См. test_mtdp_ml_gr02 за полным примером самописного нисходящего парсера на
Python (но там добавлены префиксные операторы, см. далее в этой главе).
Кроме описанного тут в тексте, там представлен полный вариант лексического
анализатора для данной грамматики с целыми числами.

// vim: set tw=78 et :