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

Московский государственныйуниверситет им. М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиИ.А. Волкова, А.А. Вылиток, Т.В. РуденкоФормальные грамматики и языки.Элементы теории трансляцииУчебное пособие для студентов II курса(издание третье, переработанное и дополненное)Москва2009УДК 519.682.1ББК 22.19я73В67Печатается по решению Редакционно-издательского совета факультетавычислительной математики и кибернетикиМГУ им. М. В. ЛомоносоваРецензенты:проф., д.ф.-м.н. Машечкин И. В.доцент, к.ф.-м.н. Терехин А.Н.И.

А. Волкова, А. А. Вылиток, Т. В. РуденкоФормальные грамматики и языки. Элементы теории трансляции: Учебное пособие для студентов II курса ( издание третье, переработанное и дополненное). — М.:Издательский отдел факультета ВМиК МГУ им. М.В.Ломоносова (лицензия ИД №05899 от 24.09.2001), 2009 — 115 с.ISBN 978-5-89407-395-8ISBN 978-5-317-03085-8Приводятся основные определения, понятия и алгоритмы теории формальных грамматик и языков, некоторые методы трансляции, а также наборы задач по рассматриваемым темам.

Излагаемые методы трансляции проиллюстрированы на примере модельного языка.В третьем издании все примеры реализации методов и алгоритмов приводятся наязыке Си  , изменен и расширен набор задач по всем разделам.Для студентов факультета ВМК в поддержку основного лекционного курса «Системы программирования» и для преподавателей, ведущих практические занятия по этомукурсу.УДК 519.682.1ББК 22.19я73ISBN 978-5-89407-395-8ISBN 978-5-317-03085-8© Факультет вычислительной математики и кибернетики МГУ им.

М. В. Ломоносова, 2009© И. А. Волкова, А. А. Вылиток, Т. В. Руденко, 2009Элементы теории формальных языков и грамматик / ВведениеЭлементы теории формальных языков и грамматикВведениеВ этом разделе изложены некоторые аспекты теории формальных языков, существенные с точки зрения трансляции. Здесь введены базовые понятия и даны определения, связанные с одним из основных механизмов определения языков — грамматиками, приведенанаиболее распространенная классификация грамматик (по Хомскому). Особое вниманиеуделяется контекстно-свободным и регулярным грамматикам. Грамматики этих классов широко используются при трансляции языков программирования.

В пособии не приводятся доказательства корректности алгоритмов и большинства сформулированных фактов, свойств,утверждений – их можно найти в книгах, указанных в списке литературы.Основные понятия и определенияОпределение: алфавит — это конечное множество символов.Предполагается, что термин «символ» имеет достаточно ясный интуитивный смысл ине нуждается в дальнейшем уточнении.Определение: цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.Определение: цепочка, которая не содержит ни одного символа, называется пустойцепочкой.

Для ее обозначения будем использовать греческую букву .Предполагается, что сама буква  в алфавит V не входит; она лишь помогает обозначить пустую последовательность символов.Определение: если  и  — цепочки, то цепочка  (результат приписывания цепочки в конец цепочки ), называется конкатенацией ( или сцеплением ) цепочек  и . Конкатенациюможно считать двуместной операцией над цепочками:   .Например, если   ab и   cd, то   abcd.Для любой цепочки  справедливы равенства:     .Для любых цепочек , ,  справедливо ()  ()   (свойство ассоциативности операции конкатенации).Определение: обращением (или реверсом) цепочки  называется цепочка, символыкоторой записаны в обратном порядке.Обращение цепочки  будем обозначать R.Например, если   abcdef, то R  fedcba.Для пустой цепочки: R  .nОпределение: n-ой степенью цепочки  (будем обозначать  ) называется конкатенаnция n цепочек :   …  .nСвойства степени:nn−10  ;   n−13Элементы теории формальных языков и грамматик / Основные понятия и определенияОпределение: длина цепочки — это число составляющих ее символов (или длина последовательности символов).Например, если   abbcaad, то длина  равна 7.Длину цепочки  будем обозначать |  |.

