Московский государственный

университет им. М. В. Ломоносова

Факультет вычислительной математики и кибернетики

И.А. Волкова, А.А. Вылиток, Т.В. Руденко

Формальные грамматики и языки.

Элементы теории трансляции

Учебное пособие для студентов II курса

(издание третье, переработанное и дополненное)

Москва

2009

УДК 519.682.1

ББК 22.19я73

В67 Печатается по решению Редакционно-издательского совета факультета вычислительной математики и кибернетики МГУ им. М. В. Ломоносова Рецензенты:

проф., д.ф.-м.н. Машечкин И. В.

доцент, к.ф.-м.н. Терехин А.Н.

И. А. Волкова, А. А. Вылиток, Т. В. Руденко Формальные грамматики и языки. Элементы теории трансляции: Учебное пособие для студентов II курса ( издание третье, переработанное и дополненное). — М.:

Издательский отдел факультета ВМиК МГУ им. М.В.Ломоносова (лицензия ИД № 05899 от 24.09.2001), 2009 — 115 с.

ISBN 978-5-89407-395- ISBN 978-5-317-03085- Приводятся основные определения, понятия и алгоритмы теории формальных грамматик и языков, некоторые методы трансляции, а также наборы задач по рассматриваемым темам. Излагаемые методы трансляции проиллюстрированы на примере модельного языка.

В третьем издании все примеры реализации методов и алгоритмов приводятся на языке Си, изменен и расширен набор задач по всем разделам.

Для студентов факультета ВМК в поддержку основного лекционного курса «Системы программирования» и для преподавателей, ведущих практические занятия по этому курсу.

УДК 519.682. ББК 22.19я ISBN 978-5-89407-395- ISBN 978-5-317-03085- © Факультет вычислительной математики и кибернетики МГУ им. М. В. Ломоносова, © И. А. Волкова, А. А. Вылиток, Т. В. Руденко, Элементы теории формальных языков и грамматик / Введение Элементы теории формальных языков и грамматик Введение В этом разделе изложены некоторые аспекты теории формальных языков, существенные с точки зрения трансляции. Здесь введены базовые понятия и даны определения, связанные с одним из основных механизмов определения языков — грамматиками, приведена наиболее распространенная классификация грамматик (по Хомскому). Особое внимание уделяется контекстно-свободным и регулярным грамматикам. Грамматики этих классов широко используются при трансляции языков программирования. В пособии не приводятся доказательства корректности алгоритмов и большинства сформулированных фактов, свойств, утверждений – их можно найти в книгах, указанных в списке литературы.

Основные понятия и определения Определение: алфавит — это конечное множество символов.

Предполагается, что термин «символ» имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.

Определение: цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.

Определение: цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать греческую букву.

Предполагается, что сама буква в алфавит V не входит; она лишь помогает обозначить пустую последовательность символов.

Определение: если и — цепочки, то цепочка (результат приписывания цепочки в конец цепочки ), называется конкатенацией ( или сцеплением ) цепочек и. Конкатенацию можно считать двуместной операцией над цепочками:.

Например, если ab и cd, то abcd.

Для любой цепочки справедливы равенства:.

Для любых цепочек,, справедливо () () (свойство ассоциативности операции конкатенации).

Определение: обращением (или реверсом) цепочки называется цепочка, символы которой записаны в обратном порядке.

Обращение цепочки будем обозначать R.

Например, если abcdef, то R fedcba.

Для пустой цепочки: R.

n Определение: n-ой степенью цепочки (будем обозначать ) называется конкатенаn ция n цепочек : ….

n n1 n n 0 ; Свойства степени:

Элементы теории формальных языков и грамматик / Основные понятия и определения Определение: длина цепочки — это число составляющих ее символов (или длина последовательности символов).

Например, если abbcaad, то длина равна 7.

Длину цепочки будем обозначать | |. Длина равна 0.

Определение: через | |s обозначают число вхождений символа s в цепочку.

Определение: обозначим через V множество, содержащее все цепочки в алфавите V, включая пустую цепочку.

Например, если V {0, 1}, то V {, 0, 1, 00, 11, 01, 10, 000, 001, 011,... }.

Определение: обозначим через V множество, содержащее все цепочки в алфавите V, исключая пустую цепочку.

Определение: язык в алфавите V — это подмножество множества всех цепочек в этом алфавите. Для любого языка L справедливо L V.

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

Механизм распознавания (распознаватель), по сути, является процедурой специального вида, которая по заданной цепочке определяет, принадлежит ли она языку. Если принадлежит, то процедура останавливается с ответом «да», т. е. допускает цепочку; иначе — останавливается с ответом «нет» или зацикливается. Язык, определяемый распознавателем — это множество всех цепочек, которые он допускает.

Примеры распознавателей:

Машина Тьюринга (МТ). Язык, который можно задать с помощью МТ, называется рекурсивно перечислимым. 1) Вместо МТ можно использовать эквивалентные алгоритмические схемы: нормальный алгоритм Маркова (НАМ), машину Поста и др.

Линейно ограниченный автомат (ЛОА). Представляет собой МТ, в которой лента не бесконечна, а ограничена длиной входного слова 2 ). Определяет контекстнозависимые языки.

Термин «рекурсивно перечислимый» происходит из теории рекурсивных функций, являющейся, также как НАМ и МТ, одной из формализаций понятия вычислимости (алгоритма). Смысл остальных названий, характеризующих распознаваемые языки, будет пояснен ниже.

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

Для записи правил вывода с одинаковыми левыми частями будем пользоваться сокращенной записью Каждое i (i 1, 2,..., n) будем называть альтернативой правила вывода из цепочки.

Пример грамматики:

МТ. Однако до сих пор открыт вопрос, существует ли для любого ЛОА эквивалентный ему детерминированный ЛОА.

Элементы теории формальных языков и грамматик / Основные понятия и определения Определение: цепочка ( T N ) непосредственно выводима из цепочки ( T N ) в грамматике G T, N, P, S (обозначается G ), если 12, 12, где 1, 2, (T N ), (T N ) и правило вывода содержится в P. Индекс G в обозначении G обычно опускают, если понятно, о какой грамматике идет речь.

Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике Gexample :

0A1 00A11. Здесь цепочка 0A, подчеркнутая двойной чертой, играет роль подцепочки из определения, цепочка 00A1 играет роль подцепочки, 1, 2 1.

(T N) в грамматике G T, N, P, S (обозначается G ), если существуют цепочки 0, 1,..., n (n 0), такие, что 0 1... n. Последовательность 0, 1,..., n называется выводом длины n. Индекс G в обозначении G опускают, если понятно, какая грамматика подразумевается.

Например, S 000A111 в грамматике Gexample (см. пример выше), т.к. существует вывод S 0A1 00A11 000A111. Длина вывода равна 3.

Определение: языком, порождаемым грамматикой G T, N, P, S, называется множество L(G) { T * | S }.

Другими словами, L(G) — это все цепочки в алфавите T, которые выводимы из S с помощью правил P. Например, L(Gexample) {0 1 | n 0}.

