Дерево порождения для КС-грамматики

В соответствии с классификацией по Хомскому грамматика является контекстно-свободной, если все порождающие правила имеют вид:

A → γ,

где A – нетерминальный символ, γ – цепочка из терминальных и нетерминальных символов.

Процесс порождения в КС-грамматике наглядно представляется в виде дерева порождения – дерева с корнем вверху. Вершинами дерева служат терминальные и нетерминальные символы. Порождение начинается с одного из правил, в левой части которого находится начальный нетерминал. Поэтому в корень дерева всегда помещается начальный нетерминал, вниз от него идут ребра, в концах которых размещаются символы правой части правила. При этом должен сохраняться порядок следования вершин в концах ребер. Далее от каждой из вершин, являющейся нетерминалом, достраиваются вниз ребра с вершинами – символами в правой части примененного порождающего правила. Если какое-то из примененных правил содержит пустую правую часть, то ребро заканчивается символом пустой цепочки. Этот процесс продолжается до тех пор, пока среди висячих вершин дерева не останется хотя бы один нетерминал. После этого обход слева направо по висячим вершинам дерева будет цепочкой языка, получившейся в процессе порождения.

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

Дата добавления: 2015-07-26; просмотров: 158; Нарушение авторских прав

Мы поможем в написании ваших работ!