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




Скачать 426.05 Kb.
НазваниеПрограмма, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке
страница6/11
Дата публикации27.03.2013
Размер426.05 Kb.
ТипПрограмма
uchebilka.ru > Информатика > Программа
1   2   3   4   5   6   7   8   9   10   11
^

Контекстно-свободные грамматики


КС-грамматика – частный случай формальной грамматики, у которой правила грамматики в общем виде выглядят так: один нетерминал любая конечная цепочка из терминалов и нетерминалов.

Терминал – объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение.

Нетерминал – объект, обозначающий какую-либо сущность языка (например, формула, арифметич. выражение, команда) и не имеющий конкретного символьного значения.

Пример правил КС-грам.:  ; . Первый нетерминал (перед стрелкой) называется аксиомой.

Итого, КС грамматика задается: конечным мн-вом нетерминалов; конечным мн-вом терминалов, которое не пересекается с мн-вом нетерминалов; конечным мн-вом правил вида , где левая часть – нетерминал, правая – цепочка терм. и нетерм. (возможно, пустая); одним нетерминальным симв. выделенным в кач-ве начального (аксиома).

КС-грамматики широко применяются для описания синтаксиса компьютерных языков.

  1. ^

    Бесполезные нетерминалы. Удаление из грамматики бесполезных нетерминалов


Нетерминалы называются бесполезными, если после их удаления вместе с правилами грамматика продолжает описывать тот же самый язык. Бесполезными нетерминалами являются бесплодные и недостижимые нетерминалы. Нетерминалы, которые не порождают ни одной терминальной цепочки, называются бесплодными. Нетерминалы, которые не появляются ни в одной цепочке, выводимой из аксиомы грамматики называются недостижимыми. Терминальный или нетерминальный символ называется продуктивным, если из него выводится какая-нибудь терминальная цепочка.

Процедура обнаружения бесполезных нетерминалов: делится на две процедуры – обнаружение бесплодных и обнаружение недостижимых нетерминалов. Сначала нужно выполнить обнаружение бесплодных, т.к. после их удаления могут появиться недостижимые нетерминалы.


Пример:

  1. 

  2. 

  3. 

  4. 

  5. 

  6. 

  7. 

  8. 

  9. 
Шаги: 1) составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминальных символов. 2) Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже занесены в список, то добавить в список нетерминал, стоящий в его левой части. 3) Если на шаге 2 список больше не пополняется новыми нетерминалами, то получен список всех продуктивных нетерминалов грамматики, а все остальные нетерминалы являются бесплодными.

Пример:

В список добавляем С (по пр. 9), затем A (5), затем S(2). Дальнейшие попытки применить шаг 2 бесполезны, значит B – бесплодный. Удаляем все правила, связанные с B.








8.

9.
Обнаружение недостижимых: Если нетерминал в левой части является достижимым, то достижимы и все символы правой части.

Шаги:

1. Добавить в список начальный нетерминал.

2. Если найдено правило, левая часть которого уже имеется в списке, то включить в список все нетерминалы, содержащиеся в правой его части.

3. Если на шаге 2 нетерминалы в список уже не поступают, то получен список всех достижимых нетерминалов, а остальные являются недостижимыми.
В нашем примере все нетерминалы достижимы.

1   2   3   4   5   6   7   8   9   10   11

Похожие:

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconМетодические указания к лабораторной работе №1 по курсу Информатика для студентов
Написание программы на языке программирования. Программы, написанные на языке C++, имеют расширение. Срр

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconКурс «Компонентные программные технологии» 1 Лабораторная работа...
Однако для реализации этой системы необходимо разработать исходный текст программы на некотором языке программирования (C++, Pascal,...

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconРезюме на английском языке (не должна быть копией аннотации на украинском языке)
В тексте резюме на английском языке следует применять терминологию, характерную для иностранных специальных текстов

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconПрограммирование
Введение в программирование на языке Pascal. Программа. Структура программы. Идентификатор. Правила записи идентификатора. Блок описаний....

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconПрограмма написана на языке программирования Delphi под ос windows Vista
Не забудьте указать номер версии в любом докладе о проблеме. Кроме того, необходимо постоянно обновлять программу и использовать...

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconПрограмма аппроксимации на языке бэйсик см-1
Для подготовки исходных данных, необходимых при построении датчиков с заданным распределением в gpss-моделях, описанный алгоритм...

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconПрограммирование на языке С++ Лабораторный практикум
Цель: Изучение символьных и строковых переменных и способов их обработки в языке Си

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconНеотъемлемое право личности?
«образование должно быть направлено на полное развитие человеческой личности», а такое развитие возможно только в том случае, если...

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconРазработка программы на ассемблере. Создание исходного текста программы,...
Целью работы является изучение технологии написания и отладки программ на языке ассемблера

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconО том, как создавать программы на встроенном в Microsoft Office языке...
Но теория будет еще полезнее, если подкрепить ее практикой примерами реально работающих программ, написанных на этом языке. А таких...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<