Определение: цепочка (T N)*, для которой S, называется сентенциальной формой в грамматике G T, N, P, S.

Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм.

Определение: грамматики G1 и G2 называются эквивалентными, если L(G1) L(G2).

Пример. Грамматики G1 {0,1}, {A,S}, P1, S и G2 {0,1}, {S}, P2, S с правилами эквивалентны, т. к. обе порождают язык L(G1) L(G2) {0 1 | n 0}.

L(G1) {} L(G2) {}.

Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые, отличаются не более, чем на.

Например, почти эквивалентны грамматики Элементы теории формальных языков и грамматик / Классификация грамматик и языков по Хомскому так как L(G1) {0 1 | n 0}, а L(G2) {0 1 | n 0}, т. е. L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.

Классификация грамматик и языков по Хомскому Определим с помощью ограничений на вид правил вывода четыре типа грамматик:

тип 0, тип 1, тип 2, тип 3. Каждому типу грамматик соответствует свой класс 3) языков. Если язык порождается грамматикой типа i (для i 0, 1, 2, 3), то он является языком типа i.

Любая порождающая грамматика является грамматикой типа 0. На вид правил грамматик этого типа не накладывается никаких дополнительных ограничений. Класс языков типа 0 совпадает с классом рекурсивно перечислимых языков.

Грамматики с ограничениями на вид правил вывода Грамматика G T, N, P, S называется неукорачивающей, если правая часть каждого правила из P не короче левой части (т. е. для любого правила P выполняется неравенство | | | | ). В виде исключения в неукорачивающей грамматике допускается наличие правила S, при условии, что S (начальный символ) не встречается в правых частях правил.

Грамматикой типа 1 будем называть неукорачивающую грамматику.

Тип 1 в некоторых источниках определяют с помощью так называемых контекстнозависимых грамматик.

Грамматика G T, N, P, S называется контекстно-зависимой (КЗ), если каждое В виде исключения в КЗ-грамматике допускается наличие правила с пустой правой частью S, при условии, что S (начальный символ) не встречается в правых частях правил.

Цепочку 1 называют левым контекстом, цепочку 2 называют правым контекстом. Язык, порождаемый контекстно-зависимой грамматикой, называется контекстнозависимым языком.

Замечание Из определений следует, что если язык, порождаемый контекстно-зависимой или неукорачивающей грамматикой G T, N, P, S, содержит пустую цепочку, то эта цепочка выводится в G за один шаг с помощью правила S. Других выводов для не существует. Если среди правил P нет правила S, то порождаемый контекстно-зависимой или неукорачивающей грамматикой G язык не содержит пустую цепочку.

Классом обычно называют множество, элементы которого сами являются множествами.

Элементы теории формальных языков и грамматик / Классификация грамматик и языков по Хомскому Утверждение 1. Пусть L — формальный язык. Следующие утверждения эквивалентны:

1) существует контекстно-зависимая грамматика G1, такая что L L(G1);

2) существует неукорачивающая грамматика G2, такая что L L(G2).

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

Из утверждения 1 следует, что язык, порождаемый неукорачивающей грамматикой, контекстно-зависим. Таким образом, неукорачивающие и КЗ-грамматики определяют один и тот же класс языков.

Грамматика G T, N, P, S называется контекстно-свободной (КС), если каждое Заметим, что в КС-грамматиках допускаются правила с пустыми правыми частями.

Язык, порождаемый контекстно-свободной грамматикой, называется контекстносвободным языком.

Грамматикой типа 2 будем называть контекстно-свободную грамматику.

КС-грамматика может являться неукорачивающей, т.е. удовлетворять ограничениям неукорачивающей грамматики.

Утверждение 2. Для любой КС-грамматики G существует неукорачивающая КСграмматика G', такая что L(G) L(G').

Согласно утверждению 2, любой контекстно-свободный язык порождается неукорачивающей контекстно-свободной грамматикой. Как следует из определений, такая КСграмматика может содержать не более одного правила с пустой правой частью, причем это правило имеет вид S, где S — начальный символ, и при этом никакое правило из P не содержит S в своей правой части.

В разделе «Преобразования грамматик» будет приведен алгоритм, позволяющий устранить из любой КС-грамматики все правила с пустыми правыми частями (в получившейся грамматике может быть правило S в случае, если пустая цепочка принадлежит языку, при этом начальный символ S не будет входить в правые части правил).

Грамматика G T, N, P, S называется праволинейной, если каждое правило из Р Грамматика G T, N, P, S называется леволинейной, если каждое правило из Р имеет вид A Bw либо A w, где A, B N, w T.

Утверждение 3. Пусть L — формальный язык. Следующие два утверждения эквивалентны:

существует праволинейная грамматика G1, такая что L L(G1);

существует леволинейная грамматика G2, такая что L L(G2).

Элементы теории формальных языков и грамматик / Классификация грамматик и языков по Хомскому Из утверждения 3 следует, что праволинейные и леволинейные грамматики определяют один и тот же класс языков. Такие языки называются регулярными. Право- и леволинейные грамматики также будем называть регулярными.

Регулярная грамматика является грамматикой типа 3.

Автоматной грамматикой называется праволинейная (леволинейная) грамматика, такая, что каждое правило с непустой правой частью имеет вид: A a либо A aB (для леволинейной, соответственно, A a либо A Ba), где A, B N, a T. 4) Автоматная грамматика является более простой формой регулярной грамматики. Существует алгоритм, позволяющий по регулярной (право- или леволинейной) грамматике построить соответствующую автоматную грамматику. Таким образом, любой регулярный язык может быть порожден автоматной грамматикой. Кроме того, существует алгоритм, позволяющий устранить из регулярной (автоматной) грамматики все -правила (кроме S в случае, если пустая цепочка принадлежит языку; при этом S не будет встречаться в правых частях правил) 5). Поэтому справедливо:

Утверждение 4. Для любой регулярной (автоматной) грамматики G существует неукорачивающая регулярная (автоматная) грамматика G, такая что L(G) L(G).

Утверждение 5. Справедливы следующие соотношения:

любая регулярная грамматика является КС-грамматикой;

любая неукорачивающая КС-грамматика является КЗ-грамматикой;

любая неукорачивающая грамматика является грамматикой типа 0.

Утверждение 5 следует непосредственно из определений.

Рассматривая только неукорачивающие регулярные и неукорачивающие КСграмматики, что согласно утверждениям 2 и 4 не ограничивает классы соответствующих языков, получаем следующую иерархию классов грамматик:

неукорачивающие Регулярные неукорачивающие КС КЗ Тип (Запись A B означает, что A является собственным подклассом класса B.) Вместо класса КЗ-грамматик в данной иерархии можно указать более широкий класс неукорачивающих грамматик, которые, как известно, порождают те же языки, что и КЗграмматики.

В разделе «Разбор по регулярным грамматикам» будет рассмотрен алгоритм построения по конечному автомату эквивалентной грамматики. Построенная алгоритмом грамматика будет автоматной.

Алгоритм устранения правил с пустой правой частью для КС-грамматик, приведенный в разделе «Преобразования грамматик», пригоден также и для устранения -правил из регулярных и автоматных грамматик.

