Построение распознавателя для заданной грамматики и реализация его в виде программы которая проверяет (стр. 2 из 4)
Грамматика описывает бесконечный язык, если хотя бы одно из правил рекурсивно, т.е. в правой части содержится его левая часть в явном или неявном виде.
Пример: Задана грамматика G [Z]: VN = {Z,A,B}; VT = {a,b,c}; Z-начальный символ.
P = { Z-ABc; (1)
A-aB; (2)
B-b }. (3)
С помощью грамматики G можно продуцировать (получать) цепочки в алфавите терминалов.
Порядок вывода можно записать в следующем виде:
(1) (2) (3) (3) (номера примененных правил)
Z-AВc-aBВc-aBbc-abbc.
Вывод продолжается до тех пор, пока на очередном шаге не получится цепочка, состоящая только из терминальных символов (т.е. нельзя применить ни одно из правил вывода).
Сокращенно вывод можно записать, пропустив промежуточные результаты, так Z+ - abbc (цепочка abbc выводима из начального символа Z в заданной грамматике).
Сентенциальная форма - любая цепочка терминальных и нетерминальных символов, которая получается на любом шаге процесса вывода. Множество сентенциальных форм можно получить из дерева вывода, обходя его по узлам и соблюдая следующие правила:
- начинать обход с самого левого узла;
- обход надо совершать так, чтобы при переходе к следующему узлу образованное поддерево не включало, как элемент, предыдущее поддерево.
Фраза - часть сентенциальной формы, выводимая из одного нетерминала за несколько шагов. Для простой фразы шаг вывода равен 1.
Одну и ту же цепочку можно получить, применяя правила в различных последовательностях (деревья выводов различны). Если для однозначности в
процессе вывода на каждом шаге применять правило к самому левому (правому) нетерминалу в сентенциальной форме, то получим левосторонний (правосторонний) вывод. Таким образом:
1. Каждой цепочке выводимой в заданной грамматике соответствует одно или несколько деревьев вывода.
2. Каждому дереву соответствует один или больше выводов.
3. Каждому дереву соответствует единственный правый и единственный левый выводы.
4. Если каждой цепочке, выводимой в данной грамматике, соответствует единственное дерево вывода, то такая грамматика называется однозначной (в правой части каждого правила такой грамматики содержится не более одного нетерминала).
Языком L (G), порождаемым грамматикой G, называется множество всех цепочек в алфавите терминальных символов VT, выводимых из начального символа грамматики.
В процессе функционирования грамматики возможны два варианта:
1. Проверять цепочки на принадлежность их к языку, порождаемому заданной грамматикой. Варианты этого процесса могут быть следующими:
а) вывод цепочки из начального символа грамматики (построить дерево вывода или вывод начиная с корня) - нисходящий вывод;
б) вывод можно также делать начиная с кроны дерева (готового предложения); если удается прийти к начальному символу, то предложение принадлежит заданной грамматике - восходящий вывод.
В обоих вариантах строится дерево вывода.
2. Получать цепочки, которые принадлежат к языку, порождаемому заданной грамматикой.
1.2 Классификация грамматик
Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматик (см. рис. на следующей странице):
Каждый тип грамматик включает грамматики более высоких типов, как частные случаи.
 |
