5.2.3. Операции над контекстными языками

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

Доказательство:

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

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

Например: G1: SaA G2: Sb

Abcb

Aa

Выполним операцию конкатенации без преобразования полутерминалов, проиндексировав нетерминалы исходных грамматик:

SS1S2

S2ab

S1aA1

A1bcb

A1a.

В результате может быть выведена цепочка – acb, не принадлежащая языку. Теперь выполним преобразование полутерминалов и только затем проиндексируем грамматики, в результате чего цепочки, не принадлежащие языку, в грамматике не выводимы:

SS1S2

S2Bb2 S1Aa1A1

A₁a_1; A1Bb1Cc1Bb1

Bb2b Aa1a; Bb1b; Cc1c

5.3. Выводы для практики

В результате операций над языками получается новое множество цепочек, то есть новый язык, который “собран из кусков”, состоит из частей исходных языков. С практической точки зрения очень важно, что язык можно разложить на более простые языки и формировать сложный язык на базе простых языков и операций над ними. Так, если нам известен язык букв L_б (любая латинская буква) и язык цифр L_ц, то можно совершенно тривиально определить язык идентификаторов L_и , конкатенацию языка букв и итерацию объединения языка букв и языка цифр: L_и = L_б (L_б L_ц )^.

Отметим, что при реализации на ЭВМ программы синтаксического анализа различных языков лучше всего представлять в виде логических процедур-функций, дающих положительный ответ в случае принадлежности цепочки или ее фрагмента рассматриваемому языку и отрицательный при обнаружении ошибок. При таком построении итерация языка подменяется вызовом соответствующей процедуры внутри цикла; конкатенация - последовательным вызовом процедур анализа составляющих языков; объединение - альтернативным вызовом процедур; подстановка - заменой анализа терминала на процедуру анализа подставляемого языка.

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

+ победы = ничьи - поражения;

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

L = L₊ L_блок L₌ L_блок L _- L_блок L_; ,

где L ₊ = {+}, L ₌ = {=}, L _- = {-}, L _блок = L _и  L _к , L_и = L_б (L_б L_ц ) ^, L _к = L_ц⁺, L_б = {a,b,...,y,z}, L_ц = {0,1,...,9}, L_;={;}.