Элементы теории формальных языков и грамматик / Классификация грамматик и языков по Хомскому Утверждение 6. Справедливы следующие соотношения:

каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными, например:

каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками, например:

каждый КЗ-язык является языком типа 0 (т. е. рекурсивно перечислимым языком), но существуют языки типа 0, которые не являются КЗ-языками, например: язык, состоящий из записей самоприменимых алгоритмов Маркова в некотором алфавите. 6) Из утверждения 6 следует иерархия классов языков:

На рис. 1 иерархия Хомского для классов языков изображена в виде диаграммы Венна. Классы вкладываются друг в друга. Самый широкий класс языков (типа 0) содержит в себе все остальные классы.

Утверждение 7. Проблема «Можно ли язык, описанный грамматикой типа k (k 0, 1, 2), описать грамматикой типа k 1?» является алгоритмически неразрешимой.

Заметим, что для k 1, 2, 3 язык типа k является также и языком типа k 1 (согласно иерархии на рис.1, класс языков типа k является подклассом класса языков типа k 1). Несмотря на то, что нет алгоритма, позволяющего по заданному описанию языка L (например, по грамматике), определить максимальное k, такое что L является языком типа k, при ответе на вопрос «Какого типа заданный язык L?» в примерах и задачах будем указывать, если не оговорено иное, максимально возможное k (0, 1, 2, или 3) для заданного языка L.

Рассмотрим, например, язык La,b {a, b}, состоящий из двух однобуквенных цепочек.

Какого типа язык La,b? Ответ: типа 3, так как, во-первых, он порождается грамматикой Понятие записи нормального алгоритма Маркова определяется в [10].

Элементы теории формальных языков и грамматик / Примеры грамматик и языков S a | b типа 3; во-вторых, не существует грамматики типа k 3, которая бы порождала La,b (т. е. 3 — это максимально возможное k, такое, что La,b является языком типа k).

Отметим, что согласно иерархии языков, следующие утверждения также справедливы: «La,b является языком типа 2», «La,b является языком типа 1», «La,b является языком типа 0». Но, с учетом вышесказанного, эти утверждения не считаются исчерпывающими ответами на вопрос «Какого типа язык La,b?».

Соглашение: в примерах и задачах для краткости вместо полной четверки G T, N, P, S будем иногда выписывать только так называемую «схему» грамматики — правила вывода Р, считая, что большие латинские буквы обозначают нетерминальные символы, начальный символ (цель) грамматики обязательно стоит в левой части первого правила, — пустая цепочка, все остальные символы — терминальные.

1) Правила грамматики G1 удовлетворяют ограничениям на правила КС-грамматик, но не удовлетворяют ограничениям регулярных грамматик, т. е. это грамматика типа 2, и поэтому L(G1) является языком типа 2 (следовательно, это язык и типа 1, и типа 0). Заметим, что L(G1) {00 0 1 | n 0} {0 1 | n 0} и этот язык является также языком типа 3, поскольку описывается следующей регулярной грамматикой:

Итак, максимальное k, для которого L(G1) является языком типа k, равно 3.

2) По виду правил G2 является грамматикой типа 2 и не является грамматикой типа 3.

Следовательно, L(G2) является языком типа 2. Является ли L(G2) языком типа 3? Ответ на этот вопрос отрицательный, так как не существует регулярной грамматики (т. е. грамматики типа 3), порождающей язык L(G2) {a b | n 0}7).

Итак, максимальное k, для которого L(G2) является языком типа k, равно 2.

Примеры грамматик и языков Примеры грамматик и языков, иллюстрирующие классы иерархии Хомского, приведем в порядке, обратном классификации, т. е. будем идти от простого к сложному.

Нерегулярность языка {anbn | n 0} будет доказана в разделе «Разбор по регулярным грамматикам».

Элементы теории формальных языков и грамматик / Примеры грамматик и языков 1) Грамматика S aS | a является праволинейной (неукорачивающей) грамматикой.

Она порождает регулярный язык {a | n 0}. Этот язык может быть порожден и леволинейной грамматикой: S Sa | a. Заметим, что обе эти грамматики являются автоматными.

2) Грамматика S aS | является праволинейной и порождает регулярный язык {a | n 0}. Для любого регулярного языка существует неукорачивающая регулярная грамматика (см. утверждение 4). Построим неукорачивающую регулярную грамматику для данного языка:

В самом деле, правило с пустой правой частью может применяться только один раз и только на первом шаге вывода; остальные правила таковы, что их правая часть не короче левой, т. е. грамматика неукорачивающая.

леволинейная; она порождает регулярный язык, состоящий из всех непустых цепочек в алфавите {a, b}, заканчивающихся символом (маркер конца) и не содержащих подцепочку aa. То есть в цепочках этого языка символ a не может встречаться два раза подряд, хотя бы один символ b обязательно присутствует между любыми двумя a. С помощью теоретикомножественной формулы данный язык описывается так: { | {a, b}, aa }.

Контекстно-свободные является контекстно-свободной (неукорачивающей) и порождает КС-язык {(ac) (cb) | n 0}, который, как и встречавшийся нам ранее язык {a b | n 0}, не является регулярным, т. е.

не может быть порожден ни одной регулярной грамматикой.

порождает КС-язык {xx R, x{a, b} }. Данный язык не является регулярным. Грамматика не удовлетворяет определению неукорачивающей, но для нее существует эквивалентная неукорачивающая грамматика (см. утверждение 2). Приведем такую грамматику:

Элементы теории формальных языков и грамматик / Примеры грамматик и языков Неукорачивающие и контекстно-зависимые неукорачивающая и порождает язык {a nbnc n | n 0}, который является языком типа 1, но не является языком типа 2 (этот факт доказывается с помощью «леммы о разрастании цепочек КС-языка» [3, т.1]).

Правило CB BC не удовлетворяет определению КЗ-грамматики. Однако, заменив это правило тремя новыми CB СD, CD BD, BD BC (добавляем новый символ D в множество нетерминалов N ), мы получим эквивалентную серию контекстно-зависимых правил, которые меняют местами символы C и B. Таким образом, получаем эквивалентную КЗграмматику:

Без ограничений на вид правил (тип 0) второе правило не удовлетворяет ограничениям неукорачивающей грамматики. Существует бесконечно много выводов в данной грамматике, однако порождаемый язык конечен и состоит из единственной цепочки: {}.

Следующая грамматика также не является неукорачивающей и порождает пустой язык, так как ни одна терминальная цепочка не выводится из S (для обозначения пустого языка используется — знак пустого множества):

Заметим, что языки L {} и L (пустой язык) могут быть описаны грамматиками типа 3. Кроме того, отметим, что L L, так как L не содержит цепочек вообще, а L — язык, состоящий из одной цепочки (пустая цепочка по определению равноправна с остальными цепочками в алфавите).

8) Содержательные примеры грамматик, порождающих языки, не принадлежащие классу контекстно-зависимых (тип 1), не приводятся из-за их громоздкости. Ниже обсуждается лишь возможность построения такой грамматики для одного языка типа 0.

