Дерево вывода грамматики. Алгоритм построение дерева вывода

Деревом вывода грамматики G (деревом разбора, синтаксическим деревом) называется дерево (граф), которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

· каждая вершина дерева обозначается символом грамматики;

· корнем дерева является вершина, обозначенная целевым символом грамматики S;

· листьями дерева являются вершины, обозначенные терминальными символами грамматики или символом ε;

· если некоторый узел обозначен символом AÎN, а связанные с ним узлы – символами b1, b2,…, bn|n > 0, 0 < i ≤ n, b_iÎVÈ{ε}, то в грамматике существует правило A ->b1b2…bn ÎP.

Алгоритм построения дерева вывода сверху вниз:

· целевой символ грамматики помещается в вершину дерева;

· в грамматике выбирается необходимое правило и целевой символ раскрывается на несколько символов первого уровня;

· среди всех концевых вершин дерева выбирается крайняя (левая для левостороннего вывода, правая – для правостороннего вывода) вершина, обозначенная нетерминальным символом;

· для нее выбирается нужное правило и она снова раскрывается на несколько вершин следующего уровня;

· если все концевые вершины обозначены терминальными символами, процесс закончен. Иначе – возврат на шаг 3.

Алгоритм построения дерева вывода снизу вверх:

· в качестве листьев выбираются терминальные символы конечной цепочки вывода, которые образуют последний уровень дерева;

· далее в грамматике выбирается соответствующее правило, согласно которому крайние символы в слое дерева соединяются с новой вершиной;

· и так до тех пор, пока все вершины не окажутся соединены в корневой вершине.

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

Однозначность и эквивалентность грамматик.

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

Грамматики называют эквивалентными, если порождают один и тот же язык.

Классификация грамматик по Хомскому.

Тип 0. Произвольные грамматики (грамматики с фразовой структурой, или без ограничений)

· На структуру их правил таких грамматик не накладывается никаких ограничений, т.е. правила имеют вид: α -> β, αÎV⁺, βÎV*.

· Это самый общий тип грамматик. Грамматики, которые относятся только к этому и не могут быть отнесены ни к какому другому типу, являются самыми сложными по структуре.

Тип 1– Контекстно-зависимые (КЗ) (неукорачивающие грамматики)

· Имеют правила вида α₁Aα₂ -> α₁β α₂, α₁, α₂ÎV*, AÎN, βÎV⁺.

· В КЗ-грамматиках при построении предложений заданного языка один и тот же нетерминальный символ может быть заменен различными терминальными цепочками в зависимости от контекста, в котором он встречается.

· При построении компиляторов такие грамматики не применяются, поскольку языки программирования имеют более простую структуру и могут быть построены с помощью грамматик других типов.

Тип 2 – Контекстно-свободные (КС) грамматики

· Имеют правила вида A ->β, AÎN, bÎV⁺.

· Характерная особенность – в левой части правил всегда один нетерминальный символ, в правой части у них стоит всегда хотя бы один символ.

· КС-грамматики широко используются при описании синтаксических конструкций языков программирования.

Тип 3 – Автоматные (регулярные) грамматики

· К этому типу относятся два эквивалентных класса грамматик: леволинейные и праволинейные.

· Леволинейные грамматики могут иметь правила двух видов:

A -> Bα || A -> α, A,BÎN, αÎT.

· Праволинейные грамматики имеют правила тоже двух видов:

A -> αB || A -> α, A,BÎN, αÎT.

· Регулярные грамматики используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев и т.д.

Любая регулярная грамматика является также КС-грамматикой и КЗ-граматикой и произвольной грамматикой.

Самыми простыми являются грамматики типа 3, самыми сложными – типа 0.

Для КС и регулярных грамматик для любой сентенциальной формы всегда можно построить левосторонний или правосторонний вывод, а следовательно всегда можно построить дерево вывода.

Формулировка задачи разбора. Построение дерева разбора.

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

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

Задача разработчиков состоит в построении распознавателя данного языка, который является основой синтаксического анализатора (основной части транслятора).

Задача разбора - на основе имеющейся грамматики некоторого языка необходимо построить распознаватель для этого языка.

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

Фактически заключается в восстановлении дерева вывода для заданной сентенции или иными словами разбор – это вывод, прослеженный в обратном порядке.