Классификация грамматик

Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматик (рисунок 1):

Рисунок 1 – Классификация грамматик

Каждый тип грамматик включает грамматики более высоких типов, как частные случаи.

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

Эквивалентные преобразования грамматик

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

Две грамматики эквивалентны, если они порождают один и тот же язык(одни и те же цепочки терминальных символов).Рассмотрим ряд процедур, которые всегда приводят к эквивалентным преобразованиям.

Удаление или добавление бесполезных (непродуктивных и недостижимых) нетерминалов

В множестве Р правил грамматики G непродуктивным называют нетерминал, из которого нельзя получить цепочку терминалов. Для поиска в множестве правил непродуктивных нетерминалов используется следующее свойство.

Свойство А: Если все символы правой части правила продуктивны, то продуктивен и символ, стоящий в его левой части.

Алгоритм поиска непродуктивных нетерминалов в множестве правил P грамматики G:

– составить список нетерминалов для которых найдется хотя бы одно правило, правая часть которого состоит только из терминалов;

– если найдется такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал стоящий в его левой части;

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

Hетерминалы грамматики не попавшие в список, построенный по приведенному выше алгоритму, являются непродуктивными и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.

В множестве правил грамматики недостижимым называют нетерминал, который не участвует в процессе вывода. цепочек. Для поиска недостижимых нетерминалов используется следующее свойство.

Свойство Б: Если нетерминал в левой части правила является достижимым, то достижимы все нетерминалы, стоящие в правой части этого правила.

Алгоритм поиска недостижимых нетерминалов в множестве правил P грамматики G:

– образовать одноэлементный список из начального нетерминала грамматики;

– если в множестве Р найдено правило, левая часть которого уже в списке, то включить в список все нетерминалы из его правой части;

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

Hетерминалы грамматики не попавшие в список, построенный по приведенному выше алгоритму, являются недостижимыми и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.

Не нарушая эквивалентности, можно также исключить правила такого вида: A à A или A à B, B à C, C à A (циклический блок правил).

Построение грамматик для заданного КА

Любое регулярное множество, которое распознается КА, можно описать с помощью автоматной грамматики. Алгоритм построения грамматики следующий:

– Начальное состояние КА- начальный символ грамматики.

– Алфавит КА (без символа конец цепочки–"┤") - терминальные символы грамматики.

– Множество состояний КА - нетерминальные символы грамматики.

– Если в таблице переходов КА есть переход из состояния А в состояние В при воздействии входного символа х – ввести правило следующего вида: А à xB.

– Если D– допускающее состояние КА, то ввести правило следующего вида: Dà*,где *– пустая цепочка(для отвергающих состояний правил нет).

– Закончить составление правил, когда будут обработаны все непустые клетки управляющей таблицы ("0" – пустая клетка).

Разработка программного продукта

Современные требования к программным продуктам

– Удобный, легкий в обращении интерфейс.

– В программе необходимо предусмотреть неквалифицированные действия пользователя.

– К программе должна прилагаться специально разработанная справочная система.

– Программа должна работать в разных операционных системах.

– Надёжность работы программы.