Введение в теорию построения оптимизирующих компиляторов, 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;

}

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


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


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

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

struct node

{

int tag;

int n;

struct node ** p;

}

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

struct node

{

int tag;

int n;

struct node * p[0];

}

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


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

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

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


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

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

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


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

  2. Что



Введение в теорию построения оптимизирующих компиляторов


01 02 03 04 05 06 07 08 09 10


Календарь

вт вт вт вт вт
Сентябрь
    19 26
Октябрь
  10   24 31
Ноябрь
07 14 21
Декабрь
05 12


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы