formal_languages_translation_theory (Формальные грамматики), страница 6

PDF-файл formal_languages_translation_theory (Формальные грамматики), страница 6 Программное обеспечение систем автоматизированного проектирования (ПО САПР) (112565): Книга - 3 семестрformal_languages_translation_theory (Формальные грамматики) - PDF, страница 6 (112565) - СтудИзба2021-10-05СтудИзба

Описание файла

PDF-файл из архива "Формальные грамматики", который расположен в категории "". Всё это находится в предмете "программное обеспечение систем автоматизированного проектирования (по сапр)" из 3 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 6 страницы из PDF

Это означает, что исходнаяцепочка a1a2...an   L(G).(2) прочитана вся цепочка; на каждом шаге находилась единственная нужная свертка;на последнем шаге свертка произошла к символу, отличному от S. Это означает,что исходная цепочка a1a2...an   L(G).(3) на некотором шаге не нашлось нужной свертки, т. е. для полученного на предыдущем шаге нетерминала A и расположенного непосредственно справа от негоочередного терминала ai исходной цепочки не нашлось нетерминала B, для которого в грамматике было бы правило вывода B → Aai. Это означает, что исходнаяцепочка a1a2...an   L(G).(4) на некотором шаге работы алгоритма оказалось, что есть более одной подходящейсвертки, т.

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

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

Сделаем это в виде таблицы, столбцы которой помечены терминальными символами. Первая строка помечена символом Н (НN), а значение каждого элементаэтой строки — это нетерминал, к которому можно свернуть помечающий столбец терминальный символ. Остальные строки помечены нетерминальными символами грамматики.Значение каждого элемента таблицы, начиная со второй строки — это нетерминальный символ, к которому можно свернуть пару «нетерминал-терминал», которыми помечены соответствующие строка и столбец.Например, для леволинейной грамматики Gleft  {a, b, }, {S, A, B, C}, P, S , гдеP:S → CC → Ab | BaA → a | CaB → b | Cb ,такая таблица будет выглядеть следующим образом:abHAB—CABSA—C—BC——S———Знак «—» ставится в том случае, если соответствующей свертки нет.Но чаще информацию о возможных свертках представляют в виде диаграммы состояний (ДС) — неупорядоченного ориентированного помеченного графа, который строитсяследующим образом:(1) строим вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала — одну вершину), и еще одну вершину, помеченную символом, отличным от нетерминальных, например, H.

Эти вершины будем называть состояниями. H — начальное состояние.(2) соединяем эти состояния дугами по следующим правилам:а) для каждого правила грамматики вида W → t соединяем дугой состояния Hи W (от H к W ) и помечаем дугу символом t;б) для каждого правила W → Vt соединяем дугой состояния V и W (от V к W) ипомечаем дугу символом t;Диаграмма состояний для грамматики Gleft (см. пример выше) изображена на рис.4:HabAbabBCSaРис. 4.

Диаграмма состояний для грамматики Gleft.23Элементы теории трансляции / Разбор по регулярным грамматикамАлгоритм разбора по диаграмме состояний(1) объявляем текущим начальное состояние H;(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: считываем очередной символ исходной цепочки и переходим из текущего состояния в другое состояние по дуге, помеченной этим символом.

Состояние, в которое мы при этом попадаем, становится текущим.При работе этого алгоритма возможны следующие ситуации (аналогичные ситуациям,которые возникают при разборе непосредственно по регулярной грамматике):1) Прочитана вся цепочка; на каждом шаге находилась единственная дуга, помеченная очередным символом анализируемой цепочки; в результате последнего перехода оказались в состоянии S. Это означает, что исходная цепочка принадлежитL(G).2) Прочитана вся цепочка; на каждом шаге находилась единственная «нужная» дуга;в результате последнего шага оказались в состоянии, отличном от S.

Это означает,что исходная цепочка не принадлежит L(G).3) На некотором шаге не нашлось дуги, выходящей из текущего состояния и помеченной очередным анализируемым символом. Это означает, что исходная цепочкане принадлежит L(G).4) На некотором шаге работы алгоритма оказалось, что есть несколько дуг, выходящих из текущего состояния, помеченных очередным анализируемым символом,но ведущих в разные состояния.

Это говорит о недетерминированности разбора.Анализ этой ситуации будет приведен ниже.Диаграмма состояний определяет конечный автомат, построенный по регулярнойграмматике, который допускает множество цепочек, составляющих язык, определяемый этойграмматикой. Состояния и дуги ДС — это графическое изображение функции переходов конечного автомата из состояния в состояние при условии, что очередной анализируемый символ совпадает с символом-меткой дуги. Среди всех состояний выделяется начальное (считается, что в начальный момент своей работы автомат находится в этом состоянии) и заключительное (если автомат завершает работу переходом в это состояние, то анализируемая цепочка им допускается).

