Нисходящий синтаксический анализ решает задачу построения для входной строки дерева разбора, начиная с корня, в порядке обхода в глубину слева-направо. Эквивалентно, это соответствует поиску левого порождения для входной строки.

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

Проверка совпадения префиксов порождения и входной строки достаточно тривиальна. Для выбора продукции существует два подхода:

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

Обе этих стратегии могут быть реализованы при разборе методом рекурсивного спуска.

Разбор методом рекурсивного спуска

Концептуально, разбор методом рекурсивного спуска сводится к созданию процедур для каждого нетерминала, и рекурсивному вызову этих процедур. Процедуры для нетерминалов типично имеют следующий вид:

function A() {
  выбрать продукцию A -> X₁…Xₙ;
  for (k in 1…n) {
    if (Xₖ -- нетерминал)
      Xₖ();
    else if (Xₖ -- терминал и Xₖ == входному символу)
      переход к следующему входному символу;
    else
      обработка ошибки;
  }
}

Собственно, в случае разбора с возвратом, выбор продукции и обработка ошибки сводятся к выбору первой же продукции и проверке следующей соответственно. В случае разбора с предпросмотром, выбор может требовать “подглядеть” один или несколько следующих символов входной строки.

Одним из недостатков метода рекурсивного спуска является то, что грамматика с левой рекурсией, т.е. с ситуацией, когда левое порождение от некого нетерминала \(A\) приводит (за один или несколько шагов) к \(A\alpha\), приведёт к бесконечной рекурсии анализатора.

Например, разбор леворекурсивной грамматики

\[\begin{align} S \to\; & P \\ P \to\; & P + n | n \\ \end{align}\]

на основе приведённого выше алгоритма оказывается невозможен.

Устранение левой рекурсии

В большинстве случаев, устранение левой рекурсии возможно чисто механически.

Для тривиального случая, когда заголовок продукции оказывается в крайней левой позиции тела этой продукции, и существует альтернативная продукция с тем же заголовком, в которой нет левой рекурсии, т.е. есть нетерминал с продукциями вида \[A \to A\alpha | \beta,\] они могут быть заменены без изменения языка продукциями вида \[\begin{align} A \to\;& \beta A', \\ A' \to\;& \alpha A' | \varepsilon, \\ \end{align}\] не содержащими левой рекурсии.

Это легко обобщается на случай нескольких леворекурсивных и нелеворекурсивных продукций: \[A \to A\alpha_1 | \ldots | A\alpha_n | \beta_1 | \ldots | \beta_m,\] заменяется без изменения языка на \[\begin{align} A\, & \to \beta_1 A' | \ldots | \beta_m A', \\ A' & \to \alpha_1 A' | \ldots | \alpha_n A' | \varepsilon. \\ \end{align}\]

Эти подстановки, однако, не устраняют левую рекурсию, получаемую за более, чем один шаг порождения.

Систематически устранить левую рекурсию можно при помощи следующего алгоритма:

Упорядочить нетерминальные символы в произвольном порядке;
for(∀ нетерминалов A) {
  for(∀ нетерминалов B < A) {
    for(∀ A -> B α) {
      for(∀ B -> β) {
        Добавить A -> β α;
      }
      Удалить A -> B α;
    }
  }
  Устранить прямую левую рекурсию в продукциях для A;
}

Этот алгоритм гарантированно работает на грамматиках, не содержащих циклов (т.е. ситуаций \(A\overset{+}{\Rightarrow} A\)) и пустых продукций (т.е. продукций вида \(A\to \varepsilon\)). Существуют алгоритмы систематического удаления циклов и пустых продукций из грамматики.

Алгоритм удаления пустых продукций:

while(∃ A -> ε) {
  for(∀ B -> α A β) {
    Добавить B -> α β;
    if (! (∃ A -> γ && γ != ε)) {
      Удалить B -> α A β;
    }
  }
  Удалить A -> ε;
}

После устранения пустых продукций возможно удаление циклов простым устранением “единичных” правил вида \(A \to B\):

while(∃ A -> B) {
  for(∀ B -> α && α != B && B -> α не было удалено ранее) {
    Добавить A -> α;
  }
  Удалить A -> B;
}

Нисходящий синтаксический анализ. Рекурсивный анализ.

Разбор методом рекурсивного спуска

Устранение левой рекурсии