Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Проверка существования языка грамматики



 

Алгоритм Проверка существования языка грамматики

 

Вход: КС-грамматика .

Выход: заключение о существовании или отсутствии языка грамматики.

Определим множество нетерминалов, порождающих терминальные строки .

Шаг 1. Положить N0=Ø.

Шаг 2. Вычислить и

Шаг 3. Если , то положить i=i+1 и перейти к пункту 2, иначе считать .

Если , то выдать сообщение о том, что язык грамматики существует, иначе сообщить об отсутствии языка.

 

Пример Дана грамматика , где множество правил : . Построим последовательность приближений множества N:

N0 = Ø;

N1 = {A, B};

N2 = {S, A, B};

N3 = {S, A, B}.

Т.к. N2=N3, то N = {S, A, B}, следовательно, язык грамматики существует, потому что начальный символ .

 

Устранение недостижимых символов

 

Определение Бесполезными символами грамматики называют:

а) нетерминалы, не порождающие терминальных строк, т.е. множество символов

б) недостижимые нетерминалы, порождающие терминальные строки, т.е. множество символов

в) недостижимые терминалы, т.е. множество символов


Алгоритм Устранение нетерминалов, не порождающих терминальных строк

Вход: КС-грамматика .

Выход: КС-грамматика , такая, что и для всех существуют выводы , где .

Шаг 1. Определить множество нетерминалов, порождающих терминальные строки, с помощью алгоритма 4.1.

Шаг 2. Вычислить , где - это множество правил, содержащих бесполезные нетерминалы .

Пример Дана грамматика с правилами

Преобразуем ее в эквивалентную грамматику по алгоритму 4.2:

N0 = Ø;

N1 = {S, B, C};

N2 = {S, B, C}.

Т.к. N1= N2, то N = {S, B, C}. После удаления бесполезных нетерминалов и правил вывода, получим грамматику с правилами

 

Алгоритм Устранение недостижимых символов

 

Вход: КС-грамматика .

Выход: КС-грамматика , такая, что и для всех существует вывод , где .

Определим множество достижимых символов Z грамматики G, т.е. множество

 

Шаг 1. Положить

Шаг 2. Вычислить очередное приближение следующим образом:

Шаг 3. Если то положить i: =i+1 и перейти к шагу 2, иначе считать .

Шаг 4. Вычислить , где - это множество правил, содержащих недостижимые символы .

Пример Данаграмматика с правилами

Преобразуем ее в эквивалентную грамматику по алгоритму 4.3:

W0 = {S};

W1 = {S, a, b};

W2 = {S, a, b}.

Т.к. W1=W2, то W={S, a, b}. Множество недостижимых символов Тогда после удаления недостижимых символов, получим грамматику с правилом

Устранение e-правил

Алгоритм Устранение e-правил

Вход: КС-грамматика .

Выход: Эквивалентная КС-грамматика без e-правил для всех нетерминальных символов, кроме начального, который не должен встречаться в правых частях правил грамматики.

Шаг 1. В исходной грамматике найти e-порождающие нетерминальные символы , такие, что .

1.1 Положить .

1.2 Вычислить .

1.3 Если , то положить i: =i+1 и перейти к пункту 1.2, иначе считать .

Шаг 2. Из множества правил исходной грамматики перенести во множество все правила, за исключением e-правил, т.е. для всех

Шаг 3. Пополнить множество правилами, которые получаются из каждого правила этого множества путем исключения всевозможных комбинаций e-порождающих нетерминалов в правой части. Полученные при этом e-правила во множество не включать.

Шаг 4. Если , то , где ; иначе

Пример Дана грамматика с правилами . Преобразуем ее в эквивалентную грамматику по алгоритму 4.4.

Шаг 1. N0 = {A, B};

N1 = {S, A, B};

N2 = {S, A, B}.

Т.к. N1 = N2, то искомое множество построено и N = {S, A, B}.

Шаг 2, 3. Множество 1) ; 2) ; 3)

Шаг 4. Т.к. , то введем новый нетерминал С и пополним множество правилом вида . Результирующая грамматика будет иметь вид: с правилами .

Устранение цепных правил

Алгоритм Устранение цепных правил

Вход: КС-грамматика .

Выход: Эквивалентная КС-грамматика без цепных правил, т.е. правил вида , где .

Шаг 1. Для каждого нетерминала вычислить множество выводимых из него нетерминалов, т.е. множество где

1.1 Положить

1.2 Вычислить

1.3 Если , то положить i: =i+1 и перейти к пункту 1.2, иначе считать

Шаг 2. Построить множество так: если не является цепным правилом , то включить в правило для каждого , такого, что .

 

Пример Грамматика с правилами . Преобразуем ее в эквивалентную грамматику по алгоритму 4.5.

Шаг 1.

Т.к. , то

Т.к. , то

Т.к. , то

Шаг 2. Преобразовав правила вывода грамматики, получим грамматику с правилами

.

Левая факторизация правил


Поделиться:



Популярное:

Последнее изменение этой страницы: 2016-04-11; Просмотров: 1728; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.028 с.)
Главная | Случайная страница | Обратная связь