Контакты

Случайная статья

Преобразование формальных грамматик

Стр 1 из 2Следующая ⇒

Министерство науки и высшего образования РФ

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Тульский государственный университет»

Институт прикладной математики и компьютерных наук

Кафедра прикладной математики и информатики

Отчет по лабораторной работе № 5

по курсу «Системы программирования»

Преобразование формальных грамматик

Выполнил: студент группы 221211 ________________ Потягин К. В.

Проверил: ________________ Родионова Г. А.

Тула 2022 г.

1. Цель работы: изучить алгоритмы преобразования КС-грамматик

2. Задание: Для заданного варианта грамматики произвести следующие преобразования

1) устранение бесполезных символов

2) преобразование КС-грамматики с ε -правилами в эквивалентную НКС-грамматику

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

4) удаление произвольного правила вывода

5) устранение прямой левой рекурсии

6) произвести левую факторизацию

7) преобразование к нормальной форме Хомского.

8) преобразование к нормальной форме Грейбах

9) преобразование к нормальной форме Грейбах с использованием систем уравнений

Вариант №30

S→ A A→ 1a0

S→ B B→ 1B00

A→ 1A0 B→ 1b00

3. Выполнение работы

3. 1. Устранение бесполезных символов

Из грамматики , где , и

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

Сначала определим множество производящих терминальных символов по алгоритму:

После исключения непроизводящих символов получим:

Далее определим множество достижимых символов по алгоритму:

После удаления бесполезных символов, получаем грамматику

где и

12 Следующая ⇒

© helpiks.su При использовании или копировании материалов прямая ссылка на сайт обязательна.