Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 16 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

18
Пример дерева вывода для цепочки a+b+a в грамматике G:
T
T
a
T
S
a
S
b
+
+
S
Дерево вывода можно строить нисходящим либо восходящим способом.
При нисходящем разборе дерево вывода формируется от корня к листьям;
на каждом шаге для вершины, помеченной нетерминальным символом, пыта-
ются найти такое правило вывода, чтобы имеющиеся в нем терминальные сим-
волы «проектировались» на символы исходной цепочки.
Метод восходящего разбора заключается в том, что исходную цепочку пы-
таются «свернуть» к начальному символу S; на каждом шаге ищут подцепочку,
которая совпадает с правой частью какого-либо правила вывода; если такая
подцепочка находится, то она заменяется нетерминалом из левой части этого
правила.
КС-грамматика G называется неоднозначной, если существует хотя бы од-
на цепочка α ∈ L(G), для которой может быть построено два или более различ-
ных деревьев вывода. В противном случае грамматика называется однозначной.
Если грамматика однозначная, то при любом способе построения будет
получено одно и то же дерево разбора.
Язык, порождаемый грамматикой, называется неоднозначным, если он не
может быть порожден никакой однозначной грамматикой.
Пример неоднозначной грамматики: G = ({if, then, else, a, b}, {S}, P, S),
где: P = {S → if b then S else S | if b then S | a}. В этой грамматике для цепочки
‘if b then if b then a else a’ можно построить два дерева вывода.
Однако это не означает, что язык L(G) обязательно неоднозначный. Неод-
нозначность – это свойство грамматики, а не языка, т.е. для некоторых не-
однозначных грамматик существуют эквивалентные им однозначные грамма-
тики. Если грамматика используется для определения языка программирования,
то она должна быть однозначной. В приведенном выше примере разные дере-
вья вывода предполагают соответствие else разным then. Если договориться,
что else должно соответствовать ближайшему к нему then, и подправить грам-
матику G, то неоднозначность будет устранена:
S → if b then S | if b then S’ else S | a
S’ → if b then S’ else S’ | a.
Проблема, порождает ли данная КС-грамматика однозначный язык (т.е.
существует ли эквивалентная ей однозначная грамматика), является алгорит-
мически неразрешимой.

Страницы