Построение распознователя грамматик. Построение распознавателя для заданной грамматики и реализация е. Курсовая работа по дисциплине "Основы дискретной математики"
 Скачать 227 Kb.
|
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) }. |