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

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

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

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

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

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

Но тогда,по крайней мере, некоторые из цепочек с i  j  k будут порождаться обеими группами правил и, следовательно, будут иметь по два разных дерева вывода. Доказательство того, чтоКС-язык L неоднозначный, приведено в [3, т.1, стр. 235–236].Одна из грамматик, порождающих L, такова:S → AB | DCA → aA | B → bBc | C → cC | D → aDb | Она неоднозначна; однозначных грамматик для L не существует.Дерево вывода можно строить нисходящим либо восходящим способом.При нисходящем разборе дерево вывода формируется от корня к листьям; на каждомшаге для вершины, помеченной нетерминальным символом, пытаются найти такое правило10)18Как избавиться от правил, не участвующих в построении выводов, показано в разделе «Преобразованияграмматик».Элементы теории формальных языков и грамматик / Преобразования грамматиквывода, чтобы имеющиеся в нем терминальные символы проецировались на символы исходной (анализируемой) цепочки.Метод восходящего разбора основан на обратном построении вывода с помощьюсверток от исходной цепочки к цели грамматики S.

При этом дерево растет снизу вверх —от листьев (символов анализируемой цепочки) к корню S. Если грамматика однозначная, топри любом способе построения будет получено одно и то же дерево разбора.Преобразования грамматикВ некоторых случаях КС-грамматика может содержать бесполезные символы, которые не участвуют в порождении цепочек языка и поэтому могут быть удалены из грамматики.Определение: символ x  T  N называется недостижимым в грамматикеG  T, N, P, S , если он не появляется ни в одной сентенциальной форме этой грамматики.Алгоритм удаления недостижимых символовВход: КС-грамматика G  T, N, P, S ,Выход: КС-грамматика G'  T', N', P', S , не содержащая недостижимых символов,для которой L(G)  L(G').Метод:1. V0 : {S }; i : 1.2.

Vi : Vi − 1  {x | x  T  N,A → x  P, A  Vi − 1, ,   ( T  N ) } .Если Vi  Vi − 1, то i : i  1 и переходим к шагу 2, иначе N' : Vi  N ; T' : Vi  T ;P' состоит из правил множества P, содержащих только символы из Vi ;G' : T', N', P', S .Определение:символANназывается*G   T, N, P, S , если множество {  T | A  } пусто.бесплоднымвграмматикеАлгоритм удаления бесплодных символовВход: КС-грамматика G  T, N, P, S .Выход: КС-грамматика G'  T, N', P', S , не содержащая бесплодных символов, длякоторой L(G)  L(G' ).Метод:Строим множества N0, N1, ...1. N0  , i  1.*2. Ni  Ni − 1  {A | A →   P и   (Ni − 1  T) }.Если Ni  Ni − 1, то i : i  1 и переходим к шагу 2, иначе N' : Ni ; P' состоит из правилмножества P, содержащих только символы из N'  T ; G'  T, N', P', S .Определение: КС-грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.19Элементы теории формальных языков и грамматик / Преобразования грамматикАлгоритм приведения грамматики1.

Обнаруживаются и удаляются все бесплодные нетерминалы.2. Обнаруживаются и удаляются все недостижимые символы.Удаление символов сопровождается удалением правил вывода, содержащих эти символы.11)ЗамечаниеЕсли в этом алгоритме приведения поменять местами шаги (1) и (2), то не всегда результатомбудет приведенная грамматика.Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.Некоторые применяемые на практике алгоритмы разбора по КС-грамматикам требуют, чтобы в грамматиках не было правил с пустой правой частью, т.

е. чтобы КС-грамматикабыла неукорочивающей. Для любой КС-грамматики существует эквивалентная неукорачивающая (см. утверждение 2).Ниже приводится алгоритм, позволяющий преобразовать любую КС-грамматику внеукорачивающую. На первом шаге алгоритма строится множество X, состоящее из нетерминалов грамматики, из которых выводима пустая цепочка. Построение этого множестваможно провести по аналогии с шагами алгоритма удаления бесплодных символов:*(1) X1 : { A | (A → )  P }; i :2; (2) Xi : {A | (A → )  P и   Xi − 1 }  Xi − 1. Далее, покаXi  Xi − 1 увеличиваем i на единицу и повторяем (2). Последнее Xi — искомое множество X.Алгоритм устранения правил с пустой правой частьюВход: КС-грамматика G   T, N, P, S .Выход: КС-грамматика G'   T, N', P', S' , G' — неукорачивающая, L(G')  L(G).Метод:1. Построить множество Х  {A  N | A  } ; N′:N .2.

