Дерево вывода

Выводам контекстно-свободной грамматики соответствуют деревья разбора (derivation tree, parse tree) – это некоторые упорядоченные деревья, вершины которых помечены символами алфавита или нетерминального, или терминального множества, корень дерева – начальный символ. Каждому символу некоторого W₁, на который заменяется начальный символ на первом шаге вывода, ставится в соответствующую вершину дерева, и к ней приводится дуга из корня. Полученные таким образом потомки корня упорядочены. Например:

<Пр>

<П> <с>

| |

<ис> <ГФ>

| |

кот лежит

Если хотя бы одна сентенциальная форма имеет более одного синтаксического дерева, то грамматику называют неоднозначной.

Задача разбора

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

Например: В грамматике строка «кот лежит» прямо приводима к строке <ис>лежит… и в конце концов она приводима к <Пр>.

Основная задача разбора – это вывод, но прослеженный в обратном порядке, на базе готовой формальной грамматики.

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

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