Как известно, языки типа 0 (рекурсивно перечислимые множества) можно задавать с помощью распознавателей: НАМ или МТ. Существуют алгоритмы, позволяющие по НАМ Элементы теории формальных языков и грамматик / Примеры грамматик и языков или МТ построить эквивалентную грамматику типа 0, задающую тот же язык, что и исходный распознаватель.

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

Следовательно, Lself можно описать с помощью грамматики типа 0.

Покажем, что не существует грамматики типа 1, которая порождает язык Lself. Известно, что проблема распознавания для грамматик типа 1 алгоритмически разрешима. То есть существует алгоритм, который определяет, принадлежит ли заданная цепочка языку, порождаемому грамматикой. Предположим, существует грамматика типа 1, порождающая язык Lself. Тогда алгоритм распознавания дает ответ для любой цепочки, является ли она записью самоприменимого алгоритма или нет. Имеем противоречие с известным фактом об алгоритмической неразрешимости проблемы самоприменимости. Следовательно, грамматики типа 1, порождающей язык Lself, не существует.

Замечание о связи между языком и грамматикой В приведенных ранее примерах мы утверждали, что заданная грамматика порождает определенный язык исходя из нестрогих рассуждений, интуитивно, по совокупности правил вывода. Вообще говоря, следует доказывать, что заданная грамматика порождает нужный язык. Для этого требуется доказать, что в данной грамматике:

I ) выводится любая цепочка, принадлежащая языку, II ) не выводятся никакие другие цепочки.

Доказать, что грамматика G с правилами вывода:

порождает язык L(G) { a b c | n 1}.

(В скобках слева приведена нумерация для удобства ссылок на правила).

I ) Приведем схемы порождения цепочек вида a b c, n 1 c указанием номера правила на каждом шаге вывода.

(6) a b c.

Элементы теории формальных языков и грамматик / Разбор цепочек 1. Новые символы а, [b | B] и C появляются только при применении правил (1), (2) в равных количествах, т. е. в любой сентенциальной форме всегда 2. Символ В заменяется только на b, а С — только на с.

3. Появившись, терминальные символы уже не меняют своей позиции, т. е. в любой сентенциальной форме символ а всегда левее любых [b | B] и [c | C].

Первый символ b появляется только после применения правила (2).

Символ В заменяется на b, только если слева от В стоит b, т. е. второй символ b появляется только непосредственно справа от первого b, третий b — непосредственно справа от второго b и т. д. Правило (5) применяется только после того, как исчерпана возможность применять (3), иначе Из пунктов 3, 4 и 5 следует, что любой символ b расположен всегда левее любого [c | C]. Следовательно, в любой выводимой цепочке равное количество а, b и с; а всегда стоит левее, чем b и с, b всегда стоит левее, чем с, т. е. любая цепочка имеет вид a b c, что и требовалось доказать.

Цепочка в алфавите T принадлежит языку, порождаемому грамматикой T, N, P, S, только в том случае, если существует ее вывод из начального символа S этой грамматики.

Процесс построения такого вывода (а, следовательно, и определения принадлежности цепочки языку) называется разбором 8). Построение вывода можно осуществлять и в обратном порядке: в исходной цепочке ищем вхождение правой части некоторого правила и заменяем его на левую часть (это называется сверткой), в результате исходная цепочка «сворачивается» к некоторой сентенциальной форме, затем идет следующая свертка и т. д., пока не придем к цели грамматики — S. Процесс разбора называют также анализом.

С практической точки зрения наибольший интерес представляет разбор по контекстно-свободным грамматикам. Их порождающей мощности достаточно для описания большей части синтаксической структуры языков программирования, для различных подклассов КС-грамматик имеются хорошо разработанные практически приемлемые способы решения задачи разбора.

Рассмотрим основные понятия и определения, связанные с разбором по КСграмматике.

G T, N, P, S, называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.

Разбором также называют и результат этого процесса, т. е. вывод цепочки, представленный (зафиксированный) каким-нибудь способом.

Элементы теории формальных языков и грамматик / Разбор цепочек G T, N, P, S, называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.

В грамматике для одной и той же цепочки может быть несколько выводов, эквивалентных в том смысле, что в них в одних и тех же местах применяются одни и те же правила вывода, но в различном порядке.

Например, для цепочки a b a в грамматике:

Здесь (2) — левосторонний вывод, (3) — правосторонний, а (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в указанном выше смысле.

Для КС-грамматик можно ввести удобное графическое представление вывода, называемое деревом вывода, причем для всех эквивалентных выводов деревья вывода совпадают.

Определение: ориентированное упорядоченное9) дерево называется деревом вывода (или деревом разбора) в КС-грамматике G T, N, P, S, если выполнены следующие условия:

(1) каждая вершина дерева помечена символом из множества N T {}, при этом корень дерева помечен символом S; листья — символами из T {};

(2) если вершина дерева помечена символом A, а ее непосредственные потомки — символами a1, a2,..., an, где каждое ai T N, то A a1a2...an — правило вывода (3) если вершина дерева помечена символом A, а ее непосредственный потомок помечен символом, то этот потомок единственный и A — правило вывода в На рисунке 2 изображен пример дерева для цепочки a b a в грамматике Gexpr Определение: КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка L(G), для которой может быть построено два или более различных деревьев вывода.

В противном случае грамматика называется однозначной.

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

Определение: язык, порождаемый грамматикой, называется неоднозначным, если он не может быть порожден никакой однозначной грамматикой.

Пример неоднозначной грамматики:

где P {S if b then S else S | if b then S | a}.

В этой грамматике для цепочки if b then if b then a else a можно построить два различных дерева вывода, изображенных на рисунке 3 (а, б).

Однако это не означает, что язык L(Gif-then) обязательно неоднозначный. Обнаруженная в Gif-then неоднозначность — это свойство грамматики, а не языка. Для некоторых неоднозначных грамматик существуют эквивалентные им однозначные грамматики.

Если грамматика используется для определения языка программирования, то она должна быть однозначной.

В приведенном выше примере разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и подправить грамматику Gif-then, то неоднозначность будет устранена:

Элементы теории формальных языков и грамматик / Разбор цепочек Утверждение 8. Проблема, порождает ли данная КС-грамматика однозначный язык (т.е. существует ли эквивалентная ей однозначная грамматика), является алгоритмически неразрешимой.

Более того, справедливо следующее.

Утверждение 9. Проблема, является ли данная КС-грамматика однозначной, алгоритмически неразрешима.

Поиск ответа на вопрос, неоднозначна или однозначна заданная грамматика — это искусство поиска цепочки с двумя различными деревьями вывода, или доказательство того, что таких цепочек не существует. Универсального способа решения этой задачи, к сожалению, нет.

Однако можно указать некоторые виды правил вывода, которые приводят к неоднозначности (при условии, что эти правила не являются тупиковыми10), т. е. действительно используются на каком-нибудь шаге вывода терминальной цепочки из начального символа):

