Эквивалентность и преобразование грамматик

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

 как проверить, является ли данная грамматика однозначной?

 если заданная грамматика является неоднозначной, то как преобразовать ее к однозначному виду?

Однозначность – это свойство грамматики, а не языка. Для некоторых языков, заданных неоднозначными грамматиками, иногда удается построить эквивалент­ную однозначную грамматику (однозначную грамматику, задающую тот же язык).

Чтобы убедиться в том, что некоторая грамматика не является однозначной (яв­ляется неоднозначной), согласно определению достаточно найти в заданном ею языке хотя бы одну цепочку, которая бы допускала более чем один левосторон­ний или правосторонний вывод (как это было в рассмотренном примере). Одна­ко не всегда удается легко обнаружить такую цепочку символов. Кроме того, если такая цепочка не найдена, мы не можем утверждать, что данная грамматика является однозначной, поскольку перебрать все цепочки языка невозможно – как правило, их бесконечное количество. Следовательно, нужны другие способы проверки однозначности грамматики.

Если грамматика все же является неоднозначной, то необходимо преобразовать ее в однозначный вид. Как правило, это возможно. Например, для рассмотрен­ной выше неоднозначной грамматики арифметических выражений над операн­дами а и b существует эквивалентная ей однозначная грамматика следующего вида
G’({+,–,*,/,(,),a,b},{S,Т,E},P’,S):

Р’:

S  S+T | S–T | Т

Т  Т*Е | Т/Е | Е

Е  (S) | а | b

В этой грамматике для рассмотренной выше цепочки символов языка а*b+а воз­можен только один левосторонний вывод:

S  S+T  Т+Т  Т*Е+Т  Е*Е+Т  а*Е+Т  а*b+Т  а*b+Е  а*b+а

Этому выводу соответствует единственно возможное дерево вывода. Оно приве­дено на рис. 1.4. Видно, что хотя цепочка вывода несколько удлинилась, но при­оритет операций в данном случае единственно возможный и соответствует их порядку в арифметике.

Рис. 1.4. Дерево вывода для однозначной грамматики арифметических выражений

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

Проблема эквивалентности грамматик в общем виде формулируется следующим образом: имеются две грамматики G и G’, необходимо построить алгоритм, кото­рый бы позволял проверить, являются ли эти две грамматики эквивалентными.

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

Точно так же неразрешима в общем виде и проблема однозначности грамматик. Это значит, что не существует (и никогда не будет существовать) алгоритм, который бы позволял для произвольной заданной грамматики G проверить, яв­ляется ли она однозначной или нет. Аналогично, не существует алгоритма, кото­рый бы позволял преобразовать заведомо неоднозначную грамматику G в экви­валентную ей однозначную грамматику G’.

В общем случае вопрос об алгоритмической неразрешимости проблем однознач­ности и эквивалентности грамматик сводится к вопросу об алгоритмической неразрешимости проблемы, известной как “проблема соответствий Поста”. Про­блема соответствий Поста формулируется следующим образом: имеется задан­ное множество пар непустых цепочек над алфавитом V: {(α1,β1), (α2,β2),...,(αn,βn)}, n > 0,
n > i > 0: αi,βiV+; необходимо проверить, существует ли среди них такая последовательность пар цепочек: (α1,β1), (α2,β2),...,(αm,βm), m>0 (необязательно различных), что α1α2…αm= β1β2…βm. Доказано, что не существует алгоритма, ко­торый бы за конечное число шагов мог дать ответ на этот вопрос, хотя на первый взгляд постановка задачи кажется совсем несложной.