Здавалка
Главная | Обратная связь

Исключение цепных правил



Преобразовать НКС-грамматику G = < T, N, S, R > в эквивалентную КС-грамматику, не содержащую цепных правил.

2.2.3.1. T = { i, :=, (, ) }, N = { S, A, B, F, L, P, Q }, R = { S ® LA, S ® LB, L ® P:= , L ® Q:= , P ® i, A ® F, Q ® i, B ® F, F ® Q(i) };

1. для каждого D из N построим множество ND {E | D ® * E}

NS={S} NA={A,F} NB{B,F} NF={F} NL={L} NP={P} NQ={Q}

 

2. Построим R’ без цепных правил

wR’ = {S ®LA, S ® LB, L ® P:= , L ® Q:= , P ® i, Q ® i, A®Q(i), B®Q(i)}, F®Q(i)};

 

Т.о. преобразованная грамматика –

G = < T, N, S, R’ >


 

Исключение цепных правил

Преобразовать НКС-грамматику G = < T, N, S, R > в эквивалентную КС-грамматику, не содержащую цепных правил.

2.2.3.1. T = { i, :=, (, ) }, N = { S, A, B, F, L, P, Q }, R = { S ® LA, S ® LB, L ® P:= , L ® Q:= , P ® i, A ® F, Q ® i, B ® F, F ® Q(i) };

1. для каждого D из N построим множество ND {E | D ® * E}

NS={S} NA={A,F} NB{B,F} NF={F} NL={L} NP={P} NQ={Q}

 

2. Построим R’ без цепных правил

wR’ = {S ®LA, S ® LB, L ® P:= , L ® Q:= , P ® i, Q ® i, A®Q(i), B®Q(i)}, F®Q(i)};


 

Исключение левой рекурсии

Алгоритм 3.7.5. Устранение прямой левой рекурсии.

Вход.Приведенная КС-грамматика G = (N, S, P, S).

Выход. Эквивалентная КС-грамматика G¢ = (N¢, S, P¢, S) без левой рекурсии.

Описание алгоритма.

1. Пусть множество нетерминалов грамматики N = {A1, A2, … , An}. Преобразуем грамматику таким образом, чтобы в правиле Ai à a цепочка a начиналась либо с терминала, либо с такого Aj, что j > i. Установим i = 1.

2. Пусть множество Ai-правил имеет вид Ai à Aia1, Ai à Aia2, …, Ai à Aiam Ai à b1, Ai à b2, …, Ai à bm, где ни одна из цепочек bj, не начинается с Ak, если k £ i. Заменим Ai-правила правилами Ai à b1, Ai à b2, …, Ai à bn, Ai à b1A¢i, Ai à b2A¢I, …, Ai à bn A¢i и Ai¢à a1, Ai¢à a2, …, Ai¢ à am, Ai¢à a1A¢i, Ai¢ à a2A¢i, …, Ai¢à amA¢i, где A¢i – новый нетерминальный символ. После выполнения такой замены правые части всех Ai-правил начинаются с терминального символа или с нетерминала Ak, для некоторого k > i.

3. Если i = n, то преобразование завершено, иначе положить i = i + l и j = l.

4. Заменить каждое правило Ai à Aja правилами Ai à b1a, Ai à b2a, …, Ai à bma, где Aj à b1, Aj à b2, …, Aj à bm – все Aj-правила грамматики. Правая часть Aj – правила начинается с терминального символа или с нетерминала Ak для k > j, поэтому правая часть каждого построенного Ai – правила обладает этим же свойством.

5. Если j = i – 1, то перейти к шагу 2 алгоритма, иначе положить j = j + 1 и перейти к шагу 4.

Конец алгоритма

 

Пример 3.11

Исключить левую рекурсию из грамматики G0 с правилами

(1) E à E + T
(2) E à T
(3) T à T*P
(4) T à P
(5) P à i
(6) P à (E)

