Введение в теорию построения оптимизирующих компиляторов, 02 лекция (от 26 сентября)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1397 участника 212.112.242.89 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | <P STYLE="margin-bottom: 0cm">Оптимизация компиляторов 26.09.06</P> |
- | + | <P STYLE="margin-bottom: 0cm"><BR> | |
- | + | </P> | |
- | + | <P STYLE="margin-bottom: 0cm">Для автоматической генерации | |
+ | синтаксических анализаторов существуют специальные программы, такие | ||
+ | как уacc/bison. yacc – yet anpther compiler compiler, первая | ||
+ | статья, в которй он упоминается – Johnson, 1974.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">К 70 годам теория синтаксического | ||
+ | анализа была разработана достаточно хорошо. Один из столпов — | ||
+ | Кнут.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">КС-грамматика: O(n^3), O(n^2)/ Это | ||
+ | недоспустимо по скорости, посему нужны граматики, у которых анализ | ||
+ | проводится за линейное время – грамматики, разбор которых | ||
+ | проводится методом рекурсивного спуска (LL(1)). Также есть, но не | ||
+ | будут раззматриваться (LR(1), LALR(1))</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Метод рекурсивного спуска – | ||
+ | начинаем с S и постпенно спускаемся вниз, раскрывая альтернативы, | ||
+ | доходя до листьев дерева разбора. Если рассмотреть это в терминах | ||
+ | цепочки, то есть уже просмотренная часть цепочки A=a1...an, | ||
+ | просмотренная часть – a1...a(p-1)<BR>, текущий символ, которфый | ||
+ | доступен – ap, дальше – непростмотренная часть. При | ||
+ | нисходящем рек спуске необходимо определить по текущемц символу и | ||
+ | просомтренной части, как разобрать оставшуюся часть, выбрать одну из | ||
+ | альтернатив. В большинстве ситуаций отдного символа из входного | ||
+ | текста недостаточно, в этом случае говорят о LL(K) – | ||
+ | грамматиках, в которых заглядывается не на 1, а на К симвлов вперед. | ||
+ | Но в современных ЯП есть типовые ситуации, которые не разбираются ни | ||
+ | при каких К. Поэтому нужно расширять язык, в соответствии с | ||
+ | извращениями – заглядывать на n симоволов вперёд, вычисление | ||
+ | предикатов и т. д. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">У LR-анализаторов подход другой. | ||
+ | Начинаем с терминала и поднимаемся к S. Работает так – есть | ||
+ | разобранная часть, есть текущий символ, доступный для чтения, и есть | ||
+ | непросомотренная часть дальше. Состояние автомата, то есть та часть | ||
+ | цепочки, коотрую он успел просомотреть, имеется в виде стека, то есть | ||
+ | есть некооторый стек. На стеке находтся продукты переработ\ки | ||
+ | исходного текста, в частности, терминальбные и нетерм симоволы. На | ||
+ | основании очсередного символа атвтомат может произвксти одно из | ||
+ | четырёх действий:</P> | ||
+ | <OL> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Shift – сдвиг. Добавляем | ||
+ | очередной симвлол в стек</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Reduce. Берём некоторую часть из | ||
+ | того, что просмотрели (она лежит в стеке). Для этой части должно | ||
+ | существовать некоторое правило в грамматике, и заменяем их на | ||
+ | нетерм, соотв правилу (A1A2A3 -> A, если есть правило A = | ||
+ | A1A2A3). Отличие от LL анализа в том, что в нём альтернативы | ||
+ | начинаются с ap, в LR же ap есть последний символ альтернативы. И | ||
+ | замена на нетерминал производится, когда все символы альтернативы | ||
+ | уже накопились, поэтому класс LR(1) языков шире класса LL(1), более | ||
+ | того, он его включает в себя. Более того, Кнут доказал, что LR(1) | ||
+ | эквивалентен LL(k). В LR есть стек, идут замены, и постепенно | ||
+ | сворачиваем входную цепочку. Сам по себе разбор, то есть определение | ||
+ | принадлежности имеет мало смысла, в процессе разбора нужно делать | ||
+ | что-то ещё, например, построение дерева разбора. Возможно, | ||
+ | одновременно с этим будет работать интерпретатор, строиться таблицы | ||
+ | и т д. Понятно,Ю чот выполнение семант действий возможно только вл | ||
+ | время erduce. В этом случае в момент замены можно выполнять | ||
+ | произвольные действия, У автомата есть свой стек, и есть стек | ||
+ | пользоваьтельских элементов, и семант дейчствие, выполняемое при | ||
+ | свёртке, этому сем действию доступны аттрибуты, соответствующие | ||
+ | частям правила, и после замены в стеке аттрибутов останется новый | ||
+ | аттрибут. A:=f(a1,a2,a3). Никаких других действий во время разбора | ||
+ | быть не может. Такая схема аттрибутных вычислений называется | ||
+ | S-аттрибутированными грамматиками. При LR разборе идём снизу вверх, | ||
+ | при этой замене можно выполнять произвольные действия, при этом | ||
+ | аттрибуты заменяются соответственно.</P> | ||
+ | </OL> | ||
+ | <P STYLE="margin-bottom: 0cm">Пример:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Как же это реализуется в инструменте, | ||
+ | который мы будем рассматривать? Основной секцией файла описания языка | ||
+ | является секция описания грамматики. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">%{</P> | ||
+ | <P STYLE="margin-bottom: 0cm">С-код</P> | ||
+ | <P STYLE="margin-bottom: 0cm">%}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Произвольные декларации, необходимые | ||
+ | для работы анализатора</P> | ||
+ | <P STYLE="margin-bottom: 0cm">%%</P> | ||
+ | <P STYLE="margin-bottom: 0cm">грамматика. В виде</P> | ||
+ | <P STYLE="margin-bottom: 0cm">L : R1 | R2 | R3</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Эта запись эквивалентна | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">L : R1</P> | ||
+ | <P STYLE="margin-bottom: 0cm">L : R2</P> | ||
+ | <P STYLE="margin-bottom: 0cm">L : R3</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Произвольные действия могут выполнятся | ||
+ | после записи альтернативы, т е | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">L : R1 {};</P> | ||
+ | <P STYLE="margin-bottom: 0cm">%%</P> | ||
+ | <P STYLE="margin-bottom: 0cm">С-код</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Первый прагматический аспект: интерфейс | ||
+ | с лексическим анализатором. Это то как, парсер будет получать символ | ||
+ | от анализатора. Бизон обычно получает очередной символ от int | ||
+ | yylex(), причём</P> | ||
+ | <P STYLE="margin-bottom: 0cm">0 – EOF</P> | ||
+ | <P STYLE="margin-bottom: 0cm">1-255 – соотв символы ASCII</P> | ||
+ | <P STYLE="margin-bottom: 0cm">всё, что больше 257 можно использовать | ||
+ | для объявления сложных лексем. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Кроме того, объявляется yylval, куда | ||
+ | анализатор может записывать различную информацию. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Как определить тип yylval? Простейший | ||
+ | способ – в разделе кода поределить тип YYSTYPE, то есть yylval | ||
+ | имеет тип YYSTYPE. Тогда дополнительная информация будет этого типа, | ||
+ | И все промежуточные вычисления будут этого типа. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Вторая альтернатива – | ||
+ | использовать директиву %union. Она означает то де самое, что и union | ||
+ | на языке Си, которая превратится в соответствующий union в | ||
+ | результирующем файле. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">%union {</P> | ||
+ | <P STYLE="margin-bottom: 0cm">struct ichinfo i; - селекторы полей, | ||
+ | которые распознаются бизоном, и которые можно использовать</P> | ||
+ | <P STYLE="margin-bottom: 0cm">struct valinfo v;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">struct treeinfo t;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Требуются ещё константы для составных | ||
+ | лексем языка. В частности, если есть ключевые слова, нужно по | ||
+ | константе на ключ слово, нужны спец константы для составных | ||
+ | разделителей, нужны спец константы для идентификаторо, чисел и т. д. | ||
+ | Соотв, нужно в разделе деклараций описать вс етипы клексем, которые | ||
+ | будут использоваться.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Есть директива %ещлут? С помощью | ||
+ | Которой перечисляются все декларации. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">%token TOK_INT</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Если используется %union, то нужно явно | ||
+ | указывать селектор. И должны явно использоваться только определённые | ||
+ | типы.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Второй вариант (более интересный): | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">%token TOK_VOID «void»</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Тогда в грамматике можно использовать | ||
+ | не константу, а строку. И читабельность грамматики резко повышается. | ||
+ | Теперь можно писать</P> | ||
+ | <P STYLE="margin-bottom: 0cm">type : TOK_INT | «void»</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Если мы хотим задать то поле, с которым | ||
+ | %token будет работать по умолчанию, то мы можем указать</P> | ||
+ | <P STYLE="margin-bottom: 0cm">%token <t> TOK_FOR «for»</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Этим говорим, что везде, где | ||
+ | исподльзуется TOK_FOR, мы используем поле t. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Все константы попадают в .h файл и | ||
+ | будут использоваться. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Предположим есть некоторе правило:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">stmt: «it» '(' expr ')' | ||
+ | stmt | if '(' expr ')' «else» stmt</P> | ||
+ | <P STYLE="margin-bottom: 0cm">LR грамматике совершенно всё равно, что | ||
+ | начала одинаковые.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">На момент reduce в стеке лежат все | ||
+ | элементы, пронуерованные с 1, причём для правил нумерация | ||
+ | независимая. В стеке аттрибутов находятся значения типа yystype, и к | ||
+ | ним можно обращаться, используя $n, где n – номер лексемы, т е | ||
+ | $1 - «if», $2 - '(', и т д. Соответственно, с этими | ||
+ | долларами мы можем делать всё, что хотим – строить дерево, | ||
+ | вычислять... Результат всего будет записываться в переменную $$. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Пример (простой): Как выглядит | ||
+ | вычисление выражения:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">%{</P> | ||
+ | <P STYLE="margin-bottom: 0cm">#define YYSTYPE double</P> | ||
+ | <P STYLE="margin-bottom: 0cm">%}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">%token TOK_NUM</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">%%</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">expr « expr '+' expr1 {$$ = $1 + | ||
+ | $3}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> | expr '-' expr1 {$$ = $1 - $3}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> | expr1 {$$ = $1}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">expr1 : expr1 '*' expr2 {$$ = $1 * $3}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> | expr1 '*' expr2 {$$ = $1 / $3}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> | expr2 {$$ = $1}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">expr2 : TOK_NUM {$$ = $1}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> | '(' expr ')' {$$ = $2}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">// - (Чернов) Вы нажали волшебную | ||
+ | кнопочку? - Нет, а что? - Просто зашумело что-то...</P> | ||
+ | <P STYLE="margin-bottom: 0cm">//Всякие спецэффекты, типа деления на | ||
+ | ноль, я не учитываю...</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Это леворекурсивные выражения. A = AC | | ||
+ | C</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Они убивают LL наповал. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Для LR ЛР-выражения предпочтительный. | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Как будет работать автомат с отчки | ||
+ | правой рекурсии?</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">CCCCCCCCC</P> | ||
+ | <OL> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Сдвигает C</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Сдвигает C</P> | ||
+ | </OL> | ||
+ | <P STYLE="margin-bottom: 0cm">...</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Когда дошли до конца, Можем делать | ||
+ | замену. И делаем её, пока в стеке не останется одно А.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Левая рекурсия:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Сразу делаем замену A=C, потом A=AC, | ||
+ | потом...</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">В случае правой рекурсии стек достигает | ||
+ | максимальной длины, в левой рекурсии замена идёт сразу.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">В случае правой рекурсии будет | ||
+ | неправильная ассоциативность.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Понятно, что отнюдь не всегда можно | ||
+ | вычислить значение выражения. Можно также строить дерево разбора. К | ||
+ | сожалению, як и бизон деревья сами не строят, и это надо делать | ||
+ | вручную.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">В дереве имеется несколько типов | ||
+ | объектов.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Сейчас мы сами опишем тип, который | ||
+ | будет использоваться при анализе</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Struct parseinfo</P> | ||
+ | <P STYLE="margin-bottom: 0cm">{</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> int tag; - всевозможные типы лексем и | ||
+ | узлов деревьев</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> double val; - значение</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> struct parseinfo * left, * right;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">#define YYSTYPE struct parseinfo *</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">В чём будет заключаться работа | ||
+ | анализатора? Вместо вычислений будем строить дерево.</P> | ||
+ | <P STYLE="margin-bottom: 0cm">expr « expr '+' expr1 { ... }</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> | expr '-' expr1 { ... }</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> | expr1 {$$ = $1}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">expr1 : expr1 '*' expr2 {$$ = | ||
+ | make_tree(MODE_MUL, $1, $3); }</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> | expr1 '*' expr2 { ... }</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> | expr2 {$$ = $1}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">expr2 : TOK_NUM {$$ = $1}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> | '(' expr ')' {$$ = $2}</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">После анализа будет доступен корень | ||
+ | дерева разбора, с которым мы можем делать всё, что захотим.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">То, что строится здесь, это не совсем | ||
+ | дерево разбора. Например, для a+b*c деревом разбора было бы, реально | ||
+ | же хотелось бы строить немного сокращённое дерево, что мы и строим.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">В более сложных случаях (if) для ифа | ||
+ | будет переменное количество сыновей. Как строить деревья разбора в | ||
+ | этом случае? Есть три подхода:</P> | ||
+ | <OL> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Каждый элемент хранит ссылку вниз | ||
+ | и ссылку вправо. Плюсы: фиксированный размер структуры. Минусы – | ||
+ | долго ходить по ссылкам. Кроме того, есть такой минус: рассмотрим | ||
+ | for: «for» '(' [expr] ';' [expr] ';' [expr] ')' stmt. | ||
+ | Некорректно оно из-за квадратных скобок. Первый вариант – | ||
+ | написать 8 варианто. Второй – добавить expropt : expr {$$=$1;} | ||
+ | | {$$=0;}. В этом случае построение дерева резко усложняется. | ||
+ | Появляется много пустых листьев, которые нельзя игнорировать.</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Можно строить структуры, у которых | ||
+ | все потенциальные поддеревья, которы еопименованы. То есть:</P> | ||
+ | </OL> | ||
+ | <P STYLE="margin-bottom: 0cm">struct ifstmt</P> | ||
+ | <P STYLE="margin-bottom: 0cm">{</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> struct expr * expr;</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> struct stmt *stmtthen;</P> | ||
+ | <P STYLE="margin-bottom: 0cm"> struct stmt *stmtelse;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Плюсы – все потенциальные | ||
+ | поддеревья доступны по имени. Поджидает следующая засада – | ||
+ | начнётся невогласование типов в большом количестве. Вторая засада – | ||
+ | есть дерево и надо просто его обойти. В этом случае простейшая | ||
+ | процедура обхода превратится в огромный свитч, ибо каждый тип узла | ||
+ | надо рассматривать отдельно. Ещё один недостаток – структура | ||
+ | имеет переменный размер.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Мнение Чернова: в компиляторе | ||
+ | виртуальные функции не нужны. Ибо всё по ним размазывается.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <OL START=3> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">В каждой вершине хранить массив | ||
+ | ссылок. | ||
+ | </P> | ||
+ | </OL> | ||
+ | <P STYLE="margin-bottom: 0cm">Есть два варианта – сильно | ||
+ | извращённый вариант и не сильно извращённый вариант</P> | ||
+ | <P STYLE="margin-bottom: 0cm">struct node</P> | ||
+ | <P STYLE="margin-bottom: 0cm">{</P> | ||
+ | <P STYLE="margin-bottom: 0cm">int tag;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">int n;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">struct node ** p;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">Более извращённый вариант:</P> | ||
+ | <P STYLE="margin-bottom: 0cm">struct node</P> | ||
+ | <P STYLE="margin-bottom: 0cm">{</P> | ||
+ | <P STYLE="margin-bottom: 0cm">int tag;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">int n;</P> | ||
+ | <P STYLE="margin-bottom: 0cm">struct node * p[0];</P> | ||
+ | <P STYLE="margin-bottom: 0cm">}</P> | ||
+ | <P STYLE="margin-bottom: 0cm">С ним работать чуть сложнее, но меньше | ||
+ | на одно выделение памяти.</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">Какие возникают вопросы:</P> | ||
+ | <OL> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Управление памятью</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Ошибки и восстановление после | ||
+ | ошибок</P> | ||
+ | </OL> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <P STYLE="margin-bottom: 0cm">//При ошибке завершать работу и | ||
+ | говорить «Извините, не смогла». Ну, не смогла, так не | ||
+ | смогла.</P> | ||
+ | <P STYLE="margin-bottom: 0cm">//Восстановление после ошибок – | ||
+ | чёрная магия</P> | ||
+ | <P STYLE="margin-bottom: 0cm">//Что делать, когда грамматика не | ||
+ | грамматится?</P> | ||
+ | <P STYLE="margin-bottom: 0cm"><BR> | ||
+ | </P> | ||
+ | <OL START=3> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Конфликты в грамматиках.</P> | ||
+ | <LI><P STYLE="margin-bottom: 0cm">Что | ||
+ | </P> | ||
+ | </OL> | ||
+ | |||
+ | |||
+ | {{Введение в теорию построения оптимизирующих компиляторов}} | ||
+ | {{Lection-stub}} |
Текущая версия
Оптимизация компиляторов 26.09.06
Для автоматической генерации синтаксических анализаторов существуют специальные программы, такие как уacc/bison. yacc – yet anpther compiler compiler, первая статья, в которй он упоминается – Johnson, 1974.
К 70 годам теория синтаксического анализа была разработана достаточно хорошо. Один из столпов — Кнут.
КС-грамматика: O(n^3), O(n^2)/ Это недоспустимо по скорости, посему нужны граматики, у которых анализ проводится за линейное время – грамматики, разбор которых проводится методом рекурсивного спуска (LL(1)). Также есть, но не будут раззматриваться (LR(1), LALR(1))
Метод рекурсивного спуска –
начинаем с S и постпенно спускаемся вниз, раскрывая альтернативы,
доходя до листьев дерева разбора. Если рассмотреть это в терминах
цепочки, то есть уже просмотренная часть цепочки A=a1...an,
просмотренная часть – a1...a(p-1)
, текущий символ, которфый
доступен – ap, дальше – непростмотренная часть. При
нисходящем рек спуске необходимо определить по текущемц символу и
просомтренной части, как разобрать оставшуюся часть, выбрать одну из
альтернатив. В большинстве ситуаций отдного символа из входного
текста недостаточно, в этом случае говорят о LL(K) –
грамматиках, в которых заглядывается не на 1, а на К симвлов вперед.
Но в современных ЯП есть типовые ситуации, которые не разбираются ни
при каких К. Поэтому нужно расширять язык, в соответствии с
извращениями – заглядывать на n симоволов вперёд, вычисление
предикатов и т. д.
У LR-анализаторов подход другой. Начинаем с терминала и поднимаемся к S. Работает так – есть разобранная часть, есть текущий символ, доступный для чтения, и есть непросомотренная часть дальше. Состояние автомата, то есть та часть цепочки, коотрую он успел просомотреть, имеется в виде стека, то есть есть некооторый стек. На стеке находтся продукты переработ\ки исходного текста, в частности, терминальбные и нетерм симоволы. На основании очсередного символа атвтомат может произвксти одно из четырёх действий:
Shift – сдвиг. Добавляем очередной симвлол в стек
Reduce. Берём некоторую часть из того, что просмотрели (она лежит в стеке). Для этой части должно существовать некоторое правило в грамматике, и заменяем их на нетерм, соотв правилу (A1A2A3 -> A, если есть правило A = A1A2A3). Отличие от LL анализа в том, что в нём альтернативы начинаются с ap, в LR же ap есть последний символ альтернативы. И замена на нетерминал производится, когда все символы альтернативы уже накопились, поэтому класс LR(1) языков шире класса LL(1), более того, он его включает в себя. Более того, Кнут доказал, что LR(1) эквивалентен LL(k). В LR есть стек, идут замены, и постепенно сворачиваем входную цепочку. Сам по себе разбор, то есть определение принадлежности имеет мало смысла, в процессе разбора нужно делать что-то ещё, например, построение дерева разбора. Возможно, одновременно с этим будет работать интерпретатор, строиться таблицы и т д. Понятно,Ю чот выполнение семант действий возможно только вл время erduce. В этом случае в момент замены можно выполнять произвольные действия, У автомата есть свой стек, и есть стек пользоваьтельских элементов, и семант дейчствие, выполняемое при свёртке, этому сем действию доступны аттрибуты, соответствующие частям правила, и после замены в стеке аттрибутов останется новый аттрибут. A:=f(a1,a2,a3). Никаких других действий во время разбора быть не может. Такая схема аттрибутных вычислений называется S-аттрибутированными грамматиками. При LR разборе идём снизу вверх, при этой замене можно выполнять произвольные действия, при этом аттрибуты заменяются соответственно.
Пример:
Как же это реализуется в инструменте, который мы будем рассматривать? Основной секцией файла описания языка является секция описания грамматики.
%{
С-код
%}
Произвольные декларации, необходимые для работы анализатора
%%
грамматика. В виде
L : R1 | R2 | R3
Эта запись эквивалентна
L : R1
L : R2
L : R3
Произвольные действия могут выполнятся после записи альтернативы, т е
L : R1 {};
%%
С-код
Первый прагматический аспект: интерфейс с лексическим анализатором. Это то как, парсер будет получать символ от анализатора. Бизон обычно получает очередной символ от int yylex(), причём
0 – EOF
1-255 – соотв символы ASCII
всё, что больше 257 можно использовать для объявления сложных лексем.
Кроме того, объявляется yylval, куда анализатор может записывать различную информацию.
Как определить тип yylval? Простейший способ – в разделе кода поределить тип YYSTYPE, то есть yylval имеет тип YYSTYPE. Тогда дополнительная информация будет этого типа, И все промежуточные вычисления будут этого типа.
Вторая альтернатива – использовать директиву %union. Она означает то де самое, что и union на языке Си, которая превратится в соответствующий union в результирующем файле.
%union {
struct ichinfo i; - селекторы полей, которые распознаются бизоном, и которые можно использовать
struct valinfo v;
struct treeinfo t;
}
Требуются ещё константы для составных лексем языка. В частности, если есть ключевые слова, нужно по константе на ключ слово, нужны спец константы для составных разделителей, нужны спец константы для идентификаторо, чисел и т. д. Соотв, нужно в разделе деклараций описать вс етипы клексем, которые будут использоваться.
Есть директива %ещлут? С помощью Которой перечисляются все декларации.
%token TOK_INT
Если используется %union, то нужно явно указывать селектор. И должны явно использоваться только определённые типы.
Второй вариант (более интересный):
%token TOK_VOID «void»
Тогда в грамматике можно использовать не константу, а строку. И читабельность грамматики резко повышается. Теперь можно писать
type : TOK_INT | «void»
Если мы хотим задать то поле, с которым %token будет работать по умолчанию, то мы можем указать
%token <t> TOK_FOR «for»
Этим говорим, что везде, где исподльзуется TOK_FOR, мы используем поле t.
Все константы попадают в .h файл и будут использоваться.
Предположим есть некоторе правило:
stmt: «it» '(' expr ')' stmt | if '(' expr ')' «else» stmt
LR грамматике совершенно всё равно, что начала одинаковые.
На момент reduce в стеке лежат все элементы, пронуерованные с 1, причём для правил нумерация независимая. В стеке аттрибутов находятся значения типа yystype, и к ним можно обращаться, используя $n, где n – номер лексемы, т е $1 - «if», $2 - '(', и т д. Соответственно, с этими долларами мы можем делать всё, что хотим – строить дерево, вычислять... Результат всего будет записываться в переменную $$.
Пример (простой): Как выглядит вычисление выражения:
%{
#define YYSTYPE double
%}
%token TOK_NUM
%%
expr « expr '+' expr1 {$$ = $1 + $3}
| expr '-' expr1 {$$ = $1 - $3}
| expr1 {$$ = $1}
expr1 : expr1 '*' expr2 {$$ = $1 * $3}
| expr1 '*' expr2 {$$ = $1 / $3}
| expr2 {$$ = $1}
expr2 : TOK_NUM {$$ = $1}
| '(' expr ')' {$$ = $2}
// - (Чернов) Вы нажали волшебную кнопочку? - Нет, а что? - Просто зашумело что-то...
//Всякие спецэффекты, типа деления на ноль, я не учитываю...
Это леворекурсивные выражения. A = AC | C
Они убивают LL наповал.
Для LR ЛР-выражения предпочтительный.
Как будет работать автомат с отчки правой рекурсии?
CCCCCCCCC
Сдвигает C
Сдвигает C
...
Когда дошли до конца, Можем делать замену. И делаем её, пока в стеке не останется одно А.
Левая рекурсия:
Сразу делаем замену A=C, потом A=AC, потом...
В случае правой рекурсии стек достигает максимальной длины, в левой рекурсии замена идёт сразу.
В случае правой рекурсии будет неправильная ассоциативность.
Понятно, что отнюдь не всегда можно вычислить значение выражения. Можно также строить дерево разбора. К сожалению, як и бизон деревья сами не строят, и это надо делать вручную.
В дереве имеется несколько типов объектов.
Сейчас мы сами опишем тип, который будет использоваться при анализе
Struct parseinfo
{
int tag; - всевозможные типы лексем и узлов деревьев
double val; - значение
struct parseinfo * left, * right;
}
#define YYSTYPE struct parseinfo *
В чём будет заключаться работа анализатора? Вместо вычислений будем строить дерево.
expr « expr '+' expr1 { ... }
| expr '-' expr1 { ... }
| expr1 {$$ = $1}
expr1 : expr1 '*' expr2 {$$ = make_tree(MODE_MUL, $1, $3); }
| expr1 '*' expr2 { ... }
| expr2 {$$ = $1}
expr2 : TOK_NUM {$$ = $1}
| '(' expr ')' {$$ = $2}
После анализа будет доступен корень дерева разбора, с которым мы можем делать всё, что захотим.
То, что строится здесь, это не совсем дерево разбора. Например, для a+b*c деревом разбора было бы, реально же хотелось бы строить немного сокращённое дерево, что мы и строим.
В более сложных случаях (if) для ифа будет переменное количество сыновей. Как строить деревья разбора в этом случае? Есть три подхода:
Каждый элемент хранит ссылку вниз и ссылку вправо. Плюсы: фиксированный размер структуры. Минусы – долго ходить по ссылкам. Кроме того, есть такой минус: рассмотрим for: «for» '(' [expr] ';' [expr] ';' [expr] ')' stmt. Некорректно оно из-за квадратных скобок. Первый вариант – написать 8 варианто. Второй – добавить expropt : expr {$$=$1;} | {$$=0;}. В этом случае построение дерева резко усложняется. Появляется много пустых листьев, которые нельзя игнорировать.
Можно строить структуры, у которых все потенциальные поддеревья, которы еопименованы. То есть:
struct ifstmt
{
struct expr * expr;
struct stmt *stmtthen;
struct stmt *stmtelse;
}
Плюсы – все потенциальные поддеревья доступны по имени. Поджидает следующая засада – начнётся невогласование типов в большом количестве. Вторая засада – есть дерево и надо просто его обойти. В этом случае простейшая процедура обхода превратится в огромный свитч, ибо каждый тип узла надо рассматривать отдельно. Ещё один недостаток – структура имеет переменный размер.
Мнение Чернова: в компиляторе виртуальные функции не нужны. Ибо всё по ним размазывается.
В каждой вершине хранить массив ссылок.
Есть два варианта – сильно извращённый вариант и не сильно извращённый вариант
struct node
{
int tag;
int n;
struct node ** p;
}
Более извращённый вариант:
struct node
{
int tag;
int n;
struct node * p[0];
}
С ним работать чуть сложнее, но меньше на одно выделение памяти.
Какие возникают вопросы:
Управление памятью
Ошибки и восстановление после ошибок
//При ошибке завершать работу и говорить «Извините, не смогла». Ну, не смогла, так не смогла.
//Восстановление после ошибок – чёрная магия
//Что делать, когда грамматика не грамматится?
Конфликты в грамматиках.
Что
Введение в теорию построения оптимизирующих компиляторов
Календарь
вт | вт | вт | вт | вт | |
Сентябрь
| 19 | 26 | |||
Октябрь
| 10 | 24 | 31 | ||
Ноябрь
| 07 | 14 | 21 | ||
Декабрь
| 05 | 12 |