b>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 (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 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 (6) })4. Определим тип полученной грамматики: по виду правил можно сказать, что это контекстно-свободная грамматика (неправосторонняя - несоответствие в правилах (1), (3) и не является S-грамматикой -есть эпсилон-правило (6)).Полученная грамматика может быть q -грамматикой- (по определению для такой грамматики множества “Выбор” для правил с одинаковыми левыми частями попарно не пересекаются).Для такой грамматики множества “Выбор” для правил с одинаковыми левыми частями попарно не пересекаются (пересечение пусто).“Выбор Q (1) ” = { a }; “Выбор Q (2) ” = b“Выбор Q (1) ” “Выбор Q (2) ” = { (пусто) };“Выбор H (4) ” = { b }; “Выбор H (6) ” = "СледH" = “Выбор H (4) ” “Выбор H (6) ” = { (пусто) };Исследуемая грамматика является q - грамматикой.5. В соответствии с известным алгоритмом строим для этой грамматики МП-распознаватель:Алфавит магазинных символов Vмаг = { Q, H, A, B, a, b, h }Управляющая таблица имеет вид:|
| a | b | h | --| | | | E | E | E | Доп. | | Q | Зам. QH | П | Зам. ahA | П | E | Отв. | | A | Зам. bBh | П | E | E | Отв. | | В | Зам. bbHh | П | E | E | Отв. | | Н | E | Зам. B | П | Выт. H | Д | Выт. H | Д | | a | Выт. a | П | E | E | Отв. | | b | E | Выт. b | П | E | Отв. | | h | E | E | Выт. h | П | Отв. | | |
4 Для проверки правильности работы МП-распознавателя выведем, применяя правила грамматики, правильную цепочку: (2) (3) (5) (5) Q b a h A b a h b B h b a h b a b b H h h b a h b a b b h h |
Необработ. цепочка | Обраб. симв. | Верхн. маг. симв | Содерж. магазина | Действия с маг. | | bahababbhh --| ahababbhh -| hababbhh-| ababbhh --| babbhh --| abbhh --| bbhh --| bhh--| hh--| h --| --| | b a h a b a b b h h --| | Q a h A b B b b H h h | Q a h A h A A bB h bbHhh bHhh Hhh hh h | Зам. ahA Выт. a Выт. h Зам. b Bh Выт. b Зам. bbHh Выт. b Выт. b Выт. H Выт. h Выт. h Доп. | | |
5. Полное описание МП - распознавателя: Входной алфавит a, b, h -- Алфавит магазинных символов {Q, A, B, H, a, b, h, } Множество состояний { S 1 } Начальная конфигурация (S 1, Q, ) Допускающая конфигурация (S 1, ) Управляющая таблица приведена выше. 6. Программа, реализующая МП - распознаватель, приведена в приложении. 2.2 Современные требования к программным продуктам1. Лицензионная чистота (применение программного продукта допустимо только в рамках лицензионного соглашения).2. Возможность консультации с разработчиком и другие формы сопровождения.3. Соответствие характеристикам, комплектации, классу и типу компьютеров, а также архитектуре применяемой вычислительной техники.4. Надежность и работоспособность в любом из предусмотренных режимов работы, как минимум, в русскоязычной языковой среде.5. Наличие дружественного интерфейса, поддерживающего работу с использованием русского языка (для системного и инструментального программного обеспечения допустимо наличие интерфейса на английском языке).6. Наличие документации, необходимой для практического применения и освоения работы с программным продуктом, на русском языке.7. Развитая система интерактивной помощи при работе с программным продуктом.8. Наличие спецификации, оговаривающей все требования к аппаратным и программным средствам, необходимым для функционирования данного программного продукта.2.3 Обоснование выбора средств реализацииНаиболее популярны средства разработки WINDOWS, сочетающие в себе средства разработки интерфейса с мощными компиляторами и отладчиками. Одним из таких инструментов является язык программирования BORLAND DELPHI. Возможность проектирования пользовательского интерфейса с помощью редактора форм, а также простота использования функций Windows API и мощные собственные средства отображения графических объектов явились главными критериями в выборе средств разработки предлагаемого продукта.DELPHI - сложная современная система программирования. Диапазон возможностей Delphi поистине неисчерпаем. Среда DELPHI - это сложный механизм, обеспечивающий высоко эффективную работу программиста.Программирование на DELPHI строится на тесном взаимодействии двух процессов: процесса конструирования визуального проявления программы (т.е. ее Windows-окон) и процесса написания программного кода, придающего элементам этого окна и программе в целом необходимую функциональность. Написание программы облегчено визуализацией разработки интерфейса. Сначала разработчик конструирует форму (внешний вид программы). Среда разработки автоматически вносит изменения в написанный код программы (тем самым значительно облегчает работу разработчику). DELPHI основан на объектном программировании языка программирования высокого уровня TURBO PASCAL. Именно Delphi стал тем продуктом, на примере которого стало ясно, что один продукт может столь удачно сочетать несколько передовых технологий:* высокопроизводительный компилятор;* объектно-ориентированная модель компонент.* визуальное (а, следовательно, и быстрое) построение приложений из программных прототипов.Таким образом, Delphi обеспечивает удобство и быстроту написания приложений, отвечающим самым высоким стандартам качества; поэтому он и выбран для реализации данного программного продукта.
Страницы: 1, 2, 3
|