Применив к E-правилам E à E+T , E à T описанное преобразование, получим a = +T и b = T. В соответствии с этим преобразованием, новые E-правила будут иметь вид: E à T, E à TE¢ и в грамматику необходимо добавить правило для нового нетерминала E¢: E¢ à +T.

После рассмотрения всех правил исходной грамматики G получим правила новой грамматики G¢:

E à T, E à TE¢, E¢ à +T, E¢ à +TE¢, T à P, T à PT¢, T¢ à *P, T¢ à *PT¢, P à (E+T), P à (E), P à i.


 

Пример 3.12

Устраним левую рекурсию в грамматике G, определяемой множеством правил P = {S à AB, S à a, A à BS, A à Sb, B à SA, B à BB, B à a}.

Положим А1 = S, А2 = A и А3 = B и выполним алгоритм 3.7.5 по шагам.

Шаг 1. i = 1.

Шаг 2. Правила вывода вида A1 à A1a (в обозначениях исходной грамматики S à Sa) в грамматике нет. Шаг не выполняется.

Шаг 3. i = 2, j = 1.

Шаг 4. Найдем все правила вида A2 à A1a (для нашего примера — это A à Sa). Таких правил в грамматике только одно — это правило A à Sb. Для выполнения замены этого правила нужно найти правила, в правой части которых стоит символ A1 (т.е. S).

После замены правила A à Sb получим новое множество правил P¢ = {S à AB, S à a, A à BS, A à Abb, A à ab, B à SA, B à BB, B à a}.

Шаг 5. j = i – 1. Переход к шагу 2.

Шаг 2. (i = 2). Правила A à BS, A à Abb, A à ab заменяем правилами: A à BS, A à ab, A à BSA¢, A à abA¢ и A¢ à Bb, A¢ à BbA¢. Получаем следующее множество правил: P¢ = { S à AB, S à a, A à BS, A à ab, A à BSA¢, A à abA¢, A¢ à Bb, A¢ à BbA¢, B à SA, B à BB, B à a}.

Шаг 3. i = 3, j = 1.

Шаг 4. Используя правила S à AB, S à a, заменяем правило B à SA правилами B à ABA, B à aA. Получаем новое множество правил грамматики: P¢ = { S à AB, S à a, A à BS, A à ab, A à BSA¢, A à abA¢, A¢ à Bb, A¢ à BbA¢, B à ABA, B à aA}.

Шаг 5. j ¹ i – 1, j = 2. Переход к шагу 4.

Шаг 4. (i = 3, j = 2). Используя правила A à BS, A à ab, A à BSA¢, A à abA¢, заменяем правило B à ABA правилом B à aA, B à BSBA, B à abBA, B àBSA¢BA, B à abA¢BA и получаем новое множество правил грамматики P¢ = {S à AB, S à a, A à BS, A à ab, A à BSA¢, A à abA¢, A¢ à Bb, A¢ à BbA¢, B à aA, B à BSBA, B à abBA, B à BSA¢BA, B à abA¢BA}.

Шаг 5. j = i – 1. Переход к шагу 2.

Шаг 2. (i = 3). Правила B à BSBA, B à BSA¢BA, B à aA, B à abBA, B à abA¢BA заменяем правилами B à ab, B à abBA, B à abA¢BA, B à abB¢, B à abBAB¢, B à abA¢BAB¢, B¢à SBA, B¢à SA¢BA, B¢à SBAB¢, B¢à SA¢BAB¢.

Шаг 3. i = n, выход из алгоритма с окончательным множеством правил грамматики P¢ = {S à AB, S à a, A à BS, A à ab, A à BSA¢, A à abA¢, A¢ à Bb, A¢ à BbA¢, B à ab, B à abBA, B à abA¢BA, B à abB¢, B à abBAB¢, B à abA¢BAB¢, B¢à SBA, B¢à SA¢BA, B¢à SBAB¢, B¢à SA¢BAB¢}.








©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.