Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
Московский государственный университет им. М. В. Ломоносова Факультет вычислительной математики и кибернетики И.А. Волкова, А.А. Вылиток, Т.В. Руденко Формальные грамматики и языки. Элементы теории трансляции Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 УДК 519.682.1 ББК 22.19я73 В67 Печатается по решению Редакционно-издательского совета факультета вычислительной математики и кибернетики МГУ им. М. В. Ломоносова Рецензенты: проф., д.ф.-м.н. Машечкин И. В. доцент, к.ф.-м.н. Терехин А.Н И. А. Волкова, А. А. Вылиток, Т. В. Руденко Формальные грамматики и языки. Элементы теории трансляции: Учебное посо- бие для студентов II курса ( издание третье, переработанное и дополненное). — М.: Издательский отдел факультета ВМиК МГУ им. М.В.Ломоносова (лицензия ИД № 05899 от 24.09.2001), 2009 — 115 с. ISBN 978-5-89407-395-8 ISBN 978-5-317-03085-8 Приводятся основные определения, понятия и алгоритмы теории формальных грам- матик и языков, некоторые методы трансляции, а также наборы задач по рассматрива- емым темам. Излагаемые методы трансляции проиллюстрированы на примере модель- ного языка. В третьем издании все примеры реализации методов и алгоритмов приводятся на языке Си , изменен и расширен набор задач по всем разделам. Для студентов факультета ВМК в поддержку основного лекционного курса «Систе- мы программирования» и для преподавателей, ведущих практические занятия по этому курсу. УДК 519.682.1 ББК 22.19я73 ISBN 978-5-89407-395-8 ISBN 978-5-317-03085-8 © Факультет вычислительной математики и киберне- тики МГУ им. М. В. Ломоносова, 2009 © И. А. Волкова, А. А. Вылиток, Т. В. Руденко, 2009 Элементы теории формальных языков и грамматик / Введение 3 Элементы теории формальных языков и грамматик Введение В этом разделе изложены некоторые аспекты теории формальных языков, существен- ные с точки зрения трансляции. Здесь введены базовые понятия и даны определения, связан- ные с одним из основных механизмов определения языков — грамматиками, приведена наиболее распространенная классификация грамматик (по Хомскому). Особое внимание уделяется контекстно-свободным и регулярным грамматикам. Грамматики этих классов ши- роко используются при трансляции языков программирования. В пособии не приводятся до- казательства корректности алгоритмов и большинства сформулированных фактов, свойств, утверждений – их можно найти в книгах, указанных в списке литературы. Основные понятия и определения Определение: алфавит — это конечное множество символов. Предполагается, что термин «символ» имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении. Определение: цепочкой символов в алфавите V называется любая конечная последо- вательность символов этого алфавита. Определение: цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать греческую букву Предполагается, что сама буква в алфавит V не входит; она лишь помогает обозна- чить пустую последовательность символов. Определение: если и — цепочки, то цепочка (результат приписывания цепочки в конец цепочки ), называется конкатенацией ( или сцеплением ) цепочек и . Конкатенацию можно считать двуместной операцией над цепочками: Например, если ab и cd, то abcd. Для любой цепочки справедливы равенства: Для любых цепочек , , справедливо ( ) ( ) (свойство ассоциатив- ности операции конкатенации). Определение: обращением (или реверсом)цепочки называется цепочка, символы которой записаны в обратном порядке. Обращение цепочки будем обозначать R Например, если abcdef, то R fedcba. Для пустой цепочки: R Определение: n-ой степенью цепочки (будем обозначать n ) называется конкатена- ция n цепочек : n … n Свойства степени: 0 ; n n − 1 n − 1 Элементы теории формальных языков и грамматик / Основные понятия и определения 4 Определение: длина цепочки — это число составляющих ее символов (или длина по- следовательности символов). Например, если 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) ЛОА является недетерминированной машиной: в какой-то момент вычисления (во время работы ЛОА над заданной цепочкой) может возникнуть ситуация, когда есть две или более подходящие для исполнения ко- манды, то есть выбор исполняемой команды не детерминирован. С этого момента возникают две или более копии ЛОА, соответствующие каждому возможному выбору; эти копии продолжают вычисления независи- мо (параллельно). Ответ «да» ЛОА дает, если хотя бы одно из вычислений успешно завершается. Известен алгоритм, позволяющий по любой недетерминированной МТ построить эквивалентную детерминированную Элементы теории формальных языков и грамматик / Основные понятия и определения 5 Автомат с магазинной (внешней) памятью (МП-автомат). В отличие от ЛОА, го- ловка не может изменять входное слово и не может сдвигаться влево; имеется до- полнительная бесконечная память (магазин, или стек), работающая по дисциплине 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) будем называть альтернативой правила вывода из цепочки Пример грамматики: G example {0, 1}, {A, S}, P, S , где P состоит из правил: МТ. Однако до сих пор открыт вопрос, существует ли для любого ЛОА эквивалентный ему детерминиро- ванный ЛОА. Элементы теории формальных языков и грамматик / Основные понятия и определения 6 S → 0A1 0A → 00A1 A → Определение: цепочка ( T N ) * непосредственно выводима из цепочки ( T N ) в грамматике G T, N, P, S (обозначается → G ), если 1 2 , 1 2 , где 1 , 2 , (T N ) * , (T N ) и правило вывода → содержится в P. Индекс G в обо- значении → G обычно опускают, если понятно, о какой грамматике идет речь. Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике G example : 0A1 → 00A11. Здесь цепочка 0A, подчеркнутая двойной чертой, играет роль подцепочки из определения, цепочка 00A1 играет роль подцепочки , 1 , 2 1. Определение: цепочка (T N ) * выводима из цепочки (T N) в грамматике G T, N, P, S (обозначается G ), если существуют цепоч- ки 0 , 1 , ..., n (n 0), такие, что 0 → 1 → ... → n . Последовательность 0 , 1 , ..., n называется выводом длины n. Индекс G в обозначении G опускают, если по- нятно, какая грамматика подразумевается. Например, S 000A111 в грамматике G example (см. пример выше), т.к. существует вы- вод S → 0A1→ 00A11→ 000A111. Длина вывода равна 3. Определение: языком, порождаемым грамматикой G T, N, P, S , называется множество L(G) { T * | S }. Другими словами, L(G) — это все цепочки в алфавите T, которые выводимы из S с помощью правил P. Например, L(G example ) {0 n 1 n | n 0}. Определение: цепочка (T N) * , для которой S , называется сентенциальной формой в грамматике G T, N, P, S Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм. Определение: грамматики G 1 и G 2 называются эквивалентными, если L(G 1 ) L(G 2 ). Пример. Грамматики G 1 {0,1}, {A,S}, P 1 , S и G 2 {0,1}, {S}, P 2 , S с правилами P 1 : S → 0A1 0A → 00A1 A → P 2 : S → 0S1 | 01 эквивалентны, т. к. обе порождают язык L(G 1 ) L(G 2 ) {0 n 1 n | n 0}. Определение: грамматики G 1 и G 2 почти эквивалентны, если L(G 1 ) { } L(G 2 ) { }. Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые, отличаются не более, чем на Например, почти эквивалентны грамматики G 1 {0,1}, {A, S}, P 1 , S и G 2 {0, 1}, {S}, P 2 , S с правилами Элементы теории формальных языков и грамматик / Классификация грамматик и языков по Хомскому 7 P 1 : S → 0A1 0A → 00A1 A → , P 2 : S → 0S1 | так как L(G 1 ) {0 n 1 n | n 0}, а L(G 2 ) {0 n 1 n | n 0}, т. е. L(G 2 ) состоит из всех цепочек язы- ка L(G 1 ) и пустой цепочки, которая в L(G 1 ) не входит. Классификация грамматик и языков по Хомскому Определим с помощью ограничений на вид правил вывода четыре типа грамматик: тип 0, тип 1, тип 2, тип 3. Каждому типу грамматик соответствует свой класс 3) языков. Если язык порождается грамматикой типа i (для i 0, 1, 2, 3), то он является языком типа i. Тип 0 Любая порождающая грамматика является грамматикой типа 0. На вид правил грам- матик этого типа не накладывается никаких дополнительных ограничений. Класс языков ти- па 0 совпадает с классом рекурсивно перечислимых языков. Грамматики с ограничениями на вид правил вывода Тип 1 Грамматика G T, N, P, S называется неукорачивающей, если правая часть каждого правила из P не короче левой части (т. е. для любого правила → P выполняется нера- венство | | | | ). В виде исключения в неукорачивающей грамматике допускается нали- чие правила S → , при условии, что S (начальный символ) не встречается в правых частях правил. Грамматикой типа 1 будем называть неукорачивающую грамматику. Тип 1 в некоторых источниках определяют с помощью так называемых контекстно- зависимых грамматик. Грамматика G T, N, P, S называется контекстно-зависимой (КЗ), если каждое правило из P имеет вид → , где 1 A 2 , 1 2 , A N, (T N ) , 1 , 2 (T N) * . В виде исключения в КЗ-грамматике допускается наличие правила с пустой правой частью S → , при условии, что S (начальный символ) не встречается в правых частях правил. Цепочку 1 называют левым контекстом, цепочку 2 называют правым контек- стом. Язык, порождаемый контекстно-зависимой грамматикой, называется контекстно- зависимым языком. |