(3) A A | A | (здесь хотя бы одна из цепочек или не пуста) Отметим, что это всего лишь некоторые шаблоны. Все ситуации, приводящие к неоднозначности, перечислить невозможно в силу утверждения 9.

Пример неоднозначного КС-языка:

Интуитивно неоднозначность L объясняется тем, что цепочки с i j должны порождаться группой правил вывода, отличных от правил, порождающих цепочки с j k. Но тогда, по крайней мере, некоторые из цепочек с i j k будут порождаться обеими группами правил и, следовательно, будут иметь по два разных дерева вывода. Доказательство того, что КС-язык L неоднозначный, приведено в [3, т.1, стр. 235–236].

Одна из грамматик, порождающих L, такова:

Она неоднозначна; однозначных грамматик для L не существует.

Дерево вывода можно строить нисходящим либо восходящим способом.

При нисходящем разборе дерево вывода формируется от корня к листьям; на каждом шаге для вершины, помеченной нетерминальным символом, пытаются найти такое правило 10) Как избавиться от правил, не участвующих в построении выводов, показано в разделе «Преобразования грамматик».

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

Метод восходящего разбора основан на обратном построении вывода с помощью сверток от исходной цепочки к цели грамматики S. При этом дерево растет снизу вверх — от листьев (символов анализируемой цепочки) к корню S. Если грамматика однозначная, то при любом способе построения будет получено одно и то же дерево разбора.

Преобразования грамматик В некоторых случаях КС-грамматика может содержать бесполезные символы, которые не участвуют в порождении цепочек языка и поэтому могут быть удалены из грамматики.

Определение: символ x T N называется недостижимым в грамматике G T, N, P, S, если он не появляется ни в одной сентенциальной форме этой грамматики.

Алгоритм удаления недостижимых символов Выход: КС-грамматика G' T', N', P', S, не содержащая недостижимых символов, P' состоит из правил множества P, содержащих только символы из Vi ;

G T, N, P, S, если множество { T | A } пусто.

Алгоритм удаления бесплодных символов Выход: КС-грамматика G' T, N', P', S, не содержащая бесплодных символов, для Строим множества N0, N1,...

Если Ni Ni 1, то i : i 1 и переходим к шагу 2, иначе N' : Ni ; P' состоит из правил множества P, содержащих только символы из N' T ; G' T, N', P', S.

Определение: КС-грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.

Элементы теории формальных языков и грамматик / Преобразования грамматик Алгоритм приведения грамматики 1. Обнаруживаются и удаляются все бесплодные нетерминалы.

2. Обнаруживаются и удаляются все недостижимые символы.

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

Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.

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

Ниже приводится алгоритм, позволяющий преобразовать любую КС-грамматику в неукорачивающую. На первом шаге алгоритма строится множество X, состоящее из нетерминалов грамматики, из которых выводима пустая цепочка. Построение этого множества можно провести по аналогии с шагами алгоритма удаления бесплодных символов:

Xi Xi 1 увеличиваем i на единицу и повторяем (2). Последнее Xi — искомое множество X.

Алгоритм устранения правил с пустой правой частью Вход: КС-грамматика G T, N, P, S.

Выход: КС-грамматика G' T, N', P', S', G' — неукорачивающая, L(G') L(G).

2. Построить P, удалив из множества правил P все правила с пустой правой частью.

3. Если S X, то ввести новый начальный символ S, добавив его в N, и в множество правил P добавить правило S S |. Иначе просто переименовать S в S.

B 1A12A2...n Ann 1, где Ai X для i 1,..., n, i ( (N X) T ) для i 1,..., n 1 (т. е.

i — цепочка, не содержащая символов из X ), заменить 2 правилами, соответствующими всем возможным комбинациям вхождений Аi между i:

11) Если начальный символ S — бесполезный в грамматике, то грамматика порождает пустой язык. Множество P после приведения такой грамматики будет пустым, однако S не следует удалять из N, так как алфавит N не может быть пустым и на последнем месте в четверке, задающей грамматику, должен стоять нетерминал — начальный символ.

/ Введение Замечание Если i для всех i 1,..., n 1, то получившееся на данном шаге правило B не включать в множество P.

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

Замечание Если применить данный алгоритм к регулярной (автоматной) грамматике, то результатом будет неукорачивающая регулярная (автоматная) грамматика.

Далее везде, если не оговорено иное, будем рассматривать только приведенные грамматики.

В этом разделе будут рассмотрены некоторые алгоритмы и технические приемы, применяемые при построении трансляторов. Практически во всех трансляторах (и в компиляторах, и в интерпретаторах) в том или ином виде присутствует большая часть перечисленных ниже процессов:

лексический анализ, синтаксический анализ, семантический анализ, генерация внутреннего представления программы, генерация объектной программы.

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

В данном разделе мы рассмотрим некоторые методы, используемые для построения анализаторов (лексического, синтаксического и семантического), язык промежуточного представления программы, способ генерации промежуточной программы, ее интерпретацию.

Излагаемые алгоритмы и методы иллюстрируются на примере модельного паскалеподобного языка (М-языка). Приводится реализация в виде программы на Си.

Информацию о других методах, алгоритмах и приемах, используемых при создании трансляторов, можно найти в [1, 2, 3, 4, 5, 8].

Элементы теории трансляции / Разбор по регулярным грамматикам Разбор по регулярным грамматикам Рассмотрим методы и средства, которые обычно используются при построении лексических анализаторов. В основе таких анализаторов лежат регулярные грамматики, поэтому рассмотрим грамматики этого класса более подробно.

Соглашение: в дальнейшем, если особо не оговорено, под регулярной грамматикой будем понимать леволинейную автоматную грамматику G T, N, P, S без пустых правых частей12). Напомним, что в такой грамматике каждое правило из Р имеет вид A Bt либо Соглашение: предположим, что анализируемая цепочка заканчивается специальным символом — признаком конца цепочки.

Для грамматик этого типа существует алгоритм определения того, принадлежит ли анализируемая цепочка языку, порождаемому этой грамматикой (алгоритм разбора):

(1) первый символ исходной цепочки a1a2...an заменяем нетерминалом A, для которого в грамматике есть правило вывода A a1 (другими словами, производим свертку терминала a1 к нетерминалу A) (2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал ai исходной цепочки заменяем нетерминалом B, для которого в грамматике есть правило вывода B Это эквивалентно построению дерева разбора методом снизу-вверх: на каждом шаге алгоритма строим один из уровней в дереве разбора, поднимаясь от листьев к корню.

При работе этого алгоритма возможны следующие ситуации:

(1) прочитана вся цепочка; на каждом шаге находилась единственная нужная свертка;

на последнем шаге свертка произошла к символу S. Это означает, что исходная (2) прочитана вся цепочка; на каждом шаге находилась единственная нужная свертка;

на последнем шаге свертка произошла к символу, отличному от S. Это означает, что исходная цепочка a1a2...an L(G).

(3) на некотором шаге не нашлось нужной свертки, т. е. для полученного на предыдущем шаге нетерминала A и расположенного непосредственно справа от него очередного терминала ai исходной цепочки не нашлось нетерминала B, для которого в грамматике было бы правило вывода B Aai. Это означает, что исходная (4) на некотором шаге работы алгоритма оказалось, что есть более одной подходящей свертки, т. е. в грамматике разные нетерминалы имеют правила вывода с одинаковыми правыми частями, и поэтому непонятно, к какому из них производить свертку. Это говорит о недетерминированности разбора. Анализ этой ситуации Допустим, что разбор на каждом шаге детерминированный.

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

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

Значение каждого элемента таблицы, начиная со второй строки — это нетерминальный символ, к которому можно свернуть пару «нетерминал-терминал», которыми помечены соответствующие строка и столбец.

Например, для леволинейной грамматики Gleft {a, b, }, {S, A, B, C}, P, S, где такая таблица будет выглядеть следующим образом:

Знак «—» ставится в том случае, если соответствующей свертки нет.

Но чаще информацию о возможных свертках представляют в виде диаграммы состояний (ДС) — неупорядоченного ориентированного помеченного графа, который строится следующим образом:

(1) строим вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала — одну вершину), и еще одну вершину, помеченную символом, отличным от нетерминальных, например, H. Эти вершины будем называть состояниями. H — начальное состояние.

