Введение в теорию построения оптимизирующих компиляторов, 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. Работает так – есть разобранная часть, есть текущий символ, доступный для чтения, и есть непросомотренная часть дальше. Состояние автомата, то есть та часть цепочки, коотрую он успел просомотреть, имеется в виде стека, то есть есть некооторый стек. На стеке находтся продукты переработ\ки исходного текста, в частности, терминальбные и нетерм симоволы. На основании очсередного символа атвтомат может произвксти одно из четырёх действий:

1. Shift – сдвиг. Добавляем очередной симвлол в стек

2. 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

1. Сдвигает C

2. Сдвигает 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) для ифа будет переменное количество сыновей. Как строить деревья разбора в этом случае? Есть три подхода:

1. Каждый элемент хранит ссылку вниз и ссылку вправо. Плюсы: фиксированный размер структуры. Минусы – долго ходить по ссылкам. Кроме того, есть такой минус: рассмотрим for: «for» '(' [expr] ';' [expr] ';' [expr] ')' stmt. Некорректно оно из-за квадратных скобок. Первый вариант – написать 8 варианто. Второй – добавить expropt : expr {$$=$1;} | {$$=0;}. В этом случае построение дерева резко усложняется. Появляется много пустых листьев, которые нельзя игнорировать.

2. Можно строить структуры, у которых все потенциальные поддеревья, которы еопименованы. То есть:

struct ifstmt

{

struct expr * expr;

struct stmt *stmtthen;

struct stmt *stmtelse;

}

Плюсы – все потенциальные поддеревья доступны по имени. Поджидает следующая засада – начнётся невогласование типов в большом количестве. Вторая засада – есть дерево и надо просто его обойти. В этом случае простейшая процедура обхода превратится в огромный свитч, ибо каждый тип узла надо рассматривать отдельно. Ещё один недостаток – структура имеет переменный размер.

Мнение Чернова: в компиляторе виртуальные функции не нужны. Ибо всё по ним размазывается.

3. В каждой вершине хранить массив ссылок.

Есть два варианта – сильно извращённый вариант и не сильно извращённый вариант

struct node

{

int tag;

int n;

struct node ** p;

}

Более извращённый вариант:

struct node

{

int tag;

int n;

struct node * p[0];

}

С ним работать чуть сложнее, но меньше на одно выделение памяти.

Какие возникают вопросы:

1. Управление памятью

2. Ошибки и восстановление после ошибок

//При ошибке завершать работу и говорить «Извините, не смогла». Ну, не смогла, так не смогла.

//Восстановление после ошибок – чёрная магия

//Что делать, когда грамматика не грамматится?

3. Конфликты в грамматиках.

4. Что