4.4. Устранение левой рекурсии и левая факторизация

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

Рассмотрим случай когда правила грамматики саморекурсивны, то есть левая часть правила и край правой части совпадают. Пусть нетерминал A имеет m леворекурсивных правил

A  A _i для 1  i  m

и n правил

A   _j для 1  j  n ,

которые не являются леворекурсивными (отметим, что отсутствие последних делает A тупиком). Заменив эти правила на правила

A  _j <список A> для 1  j  n

<список A>   _i <список A> для 1  i  m

<список A>   ,

где <список A> - новый нетерминал, мы получим эквивалентную группу правил без левой рекурсии.

Пример 4.7. Самой короткой грамматикой для представления идентификатора является леворекурсивная грамматика

<И>  б<И>б<И>ц ,

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

<И>  б<И₁>

<И₁>  б<И₁> ц<И₁> ,

мы получим обобщенную праворекурсивную грамматику идентификатора. Заметим, что исключение аннулирующего правила приведет нас к грамматике из примера 4.3. 

Если в грамматике имеется группа правил вида

A   ₁... _n ,

то цепочку  можно “вынести за скобку” и преобразовать данную группу правил к виду

A   B

B   ₁... _n .

Этот прием носит название левой факторизации и его необходимо знать для ряда приложений.

5. Свойства автоматных и контекстно-свободных

ЯЗЫКОВ

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

5.1. Общий вид цепочек а-языков

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

Теорема 5.1. Пусть L - А-язык. Существует такая константа p, что, если   L и  p , то цепочку  можно записать в виде  , где   p и  ⁱ  L , для всех i   .

Доказательство. Если L - конечный язык, то положим константу p больше длины самой длинной цепочки языка L, тогда ни одна из цепочек языка не удовлетворяет условиям теоремы и она верна. В противном случае, пусть M = (Q, , , q₀, F) - конечный автомат с n состояниями и L(M) = L. Пусть p = n. Если   L и  n, рассмотрим последовательность конфигураций, которую проходит автомат M, допуская цепочку . Так как в этой последовательности, по крайней мере, n+1 конфигурация, то найдутся две конфигурации с одинаковыми состояниями. Поэтому, должна быть такая последовательность тактов, что

(q ₀,  ) ^ (q ₁,  ) ^k (q ₁,  ) ^ (q ₂,  ) ,

для некоторого q ₁ и   k  n. Отсюда   n.

Но тогда, для любого i > 0 автомат может проделать следующую последовательность тактов:

(q ₀,  ⁱ  ) ^ (q ₁,  ⁱ  )

(q ₁,  ⁱ  ) ⁺ (q ₁,  ^i-1 )

..............

(q ₁,  ²  ) ⁺ (q ₁, )

(q ₁,  ) ⁺ (q ₁, )

(q ₁, ) ^ (q ₂,  ) .

Для случая i = 0 все еще очевиднее:

(q ₀,  ) ^ (q ₁, ) ^ (q ₂,  )

Так как   L, то и  ⁱ   L, для всех i  0. 

Эта теорема, обычно, используется для доказательства того, что некоторые выбранные цепочки не являются цепочками А-языка и, следовательно, не могут быть определены А-грамматиками.

Следствие 5.1. Язык L, состоящий из цепочек x ⁿ y ⁿ не является автоматным языком.

Допустим, что он автоматный. Тогда, для достаточно большого n цепочка x ⁿ y ⁿ может быть представлена в виде , причем    и  ⁱ   L, для всех i  0.

Если  = x...x или  = y...y, то    ⁰   L, так как количество символов x и y в цепочке  различно. Если  = x...xy...y, то  =  ²  L, так как в цепочке  символы x и y будут перемешаны. Полученное противоречие, доказывает, что L - не является А-языком. 

Следствие 5.2. Язык арифметических выражений не является А-языком, так как он может содержать произвольное количество вложенных скобок, причем количество открывающих скобок совпадает с количеством закрывающих. Аналогично, не является А-языком любой язык, содержащий вложенные конструкции, типа фигурных скобок в языке C, begin - end, repeat - until и т.п. Каждая конечная А-грамматика, порождающая подобные конструкции, будет выводить и цепочки с неравным количеством открывающих и закрывающих скобок. Тем не менее, анализировать подобные цепочки можно и с помощью автоматного подхода. При этом, в синтаксисе языка допускается произвольное количество открывающих и закрывающих скобок, а контроль их парности возлагается на семантические подпрограммы. 