Эквивалентность и преобразование грамматик
Поскольку грамматика языка программирования, по сути, всегда должна быть однозначной, то возникают два вопроса, которые необходимо в любом случае решить:
--- как проверить, является ли данная грамматика однозначной?
--- если заданная грамматика является неоднозначной, то как преобразовать ее к однозначному виду? Однозначность — это свойство грамматики, а не языка. Для некоторых языков, заданных неоднозначными грамматиками, иногда удается построить эквивалентную однозначную грамматику (однозначную грамматику, задающую тот же язык).
Чтобы убедиться в том, что некоторая грамматика не является однозначной (является неоднозначной), согласно определению достаточно найти в заданном ею языке хотя бы одну цепочку, которая бы допускала более чем один левосторонний или правосторонний вывод (как это было в рассмотренном примере). Однако не всегда удается легко обнаружить такую цепочку символов. Кроме того, если такая цепочка не найдена, мы не можем утверждать, что данная грамматика является однозначной, поскольку перебрать все цепочки языка невозможно — как правило, их бесконечное количество. Следовательно, нужны другие способы проверки однозначности грамматики.
Если грамматика все же является неоднозначной, то необходимо преобразовать ее в однозначный вид. Как правило, это возможно. Например, для рассмотренной выше неоднозначной грамматики арифметических выражений над операндами а и b существует эквивалентная ей однозначная грамматика следующего вида G1 ({+.-.*./,(.).а,b}.{S.Т,E}.P'.S):
В этой грамматике для рассмотренной выше цепочки символов языка а*b+а возможен только один левосторонний вывод:
Этому выводу соответствует единственно возможное дерево вывода. Оно приведено на рис. 9.4. Видно, что хотя цепочка вывода несколько удлинилась, но приоритет операций в данном случае единственно возможный и соответствует их порядку в арифметике.
В таком случае необходимо решить две проблемы: во-первых, доказать, что две имеющиеся грамматики эквивалентны (задают один и тот же язык); во-вторых, иметь возможность проверить, что вновь построенная грамматика является однозначной.
Проблема эквивалентности грамматик в общем виде формулируется следующим образом: имеются две грамматики G и G', необходимо построить алгоритм, который бы позволял проверить, являются ли эти две грамматики эквивалентными.
К сожалению, доказано, что проблема эквивалентности грамматик в общем случае алгоритмически неразрешима. Это значит, что не только до сих пор не существует алгоритма, который бы позволял проверить, являются ли две заданные грамматики эквивалентными, но и доказано, что такой алгоритм в принципе не существует, а значит, он никогда не будет создан.
Точно так же неразрешима в общем виде и проблема однозначности грамматик. Это значит, что не существует (и никогда не будет существовать) алгоритм, который бы позволял для произвольной заданной грамматики G проверить, является ли она однозначной или нет. Аналогично, не существует алгоритма, который бы позволял преобразовать заведомо неоднозначную грамматику G в эквивалентную ей однозначную грамматику G'.
В общем случае вопрос об алгоритмической неразрешимости проблем однозначности и эквивалентности грамматик сводится к вопросу об алгоритмической неразрешимости проблемы, известной как «проблема соответствий Поста». Проблема соответствий Поста формулируется следующим образом: имеется заданное множество пар непустых цепочек над алфавитом V: {(a1,β1,), (а2,β2),..., (ап,βп)}, n > 0, Vn > i > 0: а1,β1еV*; необходимо проверить, существует ли среди них такая последовательность пар цепочек: (a1.β1), (a2,β2),..., (аm,βm)m > 0 (необязательно различных), что a1a2...am = β1β2…βm. Доказано, что не существует алгоритма, который бы за конечное число шагов мог дать ответ на этот вопрос, хотя на первый взгляд постановка задачи кажется совсем несложной.
То, что проблема не решается в общем виде, совсем не значит, что ее нельзя решить в каждом конкретном случае. Например, для алфавита V = {а,b} можно построить множество пар цепочек {(abbb,b),(a,aab),(ba,b)} и найти одно из решений: (а,ааb),(а,ааb),(bа,b),(аbbb,Ь) — видно, что (а)(а)(bа)(аЬЬЬ) = (ааb)(ааb) (b)(b). А для множества пар цепочек {(аb,аbа),(аbа,bаа),(bаа,аа)} очевидно, что решения не существует.
Точно так же неразрешимость проблем эквивалентности и однозначности грамматик в общем случае совсем не означает, что они не разрешимы вообще. Для некоторых частных случаев — например, для определенных типов и классов грамматик (в частности, для регулярных грамматик) — эти проблемы решены. Также их иногда удается решить полностью или частично в каждом конкретном случае, и для конкретной заданной грамматики доказать, является ли она однозначной или нет. Например, приведенная выше грамматика G' для арифметических выражений над операндами а и b относится к классу грамматик операторного предшествования из типа КС-грамматик. На основе этой грамматики возможно построить распознаватель в виде детерминированного расширенного МП-автомата, а потому можно утверждать, что она является однозначной (см. раздел «Восходящие распознаватели КС-языков без возвратов», глава 12).