Д.В.Варсанофьев, А.Г.Дымченко "Основы компиляции" осень,1991 Литература 1. A.Aho, R.Sethi, J.Ullman Compilers: principles, techniques, and tools. Addison-Wesley, Reading, MA, 1986. - современный учебник, в котором подробно изложены все темы кур╕ са; у нас, к сожалению, практически недоступен. 2. A.Aho, J.Ullman Principles of compiler design. Addison-Wesley, Reading, MA, 1977. - более старая версия преды╕ дущей книги. 3. А.Ахо, Д.Ульман Теория синтаксического анализа, перевода и компиляции. т.1,2 - М.:Мир, 1978. - монография освещает те╕ оретические аспекты рассматриваемого предмета и содержит почти все интересное, известное в начале 70-х годов. 4. Д. Грис Конструирование компиляторов для цифровых вычис╕ лительных машин. - М.:Мир, 1975. - в этой замечательной, хотя и несколько устаревшей книге основное внимание уделяется практи╕ ческим вопросам; вместе с предыдущей книгой они удачно дополня╕ ют друг друга. Небесполезные сведения содержатся и во многих других книгах, вышедших на русском языке, в названии которых встречаются слова "компилятор" или "транслятор", например, 5. Р.Хантер. Проектирование и конструирование компиляторов. - М.:Финансы и статистика,1984. Д.В.Варсанофьев, А.Г.Дымченко "Основы компиляции" осень,1991 Материал к лекции 1. Языки и грамматики. Простейший компилятор. Алфавит - это любое множество символов. Понятие символа не определяется. Цепочка символов 0,1,2 записывается как "012" (или 012). Другие обозначения: R x - цепочка x с символами в обратном порядке n x - цепочка x, повторенная n раз x* - цепочка x, повторенная 0 или более раз x+ - цепочка x, повторенная 1 или более раз xy - сцепление (конкатенация) цепочек x и y |x| - длина (число символов) цепочки x e - пустая цепочка Цепочку из одного символа будем обозначать самим символом. Буквы x,y,z,u,v,w,t будем применять для обозначения цепочек. Множество всех цепочек из элементов множества E естественно обозначить через E*. Язык - это подмножество E*. Примеры язы╕ n n ков: Си, русский, { 0 1 | n >= 0 }. Язык можно задать: - перечислив все цепочки; - написав программу-распознаватель, которая получает на вход цепочку символов и выдает ответ "да", если цепочка принадлежит языку и "нет" в противном случае; - с помощью механизма порождения - грамматики. Чтобы задать грамматику, требуется указать: - множество символов алфавита (или терминальных символов) E. Будем обозначать их строчными символами алфавита и цифрами; - множество нетерминальных символов (или метасимволов), не пе╕ ресекающееся с E со специально выделенным начальным символом S. Будем обозначать их прописными буквами; - множество правил вывода, определяющих правила подстановки для цепочек. Каждое правило состоит из двух цепочек (напри╕ мер, x и y), причем x должна содержать по крайней мере один нетерминал; и означает, что цепочку x в процессе вывода мож╕ но заменить на y. Вывод цепочек языка начинается с нетерми╕ нала S. Правило грамматики будем записывать в виде x : y. (Также употребляется запись x ::= y или x -> y) Более строго, определим понятие выводимой цепочки: - S - выводимая цепочка; - если xyz - выводимая цепочка и в грамматике имеется правило y:t, то xtz - выводимая цепочка; - определяемый грамматикой язык состоит из выводимых цепочек, содержащих только терминальные символы. Примеры: а) S : e б) S : e S : 0S1 S : (S) S : SS Для сокращения записи принято использовать символ "или" - "|". Короткая форма записи предыдущих примеров: а) S : e | 0S1 б) S : e | (S) | SS Более сложный пример: в) S : aSBC | abC CB : BC bB : bb cC : cc bC : bc n n n Эта грамматика порождает язык a b c (доказательство этого факта - упражнение). Грамматики в свою очередь образуют т.н. метаязык. Выше была описана "академическая" форма записи метаязыка. На практике применяется также другая форма записи, традиционно называемая нормальными формами Бэкуса-Наура (НФБН). Терминалы в НФБН запи╕ сываются как обычные символы алфавита, а нетерминалы - как име╕ на в угловых скобках <>. Например, грамматику целых чисел без знака можно записать в виде: <число> : <цифра> | <цифра> <число> <цифра> : 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Лирическое отступление. Можно ли записать грамматику какого-ли╕ бо метаязыка на нем самом? Ответ - да. Решение - упражнение. Рассмотрим язык простейших арифметических формул: <формула> : (<формула>) | <число> | <формула><знак><формула> <знак> : + | * Почему "3+5*2" является формулой? Приведем последовательность преобразований цепочек (так называемый "разбор" или "вывод"): <формула> : <формула> <знак><формула> : <формула><знак><формула><знак><формула> : <число> <знак><формула><знак><формула> : 3 <знак><формула><знак><формула> : 3 + <формула><знак><формула> : 3 + <число> <знак><формула> : 3 + 5 <знак><формула> : 3 + 5 * <формула> : 3 + 5 * <число> : 3 + 5 * 2 Сокращенно наличие вывода (цепочки преобразований) будем за╕ писывать в виде <формула>::3+5*2. Большинство грамматик допус╕ кают несколько различных выводов для одной и той же цепочки из языка. Постройте другой вывод для цепочки "3+5*2" - упражнение. Если в процессе вывода цепочки правила грамматики применяют╕ ся только к самому левому нетерминалу, говорят, что получен ле╕ вый вывод цепочки. Аналогично определяется правый вывод. Какой вывод построен в предыдущем примере? Изобразим выполняемые замены цепочек в виде т.н. "дерева разбора" (или дерева вывода). По традиции дерево изображается "вверх ногами": <формула> / \ \ <формула> \ <формула> / | \ \ | <формула> <знак> <формула> | | / | | | | | | | | | <число> <знак> <число> <знак> <число> | | | | | 3 + 5 * 2 Нарисованное дерево имеет ветви (линии) и узлы (помечены терми╕ налами и нетерминалами), из которых растут ветви. Конечные узлы (терминалы) называются листьями. Понятия "поддерево", "корень дерева", видимо, не нуждаются в определении. Одно и то же дерево разбора может описывать различные выводы (в дереве не фиксирован порядок применения правил). Однако, между левыми (или правыми) выводами и деревьями разбора для цепочек существует однозначное соответствие (упражнение). Если для одной и той же цепочки можно изобразить два разных дерева разбора (или, что то же самое, построить, два разных правых вывода), грамматика называется неоднозначной. Описанная грамматика неоднозначна (почему? - упражнение). Тот же самый язык можно описать однозначной грамматикой: <формула> : <терм> | <терм><знак><формула> <терм> : (<формула>) | <число> <знак> : + | * Как изменится дерево разбора? - упражнение. Дерево разбора оп╕ ределяет некоторую структуру цепочки языка. Так, мы видим, что подцепочка "3+5" является "формулой". Это противоречит нашим (интуитивным) понятиям о смысле исходной формулы: 3+5 в отличие от 5*2 не является подвыражением. Мы можем учесть приоритет операций, изменив грамматику: <формула> : <терм> | <формула> + <терм> <терм> : <элемент> | <терм> * <элемент> <элемент> : (<формула>) | <число> Как добавить в язык операции вычитания и деления? - упражнение. Кроме привычной формы записи арифметических формул (т.н. "инфиксной", т.е. со знаком операции между операндами), широко распространена "постфиксная" (или обратная польская) форма за╕ писи, в которой операция расположена после операндов. Примеры: 2+3 2 3 + 2*3+4 2 3 * 4 + 2*(3+4) 2 3 4 + * В обратной польской записи скобки не требуются, а значение фор╕ мулы очень легко вычислить при использовании стека чисел - уп╕ ражнение. Перевод с одного языка на другой называется трансляцией или компиляцией. Так как любую инфиксную формулу можно переписать в постфиксную запись с сохранением порядка следования чисел (до╕ казательство - упражнение), то для компиляции формулы из ин╕ фиксной в постфиксную запись следует выделить внешнюю операцию, записать в постфиксной форме оба операнда и записать операцию вслед за ними. Для перевода операнда в постфиксную запись можно рекурсивно обратиться к программе перевода формулы. Однако следование правилам грамматики при компиляции формулы за один ее просмотр слева направо приводит к следующему фрагменту: CompForm() { CompForm() ... выполнение которого, конечно же, никогда не завершится. Пробле╕ ма возникла из-за того, что цепочки в левой и правой частях правила начинаются с одного нетерминала (говорят, что граммати╕ ка леворекурсивна). Если устранить левую рекурсию: <формула> : <терм> | <терм><плюс минус><формула> <терм> : <элемент> | <элемент><умножить разделить><терм> <плюс минус> : + | - <умножить разделить> : * | / то описанная проблема исчезнет, рекурсивный компилятор можно будет написать, однако появятся новые трудности (какое дерево разбора будет соответствовать цепочке "5-3-2"? - упражнение). Фактически, преобразовав грамматику, мы изменили порядок свертки операций. Традиционно операции одного приоритета выпол╕ няются слева направо (говорят, что операции левоассоциативны), а только что написанная грамматика определяет операции как пра╕ воассоциативные. Наиболее просто решить эту проблему можно, добавив в мета╕ язык НФБН символы итерации {} "повторить 0 или более раз". С применением новых обозначений грамматика легко запишется без левой рекурсии: <формула> : <терм> { <плюс минус> <формула> } <терм> : <элемент> { <умножить разделить> <элемент> } Написанный по этой грамматике рекурсивный компилятор также бу╕ дет выглядеть просто: char *infix, *postfix; /* указатели на входную и выход╕ ную цепочки */ CompForm() { /* компилировать формулу */ register char sign; CompTerm(); while ( (sign = *infix) == '+' || sign == '-' ) { ++infix; CompTerm(); *postfix++ = sign; *postfix++ = ' '; } } CompTerm() { /* компилировать терм */ register char sign; CompEl(); while ( (sign = *infix) == '*' || sign == '/' ) { ++infix; CompEl(); *postfix++ = sign; *postfix++ = ' '; } } CompEl () { /* компилировать элемент */ if ( *infix == '(' ) { ++infix; CompForm(); if ( *infix++ != ')' ) error(); } else { if ( !isdigit(*infix) ) error(); while ( isdigit( *infix ) ) *postfix++ = *infix++; *postfix++ = ' '; } } Использованная нами при написании компилятора техника носит название рекурсивного спуска. Входную цепочку мы просматриваем слева направо, дерево вывода проходим сверху вниз (т.е. от на╕ чального нетерминала <формула>). Функция error в компиляторе служит для вывода сообщения о том, что предъявленная цепочка не входит в язык арифметических формул. Если компилятор при получении на вход цепочки не выдает сообщения об ошибке, говорят, что эта цепочка допущена. Приве╕ дите примеры не входящих в язык арифметических формул цепочек, допускаемых компилятором - упражнение. Если разбор цепочки-программы сопровождается не переводом ее в другое представление для дальнейшего выполнения, а немедлен╕ ным исполнением (в нашем случае - вычислением значения), гово╕ рят, что программа интерпретируется. Задачи и упражнения: 1. Какой язык описывает грамматикa, является ли данная грамма╕ тика однозначной? - S : e | 0 S 0 | 1 S 1 - S : 0 S 1 | 0 1 - S : S S '+' | S S '*' | 'a' - S : '+' S S | '-' S S | 'a' - S : S '(' S ')' S | e - S : 'a' S 'b' S | 'b' S 'a' S | e - S : 'a' | S '+' S | S S | S '*' | '(' S ')' 2. Описать язык однозначной грамматикой: - обратная польская(постфиксная) запись арифметической формулы - префиксная арифметической формулы - арифметическое выражение из целых констант, имен переменных, бинарных операций '+', '-', '*', '/' и унарной операции '-' - левоассоциативный список имен, разделенных запятыми - правоассоциативный список имен, разделенных запятыми - римские цифры 3. Доказать, что двоичные числа, описываемые грамматикой n : 1 1 | 1 0 0 1 | n 0 | n n делятся на 3. Порождает ли данная грамматика все двоичные числа кратные трем? 4. Показать, что грамматика stmt : IF expr THEN stmt | IF expr THEN stmt ELSE stmt | OTHER не является однозначной. Преобразовать ее в однозначную грамма╕ тику, описывающую язык, в котором ELSE соответствует ближайшему незакрытому THEN. 5. Какие ограничения следует наложить на грамматику, чтобы при╕ менение рекурсивного спуска было возможно? 6. Напишите грамматики для следующих языков: 2 n m n m n а) 0 б) a b a b в) xx, где x - любая цепочка из нулей и единиц. Упражнения по программированию: 1. Переделайте компилятор так, чтобы он не допускал ошибочных (т.е. не порождаемых грамматикой) цепочек. 2. Добавьте в компилятор операцию возведения в степень (право╕ ассоциативная операция "^" с наивысшим приоритетом). 3. Переделайте компилятор формул в интерпретатор. 4. Добавьте в компилятор операцию "унарный минус", чтобы вход╕ ные цепочки типа -(-a*b+c) стали бы допустимыми и правильно компилировались. Цепочки вида --a, a+-b, конечно же, не дол╕ жны допускаться! 5. Реализуйте компилятор римские цифры -> арабские цифры 6. Реализуйте компилятор арабские цифры -> римские цифры В префиксной форме записи формулы знак операции предшествует операндам, например, 1+2*3 записывается в виде + 1 * 2 3 . (Именна эта форма записи была предложена Я.Лукасевичем и полу╕ чила название "польской"). 7. Вычислите значение формулы, записанной в префиксной записи, просматривая ее один раз слева направо. 8. Реализуйте компилятор формул инфиксная запись -> префиксная. 9. Реализуйте компилятор формул из постфиксной (или префиксной) записи в инфиксную. В каком направлении удобно просматривать исходную постфиксную (или префиксную) запись? Из-за наличия скобок такой перевод не является однозначным, поэтому две задачи: - в инфиксной записи допускаются "лишние" скобки; - "лишние" скобки не допускаются. - конец материала к лекции 1 - Материал к лекции 2. Иерархия Хомского. Регулярные языки. Классификация грамматик по сложности соответствующих прог╕ рамм-распознавателей называется иерархией Хомского. В ней выде╕ лены 4 класса грамматик (в порядке возрастания сложности): а) регулярные (или автоматные). Правила имеют вид: A : xB или A : x, где x - цепочка терминалов или e Примеры - упражнение. б) контекстно-свободные (или КС). Правила имеют вид: A : y, где y - цепочка из терминалов и нетерминалов Примеры - "скобочный язык" из предыдущей лекции, язык арифметических формул в) контекстно-зависимые (неукорачивающие). Правила имеют вид : z : y, где z и y - цепочки из терминалов и нетерми╕ налов, z содержит нетерминал, |z| <= |y| n n n Пример: a b c г) без ограничений Класс языка определяется классом самой простой (в смысле иерархии Хомского) из описывающих его грамматик. Следующие вло╕ жения для классов языков очевидны, если не рассматривать КС-грамматики, содержащие так называемые e-правила - правила с пустой правой частью. (Упражнение: показать, что любой КС-язык может быть описан грамматикой без e-правил). а < б < в < рекурсивные множества < г = рек.перечислимые мн-ва Для языка, определенного регулярной грамматикой, всегда мож╕ но написать контекстно-свободную грамматику (и даже грамматику без ограничений!). Тем не менее, все вложения строгие: в каждом классе существуют языки, которые нельзя задать грамматиками бо╕ лее простого класса. Конечные автоматы Рассмотрим другой способ задания регулярных языков. (Неде╕ терминированный) конечный автомат задается: - алфавитом входных символов E; - множеством состояний S; - тернарным отношением переходов на множестве { S, E U e, S }; - начальным состоянием - выделенным состоянием в S, и - конечными состояниями - непустым подмножеством S. Принято изображать автомат в виде ориентированного графа, узлы которого соответствуют состояниям (конечные состояния мы будем заключать в двойную рамку), а ребра, помеченные символами вход╕ ного алфавита или е, изображают отношение переходов. Цепочка допускается автоматом если и только если существует пусть из начального в одно из конечных состояний, такой что, прочитав метки ребер вдоль этого пути, мы получим исходную це╕ почку (буква e, естественно, не читается). Например, автомат --------╛ 0 --------╛ 1 -T-----T╛ ╕ S +-->--+ B +-->--+╕ C ╕╕ L-------- L---T---- L+--T--+- L------<-------0 допускает цепочки (01)+. Этот язык можно описать регулярной грамматикой: S : 0 B B : 1 C C : 0 B C : e Несложно показать (упражнение), что для каждого автомата можно построить регулярную грамматику, описывающую тот же самый язык, и наоборот. Детерминированный конечный автомат - частный случай неде╕ терминированного, в котором: - нет e-переходов, - отношение переходов является однозначной функцией f:( S x E U e ) -> S, определенной, может быть, не для всех пар из SxEUe. В терминах графа это означает, что из одного состояния выходит не более одного ребра с одинаковой меткой. Для детерминированного автомата очень просто проверять при╕ надлежность цепочки из E* языку. Добавив, если нужно, еще одно "тупиковое" состояние, можно сделать функцию переходов опреде╕ ленной на всех парах из S x E. ----T------╛ ╕ ╕ 0 1 ╕ s := начальное состояние +---+------+ цикл для каждого символа цепочки c выполнить ╕ S ╕ B F ╕ . s := f( s, c ) ╕ B ╕ F C ╕ конец цикла ╕ C ╕ B F ╕ ответ := s - конечное состояние ╕ F ╕ F F ╕ L---+------- Такая интерпретация детерминированного конечного автомата более наглядна и общепринята: KA - устройство, которое может находится в конечном множестве состояний и переходит из одного состояния в другоe под действием внешних событий из алфавита E. Можно ли подобным образом интерпретировать недетерминирован╕ ный автомат (или хотя бы эффективно определять принадлежность цепочки языку)? Да, можно считать, что в том случае, когда воз╕ можен более чем один переход, создается необходимое число эк╕ земпляров КА, которые переводятся во все возможные в этой ситу╕ ации состояния. Цепочка считается допущенной, если хотя бы один из экземпляров оказался в конечном состоянии. -<--------------------------╛0 ----+---╛ 0 --------╛ 1 -T--+--T╛ ╕ S +-->--+ B +-->--+╕ C ╕╕ L-------- L---T---- L+--T--+- L<-------------0 Какие цепочки допускает этот автомат? - упражнение. Заметим, что если несколько экземпляров недетерминированного КА оказались в одном состоянии, то в дальнейшем можно рассмат╕ ривать только один из них. Таким образом, максимальное коли╕ чество экземпляров не превосходит числа состояний. Проверить, допускает ли недетерминированный конечный автомат цепочку символов, также несложно: S := e-замыкание( { начальное состояние } ) цикл для каждого символа цепочки c выполнить . S := e-замыкание( F( S, c ) ) конец цикла ответ := ( S П конечные состояния ) - непусто Здесь: S - подмножество множества состояний KA; e-замыкание( S ) - множество состояний, достижимых из S за 0 и более e-переходов; F( S, c ) - множество состояний, достижимых из S за один переход, помеченный символом c. Упражнение по программированию: придумайте структуры данных для представления детерминированного и недетерминированного ко╕ нечных автоматов и запрограммируйте проверку допуска строки из символов ASCII KA. Это можно (и следует) делать за время - O(длина цепочки) для детерминированного и - O(длина цепочки*число состояний) для недетерминированного КА. Преобразование недетерминированного КА в детерминированный Недетерминированный КА всегда можно преобразовать в эквива╕ лентный (т.е. допускающий то же множество цепочек) детерминиро╕ ванный КА. Рассмотрим новый КА, состояниями которого будут под╕ множества множества состояний исходного КА (если исходный авто╕ мат имел m состояний, сколько их будет у нового? - упражнение). Исходным для нового автомата будет состояние {Начало}, конечны╕ ми - все состояния, содержащие исходное конечное состояние. Пе╕ реход A -> B по символу d имеется в новом автомате тогда и только тогда, когда в исходном автомате для любого состояния b из B, существует a из A такое, что по символу d возможен пере╕ ход a -> b, и других переходов по d из A нет. Новый автомат бу╕ дет детерминированным и эквивалентным исходному. Действительно, состояние нового автомата a+b соответствуют размещению экземпляров исходного недетерминированного КА в сос╕ тояниях a и b, а переход в новом автомате соответствует перехо╕ дам всех экземпляров недетерминированного КА. Для практических целей применяется аналогичный алгоритм: На╕ зовем состояния неразличимыми, если в них происходит переход из одного и того же состояния при одном и том же входном символе. Возьмем любое множество неразличимых состояний и добавим в спи╕ сок состояний КА еще одно - их "сумму", перемещая переходы: Было: ╕ Стало: --╛1 --╛0 --╛ ╕ --╛1 ----╛0 ╕ +->+Б+->+В╕ ╕ ╕ +->+Б+Г+>T->╛ ╕А╕ L-- L-- ╕ ╕А╕ L---- ╕ ╕ ╕ ╕1 --╛0 --╛ ╕ ╕ ╕ --╛0 -+╛ ╕ ╕ +->+Г+->+Д╕ ╕ ╕ ╕ ╕Б+->+В╕ ╕ L-- LT- L-- ╕ L-- L-- L-- ╕ --╛1 ╕ ╕ --╛1 --╛0 -+╛ ╕Е+->-- ╕ ╕Е+->+Г+->---+Д╕ L-- ╕ L-- L-- L-- Получим новый (быть может, вновь недетерминированный) КА. Будем повторять наши действия, пока в КА остаются неразличимые состо╕ яния. Этот процесс в конце концов завершится (почему? - упраж╕ нение). При этом мы получим детерминированный автомат, эквива╕ лентный исходному (почему? - упражнение). Применив этот метод к недетерминированному КА из примера в этой лекции, получим: --<----------╛ 1 --------╛ 0 --------╛ 1 -T--+--T╛0 -----+----╛ ╕ S +->--+ B +->--+╕ C ╕+-->+ S + B ╕ L-------- L---T---- L+-----+- L----T----- L--<----------------------- 0 Минимизация конечного автомата По конечному автомату часто можно построить автомат с мень╕ шим числом состояний, эквивалентный исходному. Соответствующий процесс называется минимизацией конечного автомата. Вначале выбросим из автомата все состояния, недостижимые из начального. Затем разобьем все состояния КА на классы эквивалентности сле╕ дующим способом: в первый класс отнесем все конечные состояния, а во второй - все остальные. Назовем эти состояния 0-эквива╕ лентными. Теперь построим новое 1-эквивалентное разбиение, вы╕ делив те состояния, которые по одинаковым символам переходят в 0-эквивалентные состояния. Последовательно строя n+1-эквива╕ лентные состояния по n-эквивалентным, мы будем увеличивать чис╕ ло классов эквивалентности. Прекратим этот процесс тогда, когда n+1-эквивалентное состояние совпадет с n-эквивалентным. Каждый полученный класс эквивалентности и будет состоянием нового ми╕ нимизированного КА, эквивалентного исходному (почему? - упраж╕ нение). Рассмотрим, например, следующий КА: --------╛1 -T-----T╛ 0--------╛ -------╛0->+ B +->--+╕ D ╕+<-+ F ╕ ╕Начало+-- L-T------ -++---T-+- L---T-T-- ╕ ╕ ╕ --<-----0 -->- ╕1 -->- ╕1 ╕ ╕ ╕ ╕ ╕ ╕ ╕ ╕ ╕ ╕ L<-+------╛0 ╕1 -<- ╕0 -<- ╕ A +-╛ -----+--╛1 LTT+--+-T╛ 1-+--+---╛ L-------1L>+ C +->--+╕ E ╕╕<-+ G ╕ L-------- L+-----+- L-------- Состояния F и G недостижимы (это можно выяснить, например, вы╕ числив транзитивное замыкание отношения "есть переход"). Пос╕ троим классы n-эквивалентности для оставшихся состояний: n Классы 0 (ABC) (DE) 1 (A) (BC) (DE) 2 (A) (BC) (DE) Результат: ------╛0,1 ------╛1 -T---T╛ ╕ A +---->+ B+C +---->+╕D+E╕╕ L------ L--T--- L+-T-+- L-<----------0 Упражнение: докажите, что для любого КА существует и единственен с точностью до изоморфизма минимальный эквива╕ лентный ему конечный автомат. Покажите, что описанный выше ал╕ горитм минимизации получает на выходе минимальный автомат. Упражнение по программированию: придумайте структуры данных и запрограммируйте процедуры построения детерминированного КА, и минимизации КА. Какая временная и пространственная сложность предложенных вами алгоритмов в терминах числа состояний исход╕ ного и выходного автоматов? Регулярные языки и регулярные выражения Рассмотрим специальный класс операций над языками - регуляр╕ ные операции, множество языков, получаемое в результате приме╕ нения конечного числа регулярных операций из элементарных язы╕ ков, - регулярные множества, способ их описания - регулярные выражения и недетерминированные конечные автоматы, допускающие цепочки из этих множеств. ---------------------T-----------T----------------------------╛ ╕ Регулярное ╕Регулярное ╕ Конечный автомат ╕ ╕ множество ╕ выражение ╕ ╕ +--------------------+-----------+----------------------------+ ╕ Пустая цепочка ╕ e ╕ ------╛ e -T---T╛ ╕ ╕ ╕ ╕ ╕ S +--->---+╕ E ╕╕ ╕ ╕ ╕ ╕ L------ L+---+- ╕ +--------------------+-----------+----------------------------+ ╕ Один символ a из E ╕ a ╕ ------╛ а -T---T╛ ╕ ╕ ╕ ╕ ╕ S +--->---+╕ E ╕╕ ╕ ╕ ╕ ╕ L------ L+---+- ╕ +--------------------+-----------+----------------------------+ ╕ ╕ ╕ ----╛ e --T-----T-╛ e -T-T╛╕ ╕ P U Q ╕ p|q ╕ ╕ +->-+s╕Авт.P╕e+->-+╕ ╕╕╕ ╕ ╕ ╕ ╕ S ╕ L-+-----+-- ╕╕E╕╕╕ ╕ ╕ ╕ ╕ ╕ e --T-----T-╛ e ╕╕ ╕╕╕ ╕ ╕ ╕ ╕ +->-+s╕Авт.Q╕e+->-+╕ ╕╕╕ ╕ ╕ ╕ L---- L-+-----+-- L+-+-╕ +--------------------+-----------+----------------------------+ ╕ PQ (конкатенация) ╕ pq ╕ ----T-----T----T-----TT-T╛ ╕ ╕ ╕ ╕ ╕ S ╕Авт.P╕ es ╕Авт.Q╕╕Е╕╕ ╕ ╕ ╕ ╕ L---+-----+----+-----++-+- ╕ +--------------------+-----------+----------------------------+ ╕ P* (итерация) ╕ p* ╕ ---<----╛e ╕ ╕ ╕ ╕ ----╛ e -+T-----T+╛ e -T-T╛╕ ╕ ╕ ╕ ╕ S +->-+s╕Авт.P╕e+->-+╕E╕╕╕ ╕ ╕ ╕ L-T-- L-+-----+-- L+T+-╕ ╕ ╕ ╕ eL---------->----------- ╕ +--------------------+-----------+----------------------------+ ╕ P (просто скобки)╕ (p) ╕ ------T-------TT---T╛ ╕ ╕ ╕ ╕ ╕ S ╕ Авт.P ╕╕ E ╕╕ ╕ ╕ ╕ ╕ L-----+-------++---+- ╕ L--------------------+-----------+----------------------------- В регулярном выражении "*" имеет больший приоритет, чем кон╕ катенация, а конкатенация - больший чем "|". Примеры регулярных выражений: (0|1)*, (0|1)(0|1)*. Какие множества они описывают? Для регулярного выражения предложен способ построения неде╕ терминированного конечного автомата, допускающего соответству╕ ющее выражению регулярное множество. Предложенная конструкция не является самой экономной (автомат обычно содержит много "лишних" e-переходов), однако построенный автомат обладает следующими полезными свойствами: - у него только одно конечное состояние, - в начальное состояние не входит ни одно ребро, - из конечного состояния не выходит ни одно ребро. Таким образом, мы доказали, что регулярные множества < регу╕ лярные языки = языки, допускаемые КА. Покажем, что допускаемое КА множество - регулярно. (Это утверждение называется теоремой Клини). Доказательство: Пусть S1,...Sn - состояния детерминированно╕ го КА, S1 - начальное состояние. Рассмотрим все пути в графе переходов с началов в Si, концом в Sj, промежуточными узлами из множества {S1...Sk} (1<=i<=n, 1<=j<=n, 0<=k<=n) и множества це╕ почек из E - L(i,j,k), соответствующие этим путям. Докажем ин╕ дукцией по k, что множества L - регулярны. L(i,j,0) - состоит из меток ребер, ведущих из Si в Sj, сле╕ довательно, регулярно. Для 0<=k<=n-1 L(i,j,k+1) = L(i,j,k) U L(i,k+1,k) L(k+1,k+1,k)* L(k+1,j,k) получено с помощью регулярных операций из регулярных мно╕ жеств, следовательно, регулярно. Множество цепочек, допускаемых КА, представляет собой объеди╕ нение цепочек L(1,j,n), таких, что Sj - конечное состояние КА, следовательно, регулярно. (Конец доказательства). Мы рассмотрели 4 способа описания языков: - регулярные (автоматные, праволинейные) грамматики, - недетерминированные КА, - детерминированные КА, - регулярные выражения, и показали, что они описывают один класс языков - регулярные языки. Этот класс языков "устроен очень хорошо" - для всех ти╕ пичных вопросов известны ответы и эффективные алгоритмы. Приме╕ ры таких вопросов (получение ответов - упражнение): - является ли объединение, пересечение, дополнение регулярных языков регулярным, - является ли регулярный язык конечным, пустым, - совпадают ли два регулярных языка, - является ли один регулярный язык подмножеством другого, и т.д. (Замечание. Для других классов иерархии Хомского дела обстоят значительно хуже, например, проблема эквивалентности для КС-языков алгоритмически неразрешима.) Лемма о разрастании для регулярных языков Так называмые "леммы о разрастании" для классов языков - удобный способ доказательства того, что конкретный язык не от╕ носится к данному классу. Лемма для регулярного языка: Существует такое число m, что любую цепочку x, |x| > m, принадлежащую языку, можно разбить на три части: x = uvw так, что 0<|v|<=m и цепочки uv*w также будут принадлежать языку. Доказательство: построим КА для распознава╕ ния языка. Пусть этот автомат имеет m состояний. Тогда при раз╕ боре цепочки x хотя бы одно из состояний (например, А) прохо╕ дится дважды (почему? - упражнение). Разобьем цепочку x на три части - до состояния А, от А до А, остальное. Это и есть цепоч╕ ки u,v,w (почему v можно размножать, сохраняя принадлежность цепочки языку? - упражнение). n n Как показать, что язык 0 1 не является регулярным? - упраж╕ нение. Задачи и упражнения 1. Написать регулярную грамматику и регулярное выражение, порождающие тот же язык, что и грамматика: S : AB ; A : X|Y ; X : x|xX ; Y : y|yY ; B : b|bB 2. Построить регулярную грамматику и конечный автомат, соот╕ ветствующие регулярному выражению: (101)*(010)* 3. Постройте недетерминированный а затем детерминированный конечные автоматы, воспринимающие регулярное выражение: (101)*(110)* 4. Построить детерминированные конечные автоматы для следу╕ ющих регулярных выражений. Для каждого полученного автомата построить эквивалентный минимальный автомат. Убедиться в изо╕ морфизме минимальных автоматов, следовательно, в эквивалентнос╕ ти исходных выражений: (a|b)* (a*|b*)* ((e|a)b*)* 5. Написать регулярное выражение, описывающее следующий язык - слово, буквы которого расположены в алфавитном порядке - последовательность цифр, в которой нет повторяющихся цифр - последовательность цифр, в которой не более чем одна цифра встречается несколько раз - строка из нулей и единиц, в которой нет подстроки 0 0 1 - строка из нулей и единиц, в которой нет подпоследователь╕ ности 0 0 1 6. Опишите регулярной грамматикой и приведите регулярное вы╕ ражение для идентификатора Фортрана. (До шести букв или цифр, первый символ должен быть буквой). 7. Напишите программу распознавания вещественных констант. Она должна воспринимать константы вида: 1.2 -0.4 +3.14 .2 1. -1.е38 1е+2 +0.5е-23 и т.д. 8. Построить минимальные детерминированные конечные автоматы для следующих регулярных выражений (a|b)*a(a|b) (a|b)*a(a|b)(a|b) (a|b)*a(a|b)(a|b)(a|b) Доказать, что любой детерминированный конечный автомат для вы╕ ражения (a|b)a(a|b)(a|b)...(a|b), содержащего n-1 (a|b) в конце содержит не менее чем 2**n состояний. 9. Напишите программу, которая проверяет, является ли имя файла частным случаем разновидности регулярного выражения, в котором метасимвол * обозначает любую (в том числе и пустую) последовательность символов кроме ".", а метасимвол ? - любой символ кроме "." - конец материала к лекции 2 - Материал к лекции 3. Lex и другие. Lex - программа для генерации сканеров (лексических анализа╕ торов). Входной язык содержит описания лексем в терминах регу╕ лярных выражений. Результатом работы LEX'a является программа на языке Си, которая читает файл yyin (обычно это стандартный ввод) и выделяет из него последовательности символов (лексемы), соответствующие регулярным выражениям. Рассмотрим способы записи регулярных выражений во входном языке Lex'а. Алфавит Lex'а совпадает с алфавитом используемой ЭВМ. Символ из алфавита, естественно, представляет регулярное выражение из одного символа. Специальные символы (в том числе +-*?()[]{}|/\^$.<> ) записываются после специального префикса \. Кроме того, применимы все традиционные способы кодирования символа в языке C. Символы и цепочки можно брать в кавычки: Например: а "а" \а - три способа кодирования символа а \n \t \007 "continue" Имеется возможность задания класса символов: [0-9] или [0123456789] - любая цифра [A-Za-z] - любая буква [^0-7] - любой символ, кроме восьм. цифр . - любой символ, кроме \n Грамматика для записи регулярных выражений (в порядке убывания приоритета): <р> : <р>* - повторение 0 или более раз <р> : <р>+ - повторение 1 или более раз <р> : <р>? - необязательный фрагмент <р> : <р><р> - конкатенация <р> : <р>{m,n} - повторение от m до n раз <р> : <р>{m} - повторение m раз <р> : <р>{m,} - повторение m или более раз <р> : ^<р> - фрагмент в начале строки <р> : <р>$ - фрагмент в конце строки <р> : <р>|<р> - любое из выражений <р> : <р>/<р> - первое выражение, если за ним следует второе <р> : (р) - скобки, используются для группировки Примеры: [A-Za-z]([A-Za-z0-9]{0,7}) - идентификатор (имя) в языке C ^#" "*define - начало #define в языке C Программа на входном языке Lex состоит из трех частей, разде╕ ленных символами %%: Описания %% Правила %% Программы Раздел описаний содержит определения макросимволов (метасим╕ волов) в виде: ИМЯ ВЫРАЖЕНИЕ Если в последующем тексте в регулярном выражении встречается {ИМЯ}, то оно заменяется на ВЫРАЖЕНИЕ. Если строка описаний на╕ чинается с пробелов или заключена в скобки %{ ... }%, то она просто копируется в выходной файл. Раздел правил содержит строки вида ВЫРАЖЕНИЕ {ДЕЙСТВИЕ} ДЕЙСТВИЕ - это фрагмент программы на C, который выполняется тогда, когда обнаружена цепочка, соответствующая ВЫРАЖЕНИЮ. Действие, указанное в начале раздела без выражения, выполняется до начала разбора. Lex делает попытку выделить наиболее длинную цепочку из входного потока. Если несколько правил дают цепочку одинаковой длины, применяется первое правило. Так, при разборе по следующим правилам для цепочки "123" по будет применено пер╕ вое правило, а для цепочки "123." - третье: [0-9]+ (\+|\-)?[0-9]+ (\+|\-)?[0-9]+"."[0-9]+ Если ни одно из правил не удастся применить, входной символ бу╕ дет скопирован в yyout. Если это нежелательно, в конец правил можно добавить, например, строки: . {/* Ничего не делать */} \n { } Раздел программ может содержать произвольные тексты на C и целиком копируется в выходной файл. Обычно здесь записывается функция yywrap(), которая определяет, что делать при достижении автоматом конца входного файла. Ненулевое возвращаемое значение приводит к завершению разбора, нулевое - к продолжению (перед продолжением, естественно, надо открыть какой-нибудь файл как yyin). Интерпретатор таблиц КА имеет имя yylex(). Автомат прекраща╕ ет работу (происходит возврат из функции yylex()), если в одном из действий выполнен оператор return (результат yylex() будет совпадать с указанным в операторе) или достигнут конец файла и значение yywrap() отлично от 0 (результат yylex() будет равен 0). Традиционный пример входной программы для Lex'а - подсчет числа слов и строк в файле: /***************** Раздел определений *********************/ /* NODELIM означает любой символ, кроме разделителей слов */ NODELIM [^" "\t\n] int l, w, c; /* Число строк, слов, символов */ %% /******************** Раздел правил ***********************/ { l=w=c=0; /* Инициализация */ } {NODELIM}+ { w++; c+=yyleng; /* Слово */ } \n { l++; /* Перевод строки */ } . { c++; /* Остальные символы */ } %% /******************* Раздел программ **********************/ main() { yylex(); } yywrap() { printf( " Lines - %d Words - %d Chars - %d\n", l, w, c ); return( 1 ); } Внутри действий в правилах можно использовать некоторые спе╕ циальные конструкции и функции Lex'а: yytext - указатель на отождествленную цепочку символов, терминированную нулем; yyleng - длина этой цепочки yyless(n) - вернуть последние n символов цепочки обратно во входной поток; yymore() - считать следующие символы в буфер yytext после текущей цепочки yyunput(c)- поместить байт c во входной поток ECHO - копировать текущую цепочку в yyout Упражнение: опишите на языке регулярных выражений LEX'а следующие регулярные множества: - комментарий Си - комментарий Паскаля - вещественная константа Си - целая константа Си ( 0, 12, -3, 0xFF ) Программа для Lex'а, которая печатает все слова с переносами из входного потока: NODELIM [^, :\.;\n\-\╕] HYPHEN [\-\╕] %% {NODELIM}+{HYPHEN}\n{NODELIM}+ { printf ("%s\n",yytext); } {NODELIM}* { /* Необязательно */ } . | \n { } %% yywrap() { return(1); } main() { yylex(); } Если убрать необязательное правило из предыдущей программы, программа по-прежнему будет работать, но значительно медленнее, поскольку при этом механизм вызова действий будет вызываться для каждого символа (а не каждого слова). В некоторых случаях бывает удобно описать необходимые дей╕ ствия в терминах нескольких разных состояний (т.е. разных ко╕ нечных автоматов) с явным переключением с одного на другое. В этом случае набор имен состояний следует перечислить в специ╕ альной строке %Start, а перед выражениями записывать имя соот╕ ветствующего состояния в угловых скобках. Переключение в новое состояние выполняется с помощью оператора BEGIN. Например, сле╕ дующая программа удаляет комментарии из программ на C (out - вне комментария, in - внутри): %Start out in %% { BEGIN out; } "/*" { BEGIN in; } .|\n { printf("%s",yytext); } "*/" { BEGIN out; } .|\n { } %% yywrap() { return(1); } main() { yylex(); } Для вызова программы Lex в ОС UNIX следует ввести команду "lex имя_исходного_файла". Выходной файл имеет имя "lex.yy.c". Упражнения по программированию: 1. Написать программу для Lex'а, которая заменяет в Фортран-программе все слова DOUBLE PRECISION на REAL. 2. Написать программу для Lex'а, которая выводит все встречен╕ ные в тексте слова, начинающиеся с заглавной буквы. 3. Написать программу для Lex'а для удаления комментариев из программы на C, которая будет учитывать возможность наличия вложенных комментариев и игнорировать "/*" внутри символьных констант. Как устроен LEX. Мы попытаемся обсудить здесь то, как мог бы быть реализован генератор сканеров, из этого обсуждения не следует, что UNIX' овская программа LEX устроена именно так. Для каждого из регулярных выражений r1, ... rn несложно построить недетерминированный конечный автомат, затем, следует объединить полученные автоматы, создав новое начальное состо╕ яние с e-переходами в начальные состояния каждого регулярного выражения. (Полученный автомат будет распознавать выражение r1| r2|...rn). Например, для выражений a, abb, a*b+, будет построен следующий автомат: e --╛ a -T-T╛ ----->--+1+->-+╕2╕╕ a --+-╛ L-- L+-+- ╕ ╕ e --╛ a --╛ b --╛ b -T-T╛ ╕ 0 +-->--+3+->-+4+->-+5+->-+╕6╕╕ abb ╕ ╕ L-- L-- L-- L+-+- L-T-- -<╛a --<╛b ╕ e -+╛╕ -T+T╛╕ L---->--+7++>-+╕8╕+- a*b+ L-- b L+-+- Для выделения лексем из входной цепочки можно применить нем╕ ного модифицированный алгоритм моделирования недетерминирован╕ ного КА. Отличие состоит в том, что наличие в текущем множестве состояний конечного состояния не является основанием для оста╕ новки автомата - не исключено, что цепочка может быть продолже╕ на до более длинной лексемы. В этом случае следует запомнить лексему и соответствующее ей регулярное выражение (более точно, то из подходящих выражений, которое было записано выше по тексту в исходной LEX-программе) и продолжить интерпретацию КА. Этот процесс завершается, если из текущего множества состо╕ яний КА нет перехода для очередного символа из входной цепочки. Только теперь можно считать распознанной последнюю запомненную лексему, выполнить соответствующее ей действие, возвратить "лишние" просмотренные символы в входную цепочку, установить автомат в начальное состояние и продолжить поиск следующей лек╕ семы. Построенный выше автомат при интерпретации цепочки aaba... пройдет следующие множества состояний: --------╛ a ------╛ a --╛ b --╛ a -----╛ ╕0,1,3,7+->-+2,4,7+->-+7+->-+8+->-+stop╕ L-------- L------ L-- L-- L----- a(a) aab(a*b+) В результате будет распознана лексема aab, как отвечающая регу╕ лярному выражению a*b+. Детерминированный КА, полученный из построенного выше неде╕ терминированного КА также может быть использован для выделения лексем. Напомним, что состояние ДКА соответствует множеству состояний НКА. Если это множество содержит конечные состояния НКА, то следует пометить соотвествующее ему (конечное) состо╕ яние ДКА, первым регулярным выражением. Например для рассмот╕ ренного выше примера может быть построен следующий ДКА: -----------T-------T-----T-------------╛ ╕Состояние ╕ a ╕ b ╕Рег.выражение╕ +----------+-------+-----+-------------+ ╕ 0,1,3,7 ╕ 2,4,7 ╕ 8 ╕ - ╕ ╕ 2,4,7 ╕ 7 ╕ 5,8 ╕ а ╕ ╕ 8 ╕ - ╕ 8 ╕ a*b+ ╕ ╕ 7 ╕ 7 ╕ 8 ╕ - ╕ ╕ 5,8 ╕ - ╕ 6,8 ╕ a*b+ ╕ ╕ 6,8 ╕ - ╕ 8 ╕ abb ╕ L----------+-------+-----+-------------- Упражнение: На прошлой лекции была предложена схема постро╕ ения НКА для регулярного выражения, содержащего операции *, |, скобки и конкатенацию. Распространите эту схему на регулярные выражения, допускаемые LEX'ом: 1. Р+, Р?, Р{m,n}, Р{m}, Р{m,}; 2. ^P, P$ (в начале и в конце строки); 3. Р1/P2 (P1, за которым следует Р2). Упражнение: Естественные структуры данных, представляющие ДКА, выделяющий лексемы, просты: состояние s - целое число из диапазона 1..число состояний, Функция переходов - f:(s,c)->s, Рег.выражение - вектор целых с индексом 1..число состояний (элемент вектора - номер регулярного выражения или ноль для состояний автомата, не являющихся конечными). Реализация функции переходов в виде таблицы очень эффективна с точки зрения скорости, но требует слишком много памяти. (Ко╕ нечный автомат типичного сканера может содержать 100-500 состо╕ яний, входной алфавит - 256 символов. Память 25-250 Кбайт, тре╕ буемая для такой таблицы, часто неприемлемо велика.) Предложите достаточно быстрый, но более экономный по памяти способ хранения функции переходов. Разумеется, он должен учиты╕ вать вид "типичной" функции f. Поиск регулярных множеств. Рассмотрим задачу поиска регулярного множества R в цепочке символов L. (Вряд ли она часто встречается при реализации ком╕ пиляторов, но лежит в непосредственной близости от рассматрива╕ емых вопросов и весьма популярна. Так, например, в системе UNIX имеется по крайней мере три программы для решения этой задачи: grep, egrep, fgrep - Get Regular Expression Pattern.) Эта задача, очевидно, эквивалентна задаче принадлежности це╕ почки L регулярному множеству (.*)(R)(.*) и может быть решена построением детерминированного или недетерминированного конеч╕ ного автомата и применением его к цепочке L. Какой из автоматов лучше? Ответ "конечно, детерминированный, т.к. он работает быстрее", в общем случае, неверен. Проблема заключается в том, что существуют семейства регулярных выражений, для которых чис╕ ло состояний минимального ДКА экспоненциально зависит от длины выражения, в то время как число состояний НКА, полученного пря╕ мо из регулярного выражения, линейно зависит от его длины. (Пример такого семейства - упражнение в предыдущей лекции). Это делает невозможным применение ДКА для поиска некоторых регуляр╕ ных множеств, описываемых регулярными выражениями весьма уме╕ ренной длины. Для таких приложений более эффективной чем НКА может ока╕ заться так называемая "ленивая" техника. Она основана на тех же самых идеях, что и виртуальная или cache-память. В этом случае ДКА строится в процессе просмотра цепочки, причем вычисляются и заносятся в cache-буфер только необходимые для данной цепочки состояния и переходы ДКА. По-видимому, можно придумать класс задач, на которых этот метод будет эффективнее ДКА (большой, требующий много времени для вычисления ДКА, в котором реально используется небольшое подмножество). Упражнение: продумайте детали реализации "ленивого" поиска регулярного выражения. Поиск подцепочки. Полученные результаты, примененные к задаче поиска подстроки R (частный случай регулярного выражения) в последовательности символов L дают неплохой результат: ДКА требует время O(|L|+|R|) + время построения ДКА, что для длинных последова╕ тельностей лучше наивного алгоритма, который в худшем случае требует O(|L|*|R|). Весьма неожиданный результат, учитывая не╕ адекватно сложные методы для столь элементарной задачи. Упражнение: докажите, что минимальный ДКА для регулярного выражения (.)*r1r2...rn(.)* имеет ровно n+1 состояние. Вполне естественная задача - придумать столь же эффективный алгоритм поиска подстроки, не требующий трудоемкого процесса построения ДКА. Одно из решений - алгоритм Кнута-Морриса-Пратта Предобработка: для образца поиска R[1:k] вычисляется так на╕ зываемая функция возвратов f[i] - длина самого длинного собственного суффикса цепочки R[1:i], совпадающего с началом R. Другими словами f[i]=j 1<=i<=k, если и только если j (0<=j0 && r[i+1]!=r[s+1] ) s=f[s]; f[i+1] = r[i+1]==r[s+1] ? ++s : 0; } Упражнения: - докажите, что программа правильно вычисляет функцию f; - докажите, что время работы программы O(k). Поиск: /* Поиск подцепочки r[1..k] в цепочке l[1..n] */ for( s=0, i=1; i<=n; i++ ) { while( s>0 && l[i]!=r[s+1] ) s=f[s]; if( l[i]==r[s+1] ) if( ++s == k ) return YES; } return NO; Упражнения: - докажите, что программа правильно ищет вхождение R в L; - докажите, что время работы программы O(k+n); - используя функцию возвратов f, предложите алгоритм, строящий ДКА для выражения (.)*r1r2...rк(.)* за время O(k). Обобщите КМП-алгоритм для поиска одного слова из заданного множества в цепочке символов. Для этого постройте структуру, которую называют бором (переводчики книги Кнута "Искусство программирования для ЭВМ" так перевели термин trie - нечто среднее между tree и retrieval: бор - имеет отношение как к вы╕ БОРке, так и к деревьям). Бор для множества { if, else, endif, end } выглядит так: i --╛ f -T-T╛ --->-+1+->-+╕3╕╕ ╕ L-- L+-+- -+╛ e --╛ n --╛ d -T-T╛ i --╛ f -T--T╛ ╕0+->-+2+->-+4+->-+╕6╕+->-+8+->-+╕10╕╕ L-- LT- L-- L+-+- L-- L+--+- ╕ l --╛ s --╛ e -T-T╛ L-->-+5+->-+7+->-+╕9╕╕ L-- L-- L+-+- - определите функцию возвратов на множестве узлов бора, - предложите алгоритм вычисления функции возвратов за время O(число вершин бора), - предложите линейный алгоритм поиска одного из ключевых слов, использующий функцию возвратов, - используя функцию возвратов, предложите линейный алгоритм построения минимального ДКА для выражения (.)*(W1|...Wn)(.)* Еще один эффективный (по-видимому более быстрый в типичных приложениях) алгоритм изобрели Boyer и Moore в конце 70-х го╕ дов. Идея - сравнивать символы цепочки и образца справа-налево. Несовпадение очередной пары символов часто дает достаточно ин╕ формации для того, чтобы передвинуть образец для следующего сравнения сразу на несколько символов вперед. Так, например достаточно всего двух сравнений, чтобы убедиться, что подстрока "дракон" не содержится в цепочке "абракадабра": абракадабра дракон дракон Упражнение: изобретите алгоритм BM до конца. Упражнение по программированию: аккуратно запрограммируйте несколько алгоритмов поиска подстроки и получите результаты о скорости их работы. Тестовые данные должны включать образцы и строки различной длины и разной природы - например, текстовые и двоичные файлы, случайные последовательности нулей и единиц и т.д. - конец материала к лекции 3 - Материал к лекции 4. КС-языки и грамматики. LL(k)-грамматики. Простейший LL(1)-компилятор. Контекстно-свободные языки Класс контекстно-свободных языков допускает распознавание с помощью недетерминированного КА со стековой (или магазинной) памятью. Контекстно-зависимые языки - последний класс языков, которые можно эффективно распознать с помощью ЭВМ. Специалисты скажут, что они допускаются двусторонними недетерминированными линейно ограниченными автоматами. Для допуска цепочек языка без ограни╕ чений в общем случае требуется универсальный вычислитель (маши╕ на Тьюринга, машина с неограниченным числом регистров и т.п.). Контекстно-зависимые языки и языки без ограничений не использу╕ ются при построении компиляторов и в дальнейшем рассматриваться не будут. Автомат со стековой памятью в отличие от обычного КА имеет стек, в который можно помещать специальные т.н. "магазинные" символы. Переход из одного состояния в другое зависит не только от входного символа, но и от верхних символов магазина (на ри╕ сунке в круглых скобках). В начале работы в магазине лежит спе╕ циальный символ S. При выполнении перехода из магазина удаляются верхние симво╕ лы, соответствующие правилу, и добавляется цепочка символов, соответствующих переходу (на рисунке изображены в квадратных скобках, первый символ цепочки становится верхним символом ма╕ газина). Допускаются также переходы, при которых входной символ игнорируется (и, тем самым, будет входным символом при следу╕ ющем переходе). Эти переходы называются e-переходами. Автомат называется недетерминированным, если при одних и тех же состо╕ янии, входном символе и вершине магазина возможен более чем один переход. Если при окончании цепочки автомат находится в одном из конечных состояний, а стек пуст, цепочка считается до╕ пущенной (после окончания цепочки могут быть сделаны e-перехо╕ ды). -------╛0(S) ------╛1(0) -T---T╛ ╕Начало+---->+ 1 +---->+╕ 2 ╕╕ L-------[0] LT---T- [] L+---+- L-<-- L-<-- 0(0)[00] 1(0)[] Какие цепочки допускает этот автомат? - упражнение. По контекстно-свободной грамматике легко строится недетерми╕ нированный КА с магазинной памятью, который допускает цепочки этого языка. Он использует только одно состояние и следующий набор переходов: e(A)[x] для каждого правила грамматики A:x а(а)[] для каждого терминала а Можно построить и другой автомат, который также содержит од╕ но состояние и имеет следующие переходы: а(е)[а] для каждого терминала а е(x)[A] для каждого правила грамматики A:x Удобно считать, что в начале разбора магазин этого автомата пуст. Тогда в конце разбора в магазине останется символ S. Ка╕ кие (правые или левые) выводы делают (для однозначной граммати╕ ки) только что построенные автоматы? - упражнение. По недетерминированному КА с магазинной памятью можно построить КС-грамматику (упражнение). Таким образом класс КС-языков и класс языков, допускаемых автоматами с магазинной памятью, эквивалентны. К сожалению, не каждый КС-язык допускает разбор с помощью детерминированного автомата. Например, язык цепочек-палиндромов из 0 и 1 не может быть допущен детерминированным КА с магазин╕ ной памятью (как выглядит недетерминированный автомат, допуска╕ ющий этот язык? - упражнение). Таким образом, недетерминирован╕ ные автоматы со стеком могут распознавать более широкий класс языков, чем детерминированные автоматы со стеком - в этом их существенное отличие от КА. Практический интерес для реализации компиляторов представляют детерминированные КС-языки - собственное подмножество КС-языков, допускающее распознавание с помощью детерминированных автоматов с магазинной памятью. Два (недетерминированных) автомата, построенных выше для КС-грамматики определяют два класса методов разбора КС-языков: сверху-вниз снизу вверх. В первом случае (пример - рекурсивный спуск) при просмотре цепочки слева направо естественно будут получаться левые выво╕ ды. При детерминированном разборе проблема будет состоять в том, какое правило применить для раскрытия самого левого нетер╕ минала. Во втором случае детерминированный разбор удобно формализо╕ вать в терминах "сдвиг" (перенос символа из входной цепочки в магазин) и "свертка" (применение к вершине магазина какого-либо правила грамматики). При просмотре входной цепочки слева напра╕ во при этом будут получаться правые выводы. Проблема в этом случае состоит в выборе между сдвигом и сверткой и в выборе правила для свертки. Следующие лекции будут посвящены практи╕ ческим методам разбора детерминированных КС-языков сверху вниз и снизу-вверх. Лемма о разрастании для КС-языков Для каждого КС-языка существует такое число m, что любую принадлежащую языку цепочку z : |z|>m можно разбить на 5 частей n n z = uvwxy : |vx| > 0, |vwx|<=m и цепочки вида uv wx y, n>=0 также принадлежат языку. Доказательство: Пусть КС-грамматика языка содержит q нетер╕ миналов, а самая длинная цепочка в правой части правил имеет длину k. Рассмотрим дерево вывода для цепочки длины k**(2*q+3) и оставим в нем только те ветвления, которые ведут к терминаль╕ ным листьям (игнорируем e-правила). Утверждение: Существует маршрут от корня до кроны, который имеет по крайней мере q+2 левых (или q+2 правых) ветвления (упражнение). Если все вершины дерева пометить раскрытыми нетерминалами, то по крайней мере один из них (например, A) встретится на этом маршруте два раза (упражнение). При это крона дерева естественным образом разобь╕ ется на 5 частей: S / ╕ \ / A \ / / ╕ \ \ / / A \ \ / / / \ \ \ -------------- u v w x y Это и будет искомое разбиение цепочки, так как uvwxy будут удовлетворять требованиям леммы (упражнение). n n n Упражнение: показать, что язык 0 1 2 не является контек╕ стно-свободным. Преобразование КС-грамматик. Проблема эквивалентности двух языков, описываемых различными КС-грамматиками, в общем случае неразрешима. Однако часто уда╕ ется преобразовать грамматику к требуемому для того или иного детерминированного разбора виду не "испортив" описываемый ею язык. Удаление бесполезных символов и правил Назовем символ А бесполезным, если он не встречается ни в одном выводе цепочки терминалов из начального символа граммати╕ ки. Oчевидно, что бесполезные символы и все содержащие их пра╕ вила могут быть удалены из грамматики. Например, в грамматике S : a | A ; A : Ab ; B : b из нетерминала A нельзя вывести ни одной терминальной цепочки, а нетерминал B не может быть выведен из начального символа S. Множество нетерминалов, из которых выводятся терминальные цепочки легко вычислить: K := { A | существует правило A:терминалы }; К1 := пусто; цикл пока К != К1 выполнять К1 := К К := К U { A | существует правило A:(нетерминалы из К1 и и терминалы) } конец цикла Следствие: проблема пустоты КС-языка разрешима - язык пуст, если и только если S не принадлежит K. После удаления из грамматики нетерминалов, не принадлежащих К, несложно найти множество L небесполезных символов: L := {S}; L1 := пусто; цикл пока L != L1 выполнять L1 := L L := L U { B | сущ. правило A:..B.., и А принадлежит L1 } конец цикла После удаления дополнения L из грамматики, она не будет со╕ держать бесполезных символов (доказательство - упражнение). Бу╕ дут ли удалены все бесполезные символы из грамматики, если если применить сначала второй, а затем первый алгоритм? Устранение е-правил Правило вида A:e будем называть e-правилом. Если язык не со╕ держит пустой цепочки, то из грамматики можно удалить все e-правила, в противном случае можно ввести новый начальный сим╕ вол S1, правилo S1 : S | e, и удалить все остальные e-правила. Описание алгоритма - упражнение. Указание: вычислить вначале множество нетерминалов, из которых выводится пустая цепочка. Следствие: КС-язык, не содержащий пустой цепочки, может быть описан неукорачивающей грамматикой. Устранение циклов и цепных правил Обозначим символом :: выводимость одной цепочки из другой с помощью непустой последовательности правил. Назовем циклом вы╕ вод вида A::A... . Для устранения циклов можно удалить из грам╕ матики все цепные правила вида A:B. Для каждого нецепного пра╕ вила вида А:..., добавим в грамматику правила B:..., для всех B, из которых с помощью цепных правил выводится А. После этого удаление цепных правил не изменит языка. Грамматику без циклов, e-правил и лишних символов называют приведенной. Упражнение. Грамматика в нормальной форме Хомского содержит только правила вида A:BC, A:a и S:e, если язык содержит пустую цепочку. Покажите, что любой КС-язык можно описать грамматикой в нормальной форме Хомского. Устранение левой рекурсии Нетерминал A называется рекурсивным, если существует вывод: Если x=e, то A называется леворекурсивным, если y=e, то право╕ рекурсивным. A :: xAy Упражнение: что можно сказать про язык, описанной граммати╕ кой без рекурсивных нетерминалов? Метод рекурсивного спуска не работал для леворекурсивных грамматик. От левой рекурсии всегда можно избавится (Это не оз╕ начает, что метод рекурсивного спуска применим к любому языку.) Покажем вначале, как 8устранить прямую левую рекурсию, т.е. правила вида A:A... . Пусть A : Aa1|...|Aan | b1|...|bn все A-правила грамматики, и ни одна из цепочек bi не начинается с A. Тогда, применяя A-правила к самому левому нетерминалу, из А можно вывести следующее регулярное множество цепочек: (b1|...|bn)(a1|...|an)* Это множество выводится и из преобразованной грамматики: A : b1|...|bn | b1T|...|bnT T : a1|...|an | a1T|...|anT Устранить общую левую рекурсию можно с помощью следующего процесса, напоминающего последовательное исключение переменных при решении системы уравнений методом Гаусса. цикл для i от 1 до n инвариант: для всех k l>k цикл для j от 1 до i-1 инвариант: для всех k l>k каждое правила Ai:Aj... заменить на правила Ai:Lj..., где Lj - все правые части Aj-правил конец цикла устранить прямую левую рекурсию для Ai конец цикла Упражнение. Грамматика в нормальной форме Грейбах содержит только правила вида A:aB, где a-терминал, B - последователь╕ ность (может быть пустая) нетерминалов, а также S:e, если язык содержит пустую цепочку. Покажите, что любой КС-язык можно опи╕ сать грамматикой в нормальной форме Грейбах. Алгоритм Кока-Янгера-Касами Даны: КС-грамматика и цепочка символов. Требуется опреде╕ лить, выводима ли данная цепочка из грамматики. Напомним, что для регулярных языков аналогичная проблема решалась за линейное от длины цепочки время. Рассмотренный ниже алгоритм решает проблему принадлежности цепочки КС-языку за полиномиальное от длины цепочки время. Вначале преобразуем грамматику в нормальную форму Хомского, т.е. в грамматику с правилами вида A:BC и A:a. Пусть a1a2...an - исходная цепочка символов. Построим треугольную таблицу Ti,j: 1<=i<=n, 1<=j<=n-i+1. Тi,j - множество нетерминалов, из которых выводится цепочка терминалов aj...aj+i-1. (подцепочка длины i, левый символ которой имеет индекс j). | T1,j нетерминалы, из которых выводятся односимвольные цепочки цикл для j от 1 до n T1,j := { A | существует правило A:aj } конец цикла | первым шагом вывода из А i-символьной цепочки (i>1) может | быть только применение правила A:BC, где из B выводится левая | подцепочка, а из C - правая, причем обе подцепочки имеют дли╕ | ну меньшую i. Так называемое "динамическое программирование": цикл для i от 2 до n цикл для j от 1 до n-i+1 Tij := пусто цикл для k от 1 до i-1 Tij := Tij U { A | (существует правило A:BC) и (B принадлежит Тk,j) и (C принадлежит Тi-k,j+k) } конец цикла конец цикла конец цикла цепочка выводима из грамматики := S принадлежит Tn,1 Алгоритм требует времени порядка n**3 и памяти n**2, где n - длина цепочки (докажите!). Это делает его малопригодным для практических целей. На практике применяются специальные подклассы КС-грамматик, для которых существуют линейные алго╕ ритмы разбора. LL(k) языки и грамматики Рассмотрим дерево вывода в процессе получения левого вывода цепочки. Промежуточная цепочка в процессе вывода состоит из це╕ почки из терминалов w, самого левого нетерминала A, недовыве╕ денной части x: -S-- / \ / -А-x-\ / ╕ \ -w-+-u---- Для продолжения разбора требуется заменить нетерминал A по одному из правил вида A:y. Если требуется, чтобы разбор был де╕ терминированным (без возвратов), это правило требуется выбирать специальным способом. Говорят, что грамматика имеет свойство LL(k), если для выбора правила оказывается достаточно рассмот╕ реть только wAx и первые k символов непросмотренной цепочки u. Первая буква L (Left, левый) относится к просмотру входной це╕ почки слева направо, вторая - к используемому левому выводу. Определим два множества цепочек: FIRST(x) - множество терминальных цепочек, выводимых из x, укороченных до k символов. FOLLOW(A)- множество укороченных до k символов терминаль╕ ных цепочек, которые могут следовать непос╕ редственно за A в выводимых цепочках. Грамматика имеет свойство LL(k), если из существования двух це╕ почек левых выводов: S :: wAx : wzx :: wu S :: wAx : wtx :: wv из условия FIRST(u)=FIRST(v) следует z=t. В случае k=1 для выбора правила для А, достаточно знать только нетерминал A и а - первый символ цепочки u: следует выбрать правило A:x, если а входит в FIRST(x) следует выбрать правило A:е, если а входит в FOLLOW(A) Покажите, что такой выбор правил непротиворечив - упражнение. Указание: Воспользуйтесь фактом, что для LL(1)-грамматики с правилами A:x и A:y множества FIRST(xFOLLOW(A)) и FIRST(yFOLLOW(A)) не пересекаются (упражнение). Для k>1 это ут╕ верждение неверно (упражнение). Упражнение: предложите алгоритм, вычисляющий множества FIRST и FOLLOW для символов КС-грамматики LL(к)-свойство накладывает довольно сильные ограничения на грамматику. Например, LL(2) грамматика S : aS | a не обладает свойством LL(1), т.к. FIRST(aS)=FIRST(a)={a}. В данном случае можно понизить величину k с помощью "факториза╕ ции" (вынесения множителя за скобку): S : aA A : S | e Любая LL(k)-грамматика однозначна. Леворекурсивная грамматика не принадлежит классу LL(k) ни для какого k. (Доказательство этих двух фактов - упражнение). Иногда удается преобразовать не LL(1)-грамматику в эквивалентную ей LL(1)-грамматику с помощью устранения левой рекурсии и факторизации. Однако проблема су╕ ществования эквивалентной LL(k)-грамматики для произвольной не LL(k)-грамматики неразрешима. Существуют детерминированные языки, которые не являются n n n 2n LL(k) ни для какого k, например - {0 10 U 0 10 | n>=1}. Пример Грамматика для арифметических формул: Ф : Т | Ф + Т Т : М | Т * М M : ( Ф ) | а не является LL(1), т.к. правила для Ф и Т содержат прямую левую рекурсию, устраним ее: ------------------------T------------T------------╛ ╕ ╕ FIRST ╕ FOLLOW ╕ +-----------------------+------------+------------+ ╕ Ф : Т Ф1 ╕ ( a ╕ ) e ╕ ╕ Ф1 : е | + Т Ф1 ╕ + e ╕ ) e ╕ ╕ Т : М Т1 ╕ ( a ╕ + ) e ╕ ╕ Т1 : е | * М Т1 ╕ * e ╕ + ) e ╕ ╕ M : ( Ф ) | а ╕ ( a ╕ * + ) e ╕ L-----------------------+------------+------------- Пустые цепочки порождают только нетерминалы Ф1 и Т1. Более одного правила имеется для нетерминалов Ф1 и Т1; множества FIRST(Ф1), FOLLOW(Ф1) и FIRST(T1), FOLLOW(T1) не пересекаются. Таким образом, преобразованная грамматика является LL(1). Символы e, помещенные в множества FIRST и FOLLOW имеют раз╕ ный смысл и не приводят к конфликтам: e в множестве FIRST ис╕ пользуется для обозначения возможности вывода пустой цепочки из данного нетерминала, e в множестве FOLLOW означает отсутствие следующего символа в конце строки терминалов. На практике роль e во втором случае может играть терминатор строки. Простейший LL(1)-компилятор формул Поскольку действия при LL(1)-разборе зависят только от пары "очередной нетерминал-очередной символ", этот разбор легко зап╕ рограммировать. Рекурсивный спуск - это один из способов коди╕ ровки LL(1)-разбора. Другой способ кодировки таблиц использует╕ ся в следующем компиляторе. Компилятор преобразует цепочки языка, соответствующего грам╕ матике: S: T {+T} Т: E {*Е} Е: <операнд>|(S) в постфиксную запись. %{ /* Коды лексем и метасимволов */ #define ID 1 /* Лексема - идентификатор */ #define META 100 /* Метасимволы грамматики */ #define S (META+0) #define T (META+1) #define E (META+2) /* Коды переходов */ #define NOGO 100 /* Коды завершения разбора */ #define OK (NOGO+1) #define ERR 110 /* Коды ошибок */ %} %% "+"|"*"|"("|")" { return(*yytext); } [A-Z0-9]+ { printf("%s ",yytext); return(ID); } \n { } . { printf("%s: ",yytext); error(0); } %% static lexcode, oldcode; /* Коды очередной и предыдущей лексем */ main() { lexcode = yylex(); parse( S ); printf("\n"); if ( lexcode ) error(4); /* Завершился ли разбор по концу файла? */ } /* * LL(1)-таблицы состоят из четырех полей: * - номер лексемы или метасимвола для сопоставления * - номер действия при успехе (семантическая программа) * - переход при успехе (номер строки/успех/неуспех/ошибка) * - переход при неуспехе */ static char stable[] = { /* LL(1) - таблица для S */ /* 00 */ T, 0, 1, ERR+1, /* 01 */ '+', 1, 2, OK, /* 02 */ T, 2, 1, ERR+1, }; static char ttable[] = { /* LL(1) - таблица для T */ /* 00 */ E, 0, 1, ERR+2, /* 01 */ '*', 1, 2, OK, /* 02 */ E, 2, 1, ERR+2, }; static char etable[] = { /* LL(1) - таблица для E */ /* 00 */ ID, 0, OK, 1, /* 01 */ '(', 0, 2, NOGO, /* 02 */ S, 0, 3, ERR+1, /* 03 */ ')', 0, OK, ERR+3, }; /* Указатели на LL(1) - таблицы */ static char *blocks[] = { stable, ttable, etable, }; /* * Интерпретатор LL(1)-таблиц * Вход: m - лексема или метасимвол * Результат: 1, когда сопоставление удалось */ parse (m) { register char *block, *p, sign; if ( m'. Грамматика называется грамматикой простого предшествования, если она приведенная, обратимая и между любыми двумя терминала╕ ми или нетерминалами выполняется не более одного отношения предшествования. Практически отношения предшествования можно вычислить следу╕ ющим образом (X,Y - терминалы или нетерминалы, A,B,C-нетермина╕ лы, y - терминал, ... - любая цепочка (м.б. пустая)): X =' Y, если в грамматике есть правило A : ...XY... X <' Y, если в грамматике есть правило A : ...XB... и B :: Y... X >' y, если в грамматике есть правило A : ...By... или A : ...BC... и B :: ...X и C :: y... Вычисляя отношения предшествования для грамматики S:aSSb|c, получим: a='S, S='S, S='b, {a,S} <' {a,c}, {b,c} >' {a,b,c}. Эта грамматика является грамматикой простого предшествования. На практике иногда удобно считать, что в начале и конце це╕ почки языка стоят символы-ограничители #. Для них отношения предшествования определяются так: # <' X, если S :: X... X >' #, если S :: ...X В нашем примере {b,c} >' #, # <' {a,c}. Отметим, что отношения <',>',=' не похожи на обычные арифме╕ тические отношения <, >, = : =' не является отношением эквива╕ лентности, <' и >' не обязательно транзитивны. Отношения предшествования удобно занести в матрицу, в кото╕ рой строки и столбцы помечены терминалами и нетерминалами грам╕ матики. Упражнение: заполните эту матрицу. Что значит ситуация, в которой между символами не выполняется ни одного из отношений предшествования? Грамматики операторного предшествования Если в правилах приведенной обратимой грамматики не встреча╕ ются рядом два нетерминала, говорят, что грамматика является операторной. Классический пример - грамматика арифметических формул. Для таких грамматик можно вычислять отношения пред╕ шествования только на множестве терминальных символов. Для это╕ го модифицируем правила вычисления отношений предшествования: a =' b, если в грамматике имеется правило A : ...ab... или A : ...aBb... a <' b, если в грамматике имеется правило A : ...aB... и B :: b... или B :: Cb... a >' b, если в грамматике имеется правило A : ...Bb... и B :: ...a или B :: ...aC # <' a, если в грамматике имеется вывод S :: Ca... или S :: a... a >' #, если в грамматике имеется вывод S :: ...aC или S :: ...a Если между любыми двумя терминалами выполняется не более од╕ ного отношения предшествования, операторная грамматика называ╕ ется грамматикой операторного предшествования. Вычислим матрицу операторного предшествования для грамматики арифметических формул: ----T------------╛ ╕ ╕ ( a * + ) #╕ S : S + T | T +---+------------+ T : T * E | E ╕ ) ╕ > > > >╕ E : (S) | a ╕ a ╕ > > > >╕ ╕ * ╕ < < > > > >╕ ╕ + ╕ < < < > > >╕ ╕ ( ╕ < < < < = ╕ ╕ # ╕ < < < < ╕ L---+------------- Эти отношения позволяют определять терминалы, входящие в правую часть сворачиваемого правила, но не нетерминалы. Однако, при практическом разборе формул нет необходимости различать не╕ терминалы S, T и E. Они были введены только для придания грам╕ матике однозначности и учета приоритета и ассоциативности опе╕ раций. Теперь, получив отношения предшествования, можно вновь заменить эти искуственно введенные нетерминалы на S: S : S+S | S*S | (S) | a и получить разбор, обрабатывая все нетерминалы одинаково. Линеаризация матрицы предшествования Для компактного хранения матрицы предшествования часто можно использовать следующий прием. По матрице M[n][n], элементы ко╕ торой принимают только три значения (<' =' >'), попытаемся построить два целочисленных вектора f и g: M[i][j] равно >', если f[i]>g[j] M[i][j] равно <', если f[i] g[c] ) { do { d = stpop(); printf ("%s",view[d]); } while ( f[sttop()]==g[d] ); } stpush(c); } while(c!=EF); } /* Реализация стека терминалов */ #define MAXSTK 100 static int stack[MAXSTK], *stptr; stinit() { stptr = stack+MAXSTK; } stpush(e) { if ( stptr==stack ) error(1); *--stptr = e; } sttop() { stcheck(); return(*stptr); } stpop() { stcheck(); return(*stptr++); } stcheck() { if (stptr==stack+MAXSTK) error(1); } static char *ermsg[] = { /* Тексты сообщений об ошибках */ /* 00 */ "ошибочный символ", /* 01 */ "отказ", }; error(e) { printf ("%s\n", ermsg[e]); exit(1); } yywrap() { return(1); } Задачи для решения на ЭВМ: 1. Переделайте компилятор так, чтобы он не допускал ошибочных (т.е. не порождаемых грамматикой) цепочек. 2. Добавьте в компилятор операцию возведения в степень (право╕ ассоциативная операция "^" с наивысшим приоритетом). 3. Переделайте компилятор формул в интерпретатор. 4. Добавьте в компилятор операцию "унарный минус". - конец материала к лекции 5 - Материал к лекции 6. LR(k)-грамматики. SLR(1), LALR(1) - грамматики. Если в процессе LR-разбора принять детерминированное решение о сдвиге/свертке удается, рассматривая только цепочку x и пер╕ вые k символов непросмотренной части входной цепочки u (эти k символов называют аванцепочкой), говорят, что грамматика обла╕ дает LR(k)-свойством. -S-- / \ /-x╛ \ --w-+--u-- Различие между LL(k)- и LR(k)-грамматиками в терминах дерева вывода: -S- / ╕ \ / A \ / / \ \ -w-+-v-+-u- В случае LL(k)-грамматик однозначно определить правило, приме╕ ненное к A, можно по w и первым k символам vu, а в случае LR(k)-грамматик - по w,v и первым k символам u. Это нестрогое рассуждение показывает, что LL(k)-языки < LR(k)-языки (опро╕ вергните его для k=0). LR(0)-грамматики Рассмотрим вначале наиболее простые грамматики этого класса - LR(0). При разборе строки LR(0)-языка можно вообще не исполь╕ зовать аванцепочку - выбор между сдвигом и сверткой делается на основании цепочки x (см.картинку). Так как в процессе разбора она изменяется только с правого конца, ее называют стеком. Бу╕ дем считать, что в грамматике нет бесполезных символов и на╕ чальный символ не встречается в правых частях правил - тогда свертка к начальному символу сигнализирует об успешном заверше╕ нии разбора. Попробуем описать множество цепочек из терминалов и нетерминалов, появляющихся в стеке в процессе всех LR-разбо╕ ров (другими словами - всех правых выводов из грамматики). Определим следующие множества: L(A:v) - левый контекст правила A:v - множество состояний стека, непосредственно перед сверткой v в A в ходе всех успеш╕ ных LR-разборов. Очевидно, каждая цепочка из L(A:v) кончается на v. Если у всех таких цепочек отрезать хвост v, то получится множество цепочек, встречающихся слева от A в процессе всех ус╕ пешных правых выводов. Обозначим это множество L(A) - левый контекст нетерминала A. Упражнение: показать, что данное определение корректно, т.е. множество L(A) не зави╕ сит от выбора правила A:v. Построим грамматику для множества L(A). Терминалами новой грамматики будут терминалы и нетерминалы исходной грамматики, нетерминалы новой грамматики обозначим ,... - их значени╕ ями будут левые контексты нетерминалов исходной грамматики. Ес╕ ли S - начальный символ исходной грамматики, то грамматика ле╕ вых контекстов будет содержать правило : e - левый контекст S содержит пустую цепочку Для каждого правила исходной грамматики, например, A : B C d E добавим в новую грамматику правила: : - L(B) включает L(A) : B - L(C) включает L(A) B : B C d - L(E) включает L(A) B C d Упражнение: показать, что L(A) не содержит других цепочек, кро╕ ме выводимых из грамматики. Полученная грамматика имеет специальный вид (такие граммати╕ ки называются леволинейными), следовательно, множества левых контекстов - регулярны. Из этого следует, что принадлежность цепочки левому контексту какого-либо нетерминала можно вычис╕ лять индуктивно с помощью конечного автомата, просматривая це╕ почку слева направо. Опишем этот процесс конструктивно. Назовем LR(0)-ситуацией правило грамматики с одной отмечен╕ ной позицией между символами правой части правила. Например, для грамматики S:A ; A:aAA ; A:b существуют следующие LR(0)-си╕ туации: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; A:_b; A:b_. (позиция обозначена символом подчеркивания). Будем говорить, что цепочка x согласована с ситуацией А:b_c, если x=ab и a принадлежит L(A). (Другими словами, LR-вывод мо╕ жет быть продолжен x_... = ab_... :: abc_... :: aA_... :: S_ .) В этих терминах L(A:b) - множество цепочек, согласованных с си╕ туацией A:b_, L(A) - цепочки, согласованные с ситуацией A:_b, для любого правила A:b. Пусть V(u) - множество ситуаций, согласованных с u. Покажем, что функция V - индуктивна. Если в множество V(u) входит ситуация A:b_cd, то ситуация A:bc_d принадлежит V(uc). (c - терминал или нетерминал; b, d - последовательности (может быть пустые) терминалов и нетермина╕ лов). Других ситуаций вида A:b_d, с непустым b в V(uc) нет. Ос╕ талось добавить в V(uc) ситуации вида C:_..., для каждого не╕ терминала C, левый контекст которого содержит uc. Если ситуация A:..._C... (C-нетерминал) принадлежит множеству V(uc), то uc принадлежит L(C) и V(uc) включает в себя ситуации вида C:_... для всех C-правил грамматики. Упражнение: показать, что других ситуаций V(uc) не содержит. V(e) содержит ситуации S:_... (S-начальный символ), а также ситуации A:_..., если нетерминал A встречается непосредственно после _ в ситуациях, уже включенных в V(e). Пример: построим функцию V для грамматики S:A; A:aAA; A:b. 0 V(e) = { S:_A; A:_aAA, A:_b } 1 V(A) = { S:A_ } 2 V(a) = { A:a_AA; A:_aAA, A:_b } V(aa)=V(a); V(ab)=V(b); 3 V(b) = { A:b_ } 4 V(aA) = { A:aA_A; A:_aAA, A:_b } V(aAa)=V(a);V(aAb)=V(b); 5 V(aAA) = { A:aAA_ } Наконец, мы готовы дать определение LR(0)-грамматики. Пусть u - содержимое стека в процессе LR-разбора, V(u)-множество LR(0) ситуаций, согласованных с u. Если V(u) содержит ситуацию вида А:x_ (x-последовательность терминалов и нетерминалов), то u принадлежит L(A:x) и допустима свертка x в A. Если V(u) со╕ держит ситуацию A:..._a... (а-терминал), то допустим сдвиг. Го╕ ворят о конфликте сдвиг-свертка, если для одной цепочки u до╕ пустимы и сдвиг, и свертка. Говорят о конфликте свертка- свертка, если допустимы свертки по различным правилам. Грамматика называется LR(0), если для всех состояний стека в процессе LR-вывода нет конфликтов сдвиг-свертка или свертка-свертка. Рассмотренная выше грамматика является LR(0)-грамматикой. Ее функция V принимает 6 различных значений (вычисляется конечным автоматом с 6 состояниями). В состояниях 0,2,4 возможен только сдвиг, в состоянии 3 - свертка по правилу A:b, в состоянии 5 - свертка A:aAA, в состоянии 1 - свертка S:A - т.е. успешное за╕ вершение разбора. Остается показать, как можно построить парсер, разбирающий предложения LR(0)-языка. Чтобы не вычислять значение функции V заново для каждого нового состояния стека, будем хранить в сте╕ ке вместе с каждым символом xi значение V на цепочке (x0...xi). стек.сделать пустым стек.добавить ( '#', начальное состояние ) цикл . выбор из V ( стек.вершина.состояние ).действие . . "сдвиг" => . . прочитать очередной символ в ( новый символ ) . . "свертка" => . . удалить правую часть правила из стека . . новый символ := левая часть правила . . "успех" => . . стоп( "успех" ) . конец выбора . старое состояние := V ( стек.вершина.состояние ) . новое состояние := старое состояние . переход [новый символ] . если новое состояние = "Ошибка" то стоп( "ошибка" ) кесли . стек.добавить ( новый символ, новое состояние ) конец цикла Таблицы LR(0)-парсера для грамматики 1) S:A; 2) A:aAA; 3) A:b. --T------T-------------T----------------------╛ ╕ ╕ Пре╕ ╕ Действие ╕ Переход ╕ ╕ ╕ фикс ╕ ╕ A a b ╕ +-+------+-------------+----------------------+ ╕0╕ e ╕ сдвиг ╕ 1 2 3 ╕ ╕1╕ A ╕ успех ╕ Ошибка Ошибка Ошибка ╕ ╕2╕ a ╕ сдвиг ╕ 4 2 3 ╕ ╕3╕ b ╕ свертка 3,А ╕ Ошибка Ошибка Ошибка ╕ ╕4╕ aA ╕ сдвиг ╕ 5 2 3 ╕ ╕5╕ aAA ╕ свертка 2,А ╕ Ошибка Ошибка Ошибка ╕ L-+------+-------------+----------------------- LR(k)-грамматики Для выбора между сдвигом или сверткой в LR(0) разборе ис╕ пользуется только состояние стека. В LR(k) разборе учитывается также k-первых символов непросмотренной части входной цепочки (так называемая аванцепочка). Для обоснования метода следует аккуратно повторить рассуждения предыдущего параграфа, внеся изменения в определения. Будем включать в левый контекст правила также аванцепочку. Если в правом выводе применяется вывод wAu : wvu, то пара {wv,FIRSTk(u)} принадлежит Lk(A:v), а пара {w,FIRSTk(u)} - Lk(A). Множество левых контекстов, как и в случае LR(0), можно вычислять с помощью индукции по левой цепочке. Назовем LR(k)-ситуацией пару: правило грамматики с отмеченной позицией и аванцепочку длины не более k. Отделять правило от аванцепочки будем вертикальной чертой. Будем говорить, что цепочка x согласована с ситуацией А:b_c|t если существует LR-вывод: x_yz = ab_yz :: abc_z :: aA_z :: S_, и FIRSTk(z)=t. Правила индуктивного вычисления множества состояний Vk следующие: Vk(e) содержит ситуации S:_a|e для всех правил S:a, где S-начальный символ. Для каждой ситуации А:_Ba|u из Vk(e), каж╕ дого правила B:b и цепочки x, принадлежащей FIRSTk(au), надо добавить в Vk(e) ситуацию B:_b|x. Если в Vк(w) входит ситуация A:b_cd|u, то ситуация A:bc_d|u будет принадлежать Vk(wc). Для каждой ситуации А:b_Cd|u из Vk(wc), каждого правила C:f и цепочки x, принадлежащей FIRSTk(du) надо добавить в Vk(wc) ситуацию C:_f|x. Пример: построим функцию V1 для грамматики S:A; A:AaAb|e. 0 V1(e) = { S:_A|e; A:_AaAb|e,a, A:_|e,a } 1 V1(A) = { S:A_|e, A:A_aAb|e,a } 2 V1(Aa) = { A:Aa_Ab|e,a; A:_AaAb|a,b, A:_|a,b } 3 V1(AaA) = { A:AaA_b|e,a, A:A_aAb|a,b } 4 V1(AaAa) = { A:Aa_Ab|a,b; A:_AaAb|a,b, A:_|a,b } 5 V1(AaAb) = { A:AaAb_|e,a } 6 V1(AaAaA) = { A:AaA_b|a,b A:A_aAb|a,b } V1(AaAaAa)=V1(AaAa) 7 V1(AaAaAb)= { A:AaAb_|a,b } ( A:_AaAb|e,a - сокращенная запись двух LR(1)-ситуаций: A:_AaAb|e и A:_AaAb|а ) Используем построенные множества LR(k)-состояний для разре╕ шения вопроса сдвиг-свертка. Пусть u - содержимое стека, а x - аванцепочка. Очевидно, что свертка по правилу A:b может быть проведена, если Vk(u) содержит ситуацию A:b_|x. Решение вопроса о допустимости сдвига требует аккуратности, если в грамматике имеются e-правила. В ситуации A:b_c|t (c не пусто) сдвиг возмо╕ жен, если c начинается с терминала и x принадлежит FIRSTk(ct). Неформально говоря, можно занести в стек самый левый символ правой части правила, подготавливая последующую свертку. Если c начинается с нетерминала (ситуация имеет вид A:b_Cd|t), то за╕ нести в стек символ, подготавливая свертку в C, можно только в случае, если C не порождает пустую цепочку. Например, в состо╕ янии V(e)={ S:_A|e; A:_AaAb|e,a, A:_|e,a } нет допустимых сдви╕ гов, т.к. при выводе из A терминальных цепочек на некотором ша╕ ге требуется применить правило A:e к нетерминалу A, находящему╕ ся на левом конце цепочки. Определим множество EFFk(x), состоящее из всех элементов множества FIRSTk(x), при выводе которых нетерминал на левом конце x (если он есть) не заменяется на пустую цепочку. В этих терминах сдвиг допустим, если в множестве Vk(u) есть ситуация А:b_c|t, c не пусто и x принадлежит EFFk(ct). Грамматика называется LR(k)-грамматикой, если ни одно LR(k) состояние не содержит двух ситуаций A:b_|u и B:c_d|v, таких что u принадлежит EFFk(dv). Такая пара соответствует конфликту свертка-свертка, если d пусто, и конфликту сдвиг-свертка, если d не пусто. LR(k)-парсер устроен аналогично LR(0). Действие из множества {сдвиг, свертка, успех, ошибка}, выполняемое на очередном шаге LR-разбора, есть функция от состояния стека Vk(u) и аванцепочки x: сдвиг, если A:b_c|t содержится в Vk(u), c!=e, x из EFF(ct); свертка, если A:a_|x содержится в Vk(u); успех, если S:A|e содержится в Vk(u); ошибка в остальных случаях. Таблицы LR(1)-парсера для грамматики S:A; A:AaAb|e. --T-------T----------------------T---------------------╛ ╕ ╕Префикс╕ Действие ╕ Переход ╕ ╕ ╕ ╕ a b e ╕ a b А ╕ +-+-------+----------------------+---------------------+ ╕0╕ e ╕ Св.0,А Ошибка Св.0,А ╕ Ошибка Ошибка 1 ╕ ╕1╕ A ╕ Сдвиг Ошибка Успех ╕ 2 Ошибка Ошибка╕ ╕2╕ Aa ╕ Св.0,А Св.0,А Ошибка ╕ Ошибка Ошибка 3 ╕ ╕3╕ AaA ╕ Сдвиг Сдвиг Ошибка ╕ 4 5 Ошибка╕ ╕4╕ AaAa ╕ Св.0,А Св.0,А Ошибка ╕ Ошибка Ошибка 6 ╕ ╕5╕ AaAb ╕ Св.4,А Ошибка Св.4,А ╕ Ошибка Ошибка Ошибка╕ ╕6╕ AaAaA ╕ Сдвиг Сдвиг Ошибка ╕ 4 7 Ошибка╕ ╕7╕ AaAaAb╕ Св.4,А Св.4,А Ошибка ╕ Ошибка Ошибка Ошибка╕ L-+-------+----------------------+---------------------- Упражнение: запрограммируйте интерпретатор LR(k)-таблиц. На практике LR(k)-грамматики при k>1 не применяются. На это имеются две причины. Первая: очень большое число LR(k) состо╕ яний. Вторая: для любого языка, определяемого LR(k)-граммати╕ кой, существует LR(1)-грамматика; более того, для любого детер╕ минированного КС-языка существует LR(1)-грамматика. Число LR(1)-состояний для практически интересных грамматик также весьма велико. LR(0) свойством такие грамматики обладают редко. На практике чаще всего используются промежуточные между LR(0) и LR(1) методы, известные под названиями SLR(1) и LALR(1). SLR(1) и LALR(1) грамматики. В основе этих двух методов лежит одна и та же идея. Построим множество канонических LR(0)-состояний грамматики. Если это множество не содержит конфликтов, то можно применить LR(0)-пар╕ сер. Иначе попытаемся разрешить возникшие конфликты, рассматри╕ вая односимвольную аванцепочку. Другими словами, попробуем построить LR(1) парсер с множеством LR(0)-состояний. В SLR(1) грамматиках (Simple LR(1) - простых LR(1)-граммати╕ ках) для разрешения конфликтов используется множество FOLLOW(X) - множество терминалов, встречающихся после X. Если в состоянии имеется ситуация A:b_, свертка допускается, если только аванце╕ почка принадлежит FOLLOW(A). Грамматика является SLR(1)-грамматикой, если для двух любых LR(0) ситуаций из одного состояния A:a_b и B:c_d выполняется одно из следующих условий: - b!=e, d!=e (конфликта нет, требуется сдвиг); - b=d=e и FOLLOW(A) не пересекается с FOLLOW(B) (конфликт "свертка/свертка" может быть устранен с учетом аванце╕ почки); - b=e, d<>e и FOLLOW(A) не пересекается с EFF(tFOLLOW(B)) (конфликт "сдвиг/свертка" может быть устранен с учетом аванцепочки). Построим LR(0)-состояния для грамматики арифметических фор╕ мул: S:E; E:E+T|T; T:T*F|F; F:(E)|a. 0 V(e) ={ S:_E; E:_E+T, E:_T, T:_T*F, T:_F, F_a, F:_(E) } 1 V(E) ={ S:E_, E:E_+T } 2 V(T) ={ E:T_, T:T_*F, 3 V(F) ={ T:F_ } 4 V(a) ={ F:a_ } 5 V(() ={ F:(_E); E:_E+T, E:_T, T:_T*F, T:_F, F_a, F:_(E) } 6 V(E+) ={ E:E+_T; T:_T*F, T:_F, F_a, F:_(E) } 7 V(T*) ={ T:T*_F; F:_a, F:_(E) } 8 V((E) ={ F:(E_), E:E_+T } (T=T; (F=F; (a=a; ((=( 9 V(E+T)={ E:E+T_, T:T_*F } E+F=F; E+a=a; E+(=( 10 V(T*F)={ T:T*F_ } T*a=a; T*(=( 11 V((E))={ F:(E)_ } (Е+=Е+; Е+Т*=Т* LR(0)-конфликты возникают в состояниях 1,2,9, но 1: FOLLOW(S) = {е}, FIRST(+T) = {+} 2: FOLLOW(E) = {+,),e} FIRST(*F) = {*} 9: FOLLOW(E) = {+,),e} FIRST(*F) = {*}, следовательно, конфликты разрешаются с использованием SLR(1) техники и грамматика является SLR(1)-грамматикой. Таблицы SLR(1)-парсера для грамматики арифметических формул ---T-------------------------T--------------------------------╛ ╕ ╕ Действие ╕ Переход ╕ ╕ ╕ e + * а ( ) ╕ + * а ( ) E T F ╕ +--+-------------------------+--------------------------------+ ╕0 ╕ Ош Ош Ош Сдв Сдв Ош ╕ Ош Ош 4 5 Ош 1 2 3 ╕ ╕1 ╕ Усп Сдв Ош Ош Ош Ош ╕ 6 Ош Ош Ош Ош Ош Ош Ош ╕ ╕2 ╕ 1,E 1,E Сдв Ош Ош 1,E ╕ Ош 7 Ош Ош Ош Ош Ош Ош ╕ ╕3 ╕ 1,T 1,T 1,T Ош Ош 1,T ╕ Ош Ош Ош Ош Ош Ош Ош Ош ╕ ╕4 ╕ 1,F 1,F 1,F Ош Ош 1,F ╕ Ош Ош Ош Ош Ош Ош Ош Ош ╕ ╕5 ╕ Ош Ош Ош Сдв Сдв Ош ╕ Ош Ош 4 5 Ош 8 2 3 ╕ ╕6 ╕ Ош Ош Ош Сдв Сдв Ош ╕ Ош Ош 4 5 Ош Ош 9 3 ╕ ╕7 ╕ Ош Ош Ош Сдв Сдв Ош ╕ Ош Ош 4 5 Ош Ош Ош 10 ╕ ╕8 ╕ Ош Сдв Ош Ош Ош Сдв ╕ 6 Ош Ош Ош 11 Ош Ош Ош ╕ ╕9 ╕ 3,Е 3,Е Ош Ош Ош 3,Е ╕ Ош 7 Ош Ош Ош Ош Ош Ош ╕ ╕10╕ 3,Т 3,Т 3,Т Ош Ош 3,Т ╕ Ош Ош Ош Ош Ош Ош Ош Ош ╕ ╕11╕ 3,F 3,F 3,F Ош Ош 3,F ╕ Ош Ош Ош Ош Ош Ош Ош Ош ╕ L--+-------------------------+--------------------------------- LALR(1)-метод (Look Ahead - заглядывание вперед) заключается в следущем. Введем на множестве LR(1)-ситуаций отношение экви╕ валентности: будем считать две ситуации эквивалентными, если они различаются только аванцепочками. Например, ситуации A:Aa_Ab|e и A:Aa_Ab|a эквивалентны. Построим каноническое мно╕ жество LR(1)-состояний и объединим состояния, состоящие из мно╕ жества эквивалентных ситуаций. Например, LR(1) состояния 2 и 4 грамматики S:A; A:AaAb|e эк╕ вивалентны: 2 V1(Aa) = { A:Aa_Ab|e,a; A:_AaAb|a,b, A:_|a,b } 4 V1(AaAa) = { A:Aa_Ab|a,b; A:_AaAb|a,b, A:_|a,b } и могут быть объединены в одно состояние 2+4 V1(Aa) = { A:Aa_Ab|e,a,b; A:_AaAb|a,b, A:_|a,b } Также эквивалентны состояния 3,6 и 5,7 этой грамматики. Если полученное множество состояний не содержит LR(1) конфликтов, и, следовательно, позволяет построить LR(1)-парсер, то говорят, что грамматика обладает свойством LALR(1). Например, грамматика S:A; A:AaAb|e является LALR(1), Таблицы LALR(1)-парсера для грамматики S:A; A:AaAb|e. ----T-------T----------------------T---------------------╛ ╕ ╕Префикс╕ Действие ╕ Переход ╕ ╕ ╕ ╕ a b e ╕ a b А ╕ +---+-------+----------------------+---------------------+ ╕ 0╕ e ╕ Св.0,А Ошибка Св.0,А ╕ Ошибка Ошибка 1 ╕ ╕ 1╕ A ╕ Сдвиг Ошибка Успех ╕ 2 Ошибка Ошибка╕ ╕2+4╕ Aa ╕ Св.0,А Св.0,А Ошибка ╕ Ошибка Ошибка 3+6 ╕ ╕3+6╕ AaA ╕ Сдвиг Сдвиг Ошибка ╕ 4 5+7 Ошибка╕ ╕5+7╕ AaAb ╕ Св.4,А Св.4,А Св.4,А ╕ Ошибка Ошибка Ошибка╕ L---+-------+----------------------+---------------------- Заметим, что при слиянии канонических LR(1)-состояний, раз╕ личающихся только аванцепочками, получается множество канони╕ ческих LR(0)-состояний, для каждой ситуации которого вычислено множество допустимых аванцепочек (Докажите!). Следовательно, SLR(1) и LALR(1) методы при успешном применении дают одинаковые таблицы парсера. Метод LALR(1) применим к более широкому классу грамматик, чем SLR(1). Это объясняется тем, что отношение FOLLOW(A), применяемое при вычислении допустимых аванцепочек в SLR(1)-методе не использует всю доступную информацию - оно не зависит от левого контекста правила A:... Действительно, су╕ ществуют LALR(1)- грамматики, не принадлежащие классу SLR(1). Упражнение: покажите, что грамматика является LALR(1), но не SLR(1): S:L=R|R; L:*R|a; R:L Упражнение: к какому типу принадлежат следующие грамматики? 1) S:Aa|dAb|cb|dca; A:c; 2) S:Aa|dAb|Bb|dBa; A:c; B:c 3) S:Aa|dAb|Bb|dBa|c; A:c; B:c - конец материала к лекции 6 - Материал к лекции 7. YACC Программа YACC (Yet Another Compiler Compiler) предназначенa для построения синтаксического анализатора контекстно-свободно╕ го языка. Анализируемый язык описывается с помощью грамматики в виде, близком форме Бэкуса-Наура (НФБН). Результатом работы YACC'a является программа на Си, реализующая восходящий LALR(1) распознаватель. Структура YACC-программы YACC-программа состоит из трех секций, разделенных символом %% - секции описаний, секции правил, в которой описывается грамматика, и секции программ, содержимое которой просто копи╕ руется в выходной файл. Пример простейшей программы на YACC'e: %token name %start e %% e : e '+' m | e '-' m | m ; m : m '*' t | m '/' t | t ; t : name | '(' e ')' ; %% Секция правил содержит информацию о том, что символ name яв╕ ляется лексемой (терминалом) грамматики, а символ e - ее на╕ чальным нетерминалом. Грамматика записана обычным образом - идентификаторы обозна╕ чают терминалы и нетерминалы, символьные константы типа '+' '-' - терминалы. Символы : | ; - принадлежат метаязыку и читаются "есть по определению", "или" и "конец правила" соответственно. Разрешение конфликтов Написанная грамматика (она обладает свойством LALR(1) - уп╕ ражнение) задает язык арифметических формул, в котором приори╕ тет '*' и '/' выше приоритета '+' и '-', a все операции левоас╕ социативны. Для указания этих свойств языка в грамматику введе╕ ны дополнительные нетерминалы m, и t. Другая грамматика этого языка: e : e '+' e | e '-' e | e '*' e | e '/' e | '(' e ')' | name ; не однозначна (и, следовательно, не LALR(1)). Попытка применить YACC для анализа данной грамматики приведет к многочисленным (16) неразрешенным конфликтам типа сдвиг/свертка (shift/reduce) в построенном автомате. Если рассмотреть конфликты более под╕ робно, выясняется, что в каждом случае можно однозначно выбрать между сдвигом или сверткой, основываясь на приоритетах операций и порядке выполнения равноприоритетных операций слева направо. (Аналогично простому и операторному предшествованию). YACC позволяет дополнить грамматику информацией такого рода и получить бесконфликтный распознаватель: %token name %left '+' '-' %left '*' '/' %% e : e '+' e | e '-' e | e '*' e | e '/' e | '(' e ')' | name ; %% Предложения %left, %right и %nonassoc в секции описаний при╕ писывают всем перечисленным за ними символам одинаковый приори╕ тет и соответствующее значение ассоциативности. (Отсутствие ас╕ социативности означает недопустимость выражений вида a @ b @ c) Приоритет увеличивается сверху вниз для каждого нового предло╕ жения. LALR(1)-конфликты сдвиг/свертка или свертка/свертка разреша╕ ются выбором более приоритетного действия. Приоритет сдвига ра╕ вен приоритету считываемой лексемы. Приоритет свертки равен приоритету самой правой лексемы в правиле, по которому произво╕ дится свертка. Можно также явно указать приоритет свертки, на╕ писав "%prec <лексема>" справа от правила. Добавить в язык формул операцию унарного минуса, более при╕ оритетную, чем бинарные операции, можно следующим образом: %token name %left '+' '-' %left '*' '/' %left UMIN %% e : e '+' e | e '-' e | e '*' e | e '/' e | '(' e ')' | name ; e : '-' e %prec UMIN ; %% Фиктивная лексема UMIN используется только для задания при╕ оритета свертки по правилу e : '-' e ; Итак, YACC разрешает конфликты (если они возникнут) по сле╕ дующим правилам: - если приоритеты альтернативных действий определены и раз╕ личны, то выполняется действие с б`ольшим приоритетом; - если приоритеты действий определены и одинаковы, то в слу╕ чае левой ассоциативности выбирается свертка, в случае правой ассоциативности - сдвиг, если они неассоциативны - возбуждается ошибочная ситуация; - иначе (приоритет хотя бы одной из альтернатив не специфи╕ цирован) в случае конфликта сдвиг/свертка выполняется сдвиг, а в случае конфликта свертка/свертка - свертка по правилу, опре╕ деленному выше по тексту в описании грамматики, в обоих случаях YACC сообщает о неразрешенном конфликте в этом состоянии. Отметим, что для конфликтной грамматики с правилами s : if '(' e ')' s | if '(' e ')' s else s ; предпочтение сдвига "правильно" разрешает конфликт при разборе выражения if( e ) if( e ) s _ else s - else будет отнесено к ближайшему if'у, как и принято в алго╕ лоподобных языках. Для конфликтной грамматики арифметических формул, эти прави╕ ла приводят к вычислению выражения справа-налево без учета при╕ оритетов операций. Семантические действия С каждым правилом грамматики может быть связано действие, которое будет выполнено при свертке по данному правилу. Оно за╕ писывается в виде заключенной в фигурные скобки последователь╕ ности операторов языка Си, расположенной после правой части со╕ ответствующего правила. statement : IF '(' expr ')' statement { if_ctr++; } | WHILE '(' expr ')' statement { while_ctr++; } | assign_st { ass_ctr++; } ; В этом примере действие if_ctr++ будет выполнено после раз╕ бора всего оператора if. При необходимости выполнить семанти╕ ческие действия, например, сразу после вычисления выражения expr, можно поместить их между символами правой части правила. statement: IF '(' expr { action_1 } ')' statement { action_2 } ; В этих случаях YACC автоматически преобразует грамматику, вводя дополнительные нетерминалы и соответствующие им правила с пус╕ той правой частью. При их свертке и будут выполнены действия, расположенные между символами исходной грамматики. statement: IF '(' expr void_1 ')' statement { action_2 } ; void_1: { action_2 } ; Семантический стек Для естественного обмена данными между действиями, каждый терминал или нетерминал может иметь значение. Для доступа к не╕ му в действиях используются псевдопеременные $$ - значение ле╕ вого символа правила, $ - значение i-ого символа правой час╕ ти правила (символы нумеруются слева направо, начиная с 1). Другими словами, кроме обычного стека состояний построенный YACC'ом анализатор содержит "семантический" стек, содержащий значения символов. Значения имеют тип YYSTYPE, который по умол╕ чанию определяется как int. Действие expr : expr '+' expr { $$ = $1 + $3; } ; может быть использовано в интерпретаторе формул, в котором зна╕ чение нетерминала "выражение" есть его вычисленное значение. Если для правила не указано никакого действия, или действие не содержит упоминания псевдопеременной $$, то значение левой части правила становится равным значению первого символа правой части, т.е. неявно выполняется действие { $$ = $1; }. Значение очередной лексемы копируется из переменной int yylval, в кото╕ рую его обычно заносит сканер. Различные символы грамматики могут иметь значения разных ти╕ пов. Для этого следует определить тип YYSTYPE как union и спе╕ цифицировать тип терминалов и нетерминалов в разделе описаний. При этом будет осуществляться контроль типов при использовании псевдопеременных, а обращение к ним будет транслироваться в об╕ ращение к соответствующему полю union. %{ #define YYSTYPE yys typedef union { int intval; long longval; nodeptr *ptrval; } yys; %{ %token ICONST %token LCONST %type expr Если в качестве внутреннего представления программы исполь╕ зуется дерево, удобно иметь в качестве значения нетерминала указатель на соответствующий ему узел дерева. Кодировка лексем и интерфейс Файл, порождаемый YACC'ом в процессе работы, содержит табли╕ цы LALR(1)-анализатора и Си-текст функции int yyparse( void ), реализующей интерпретатор таблиц и семантические действия. Для запуска парсера достаточно вызвать эту функцию. В случае успеш╕ ного разбора она возвращает 0, в случае ошибки - 1. Для получения очередной лексемы парсер вызывает функцию int yylex( void ). Она должна возвратить код лексемы и поместить ее значение в переменную YYSTYPE yylval. Код лексемы - положительное целое число. Лексемам, заданным в виде символьных констант, соответствует их код в наборе сим╕ волов ЭВМ (обычно ASCII), лежащий в диапазоне 0..255. Лексемам, имеющим символические имена, присваиваются коды начиная с 257. Выходной файл содержит операторы #define, определяющие имена лексем как их коды. Если имена лексем требуются в других фай╕ лах, следует указать ключ -d при запуске YACC'а, и он продубли╕ рует эти определения в файле y.tab.h. Этот файл следует вклю╕ чить в другие файлы программы (например, сканер), использующие коды лексем. Обработка ошибок Если анализируемое предложение не соответствует языку, то в некоторый момент возникнет ошибочная ситуация, т.е. парсер ока╕ жется в состоянии, в котором не предусмотрено ни сдвига, ни свертки для полученной ошибочной лексемы. Обычная реакция пар╕ сера - вызов функции void yyerror( const char * ) с аргументом "Syntax error" и завершение работы - возврат из функции yyparse с значением 1. Реализация функции yyerror возлагается на поль╕ зователя, и он может попытаться организовать в ней выдачу более разумной диагностики (при использовании YACC-парсера это не яв╕ ляется тривиальной задачей). Во многих случаях желательно как-нибудь продолжить разбор. Для восстановления после ошибки YACC содержит следующие средства. Имеется специальная лексема с именем error, которая может употребляться в грамматике. При возникновении ошибки ус╕ танавливается флаг ошибки, вызывается функция yyerror, а затем из стека состояний удаляются элементы, пока не встретится сос╕ тояние, допускающее лексему error. При обнаружении такого сос╕ тояния выполняется сдвиг, соответствующий лексеме error в этом состоянии и разбор продолжается. Если при установленном флаге ошибки снова возникает ошибочная ситуация, то для избежания многократных сообщений yyerror не вызывается, а ошибочная лек╕ сема игнорируется. Флаг ошибки сбрасывается только после трех успешно считанных лексем. Специальными действиями в правилах, обрабатывающих ошибочные ситуации можно более активно вмешиваться в этот процесс. yyerrok() - сбрасывает флаг ошибки yyclearin() - удаляет просмотренную вперед ошибочную лексему Макро YYERROR явным образом возбуждает ошибочную ситуацию. Пример: statement : .... | error ';' при возникновении ошибки внутри statement продолжение разбора возможно только начиная с ';' - в результате будут пропущены все лексемы до точки с запятой, которая затем будет свернута в нетерминал statement. Разное Запустить YACC в ОS UNIX можно командой: yacc [-v] [-d] имя_файла. Результат работы (текст на Си) записывается в файл y.tab.c Ключи: v - создать текстовый файл y.output с описанием состояний и конфликтов построенного анализатора d - создать файл y.tab.h с определениями лексем. В версиях YACC'а для других систем имена файлов и ключей могут быть другими, например: -i -d, имя_входного_файла.(i,c,h) в RSX11M и RT11 y.out, ytab.c ytab.h в системах с файловой системой MS-DOS Фрагмент файла y.output: state 3 stat : expr_ (4) expr : expr_+ expr + shift 11 . reduce 4 Описано состояние (state) 3, соответствующее двум основным си╕ туациям. В этом состоянии символ '+' вызывает сдвиг (shift) и переход в состояние 11, а любой другой символ - свертку (reduce) по правилу 4 - stat : expr. Пример простейшего интерпретатора формул %token ICONST %left '+' '-' %left '*' '/' %% p : /* empty */ | p s ; s : e '\n' { printf( "%d\n", $1 ); } | error '\n' ; e : e '+' e { $$ = $1 + $3; } | e '-' e { $$ = $1 - $3; } | e '*' e { $$ = $1 * $3; } | e '/' e { $$ = $1 / $3; } | '(' e ')'{ $$ = $2; } | ICONST; ; %% #include main() { yyparse(); } yyerror( mes ) char *mes; { printf( "%s\n", mes ); } yylex() { int c, d; while((c=getchar())==' '); /* Skip spaces */ if( c>='0' && c<='9' ) { /* Integer constant */ for( d=c-'0'; (c=getchar()) >='0' && c<='9'; ) d=d*10+c-'0'; ungetc( c, stdin ); yylval = d; return ICONST; } return c; /* Others */ } - конец материала к лекции 7 -