На ДС эти состояния отмечаются короткими входящей и соответственно исходящей стрелками, не соединенными с другими вершинами.Определение: детерминированный конечный автомат (ДКА) — это пятерка  K, T, ,H, S , гдеK — конечное множество состояний;T — конечное множество допустимых входных символов; — отображение множества K  T в K, определяющее поведение автомата;H  K — начальное состояние;S  K — заключительное состояние (либо множество заключительных состоянийS  K).Замечания к определению ДКА:(1) Заключительных состояний в ДКА может быть более одного, однако для любогорегулярного языка, все цепочки которого заканчиваются маркером конца (), су-24Элементы теории трансляции / Разбор по регулярным грамматикамществует ДКА с единственным заключительным состоянием. Заметим также, чтоДКА, построенный по регулярной грамматике рассмотренным выше способом,всегда будет иметь единственное заключительное состояние S.

13)(2) Отображение : K  T → K называют функцией переходов ДКА. (A, t)  B означает, что из состояния A по входному символу t происходит переход в состояние B.Иногда  определяют лишь на подмножестве K  T (частичная функция). Еслизначение (A, t) не определено, то автомат не может дальше продолжать работу иостанавливается в состоянии «ошибка».Определение: ДКА допускает цепочку a1a2...an, если  (H, a1)  A1;  (A1, a2)  A2 ; …;  (An − 2, an − 1)  An − 1;  (An − 1, an)  S, где ai  T, Aj  K, j  1, 2, ..., n  1; i  1, 2, ..., n; H —начальное состояние, S — заключительное состояние.Определение: множество цепочек, допускаемых ДКА, составляет определяемый имязык.Для более удобной работы с диаграммами состояний введем несколько соглашений: если из одного состояния в другое выходит несколько дуг, помеченных разнымисимволами, то будем изображать одну дугу, помечая ее списком из всех таких символов; непомеченная дуга будет соответствовать переходу при любом символе, кроме тех,которыми помечены другие дуги, выходящие из этого состояния; введем состояние ошибки (ER); переход в это состояние будет означать, что исходная цепочка языку не принадлежит.По диаграмме состояний легко написать анализатор для регулярной грамматики.Например, для грамматики Gleft   {a, b, }, {S, A, B, C}, P, S  с правиламиP:S → CC → Ab | BaA → a | CaB → b | Cbанализатор будет таким:#include <iostream>using namespace std;char c;// текущий символvoid gc () { cin >> c; }// считать очередной символ из входной цепочкиbool scan_G (){enum state { H, A, B, C, S, ER }; // множество состояний13)Нетрудно указать и обратный способ — построения грамматики по диаграмме состояний автомата, — причем получившаяся грамматика будет автоматной.

Каждой дуге из начального состояния Н в состояние W,помеченной символом t, будет соответствовать правило W → t; каждой дуге из состояния V в состояние W,помеченной символом t, будет соответствовать правило W → Vt. Заключительное состояние S объявляетсяначальным символом грамматики.Если в вершину Н входит некоторая дуга (это возможно в произвольно построенном автомате), то алгоритм модифицируется так: каждой дуге из начального состояния Н в состояние W, помеченной символомt, будет соответствовать правило W →Ht, и в грамматику добавляется правило Н→ε; затем к построеннойграмматике применяется алгоритм удаления правил с пустыми правыми частями.25Элементы теории трансляции / Разбор по регулярным грамматикамstate CS;CS = H;// CS —— текущее состояниеdo{ gc ();switch (CS){case H: if ( c == 'a' ){CS = A;}else if ( c == 'b' ){CS = B;}elseCS = ER;break;case A: if ( c == 'b' ){CS = C;}elseCS = ER;break;case B: if ( c == 'a' ){CS = C;}elseCS = ER;break;case C: if ( c =='a' ){CS = A;}else if ( c == 'b' ){CS = B;}else if ( c == '' )CS = S;elseCS = ER;break;}}while ( CS != S && CS != ER);return CS == S; // true, если CS != ER,}26иначе falseЭлементы теории трансляции / Разбор по регулярным грамматикамПример разбора цепочкиРассмотрим работу анализатора для грамматики G на примере цепочки abba.

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5288
Авторов
на СтудИзбе
417
Средний доход
с одного платного файла
Обучение Подробнее