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

 

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

 

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

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

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

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

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

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

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

 

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

N₀ = Ø;

N₁ = {A, B};

N₂ = {S, A, B};

N₃ = {S, A, B}.

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

 

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

 

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

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

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

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

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

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

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

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

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

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

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

N₀ = Ø;

N₁ = {S, B, C};

N₂ = {S, B, C}.

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

 

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

 

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

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

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

 

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

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

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

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

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

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

W₀ = {S};

W₁ = {S, a, b};

W₂ = {S, a, b}.

Т.к. W₁=W₂, то 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. N₀ = {A, B};

N₁ = {S, A, B};

N₂ = {S, A, B}.

Т.к. N₁ = N₂, то искомое множество построено и 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. Преобразовав правила вывода грамматики, получим грамматику с правилами

.

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

⇐ Предыдущая234567891011Следующая ⇒

Поделиться:

Популярное:

1. I. Бессмыслица существования
2. I. РУССКИЙ ЯЗЫК: ОБЩЕЕ ПОНЯТИЕ И ФОРМЫ СУЩЕСТВОВАНИЯ.
3. LANGUAGE IN USE - Повторение грамматики: система времен английских глаголов в активном залоге
4. Алгоритм «сдвиг-свертка» для грамматики операторного предшествования
5. Анализ временного существования
6. В этой работе философия предстает как искусство существования и медицинская практика.
7. Деятельность – основа существования и развития общества.
8. Доказательство существования
9. Доказательство существования нирваны
10. Допрос, очная ставка, предъявление для опознания, проверка показаний
11. Из истории методики изучения грамматики в начальных классах
12. ИССЛЕДОВАНИЕ ПЛОСКОГО НАПРЯЖЕННОГО СОСТОЯНИЯ. ПРОВЕРКА ПРОЧНОСТИ ДЛЯ СЛОЖНОГО НАПРЯЖЕННОГО СОСТОЯНИЯ