Существует две основных стратегии синтаксического анализа:
1. нисходящая (top-down parsing), когда для данного предложения, исходя из начального символа грамматики, строят вывод;
2. восходящая (bottom-up parsing), когда данного предложения, исходя из символов самого предложения (терминалов), строят разбор.

Таким образом, различают нисходящие и восходящие анализаторы.

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

<Пр>→кот<с>
<Пр>→пес<с>
<Пр>→он<с>
<с>→идет
<с>→лежит

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

Отличительная черта нисходящего анализа - это целенаправленность. На каждом шаге анализа нисходящие распознаватели формируют цель - найти вывод, начинающийся с некоторого нетерминального символа и порождающий часть входной строки. Распознаватель пытается достичь этой цели путем направленного перебора различных возможностей. Основная идея нисходящего анализа в следующем: начиная процесс анализа входной строки S1, S2...,Sn, распознаватель исходит из предположения, что эта строка является предложением входного языка. Отсюда вытекает главная цель анализа - найти вывод (построить дерево)

S S1, S2...,Sn S - начальный символ

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

ПР: Пусть требуется найти вывод для предложения «Он идет» и построить синтаксическое дерево. В качестве главной цели выбираем начальный символ формальной грамматики <Пр> . первая наша вспомогательная цель - это первый символ правой части правила (<П>), вторая вспомогательная цель - <ис>. Непосредственная проверка показывает, что вспомогательная цель «он» недостижима через <ис>, поэтому вместо <ис> выбирают новую вспомогательную цель - <М>...


   <Пр>

<П>   <с>

<М>  <ГФ>
   |        |
  он    идет

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

Восходящий анализ

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

ПР: Пусть требуется определить принадлежность нашему языку следующие формы: «он кот». Для этой строки в нашей грамматике фразами являются «он» и «кот», причем «он» - это основа. Приведение он→ <М> дает строку <М> и <кот>, причем основа → <М>:
он→<М>
<М> кот, <П><кот>, <П><ис>, <П><П> - некорректно.