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