|
Для граматики 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-нетерміналів.
Решение
S0 = {A, C}
S1 = {A, C, B}
S2 = {A, C, B}
Ответ: S2
Задача СП-7
Сформулюйте алгоритм пошуку множини непродуктивних нетерміналів.
Нетермінал продуктивний, якщо при застосуванні до нього скінченної кількості правил переходу отримуємо лише термінали.
Алгоритм поиска непродуктивных правил
S0 = {Ai | Ai ®w, wÎT*}
Sk = Sk-1 È {Ai | Ai ®w, wÎ(TÈSk-1)* }
Sm=Sm-1
(T) Термінали – букви
(N) Нетермінали – поняття, великі букви =)
Получили множество продуктивных нетерміналів Sm. Все остальные – непродуктивные.
Ответ: N\ Sm
Задача СП-8
Сформулюйте алгоритм пошуку множини недосяжних нетерміналів.
Алгоритм.
k. Sk = Sk-1 È{Ai | Aj ® a1a2...Ai...ap, AjÎSk-1}
m. Sm=Sm-1
Sm – множество достижимых нетерминалов.
Ответ: N \ Sm
Задача СП-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}, знайти множину ліворекурсивних нетерміналів.
Алгоритм
Для каждого AiÎN выполнять процедуру:
S0 = {Ak | Ai ®w1Akw2, w1=>*e}
Sn = Sn-1 È {Aj | Ak ®w1Ajw2, w1=>*e, AkÎSn-1}
Sm=Sm-1
Если AiÎSm то Ai – леворекурсивный нетерминал.
Решение
Множество e-нетерминалов: {B,C}
S0 = {A}
S1 = {A,B,D}
S2 = {A,B,D,C}
S3 = {A,B,D,C,S} +
S0 = {B,D}
S1 = {B,D,A,C} +
S0 = {B,C}+
S0 = {S}
S1 = {S,A}
S2 = {S,A,B,D}
S3 = {S,A,B,D,C} +
S0 = {B,A}
S1 = {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}, знайти множину праворекурсивних нетерміналів.
Алгоритм
Для каждого AiÎN выполнять процедуру:
S0 = {Ak | Ai ®w1Akw2, w2=>*e}
Sn = Sn-1 È {Aj | Ak ®w1Ajw2, w2=>*e, AkÎSn-1}
Sm=Sm-1
Если AiÎSm то Ai – праворекурсивный нетерминал.
Решение
Множество e-нетерминалов: {B,C}
S0 = {S,A,C} +
S0 = {D}
S1 = {D, A, B} +
S0 = {B, C} +
S0 = {}
S1 = {} -
S0 = {B,A}
S1 = {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}
S0 = {S,A,C} +
S0 = {D}
S1 = {D, B, S}
S2 = {D, B, S, C, A} +
S0 = {B, C} +
S0 = {}
S1 = {} -
S0 = {B,S}
S1 = {B,A,C}
S2 = {B,A,C,D} +
Ответ: {S,A,B,D}
Задача СП-12
Дата добавления: 2015-09-12; просмотров: 33 | Поможем написать вашу работу | Нарушение авторских прав |