(2) соединяем эти состояния дугами по следующим правилам:

а) для каждого правила грамматики вида W t соединяем дугой состояния H б) для каждого правила W Vt соединяем дугой состояния V и W (от V к W) и Диаграмма состояний для грамматики Gleft (см. пример выше) изображена на рис.4:

Элементы теории трансляции / Разбор по регулярным грамматикам Алгоритм разбора по диаграмме состояний (1) объявляем текущим начальное состояние H;

(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: считываем очередной символ исходной цепочки и переходим из текущего состояния в другое состояние по дуге, помеченной этим символом. Состояние, в которое мы при этом попадаем, становится текущим.

При работе этого алгоритма возможны следующие ситуации (аналогичные ситуациям, которые возникают при разборе непосредственно по регулярной грамматике):

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

в результате последнего шага оказались в состоянии, отличном от S. Это означает, что исходная цепочка не принадлежит L(G).

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

Анализ этой ситуации будет приведен ниже.

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

Определение: детерминированный конечный автомат (ДКА) — это пятерка K, T,, H, S, где K — конечное множество состояний;

T — конечное множество допустимых входных символов;

— отображение множества K T в K, определяющее поведение автомата;

S K — заключительное состояние (либо множество заключительных состояний S K).

Замечания к определению ДКА:

(1) Заключительных состояний в ДКА может быть более одного, однако для любого регулярного языка, все цепочки которого заканчиваются маркером конца (), суЭлементы теории трансляции / Разбор по регулярным грамматикам ществует ДКА с единственным заключительным состоянием. Заметим также, что ДКА, построенный по регулярной грамматике рассмотренным выше способом, всегда будет иметь единственное заключительное состояние S. 13) (2) Отображение : K T K называют функцией переходов ДКА. (A, t) B означает, что из состояния A по входному символу t происходит переход в состояние B.

Иногда определяют лишь на подмножестве K T (частичная функция). Если значение (A, t) не определено, то автомат не может дальше продолжать работу и останавливается в состоянии «ошибка».

Определение: ДКА допускает цепочку a1a2...an, если (H, a1) A1; (A1, a2) A2 ; … начальное состояние, S — заключительное состояние.

Определение: множество цепочек, допускаемых ДКА, составляет определяемый им язык.

Для более удобной работы с диаграммами состояний введем несколько соглашений:

если из одного состояния в другое выходит несколько дуг, помеченных разными символами, то будем изображать одну дугу, помечая ее списком из всех таких символов;

непомеченная дуга будет соответствовать переходу при любом символе, кроме тех, которыми помечены другие дуги, выходящие из этого состояния;

введем состояние ошибки (ER); переход в это состояние будет означать, что исходная цепочка языку не принадлежит.

По диаграмме состояний легко написать анализатор для регулярной грамматики.

Например, для грамматики Gleft {a, b, }, {S, A, B, C}, P, S с правилами анализатор будет таким:

13) Нетрудно указать и обратный способ — построения грамматики по диаграмме состояний автомата, — причем получившаяся грамматика будет автоматной. Каждой дуге из начального состояния Н в состояние W, помеченной символом t, будет соответствовать правило W t; каждой дуге из состояния V в состояние W, помеченной символом t, будет соответствовать правило W Vt. Заключительное состояние S объявляется начальным символом грамматики.

Если в вершину Н входит некоторая дуга (это возможно в произвольно построенном автомате), то алгоритм модифицируется так: каждой дуге из начального состояния Н в состояние W, помеченной символом t, будет соответствовать правило W Ht, и в грамматику добавляется правило Н; затем к построенной грамматике применяется алгоритм удаления правил с пустыми правыми частями.

Элементы теории трансляции / Разбор по регулярным грамматикам Элементы теории трансляции / Разбор по регулярным грамматикам Рассмотрим работу анализатора для грамматики G на примере цепочки abba. При анализе данной цепочки получим следующую последовательность переходов в ДС:

Вспомним, что каждый переход в ДС означает свертку сентенциальной формы путем замены в ней пары «нетерминал-терминал» Nt на нетерминал L, где L Nt правило вывода в грамматике. Такое применение правила в обратную сторону будем записывать с помощью обратной стрелки Nt L (обращение правила вывода). Тогда получим следующую последовательность сверток, соответствующую переходам в ДС:

Эта последовательность не что иное, как обращение (правого) вывода цепочки abba в грамматике G. Она соответствует построению дерева снизу вверх (см. рис. 5).

Разбор по праволинейной грамматике По диаграмме состояний (см. рис. 4) построим праволинейную автоматную грамматику Gright следующим способом:

нетерминалами будут состояния из ДС (кроме S );

каждой дуге из состояния V в заключительное состояние S (помеченной признаком конца ) будет соответствовать правило V ;

каждой дуге из состояния V в состояние W, помеченной символом t, будет соответствовать правило V tW;

начальное состояние H объявляется начальным символом грамматики.

14) Нетрудно описать и обратный алгоритм для праволинейной автоматной грамматики, если все ее правила с односимвольной правой частью имеют вид V. Состояниями ДС будут нетерминалы грамматики и еще одно специальное заключительное состояние S, в которое для каждого правила вида V проводится дуга Элементы теории трансляции / Разбор по регулярным грамматикам Заметим, что L(Gright) L(Gleft), так как грамматики Gright и Gleft соответствуют одной и той же ДС (см. рис. 4).

Рассмотрим разбор цепочки abba по праволинейной грамматике Gright. Последовательность переходов в ДС для этой цепочки такова:

Каждый переход, за исключением последнего, означает теперь замену в сентенциальной форме нетерминала на пару «терминал-нетерминал» с помощью некоторого правила вывода грамматики Gright. В результате получаем следующий (левый) вывод, который соответствует последовательности переходов в ДС:

Такой вывод отражает построение дерева вывода сверху вниз (см. рис. 6).