Длина  равна 0.Определение: через |  |s обозначают число вхождений символа s в цепочку .Например, | babb |a  1, | babb |b  3, | babb |c  0.*Определение: обозначим через V множество, содержащее все цепочки в алфавитеV, включая пустую цепочку .*Например, если V  {0, 1}, то V  {, 0, 1, 00, 11, 01, 10, 000, 001, 011, ... }.Определение: обозначим через V  множество, содержащее все цепочки в алфавите V,исключая пустую цепочку .*Следовательно, V  V  {}.Определение: язык в алфавите V — это подмножество множества всех цепочек в*этом алфавите.

Для любого языка L справедливо L  V .Известны различные способы описания языков [3]. Конечный язык можно описатьпростым перечислением его цепочек. Поскольку формальный язык может быть и бесконечным, требуются механизмы, позволяющие конечным образом представлять бесконечныеязыки. Можно выделить два основных подхода для такого представления: механизм распознавания и механизм порождения (генерации).Механизм распознавания (распознаватель), по сути, является процедурой специального вида, которая по заданной цепочке определяет, принадлежит ли она языку. Если принадлежит, то процедура останавливается с ответом «да», т.

е. допускает цепочку; иначе —останавливается с ответом «нет» или зацикливается. Язык, определяемый распознавателем — это множество всех цепочек, которые он допускает.Примеры распознавателей: Машина Тьюринга (МТ). Язык, который можно задать с помощью МТ, называетсярекурсивно перечислимым. 1) Вместо МТ можно использовать эквивалентные алгоритмические схемы: нормальный алгоритм Маркова (НАМ), машину Поста и др. Линейно ограниченный автомат (ЛОА). Представляет собой МТ, в которой лентане бесконечна, а ограничена длиной входного слова 2 ). Определяет контекстнозависимые языки.1)2)4Термин «рекурсивно перечислимый» происходит из теории рекурсивных функций, являющейся, также какНАМ и МТ, одной из формализаций понятия вычислимости (алгоритма). Смысл остальных названий, характеризующих распознаваемые языки, будет пояснен ниже.ЛОА является недетерминированной машиной: в какой-то момент вычисления (во время работы ЛОА надзаданной цепочкой) может возникнуть ситуация, когда есть две или более подходящие для исполнения команды, то есть выбор исполняемой команды не детерминирован.

С этого момента возникают две или болеекопии ЛОА, соответствующие каждому возможному выбору; эти копии продолжают вычисления независимо (параллельно). Ответ «да» ЛОА дает, если хотя бы одно из вычислений успешно завершается. Известеналгоритм, позволяющий по любой недетерминированной МТ построить эквивалентную детерминированнуюЭлементы теории формальных языков и грамматик / Основные понятия и определения Автомат с магазинной (внешней) памятью (МП-автомат). В отличие от ЛОА, го-ловка не может изменять входное слово и не может сдвигаться влево; имеется дополнительная бесконечная память (магазин, или стек), работающая по дисциплинеLIFO.

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

Следовательно, множество описаний языков счётно, так как множествовсех цепочек в заданном алфавите счётно. Каждый формальный язык в алфавите V является*подмножеством счётного множества V . Из теории множеств известно, что множество всехподмножеств счётного множества является несчётным. Таким образом, мощность множестваформальных языков больше мощности множества конечных описаний и, следовательно, некаждый язык представи м в виде конечного описания.Определение: декартовым произведением A  B множеств A и B называется множество { (a, b) | a  A, b  B }.Определение: порождающая грамматика G — это четверка  T, N, P, S , где T — алфавит терминальных символов ( терминалов ); N — алфавит нетерминальных символов (нетерминалов), T  N  ;* P — конечное подмножество множества (T  N)  (T  N) ; элемент (, ) множе-ства P называется правилом вывода и записывается в виде  → ;  называется левой частью правила,  — правой частью; левая часть любого правила из P обязанасодержать хотя бы один нетерминал; S — начальный символ (цель) грамматики, S  N.Для записи правил вывода с одинаковыми левыми частями → 1  → 2... → nбудем пользоваться сокращенной записью → 1 | 2 |...| n.Каждое i (i  1, 2, ..., n) будем называть альтернативой правила вывода из цепочки .Пример грамматики:Gexample  {0, 1}, {A, S}, P, S ,где P состоит из правил:МТ.