Контекстно-свободные языки и грамматики Задача и дерево разбора Р : A, где A V N, (V T V N ) + Не более одного правила: А. - презентация

1 Контекстно-свободные языки и грамматики Задача и дерево разбора Р : A, где A V N, (V T V N ) + Не более одного правила: А

2 Пример 1 Дано: G=({a, b, +}, {S, T}, {S T|T+S; T a|b}, S) Построить: вывод цепочки a+b+a Левосторонний вывод: Правосторонний вывод: S T+S a+S a+T+S a+b+S a+b+T a+b+aa+b+a S T+S T+T+S T+T+T T+T+a T+b+a a+b+aa+b+a

3 Дерево разбора (1) {V T V N }, (2) A V N, (3) A V N, S,S, {V T } a 1, a 2, …, a n, a i {V T V N } A a 1 a 2 …a n Р, n 1, A Р

4 Пример 2 Построить: дерево разбора цепочки a+b+a Дано: G=({a, b, +}, {S, T}, {S T|T+S; T a|b}, S) Нисходящее дерево вывода: S T + aTS b + S a T

5 S T +a T T b a + S Пример 3 Восходящее дерево разбора: S S T|T+S; T a|b