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 .

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

Упражнения

4.1. В грамматике

S abAcDkY

A  nmDkyvaxYejab

D  ghYokh

Y  fd

устраните правила

A  nmDkyvaxYejab

D  ghYokh

и проведите декомпозицию относительно Y. Подсчитайте количество правил результирующей грамматики и грамматики до проведения преобразований.

4.2. Исключите тупики из следующих грамматик:

(а)

S  aBcDkLMp L  f M

B  cLpDqpDcf M  LkpMLc

D  f Drf pq K  r F

F  abcab

(б)

S  ABBCkL A  aAbLc

B  BSAL L  cBjp

C  QSdC Q  qQaC

M  xNyMzSh N  xCvwM

(в)

S  BACBAL C  QSdC

A  aAbBcC Q  qQaC

B  BSALg M  xNyMzSh

L  cBjCp N  xCvwM

4.3. Устраните аннулирующие правила из следующих грамматик:

(а)

S  abCDeKp

C  dSde

D  dDDDef K

K  emcf

(б)

S  aSbSbSaS

(в)

S  ABC A  BB

B  CCa C  AAb

4.4. Устраните цепные правила из грамматики

E  E+TT

T  TFF

F  (E)a

4.5. Найдите приведенную грамматику, эквивалентную грамматике

S  AB A  CD

B  DE C  Sa

D  Sb E  Sc

4.6. Устраните левую рекурсию в следующих грамматиках:

(а)

E  E+TE-TT-T

T  TFT/FF

F  (E)a

(б)

S  AB

A  AaAbde

B  qKrBBfBg

K  vSw