Курсовая работа: Построение распознавателя для заданной грамматики и реализация его в виде программы которая проверяет

1. Каждой цепочке выводимой в заданной грамматике соответствует одно или несколько деревьев вывода.

2. Каждому дереву соответствует один или больше выводов.

3. Каждому дереву соответствует единственный правый и единственный левый выводы.

4. Если каждой цепочке, выводимой в данной грамматике, соответствует единственное дерево вывода, то такая грамматика называется однозначной (в правой части каждого правила такой грамматики содержится не более одного нетерминала).

Языком L (G), порождаемым грамматикой G, называется множество всех цепочек в алфавите терминальных символов VT, выводимых из начального символа грамматики.

В процессе функционирования грамматики возможны два варианта:

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

а) вывод цепочки из начального символа грамматики (построить дерево вывода или вывод начиная с корня) - нисходящий вывод;

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

В обоих вариантах строится дерево вывода.

2. Получать цепочки, которые принадлежат к языку, порождаемому заданной грамматикой.

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

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

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

?????????? ?????????? - ??? ??????? ???????????????? ?????? ? ????????? ?????????? ???????, ??????? ??????? - ???????? ???????????? ????????? ?????????? ?????????, ????????? ???????? ?????? ? ??????? ?????????????? ??????. ?????????? ?????????????? ?????????? - ???????? ????????? ??? ???????? (????????) ???????????? ?????????? ??????????? ?????????. ??? ????????? ????? ???? ??????????? ? ???? ???????? ?? ????? ????? ????????????????. ???????? ????? ??????????? ?????????? - ?????????????? ????? ??????? ???? ???????????????? (?????) - ??????????.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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