Построить P′, удалив из множества правил P все правила с пустой правой частью.3. Если S  X, то ввести новый начальный символ S′, добавив его в N′, и в множествоправил P′ добавить правило S′ S | . Иначе просто переименовать S в S′.4.ИзменитьP′следующимобразом.Каждоеправиловида*B → 1A12A2...n Ann  1, где Ai  X для i  1,..., n, i  ( (N′  X)  T ) для i  1,..., n  1 (т. е.ni — цепочка, не содержащая символов из X ), заменить 2 правилами, соответствующимивсем возможным комбинациям вхождений Аi между  i:B → 12...nn  1B → 12...nAnn  1...B → 12A2...nAnn  1B → 1A12A2...nAnn  111)20Если начальный символ S — бесполезный в грамматике, то грамматика порождает пустой язык. МножествоP после приведения такой грамматики будет пустым, однако S не следует удалять из N, так как алфавит N неможет быть пустым и на последнем месте в четверке, задающей грамматику, должен стоять нетерминал —начальный символ./ ВведениеЗамечаниеЕсли i   для всех i  1, ..., n  1, то получившееся на данном шаге правило B →  не включать в множество P′.5.

Удалить бесплодные и недостижимые символы и правила, их содержащие. (Кромеизначально имеющихся (в неприведенной грамматике), бесполезные символы могут возникнуть в результате шагов 2–4).ЗамечаниеЕсли применить данный алгоритм к регулярной (автоматной) грамматике, то результатом будетнеукорачивающая регулярная (автоматная) грамматика.Далее везде, если не оговорено иное, будем рассматривать только приведенные грамматики.Элементы теории трансляцииВведениеВ этом разделе будут рассмотрены некоторые алгоритмы и технические приемы, применяемые при построении трансляторов.

Практически во всех трансляторах (и в компиляторах, и в интерпретаторах) в том или ином виде присутствует большая часть перечисленныхниже процессов: лексический анализ, синтаксический анализ, семантический анализ, генерация внутреннего представления программы, оптимизация, генерация объектной программы.В конкретных компиляторах порядок этих процессов может быть несколько иным,какие-то из них могут объединяться в одну фазу, другие могут выполняться в течение всегопроцесса компиляции. В интерпретаторах и при смешанной стратегии трансляции часть этихпроцессов может вообще отсутствовать.В данном разделе мы рассмотрим некоторые методы, используемые для построенияанализаторов (лексического, синтаксического и семантического), язык промежуточногопредставления программы, способ генерации промежуточной программы, ее интерпретацию.Излагаемые алгоритмы и методы иллюстрируются на примере модельного паскалеподобногоязыка (М-языка).

Приводится реализация в виде программы на Си  .Информацию о других методах, алгоритмах и приемах, используемых при созданиитрансляторов, можно найти в [1, 2, 3, 4, 5, 8].21Элементы теории трансляции / Разбор по регулярным грамматикамРазбор по регулярным грамматикамРассмотрим методы и средства, которые обычно используются при построении лексических анализаторов. В основе таких анализаторов лежат регулярные грамматики, поэтомурассмотрим грамматики этого класса более подробно.Соглашение: в дальнейшем, если особо не оговорено, под регулярной грамматикойбудем понимать леволинейную автоматную грамматику G   T, N, P, S  без пустых правыхчастей12).

Напомним, что в такой грамматике каждое правило из Р имеет вид A → Bt либоA → t, где A, B  N, t  T.Соглашение: предположим, что анализируемая цепочка заканчивается специальнымсимволом  — признаком конца цепочки.Для грамматик этого типа существует алгоритм определения того, принадлежит лианализируемая цепочка языку, порождаемому этой грамматикой (алгоритм разбора):(1) первый символ исходной цепочки a1a2...an заменяем нетерминалом A, для которого в грамматике есть правило вывода A → a1 (другими словами, производимсвертку терминала a1 к нетерминалу A)(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал ai исходной цепочкизаменяем нетерминалом B, для которого в грамматике есть правило вывода B →Aai (i  2, 3, .., n);Это эквивалентно построению дерева разбора методом снизу-вверх: на каждом шагеалгоритма строим один из уровней в дереве разбора, поднимаясь от листьев к корню.При работе этого алгоритма возможны следующие ситуации:(1) прочитана вся цепочка; на каждом шаге находилась единственная нужная свертка;на последнем шаге свертка произошла к символу S.

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