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

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

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

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

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

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

Если грамматика все же является неоднозначной, то необходимо преобразовать ее в однозначный вид. Как правило, это возможно. Например, для рассмотренной выше неоднозначной грамматики арифметических выражений над операндами а и 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)}, n0,
ni0: ?i,?iV+; необходимо проверить, существует ли среди них такая последовательность пар цепочек: (?1,?1), (?2,?2),…,(?m,?m), m0 (необязательно различных), что ?1?2…?m= ?1?2…?m. Доказано, что не существует алгоритма, который бы за конечное число шагов мог дать ответ на этот вопрос, хотя на первый взгляд постановка задачи кажется совсем несложной.

Статьи к прочтению:

Лекция 25. Преобразование звезды в треугольник.

Похожие статьи: