Дисциплина ТЯП и МТ

Кафедра МОЭВМ

Отчет по курсовой работе

Вариант №19

Выполнили: Угаров Ю.

Лузянин Н.

Группа: № 8303

Проверил: Опалева Э.А.

Санкт-Петербург

2011 год

Раздел 2.

ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КС-ГРАММАТИК.

2.1. Общие сведения

Грамматики G₁ и G₂ называются эквивалентными, если L(G₁) = L(G₂).

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

удаление бесполезных символов;

удаление ε-правил;

удаление цепных правил;

исключение из КС-грамматики левой рекурсии.

Алгоритмы исключения бесполезных символов, ε-правил, цепных правил, леворекурсивных правил описаны в [1].

2.2. Задания

2.2.1. Исключение бесполезных символов

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

2.2.1.5.   T = { a, b, c, d ), N = { S, A, B, C }, R = { S  → aC, S  → bA, A  → cAB, B  → aC, C  → bA, C  → d };

1)Строим множество производящих нетерминальных символов

N_p = {S, B, C}

Исключаем непроизводящие нетерминалы:

R₁ = {S→ aC, B  → aC, C  → d }

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

G₁ = <{ a, b, c, d }, {B, S, C,}, S, R₁>

2) Строим множество достижимых символов:

N_r = { S, A, B, C }

Исключаем недостижимые символы:

R₂ = { S  → aC, S  → bA, A  → cAB, B  → aC, C  → bA, C  → d }

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

G₂ = <{ a, b, c, d }, { S, A, B, C }, S, R₂>

Результат: G₂ = <{ a, b, c ,d}, { S, B, C }, S, { S  → aC, S  → bA, A  → cAB, B  → aC, C  → bA, C  → d }>.

2.2.2. Исключение ε-правил

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

2.2.2.10. Т = { begin, end, d, p, ;, , }, N = { S, D, P, X, Y },

R = { S → begin D ; P end D  → dX X  → , D X  → ε P → pY Y  → ,P Y  → ε };

1) Строим множество укорачивающих нетерминалов:

N_ε = { X, Y }

2) Новое множество правил вывода:

R₁ = { S → begin D ; P end D  → dX D  → d X  → , D P → pY P → p Y  → ,P }

Результат: G₁ = <{ begin, end, d, p, ;, ,}, { S, D, P, X, Y}, S, {S → begin D ; P end D  → dX D  → d X  → , D P → pY P → p Y  → ,P }>.

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

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

2.2.3.3. T = { i,  |,  ∨, &, (, ) }, N = { S, T, P }, R = { S  → S ∨ T, S → T, T  → T&P, T  → P, P  →  | P, P  → (S), P  → i };

1) Построим множества:

NS = {S,T,P}

NT = {T,P}

Np = {P}

2) Новое множество правил вывода:

R1 = {S  → S ∨ T, S → T&P, S → |P , S → (S), S → i, T  → T&P, T  → |P, T → (S), T → i, P  →  | P, P  → (S), P  → i }

Результат: G1 = <{ i,  |,  ∨, &, (, ) }, { S, T, P }, S, { S  → S ∨ T, S → T&P, S → |P , S → (S), S → i, T  → T&P, T  → |P, T → (S), T → i, P  →  | P, P  → (S), P  → i }>.

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

Исключить левую рекурсию из КС-грамматики G = < T, N, S, R >.

2.2.4.2. T = { a, b }, N = { S, A, B }, R = { S  → Ba, S  → Ab, A  → Sa, A → AAb, A  → a, B  → Sb, B  → BBa, B  → b };

1) Заменим A-правила { A  → Sa, A → AAb, A  → a } на правила:

{ A → Baa, A → BaaA’, A’ → ba, A’ → baA’, A  → aA’, A  → a, A’ → Ab, A’ → AbA’}.

2) Заменим B-правила { B  → Sb, B  → BBa, B  → b } на правила:

{ B’  → aabb, B’  → aabbB’, B’  → aaA’bb, B  → BaaA’bbB’, B  → abb, B  → abbB’, B  → aA’bb, B  → aA’bbB’ , B’ → ab, B’ → abB’ , B  → b, B  → bB’, B’  → Ba, B’ → BaB’}.

Результат: G1 = <{ a, b }, {S, A, B, A’, B’}, S, { S  → Ba, S  → Ab, A → Baa, A → BaaA’, A’ → ba, A’ → baA’, A  → aA’, A  → a, A’ → Ab, A’ → AbA’, B’  → aabb, B’  → aabbB’, B’  → aaA’bb, B  → BaaA’bbB’, B  → abb, B  → abbB’, B  → aA’bb, B  → aA’bbB’ , B’ → ab, B’ → abB’ , B  → b, B  → bB’, B’  → Ba, B’ → BaB’ }>.