О недетерминированном разборе При анализе по леволинейной грамматике может оказаться, что несколько нетерминалов имеют одинаковые правые части, и поэтому неясно, к какому из них делать свертку (см.

ситуацию 4 в описании алгоритма). При анализе по праволинейной грамматике может окаиз V, помеченная признаком конца. Для каждого правила вида V t W проводится дуга из V в W, помеченная символом t. Начальным состоянием в ДС будет начальный символ H.

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

Например, для грамматики G {a, b, }, {S, A, B}, P, S, где разбор будет недетерминированным (т.к. у нетерминалов A и B есть одинаковые правые части — Bb).

Такой грамматике будет соответствовать недетерминированный конечный автомат.

Определение: недетерминированный конечный автомат (НКА) — это пятерка K, T,, H, S, где K — конечное множество состояний;

T — конечное множество допустимых входных символов;

— отображение множества K T в множество подмножеств K;

H K — конечное множество начальных состояний;

S K — конечное множество заключительных состояний.

(A, t) {B1, B2,..., Bn} означает, что из состояния A по входному символу t можно осуществить переход в любое из состояний Bi, i 1, 2,..., n. Также как и ДКА, любой НКА можно представить в виде таблицы (в одной ячейке такой таблицы можно указывать сразу несколько состояний, в которые возможен переход из заданного состояния по текущему символу) или в виде диаграммы состояний (ДС). В ДС каждому состоянию из множества K соответствует вершина; из вершины A в вершину B ведет дуга, помеченная символом t, если B (A, t). (В НКА из одной вершины могут исходить несколько дуг с одинаковой пометкой). Успешный путь — это путь из начальной вершины в заключительную; пометка пути — это последовательность пометок его дуг. Язык, допускаемый НКА, — это множество пометок всех успешных путей.

Если начальное состояние автомата (НКА или ДКА) одновременно является и заключительным, то автомат допускает пустую цепочку.

Замечание Автомат, построенный по регулярной грамматике без пустых правых частей, не допускает.

Для построения разбора по регулярной грамматике в недетерминированном случае можно предложить алгоритм, который будет перебирать все возможные варианты сверток (переходов) один за другим; если цепочка принадлежит языку, то будет найден успешный путь; если каждый из просмотренных вариантов завершится неудачей, то цепочка языку не принадлежит. Однако такой алгоритм практически неприемлем, поскольку при переборе вариантов мы, скорее всего, снова окажемся перед проблемой выбора и, следовательно, будем иметь «дерево отложенных вариантов» и экспоненциальный рост сложности разбора.

Один из наиболее важных результатов теории конечных автоматов состоит в том, что класс языков, определяемых недетерминированными конечными автоматами, совпадает с классом языков, определяемых детерминированными конечными автоматами.

Элементы теории трансляции / Разбор по регулярным грамматикам Утверждение 10. Пусть L — формальный язык. Следующие утверждения эквивалентны:

(1) L порождается регулярной грамматикой;

(2) L допускается ДКА;

(3) L допускается НКА.

Эквивалентность пунктов (1) и (2) следует из рассмотренных выше алгоритмов построения конечного автомата по регулярной грамматике и обратно — грамматики по автомату. Очевидно, что из (2) следует (3): достаточно записать вместо каждого перехода ДКА (C, a) b эквивалентный ему переход в НКА (C, a) {b}, начальное состояние ДКА поместить в множество начальных состояний НКА, а заключительное состояние ДКА поместить в множество заключительных состояний НКА. Приводимый ниже алгоритм построения ДКА, эквивалентного НКА, обосновывает то, что из (3) следует (2).

Алгоритм построения ДКА по НКА Выход: ДКА M1 K1, T, 1, H1, S1, допускающий тот же язык, что и автомат М :

L(M) L(M1).

1. Элементами K1, т. е. состояниями в ДКА, будут некоторые подмножества множества состояний НКА. Заметим, что в силу конечности множества K, множество K1 также коs нечно и имеет не более 2 элементов, где s — мощность K.

Подмножество {А1, A2, …, An} состояний из К будем для краткости записывать как A1A2...An. Множество K1 и переходы, определяющие функцию 1, будем строить, начиная с состояния H1: H1 A1A2...An, где А1, A2, …, An H. Другими словами, все начальные состояния НКА M объединяются в одно состояние H1 для ДКА M1. Добавляем в множество K1 построенное начальное состояние H1 и пока считаем его нерассмотренным (на втором шаге оно рассматривается и строятся остальные состояния множества K1, а также переходы 1.) 2. Пока в K1 есть нерассмотренный элемент A1A2...Am, «рассматриваем» его и выполняем для каждого t T следующие действия:

Полагаем 1 ( A1A2...Am, t ) B1B2...Bk, где для 1 j k в НКА (Ai, t) Bj для некоторых 1 i m. Другими словами, B1B2...Bk — это множество всех состояний в НКА, куда можно перейти по символу t из множества состояний A1A2...Am. В ДКА M1 получается детерминированный переход по символу t из состояния A1A2...Am в состояние B1B2...Bk. (Если k 0, то полагаем 1 ( A1A2...Am, t ) ).

Добавляем в K1 новое состояние B1B2...Bk.

Шаг 2 завершается, поскольку множество новых состояний K1 конечно.

3. Заключительными состояниями построенного ДКА M1 объявляются все состояния, содержащие в себе хотя бы одно заключительное состояние НКА M: S1 : {A1A2...Am | A1A2...Am K1, Ai S для некоторых 1 i m}.

Замечание Множество S1 построенного ДКА может состоять более, чем из одного элемента. Не для всех регулярных языков существует ДКА с единственным заключительным состоянием (пример: язык всех цепочек в алфавите {a, b}, содержащих не более двух символов b). Однако для реализации Элементы теории трансляции / Разбор по регулярным грамматикам алгоритма детерминированного разбора заключительное состояние должно быть единственным.

В таком случае изменяют входной язык, добавляя маркер в конец каждой цепочки (на практике в роли маркера конца цепочки может выступать признак конца файла, символ конца строки или другие разделители). Вводится новое состояние S, и для каждого состояния Q из множества S1 добавляется переход по символу : 1 (Q, ) S. Состояния из S1 больше не считаются заключительными, а S объявляется единственным заключительным состоянием. Теперь по такому ДКА можно построить автоматную грамматику, допускающую детерминированный разбор.

Проиллюстрируем работу алгоритма на примерах.

Грамматика, соответствующая M:

Построим ДКА по НКА, пользуясь предложенным алгоритмом. Начальным состоянием будет H.

Заключительным состоянием построенного ДКА является состояние BS.

Таким образом, M1 {H, B, A, BS }, {0, 1}, 1, H, BS. Для удобства переименуем состояния в M1 : BS обозначается теперь как S1, а в однобуквенных именах состояний вместо подчеркивания используется индекс 1. Тогда M1 {H1, B1, A1, S1}, {0, 1}, { 1(Н1, 1) B1;

1(B1, 0) A1; 1(A1, 1) S1; 1(S1, 0) A1}, H1, S1.

Грамматика, соответствующая M1:

Построим диаграмму состояний (рис. 8).