Построение грамматики - это процесс структурирования знаний в некоторой предметной области, другими словами - создание порождающего алгоритма некоторого множества, обработка которого удобна с помощью вычислительной машины. Построение распознавателя грамматики - создание алгоритма для проверки (контроля) правильности созданного конкретного множества. Оба алгоритма могут быть реализованы в виде программ на любом языке программирования. Примером такой взаимосвязи грамматика - распознаватель может служить язык программирования (любой) - компилятор.
1.3 Эквивалентные преобразования грамматик
Для построения распознавателей грамматик, других целей часто необходимо преобразовывать правила исходной грамматики к соответствующему виду. При этом язык, порождаемый исходной и полученными после преобразования грамматиками, не должен меняться.
Две грамматики эквивалентны, если они порождают один и тот же язык (одни и те же цепочки терминальных символов). Рассмотрим ряд процедур, которые всегда приводят к эквивалентным преобразованиям.
1 Удаление или добавление бесполезных (непродуктивных и недостижимых) нетерминалов
В множестве Р правил грамматики G непродуктивным называют нетерминал, из которого нельзя получить цепочку терминалов. Для поиска в множестве правил непродуктивных нетерминалов используется следующее свойство.
Свойство А. Если все символы правой части правила продуктивны, то продуктивен и символ, стоящий в его левой части.
Алгоритм поиска непродуктивных нетерминалов в множестве правил P грамматики G:
- составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого состоит только из терминалов;
- если найдется такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал, стоящий в его левой части;
- если на предыдущем шаге список не пополняется, то получен исчерпывающий список всех продуктивных нетерминалов.
Hетерминалы грамматики, не попавшие в список, построенный по приведенному выше алгоритму, являются непродуктивными и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.
В множестве правил грамматики недостижимым называют нетерминал, который не участвует в процессе вывода. цепочек. Для поиска недостижимых нетерминалов используется следующее свойство.
Свойство Б. Если нетерминал в левой части правила является достижимым, то достижимы все нетерминалы, стоящие в правой части этого правила.
Алгоритм поиска недостижимых нетерминалов в множестве правил P грамматики G:
- образовать одноэлементный список из начального нетерминала грамматики;
- если в множестве Р найдено правило, левая часть которого уже в списке, то включить в список все нетерминалы из его правой части;
- если на предыдущем шаге список не пополняется, то получен исчерпывающий список всех достижимых нетерминалов.
Hетерминалы грамматики не попавшие в список, построенный по приведенному выше алгоритму, являются недостижимыми и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.
Пример проверки нетерминалов грамматики:
G [S]: VN = {S, A, B, C, D}; VT = {a, b, c, d}; P = {S - aS (1), S - aA (2), A - bB (3),
A - bC (4), B - d (5) D - c (6) }.
1. Проверка нетерминалов на продуктивность.
В правых частях правил (5) и (6) только терминалы. Внесем в создаваемый список продуктивных нетерминалы B и, D. Затем в соответствии с правилом (3) - A (в правой части терминал и продуктивный нетерминал); в соответствии с правилом (2) - S; анализ других правил список не пополняет. Получен исчерпывающий список продуктивных нетерминалов - { B, D, A, S}. В списке отсутствует нетерминал С (непродуктивный, правило (4) для минимизации исходной грамматики исключим из множества P).
2. Проверка нетерминалов на достижимость.
Внесем на первом шаге в создаваемый список достижимых нетерминалов начальный символ грамматики S, затем на основании правила (2) дополним список нетерминалом A; правило (3) дает основания внести в список нетерминал В. Дальнейший анализ правил в соответствии с алгоритмом поиска достижимых нетерминалов список не пополняет. Получен исчерпывающий список продуктивных нетерминалов - {S,A,B}. В списке отсутствует нетерминал D (недостижимый, правило (6) для минимизации исходной грамматики исключим из множества P).
В результате этих преобразований получим минимальную грамматику G1 [S], эквивалентную исходной.
G1 [S]: VN = {S, A, B}; VT = {a, b, d}; начальный символ S;
P = { S - aS (1), S - aA (2), A - bB (3), B - d (4) }.
2. Разработка программного продукта
2.1 Построение распознавателя для грамматики
Для заданной в варианте грамматики построить распознаватель.
Вариант 10:
G [Q] = (VT = { a, b, h }; VN = { Q, A, B, H }; P = { Q -a Q H (1);
Q - b a h A (2); A - a b B h (3); H - b B (4); B - a b b H h (5); H -e (6) })
Решение:
1 Проверка нетерминальные символов исходной грамматики на достижимость (все правила, в которые входят недостижимые нетерминалы, не нарушая эквивалентности, можно исключить).
(2) (3) (5) - (номера правил)
{ Q} -{ Q, A } - { Q, A, B } - { Q, A, B, H }
(недостижимых нетерминалов нет)
2 Проверка нетерминальных символов полученной после выполнения п.1 грамматики на продуктивность (все правила, в которые входят непродуктивные нетерминальные символы, не нарушая эквивалентности, можно исключить).
(6) (5) (3) (2) - (номера правил)
-{ Н } -{ Н, B } -{Н, B, A }-{Н, B, A, Q }
(непродуктивных нетерминалов нет).
3. Определение типа полученной после выполнения предыдущих пунктов грамматики.
После эквивалентных преобразований новая грамматика не изменилась:
G [Q] = (VT = { a, b, h }; VN = { Q, A, B, H };
P = { Q-aQ H (1);
Q - b a h A (2);
A - a b B h (3);
H - b B (4);
B - a b b H h (5);
H-e (6) })
4. Определим тип полученной грамматики: по виду правил можно сказать, что это контекстно-свободная грамматика (неправосторонняя - несоответствие в правилах (1), (3) и не является S-грамматикой -есть эпсилон-правило (6)).
Полученная грамматика может быть q -грамматикой- (по определению для такой грамматики множества “Выбор” для правил с одинаковыми левыми частями попарно не пересекаются).
Для такой грамматики множества “Выбор” для правил с одинаковыми левыми частями попарно не пересекаются (пересечение пусто).
“Выбор Q (1) ” = { a }; “Выбор Q (2) ” = b
“Выбор Q (1) ” Ç “Выбор Q (2) ” = { (пусто) };
“Выбор H (4) ” = { b }; “Выбор H (6) ” = "СледH" = {h, -| }