Введение в теорию построения оптимизирующих компиляторов, 02 лекция (от 26 сентября)
Материал из eSyr's wiki.
Оптимизация компиляторов 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 |