Довольно часто в живых языках могут быть предложения, совпадающие по написанию, но допускающие неоднозначную синтаксическую трактовку. Например «пальто испачкало окно».
Здесь не ясно, что является подлежащим, а что дополнением. В таких примерах существенным является не «статическое» написание, а «динамика» процесса грамматического вывода.
Такая неоднозначность играет существенную роль для языков программирования. Поэтому возникает вопрос об однозначности различных типов грамматик и возможности найти однозначную грамматику определенного типа.
Грамматика G называется неоднозначной, если имеется цепочка хÎL(G), которая может быть выведена двумя существенно- различными способами. Под существенно- различными способами понимается следующее:
грамматике G=(VT, VH, S,P) c правилами j1®y1, j2®y2, … jk®yk поставим в соответствие грамматику G¢=(VT¢, VH¢, S¢,P¢), у которой VH¢= VH, S¢= S, VT¢= VT È {(j1,(j2…,(jk)}, то есть для каждого правила ji®yi системы правил P к терминальному символу соответствию добавляется (ji .
Система P¢ получается из системы P заменой некоторого правила ji®yi правилом ji®(jiyi).
Очевидно, что каждому выводу цепочки Х в L(G) однозначно соответствует вывод цепочки Х¢ в L(G¢).
Эта цепочка Х¢ совпадает с Х, если в ней опустить все скобки.
Скобки, таким образом, сохраняют «динамику» вывода.
Пример.
G=({0,1},S, S, P)
P={S®0, S®S1S}
G¢=({0,1},S, S, P¢)
P¢={S®(s0), S®(sS1S)}
Цепочка 01010 языка L(G) может быть выведена различными способами:
S®S1S®01S®01S1S®0101S®01010
S®S1S®S10®S1S10®01S10®01010.
Им соответствует разные структурные описания, полученные в L(G¢):
(s(s0)1(s(s0)1(s0)));
(s(s(s0)1(s0)1(s0)).
Выводы цепочки Х в некотором языке L(G) называются существенно- различными, если структурные описания Х¢, соответствующие этим выводам, отличаются друг от друга.
Если задается конкретная грамматика G одного из типов и нужно установить, является ли она неоднозначной, то алгоритмическая разрешимость такой задачи устанавливается следующей теоремой.
Теорема 5.3.1.
Для языков типа 3 существует алгоритм, позволяющий по заданным грамматикам определить, является ли она однозначной. Для остальных типов языков эти задачи алгоритмически неразрешимы.
Язык данного типа называется существенно-неоднозначным, если любая грамматика G этого типа, порождающая этот язык, неоднозначна, то есть если в заданном классе грамматик нельзя найти грамматику без неоднозначностей, эквивалентную заданной.
В противном случае язык L называется языком без неоднозначностей или однозначно выводимым.
Две следующие теоремы относятся к вопросу о существовании существенно-неоднозначных языков различных типов.
Теорема 5.3.2 Хомского и Миллера
Не существует неоднозначных языков типов 0, 2D, 3. Все эти языки однозначно выводимы. (2D- подкласс языков типа 2, называемые «детерминированные бесконтекстные языки»).
Теорема5.3.3. Парика
Существуют существенно- неоднозначные бесконтекстные языки.
Для зыков типа 1 (контекстных) этот вопрос не решен.
Следующая теорема рассматривает алгоритмическую разрешимость распознавания существенной неоднозначности.
Теорема5.3.4. Гладкого
Не существует алгоритма для решения задачи о том, является ли заданный язык типа 2D существенно-неоднозначным.
Однако в некоторых случаях этот вопрос может быть решен.
0 коммент.:
Отправить комментарий