Свойства детерминированных кс-языков

Детерминированные КС-языки — это класс тех КС-языков, цепочки которых можно распознавать с помощью ДМП-автоматов. Класс детерминированных КС-языков, естественно, является собственным подмножеством всего класса КС-языков [δ, т. 1].

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

Класс детерминированных КС-языков интересен тем, что для него разрешима проблема однозначности. Доказано, что если язык может быть распознан с помощью ДМП-автомата (и потому является детерминированным КС-языком), то он может быть описан на основе однозначной КС-грамматики. Именно поэтому данный класс как раз и используется для построения синтаксических конструкций языков программирования.

Дополнительно следует заметить, что в общем случае подавляющее большинство языков программирования (таких, как Pascal, С, FORTRAN и т. п.) формально не являются КС-языками. Причина в том, что в языках программирования всегда присутствует контекстная зависимость, которая выражается, например, в необходимости предварительного описания переменных, в соответствии количества и типов формальных и фактических параметров процедур и функций и т. п. Но с целью упрощения работы компиляторов подобного рода зависимости на этапе синтаксического анализа не учитывают, рассматривая только сами конструкции языков программирования, которые формально могут быть описаны с помощью КС-грамматик. Соблюдение контекстных условий (зависимостей) в компиляторах проверяется уже на этапе семантического анализа при подготовке к генерации кода.

Лемма о разрастании кс-языков

Лемма о разрастании КС-языков звучит так: если взять достаточно длинную цепочку символов, принадлежащую произвольному КС-языку, то в ней всегда можно выделить две подцепочки, длина которых в сумме больше нуля, таких, что, повторив их сколь угодно большое число раз, можно получить новую цепочку символов, принадлежащую данному языку [δ, т. 1].

Формально ее можно определить следующим образом: если L — это КС-язык, то э keN, k > 0, что если |a| > k и aeL, то a = еβδуw, где βу≠λ, |βδу| < k и еβiδу'wеL Vi > 0 (где N — это множество целых чисел)¹.

Как и для регулярных языков, лемма о разрастании для КС-языков служит для проверки принадлежности заданного языка классу КС-языков. Доказано, что всякий язык является КС-языком тогда и только тогда, когда для него выполняется лемма о разрастании КС-языков.

Например, докажем, что язык L = {aⁿbⁿcⁿ | n > 0} не является КС-языком.

Предположим, что этот язык все же является КС-языком. Тогда для него должна выполняться лемма о разрастании, и существует константа k, заданная в этой лемме. Возьмем цепочку а = a^kb^kc^k, |а| > k, принадлежащую этому языку. Если ее записать в виде а = еβδуw, то по условиям леммы |βδу| < k, следовательно, цепочка βδу не может содержать вхождений всех трех символов a, b и с — каких-то

____________________________________________________________

¹ Для КС-языков, как и для регулярных языков, с помощью леммы о разрастании можно повторять подцепочки сколько угодно раз и получать новые цепочки языка — исходная цепочка как бы «разрастается» (отсюда название леммы). На самом деле лемма о разрастании для КС-языков является частным случаем более общей леммы, известной как «лемма Огдена» [δ, т. 1]. символов в ней нет. Рассмотрим цепочку еβ⁰δу⁰w = еδw. По условиям леммы она должна принадлежать языку, но в то же время она содержит либо k символов а, либо k символов с и при этом не может содержать k вхождений каждого из символов a, b и с, так как |εδw| < 3k. Значит, какой-то символ в ней встречается меньше, чем другие — такая цепочка не может принадлежать языку L. Следовательно, язык L не удовлетворяет требованиям леммы о разрастании КС-языков и поэтому не является КС-языком.

Преобразование КС-грамматик. Приведенные грамматики

Преобразование грамматик. Цель преобразования

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

Таким образом, можно выделить две основные цели преобразований КС-грамматик: упрощение правил грамматики и облегчение создания распознавателя языка. Не всегда эти две цели можно совместить. В случае с языками программирования, когда итогом работы с грамматикой является создание компилятора языка, именно вторая цель преобразования является основной. Поэтому упрощениями правил пренебрегают, если при этом удается упростить построение распознавателя языка [12, 15, 32].

Все преобразования условно можно разбить на две группы:

--- первая группа — это преобразования, связанные с исключением из грамматики тех правил и символов, без которых она может существовать (именно эти преобразования позволяют выполнить основные упрощения правил);

--- вторая группа — это преобразования, в результате которых изменяется вид и состав правил грамматики, при этом грамматика может дополняться новыми правилами, а ее словарь нетерминальных символов — новыми символами (то есть преобразования второй группы не связаны с упрощениями).

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

Тогда формально преобразование можно определить следующим образом:

Приведенные грамматики

Приведенные грамматики — это КС-грамматики, которые не содержат недостижимых и бесплодных символов, циклов и λ-правил («пустых» правил). Приведенные грамматики называют также КС-грамматиками в каноническом виде.

Для того чтобы преобразовать произвольную КС-грамматику к приведенному виду, необходимо выполнить следующие действия:

---удалить все бесплодные символы;

---удалить все недостижимые символы;

---удалить λ-правила;

---удалить цепные правила.

Следует подчеркнуть, что шаги преобразования должны выполняться именно в указанном порядке, и никак иначе.

Удаление недостижимых символов

Символ xe(VTuVN) называется недостижимым, если он не встречается ни в одной сентенциальной форме грамматики G(VT,VN,P,S).

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

Алгоритм удаления недостижимых символов строит множество достижимых символов грамматики G(VT,VN,P,S) - Vj. Первоначально в это множество входит только целевой символ грамматики S, затем оно пополняется на основе правил грамматики. Все символы, которые не войдут в данное множество, являются недостижимыми и могут быть исключены в новой грамматике G' из словаря и из правил.

Алгоритм удаления недостижимых символов по шагам

Удаление бесплодных символов

В грамматике G(VT,VN,P,S) символ AeVN называется бесплодным, если для него выполняется: {аА=>*а, aeVT} = 0, то есть нетерминальный символ является бесплодным тогда, когда из него нельзя вывести ни одной цепочки терминальных символов. В простейшем случае символ является бесплодным, если во всех правилах, где этот символ стоит в левой части, он также встречается и в правой части. Более сложные варианты предполагают зависимости между цепочками бесплодных символов, когда они в любой последовательности вывода порождают друг друга. Для удаления бесплодных символов используется специальный алгоритм удаления бесплодных символов. Он работает со специальным множеством нетерминальных символов yj. Первоначально в это множество попадают только те символы, из которых непосредственно можно вывести терминальные цепочки, затем оно пополняется на основе правил грамматики G.

Алгоритм удаления бесплодных символов по шагам

Пример удаления недостижимых и бесплодных символов

Рассмотрим работу алгоритмов удаления недостижимых и бесплодных символов на примере грамматики:

Следует обратить внимание, что для правильного выполнения преобразований необходимо сначала удалить бесплодные символы, а потом — недостижимые символы, но не наоборот. То есть порядок, в каком будут выполняться алгоритмы, имеет существенное значение.

Удалим бесплодные символы:

Получили грамматику:

Удалим недостижимые символы:

В итоге получили грамматику:

Алгоритмы удаления бесплодных и недостижимых символов относятся к первой группе преобразований КС-грамматик. Они всегда ведут к упрощению грамматики, сокращению количества символов алфавита и правил грамматики.