| Текущая версия |
Ваш текст |
| Строка 1: |
Строка 1: |
| - | <P STYLE="margin-bottom: 0cm">Оптимизация компиляторов 10.10.06</P>
| + | == From Ebaums Inc to MurkLoar. == |
| - | <P STYLE="margin-bottom: 0cm"><BR>
| + | We at EbaumsWorld consider you as disgrace of human race. |
| - | </P>
| + | Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated. |
| - | <OL>
| + | Dig yourself a grave - you will need it. |
| - | <LI><P STYLE="margin-bottom: 0cm">Восстановление после ошибок –
| + | |
| - | способность паремера разумным образом восстановить что могло бы быть
| + | |
| - | в месте синтаксической ошибки и продолжить разбор. Часто возникает
| + | |
| - | ситуация, когда парсер восстанавливается неправильно. Следствием
| + | |
| - | являются наведённые ошибки. Чем меньше наведенных ошибок, тем лучше
| + | |
| - | восстановление. Особый интерес представляет синтакс разбор. Синт
| + | |
| - | разбор – есть две стратегии – удаляе м либо добавляем
| + | |
| - | токены до возможности продолжения. Як и бизон реализуют
| + | |
| - | восстановление с помощью удаления лексем. Если мы специфицируем
| + | |
| - | грамматику, то восстановление после ошибок тоже можно возложить на
| + | |
| - | генератор. В контексте нисходящего анализа это сделать проще,
| + | |
| - | восходящего – сложнее. У бизона и яка нет автоматического
| + | |
| - | восстановления, есть только ручное. Реализация: в грамматике
| + | |
| - | допускается лексема с названием error. Это якобы лексема, которая не
| + | |
| - | являетс лексемой. В како момент парсер может зафиксировать ошибки:</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">1. неожиданный конец файла</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">2. состояние + текущий символ не
| + | |
| - | существует ни операции ни сдвига, ни свёртки. Например: x=(a+)+c.
| + | |
| - | Тогда, прочитав x=(a+, и имея текущий символ ), просматривая таблицу
| + | |
| - | свёртки обнаруживаем, что такого символа не предусмотрена –
| + | |
| - | ошибка. Как в такой ситуации поступает Як/Бизон. У него есть стек
| + | |
| - | состояний. При ошибке начинаем из стека выбрасывать состояния, пока
| + | |
| - | не дойдём до состояния, в котором существует такая ситуация,
| + | |
| - | допустимой для сдвига является лексема error. Например, в грамматике
| + | |
| - | может быть такое правило:</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">expr: '(' expr ')' | '(' error ')'</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Начали разбирать expr, наткнулись на
| + | |
| - | ошибку, начали состояния выкидывать. Error означает, что надо
| + | |
| - | пропускать любые лексемы, пока не встретим ')'. Как только дошли до
| + | |
| - | закрывающей скобочки, ситаем, что правило успешно, сворачиваем стек,
| + | |
| - | переходим к разбору той точки, где вызывали expr.
| + | |
| - | </P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">В рещультате мы должны правильно
| + | |
| - | разместить лексемы error, чтобы минимизировать количество наведённых
| + | |
| - | ошибок.</P>
| + | |
| - | </OL>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Хорошее восстановление - это искусство.</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Например:</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">stmt: ... | error;</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">... | '{' error '}'</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">Грамматика адекватно отражает язык,
| + | |
| - | который хочется разбирать.</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>
| + | |
| - | <OL>
| + | |
| - | <LI><P STYLE="margin-bottom: 0cm">Shift/reduce конфликт – if
| + | |
| - | ... if ... else ... . альтернативы:. Обычно приоритет сдвигу. 50 на
| + | |
| - | 50 – иногда безобидны, иногда нет.</P>
| + | |
| - | <LI><P STYLE="margin-bottom: 0cm">Reduce/reduce конфликт –
| + | |
| - | означает, что есть проблемы в грамматике.
| + | |
| - | </P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">type: «int » | IDENT</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">declr : '*' declr | IDENT;</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">decl : type declr;</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Это декларация. Хотим описать
| + | |
| - | выражение.</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Expr = IDENT | expr '*'' IDENT</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">stmt: {'{' stmt or decl-list '}' |
| + | |
| - | expr;</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">stmt_or_decl_list: stmt . Decl;</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Что происходит в такой ситуации?
| + | |
| - | Положили «IDENT» «*»</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">IDENT может быть или типом, Или
| + | |
| - | выражением.</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Правильного выбора мы сделать не можем</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Если написать a * b, то нельзя казать,
| + | |
| - | выражение это или объявление. То же в С++: a(b).</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Одно из решений:</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">type: «int » | TYPENAME</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Вопрос в том, как их различать. Для
| + | |
| - | этого нужен доступ к области видимости синтаксического анализа.
| + | |
| - | </P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Stmt: '{' {начать новую область
| + | |
| - | видимости} {stmt_or_decl_list} {код}</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Из-за того,, что синт анализатор т
| + | |
| - | акой умный, возникают роблемы.</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">TYPEDEF INT a</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">int main()</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">{</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">int a;</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">} «int» TYPENAME ';'</P>
| + | |
| - | </OL>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Выход:</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">expr : expr '+' expr | expr '*' expr |
| + | |
| - | '-' expr | IDENT</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">приоритеты для операций:</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">expr : epr '+' expr1 | expr1;</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">expr : expr1 '*' expr2 | expr2</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">expr2 : '-' expr3 | expr3</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">expr3 : IDENT</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">%left '+'</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">%left '*'</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">%noassoc UMINUS</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">тогда правиля для плюс и умножить
| + | |
| - | разберутся корректно. Отдельно надо рассмотреть унарный минус</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">expr : expr '+' expr | expr '*' expr |
| + | |
| - | '-' expr %prec UMINUS | IDENT
| + | |
| - | </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">сделать разбор недетерминированным –
| + | |
| - | Generalized LR-parsing</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">В достаточно новом бизоне включается
| + | |
| - | опцией %glr-parser</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Теперь этот автомат начинает вести себя
| + | |
| - | как недетерминированный автомат. То есть, когда возникает конфликт,
| + | |
| - | то возможен разбор по двум вариантам, и обе будут запущены. Рано или
| + | |
| - | поздно может случится так, что останется одна ветка.
| + | |
| - | </P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Если до конца доживут две ветки: тогда
| + | |
| - | выбор за нами. Например, в плюсах приоритет отдаётся выражению. Или
| + | |
| - | можно напистаь конструкцию %merge бла-бла-бла, где написать свой код.</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm"><BR>
| + | |
| - | </P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">С парсерами странная ситуация,
| + | |
| - | почему-то их любят писать в ручную. В GCC переписали си плюс плюс и
| + | |
| - | си разборщик.</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm"><BR>
| + | |
| - | </P>
| + | |
| - | <OL START=2>
| + | |
| - | <LI><P STYLE="margin-bottom: 0cm">Вопрос управления памятью</P>
| + | |
| - | </OL>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Компилятор создаёт огромное количество
| + | |
| - | динамических структур, всё это будет добавляться, ссылки туда-сюда-по
| + | |
| - | диагонали. Вопрос, как с ними работать, встаёт в полный рост.</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">В контексте бизона с этим особые
| + | |
| - | проблемы. Старые версии бизона просто убивали стек, и если там были
| + | |
| - | указатели, то они терялись.</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Что делается:</P>
| + | |
| - | <OL>
| + | |
| - | <LI><P STYLE="margin-bottom: 0cm">Самим освобождать и выделять
| + | |
| - | память – malloc/free. Проблема – просто сложно за всем
| + | |
| - | уследить.</P>
| + | |
| - | <LI><P STYLE="margin-bottom: 0cm">Разбивают всю память на арены.
| + | |
| - | Арена памяти – некоторая область памяти, из которй запрашиваем
| + | |
| - | память с помощью alloc. Операция free для индивидуального куска не
| + | |
| - | определена, освободить можно только арену целиком (free_arena). Это
| + | |
| - | намного удобнее, чем предыдущий вариант. Проблема – иногда
| + | |
| - | сложно определить, на какой арене выделять объект. Например, может
| + | |
| - | быть арена для дерева, графов, постоянно живущих объектов (таблицы
| + | |
| - | идентификаторов). Например после перестройки графа старую арену
| + | |
| - | можно освобождать. Проблемы – можно не угадать с размером
| + | |
| - | памяти. Особенно активно динамика работает в оптимищаторе, и так это
| + | |
| - | мало поможет.</P>
| + | |
| - | <LI><P STYLE="margin-bottom: 0cm">Сборка мусора. Оказывается, она
| + | |
| - | возможна в Си и Си++. Boehm-Demers-Weiser conservative garbage
| + | |
| - | collector. Есть указатели на кучу. Те, которые в куче не находятся,
| + | |
| - | называются root pointers. Они могут быть в</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">1.регистры процессора</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">2. стек</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">3. область статических данных</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">рассматриваем их как массив
| + | |
| - | указателей. Там могут быть данные, которые могут совпадать с
| + | |
| - | указателями на валидные области памяти, но мы их так и считаем. Кучу
| + | |
| - | тоже рассматриваем как массив указателей.</P>
| + | |
| - | </OL>
| + | |
| - | <P STYLE="margin-bottom: 0cm"><BR>
| + | |
| - | </P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">//Если вы хотит выстрелить в ногу,
| + | |
| - | зачем вам garbage collector? Стреляйте в ногу маллоками.</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm"><BR>
| + | |
| - | </P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">4 этапа:</P>
| + | |
| - | <OL>
| + | |
| - | <LI><P STYLE="margin-bottom: 0cm">prepare - Сбрасываются все биты
| + | |
| - | доступности</P>
| + | |
| - | <LI><P STYLE="margin-bottom: 0cm">mark – обходим граф,
| + | |
| - | помечаюм всё, до чего мы дошли, что это достижимая область</P>
| + | |
| - | <LI><P STYLE="margin-bottom: 0cm">sweep – теперь обходим все
| + | |
| - | блоки в нашем порядке. Недостижимые блоки помечаем в очередь на
| + | |
| - | удаление</P>
| + | |
| - | <LI><P STYLE="margin-bottom: 0cm">уничтожение объектов (в
| + | |
| - | топологическом порядке)</P>
| + | |
| - | </OL>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Сборка мусора может быть быстрее за
| + | |
| - | счёт того, что она выполняется редко.</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Она удобнее.</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm">Сборщик мусора этих товарищей
| + | |
| - | используется в GCC 4.x</P>
| + | |
| - | <P STYLE="margin-bottom: 0cm"><BR>
| + | |
| - | </P>
| + | |
| - | | + | |
| - | | + | |
| - | {{Введение в теорию построения оптимизирующих компиляторов}}
| + | |
| - | {{Lection-stub}}
| + | |