Элементы теории трансляции / Разбор по регулярным грамматикам Пример 2. Дана регулярная грамматика G T, N, P, S которой соответствует НКА. С помощью преобразования НКА в ДКА построить грамматику, по которой возможен детерминированный разбор.

Построим функцию переходов НКА:

Процесс построения функции переходов ДКА удобно изобразить в виде таблицы, начав ее заполнение с начального состояния H, добавляя строки для вновь появляющихся состояний:

Элементы теории трансляции / Разбор по регулярным грамматикам Переобозначим сотояния: A A, H H, AS Y, S X. Два заключительных состояния X и Y сведем в одно заключительное состояние S, используя маркер конца цепочки. После такой модификации получаем ДКА с единственным заключительным состоянием S и функцией переходов:

По ДКА строим грамматику G1, позволяющую воспользоваться алгоритмом детерминированного разбора:

В заключение раздела о регулярных языках приведем пример использования автоматов в решении теоретических задач.

Доказать, что контекстно-свободный язык L = { a b | n 0} нерегулярен.

Предположим, что язык L регулярен. Тогда существует конечный автомат ( ДКА или НКА ) A ( K,,, I, F ), допускающий язык L : L( A) L. ( Согласно утверждению 10, любой регулярный язык может быть задан конечным автоматом). Пусть число состояний автоkk kk мата A равно k (k 0). Рассмотрим цепочку a b L. Так как L =L (A), a b L (A). Это означает, что в автомате A есть успешный путь T с пометкой a b :

где pi K для i 1,,2k 1. Так как в автомате A всего k состояний, среди p1, p2, …, pk найдутся хотя бы два одинаковых. Иными словами, существуют i, j, 1 i < j k, такие что pi pj. Таким образом, участок pi этого цикла равна m (m 0, так как цикл — это непустой путь). Рассмотрим успешный путь T, который отличается от T тем, что циклический участок pi a a p j присутствует в нем дважды:

Элементы теории трансляции / Разбор по регулярным грамматикам b L(A). Так как ab L, получаем, что L L(A). Это противоречит равенa ству L L(A). Следовательно, предположение о том, что L регулярен, неверно Регулярные выражения Кроме регулярных грамматик и конечных автоматов, существует еще один широко используемый в математических теориях и приложениях формализм, задающий регулярные языки. Это регулярные выражения. Они позволяют описать любой регулярный язык над законкатенация), (итерация). 15) Определение. Пусть L, L1, L2 — языки над алфавитом. Тогда будем называть язык L1 L2 объединением языков L1 и L2 ; язык L1L2 {| L1, L2} — конкатенацией (сцеплением) языков L1 и L2 (содержит всевозможные цепочки, полученные сцеплениL ем цепочек из L1 с цепочками из L2);

Определение. Пусть — алфавит, не содержащий символов,,,, (, ). Определим рекурсивно регулярное выражение над алфавитом и регулярный язык L(), задаваемый этим выражением:

1) a {, } есть регулярное выражение; L(a) {a} для a {}; L() ;

2) если и — регулярные выражения, то:

3) все регулярные выражения конструируются только с помощью пунктов 1 и 2.

Если считать, что операция «» имеет самый низкий приоритет, а операция «» — наивысший, то в регулярных выражениях можно опускать лишние скобки.

Примеры регулярных выражений над алфавитом {a, b}:

Соответствующие языки:

15) Операцию итерации называют также звездочкой Клини, в честь ученого, предложившего регулярные выражения для описания регулярных языков. «Регулярность» в названии этого класса языков означает повторяемость некоторых фрагментов цепочек. На примере диаграмм конечных автоматов видно, что повторяемость фрагментов обусловлена наличием циклов в диаграмме.

Элементы теории трансляции / Задачи лексического анализа L( (aa (ab) bb) ) {}{ aa x1bb aa x2bb... xkbb | k 1, xi {(ab) | n 0} для i 1,..., k }.

Существуют алгоритмы построения регулярного выражения по регулярной грамматике или конечному автомату и обратные алгоритмы, позволяющие преобразовать выражение в эквивалентную грамматику или автомат [3].

Регулярные выражения используются для описания лексем языков программирования, в задачах редактирования и обработки текстов; подходят для многих задач сравнения изображений и автоматического преобразования. Расширенные их спецификации (эквивалентные по описательной силе, но более удобные для практики) входят в промышленный стандарт открытых операционных систем POSIX и в состав базовых средств языка программирования Perl.

Задачи лексического анализа Лексический анализ (ЛА) — это первый этап процесса компиляции. На этом этапе литеры, составляющие исходную программу, группируются в отдельные лексические элементы, называемые лексемами.

Лексический анализ важен для процесса компиляции по нескольким причинам:

а) замена в программе идентификаторов, констант, ограничителей и служебных слов лексемами делает представление программы более удобным для дальнейшей обработки;

б) лексический анализ уменьшает длину программы, устраняя из ее исходного представления несущественные пробельные символы и комментарии;

в) если будет изменена кодировка в исходном представлении программы, то это отразится только на лексическом анализаторе.

Выбор конструкций, которые будут выделяться как отдельные лексемы, зависит от языка и от точки зрения разработчиков компилятора. Обычно принято выделять следующие типы лексем: идентификаторы, служебные слова, константы и ограничители. Каждой лексеме сопоставляется пара:

Соглашение: эту пару тоже будем называть лексемой, если это не будет вызывать недоразумений.

Таким образом, лексический анализатор — это транслятор, входом которого служит цепочка символов, представляющих исходную программу, а выходом — последовательность лексем.

Очевидно, что лексемы перечисленных выше типов можно описать с помощью регулярных грамматик. Поскольку лексемы не пусты, для описания лексического состава любого языка программирования достаточно автоматных грамматик без -правил.

Например, идентификатор (I ) описывается так:

Элементы теории трансляции / Задачи лексического анализа Для грамматик этого класса, как мы уже видели, существует простой и эффективный алгоритм анализа того, принадлежит ли заданная цепочка языку, порождаемому этой грамматикой. Однако перед лексическим анализатором стоит более сложная задача:

он должен сам выделить в исходном тексте цепочку символов, представляющую лексему, и проверить правильность ее записи;

зафиксировать в специальных таблицах для хранения разных типов лексем факт появления соответствующих лексем в анализируемом тексте;

преобразовать цепочку символов, представляющих лексему, в пару тип_лексемы, указатель_на_информацию_о_ней ;

удалить пробельные литеры и комментарии.

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

Смысл ti прежний: если в состоянии A очередной анализируемый символ совпадает с ti для какого-либо i 1, 2, …, n, то осуществляется переход в состояние B, при этом необходимо выполнить действия D1, D2,..., Dm.

Задача. По заданной регулярной грамматке, описывющей целое число без знака, построить диаграмму с действиями по нахождению и печати квадрата данного числа.

Перевод числа во внутренне представление (переменная n типа int) будем осуществлять по схеме Горнера: распознав очередную цифру числа, умножаем текущее значениие n на 10 и добавляем числовое значение текущей цифры (текущий символ хранится в переменной c типа char). Встретив маркер конца, печатаем квадрат числа n.