Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Сформулюйте алгоритм пошуку e-нетерміналів для КВ-граматики.

Для граматики G={N, S, P, S} з схемою

Р: S ® a B D | D A C | b

A ® S C B | S A B C | C b D | e

B ® C A | d

C ® A D C | a | e

D ® E a C | S C

E ® BCS | a

де N = {S, A, B, C, D, E}, S = {a, b, d}, знайти множину e-нетерміналів.

Решение

S₀ = {A, C}

S₁ = {A, C, B}

S₂ = {A, C, B}

Ответ: S₂

Задача СП-7

Сформулюйте алгоритм пошуку множини непродуктивних нетерміналів.

Нетермінал продуктивний, якщо при застосуванні до нього скінченної кількості правил переходу отримуємо лише термінали.

Алгоритм поиска непродуктивных правил

S₀ = {A_i | A_i ®w, wÎT^*}

S_k = S_k-1 È {A_i | A_i ®w, wÎ(TÈS_k-1)^* }

S_m=S_m-1

(T) Термінали – букви

(N) Нетермінали – поняття, великі букви =)

Получили множество продуктивных нетерміналів S_m. Все остальные – непродуктивные.

Ответ: N\ S_m

Задача СП-8

Сформулюйте алгоритм пошуку множини недосяжних нетерміналів.

Алгоритм.

1. S₀ = {S}

k. S_k = S_k-1 È{A_i | A_j ® a₁a₂...A_i...a_p, AjÎSk-1}

m. S_m=S_m-1

Sm – множество достижимых нетерминалов.

Ответ: N \ S_m

Задача СП-9

Сформулюйте алгоритм пошуку множини ліворекурсивних нетерміналів.

Для граматики G={N, S, P, S} зі схемою Р:

S ® A b S | A C

A ® B D

C ® S a | e

B ® B C | e

D ® a B | B A

де N={S, A, C, B, D}, S = {a, b}, знайти множину ліворекурсивних нетерміналів.

Алгоритм

Для каждого A_iÎN выполнять процедуру:

S₀ = {A_k | A_i ®w₁A_kw₂, w₁=>^*e}

S_n = S_n-1 È {A_j | A_k ®w₁A_jw₂, w₁=>^*e, A_kÎS_n-1}

S_m=S_m-1

Если A_iÎS_m то A_i – леворекурсивный нетерминал.

Решение

Множество e-нетерминалов: {B,C}

1. Рассмотрим S

S₀ = {A}

S₁ = {A,B,D}

S₂ = {A,B,D,C}

S₃ = {A,B,D,C,S} +

1. Рассмотрим A

S₀ = {B,D}

S₁ = {B,D,A,C} +

1. Рассмотрим B

S₀ = {B,C}+

1. Рассмотрим C

S₀ = {S}

S₁ = {S,A}

S₂ = {S,A,B,D}

S₃ = {S,A,B,D,C} +

1. Рассмотрим D

S₀ = {B,A}

S₁ = {B,A,C,D} +

Ответ: все нетерминалы леворекурсивные

Задача СП-10

Сформулюйте алгоритм пошуку множини праворекурсивних нетерміналів.

Для граматики G={N, S, P, S} зі схемою Р:

S ® A b S | A C

A ® B D

C ® S a | e

B ® B C | e

D ® a B | B A

де N={S, A, C, B, D}, S = {a, b}, знайти множину праворекурсивних нетерміналів.

Алгоритм

Для каждого A_iÎN выполнять процедуру:

S₀ = {A_k | A_i ®w₁A_kw₂, w₂=>^*e}

S_n = S_n-1 È {A_j | A_k ®w₁A_jw₂, w₂=>^*e, A_kÎS_n-1}

S_m=S_m-1

Если A_iÎS_m то A_i – праворекурсивный нетерминал.

Решение

Множество e-нетерминалов: {B,C}

1. Рассмотрим S

S₀ = {S,A,C} +

1. Рассмотрим A

S₀ = {D}

S₁ = {D, A, B} +

1. Рассмотрим B

S₀ = {B, C} +

1. Рассмотрим C

S₀ = {}

S₁ = {} -

1. Рассмотрим D

S₀ = {B,A}

S₁ = {B,A,C,D} +

Ответ: {S,A,B,D}

Задача СП-11

Сформулюйте алгоритм пошуку множини праворекурсивних нетерміналів.

Для граматики G={N, S, P, S} зі схемою Р:

S ® A b S | A C

A ® B D

C ® S a | e

B ® B C | e

D ® a B | B S

де N={S, A, C, B, D}, S = {a, b}, знайти множину праворекурсивних нетерміналів.

Решение

Множество e-нетерминалов: {B,C}

1. Рассмотрим S

S₀ = {S,A,C} +

1. Рассмотрим A

S₀ = {D}

S₁ = {D, B, S}

S₂ = {D, B, S, C, A} +

1. Рассмотрим B

S₀ = {B, C} +

1. Рассмотрим C

S₀ = {}

S₁ = {} -

1. Рассмотрим D

S₀ = {B,S}

S₁ = {B,A,C}

S₂ = {B,A,C,D} +

Ответ: {S,A,B,D}

Задача СП-12