Введение в теорию построения оптимизирующих компиляторов, 03 лекция (от 10 октября)

Материал из eSyr's wiki.

Оптимизация компиляторов 10.10.06

1. Восстановление после ошибок – способность паремера разумным образом восстановить что могло бы быть в месте синтаксической ошибки и продолжить разбор. Часто возникает ситуация, когда парсер восстанавливается неправильно. Следствием являются наведённые ошибки. Чем меньше наведенных ошибок, тем лучше восстановление. Особый интерес представляет синтакс разбор. Синт разбор – есть две стратегии – удаляе м либо добавляем токены до возможности продолжения. Як и бизон реализуют восстановление с помощью удаления лексем. Если мы специфицируем грамматику, то восстановление после ошибок тоже можно возложить на генератор. В контексте нисходящего анализа это сделать проще, восходящего – сложнее. У бизона и яка нет автоматического восстановления, есть только ручное. Реализация: в грамматике допускается лексема с названием error. Это якобы лексема, которая не являетс лексемой. В како момент парсер может зафиксировать ошибки:

   1. неожиданный конец файла

   2. состояние + текущий символ не существует ни операции ни сдвига, ни свёртки. Например: x=(a+)+c. Тогда, прочитав x=(a+, и имея текущий символ ), просматривая таблицу свёртки обнаруживаем, что такого символа не предусмотрена – ошибка. Как в такой ситуации поступает Як/Бизон. У него есть стек состояний. При ошибке начинаем из стека выбрасывать состояния, пока не дойдём до состояния, в котором существует такая ситуация, допустимой для сдвига является лексема error. Например, в грамматике может быть такое правило:

   expr: '(' expr ')' | '(' error ')'

   Начали разбирать expr, наткнулись на ошибку, начали состояния выкидывать. Error означает, что надо пропускать любые лексемы, пока не встретим ')'. Как только дошли до закрывающей скобочки, ситаем, что правило успешно, сворачиваем стек, переходим к разбору той точки, где вызывали expr.

   В рещультате мы должны правильно разместить лексемы error, чтобы минимизировать количество наведённых ошибок.

Хорошее восстановление - это искусство.

Например:

stmt: ... | error;

... | '{' error '}'

Восстановление в контексте рекурсивного спуска:

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

Грамматика адекватно отражает язык, который хочется разбирать.

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

Конфликты в грамматике: возможно несколько действий, которые зависят от класса конфликтов:

1. Shift/reduce конфликт – if ... if ... else ... . альтернативы:. Обычно приоритет сдвигу. 50 на 50 – иногда безобидны, иногда нет.

2. Reduce/reduce конфликт – означает, что есть проблемы в грамматике.

   type: «int » | IDENT

   declr : '*' declr | IDENT;

   decl : type declr;

   Это декларация. Хотим описать выражение.

   Expr = IDENT | expr '* IDENT

   stmt: {'{' stmt or decl-list '}' | expr;

   stmt_or_decl_list: stmt . Decl;

   Что происходит в такой ситуации? Положили «IDENT» «*»

   IDENT может быть или типом, Или выражением.

   Правильного выбора мы сделать не можем

   Если написать a * b, то нельзя казать, выражение это или объявление. То же в С++: a(b).

   Одно из решений:

   type: «int » | TYPENAME

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

   Stmt: '{' {начать новую область видимости} {stmt_or_decl_list} {код}

   Из-за того,, что синт анализатор т акой умный, возникают роблемы.

   TYPEDEF INT a

   int main()

   {

   int a;

   } «int» TYPENAME ';'

Выход:

expr : expr '+' expr | expr '*' expr | '-' expr | IDENT

приоритеты для операций:

expr : epr '+' expr1 | expr1;

expr : expr1 '*' expr2 | expr2

expr2 : '-' expr3 | expr3

expr3 : IDENT

Но это не очень наглядно.

У бизона и як есть специальные директивы поределения приоритетов:

%left '+'

%left '*'

%noassoc UMINUS

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

expr : expr '+' expr | expr '*' expr | '-' expr %prec UMINUS | IDENT

Ноэ от никак не улучшает ситуацию.

Выход:

сделать разбор недетерминированным – Generalized LR-parsing

В достаточно новом бизоне включается опцией %glr-parser

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

Если до конца доживут две ветки: тогда выбор за нами. Например, в плюсах приоритет отдаётся выражению. Или можно напистаь конструкцию %merge бла-бла-бла, где написать свой код.

С парсерами странная ситуация, почему-то их любят писать в ручную. В GCC переписали си плюс плюс и си разборщик.

2. Вопрос управления памятью

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

В контексте бизона с этим особые проблемы. Старые версии бизона просто убивали стек, и если там были указатели, то они терялись.

Что делается:

1. Самим освобождать и выделять память – malloc/free. Проблема – просто сложно за всем уследить.

2. Разбивают всю память на арены. Арена памяти – некоторая область памяти, из которй запрашиваем память с помощью alloc. Операция free для индивидуального куска не определена, освободить можно только арену целиком (free_arena). Это намного удобнее, чем предыдущий вариант. Проблема – иногда сложно определить, на какой арене выделять объект. Например, может быть арена для дерева, графов, постоянно живущих объектов (таблицы идентификаторов). Например после перестройки графа старую арену можно освобождать. Проблемы – можно не угадать с размером памяти. Особенно активно динамика работает в оптимищаторе, и так это мало поможет.

3. Сборка мусора. Оказывается, она возможна в Си и Си++. Boehm-Demers-Weiser conservative garbage collector. Есть указатели на кучу. Те, которые в куче не находятся, называются root pointers. Они могут быть в

   1.регистры процессора

   2. стек

   3. область статических данных

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

//Если вы хотит выстрелить в ногу, зачем вам garbage collector? Стреляйте в ногу маллоками.

4 этапа:

1. prepare - Сбрасываются все биты доступности

2. mark – обходим граф, помечаюм всё, до чего мы дошли, что это достижимая область

3. sweep – теперь обходим все блоки в нашем порядке. Недостижимые блоки помечаем в очередь на удаление

4. уничтожение объектов (в топологическом порядке)

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

Она удобнее.

Сборщик мусора этих товарищей используется в GCC 4.x