Сентенциальной формой грамматики G называется цепочка, выводимая из начального нетерминала грамматики G.

Сентенцией грамматики G называется сентенциальная форма, состоящая только из терминальных символов.

Язык, поражденный граматикой, есть множество всех ее сентенций.

 

Задача рабора состоит в востановлении дерева вывода для заданной сентенции.

 

Разбор - это построение вывода для заранее заданной цепочки. Другими словами, разбор- это тот же вывод, прослеженный в обратном порядке.

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

определяет структуру этой цепочки. Дерево вывода представляет структуру цепочки нагляднее независимо от последовательности применения правил. Результатом решения задачи

разбора в случае, если удалось восстановить дерево для заданной терминальной цепочки, является выявление структуры этой цепочки. Построенное дерево называется деревом разбора. Успешное восстановление дерева разбора для заданной цепочки означает что эта цепочка есть

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

 

Разбор называют также распознованием или синтаксическим анализом. Синтаксический анализ имеет две цели - выяснение пренадлежности цепочки и выявление ее структуры.

Работа любого транслятора основана на распозновании структуры предложений транслируемого языка. Синтаксический анализ - обязательная фаза в работе компиляторов и интерпретаторов языков программирования.

Синтаксический анализатор - это часть транслятора, составляющая его основу.

 

Только распозновая структуру входной программы определяя наличие или отсутствие определенных его частей - описаний,операторов, выражений и подвыражений - транслятор может выполнять работу по переводу программы на другой язык. Часто трансляторы в явном виде строят дерево

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