Дизайн компилятора - Краткое руководство

Компьютеры - это сбалансированное сочетание программного и аппаратного обеспечения. Аппаратное обеспечение - это просто часть механического устройства, и его функции контролируются совместимым программным обеспечением. Аппаратное обеспечение понимает инструкции в форме электронного заряда, который является аналогом двоичного языка в программировании. В двоичном языке есть только два алфавита, 0 и 1. Для обучения аппаратные коды должны быть записаны в двоичном формате, который представляет собой просто последовательность единиц и нулей. Написание таких кодов было бы сложной и обременительной задачей для компьютерных программистов, поэтому у нас есть компиляторы для написания таких кодов.

Система обработки языков

Мы узнали, что любая компьютерная система состоит из аппаратного и программного обеспечения. Оборудование понимает язык, который люди не понимают. Поэтому мы пишем программы на языке высокого уровня, который нам легче понять и запомнить. Затем эти программы вводятся в серию инструментов и компонентов ОС, чтобы получить желаемый код, который может использоваться машиной. Это известно как система обработки языка.

Язык высокого уровня преобразуется в двоичный язык на разных этапах. Аcompilerэто программа, которая преобразует язык высокого уровня в язык ассемблера. Точно так жеassembler это программа, которая преобразует язык ассемблера в язык машинного уровня.

Давайте сначала поймем, как программа, использующая компилятор C, выполняется на главной машине.

• Пользователь пишет программу на языке C (язык высокого уровня).

• Компилятор C компилирует программу и переводит ее в программу сборки (язык низкого уровня).

• Затем ассемблер переводит программу сборки в машинный код (объект).

• Инструмент компоновщика используется для связывания всех частей программы вместе для выполнения (исполняемый машинный код).

• Загрузчик загружает их все в память, после чего программа запускается.

Прежде чем углубляться непосредственно в концепции компиляторов, мы должны понять несколько других инструментов, которые тесно работают с компиляторами.

Препроцессор

Препроцессор, обычно рассматриваемый как часть компилятора, - это инструмент, который производит ввод для компиляторов. Он занимается обработкой макросов, расширением, включением файлов, расширением языка и т. Д.

Переводчик

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

Ассемблер

Ассемблер переводит программы на ассемблере в машинный код. Вывод ассемблера называется объектным файлом, который содержит комбинацию машинных инструкций, а также данные, необходимые для размещения этих инструкций в памяти.

Компоновщик

Linker - это компьютерная программа, которая связывает и объединяет различные объектные файлы вместе для создания исполняемого файла. Все эти файлы могли быть скомпилированы отдельными ассемблерами. Основная задача компоновщика состоит в том, чтобы найти и определить местонахождение модуля / подпрограмм, на которые имеются ссылки, в программе и определить место в памяти, куда будут загружены эти коды, при этом инструкция программы будет иметь абсолютные ссылки.

Загрузчик

Загрузчик является частью операционной системы и отвечает за загрузку исполняемых файлов в память и их выполнение. Он вычисляет размер программы (инструкций и данных) и создает для нее место в памяти. Он инициализирует различные регистры для запуска выполнения.

Кросс-компилятор

Компилятор, работающий на платформе (A) и способный генерировать исполняемый код для платформы (B), называется кросс-компилятором.

Компилятор исходного кода

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

Архитектура компилятора

Компилятор можно в общих чертах разделить на две фазы в зависимости от способа компиляции.

Фаза анализа

Известный как внешний интерфейс компилятора, analysis На этапе анализа компилятор считывает исходную программу, разделяет ее на основные части, а затем проверяет наличие лексических, грамматических и синтаксических ошибок. На этапе анализа создается промежуточное представление исходной программы и таблицы символов, которые должны быть переданы на этап синтеза в качестве входных данных. .

Фаза синтеза

Известный как серверная часть компилятора, synthesis phase генерирует целевую программу с помощью промежуточного представления исходного кода и таблицы символов.

У компилятора может быть много фаз и проходов.

• Pass : Проход относится к обходу компилятора через всю программу.

• Phase: Фаза компилятора - это различимый этап, который принимает входные данные из предыдущего этапа, обрабатывает и выдает выходные данные, которые можно использовать в качестве входных данных для следующего этапа. У пасса может быть более одной фазы.

Фазы компилятора

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

Лексический анализ

Первая фаза сканера работает как сканер текста. На этом этапе исходный код сканируется как поток символов и преобразуется в значимые лексемы. Лексический анализатор представляет эти лексемы в виде токенов как:

<token-name, attribute-value>

Синтаксический анализ

Следующий этап называется синтаксическим анализом или parsing. Он принимает токен, полученный в результате лексического анализа, в качестве входных данных и генерирует дерево синтаксического анализа (или дерево синтаксиса). На этом этапе расположение токенов проверяется на соответствие грамматике исходного кода, т. Е. Синтаксический анализатор проверяет, является ли выражение, созданное токенами, синтаксически правильным.

Семантический анализ

Семантический анализ проверяет, соответствует ли построенное дерево синтаксического анализа правилам языка. Например, присвоение значений осуществляется между совместимыми типами данных и добавлением строки к целому числу. Также семантический анализатор отслеживает идентификаторы, их типы и выражения; объявлены ли идентификаторы перед использованием или нет и т. д. Семантический анализатор выдает аннотированное синтаксическое дерево в качестве вывода.

Генерация промежуточного кода

После семантического анализа компилятор генерирует промежуточный код исходного кода для целевой машины. Он представляет собой программу для некоторой абстрактной машины. Он находится между языком высокого уровня и машинным языком. Этот промежуточный код должен быть сгенерирован таким образом, чтобы его было легче транслировать в целевой машинный код.

Оптимизация кода

На следующем этапе выполняется оптимизация кода промежуточного кода. Оптимизация может рассматриваться как что-то, что удаляет ненужные строки кода и упорядочивает последовательность операторов, чтобы ускорить выполнение программы без потери ресурсов (ЦП, память).

Генерация кода

На этом этапе генератор кода берет оптимизированное представление промежуточного кода и отображает его на целевой машинный язык. Генератор кода переводит промежуточный код в последовательность (обычно) перемещаемого машинного кода. Последовательность инструкций машинного кода выполняет задачу так же, как и промежуточный код.

Таблица символов

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

Лексический анализ - это первая фаза компилятора. Он берет модифицированный исходный код из языковых препроцессоров, которые записываются в форме предложений. Лексический анализатор разбивает эти синтаксисы на серию токенов, удаляя любые пробелы или комментарии в исходном коде.

Если лексический анализатор находит токен недействительным, он выдает ошибку. Лексический анализатор тесно взаимодействует с анализатором синтаксиса. Он считывает символьные потоки из исходного кода, проверяет допустимые токены и передает данные синтаксическому анализатору, когда тот требует.

Токены

Лексемы называются последовательностью символов (буквенно-цифровых) в токене. Есть несколько предопределенных правил для каждой лексемы, которая должна быть идентифицирована как действительный токен. Эти правила определяются правилами грамматики с помощью шаблона. Шаблон объясняет, что может быть токеном, и эти шаблоны определяются с помощью регулярных выражений.

В языке программирования ключевые слова, константы, идентификаторы, строки, числа, операторы и символы пунктуации могут рассматриваться как токены.

Например, в языке C строка объявления переменной

int value = 100;

содержит токены:

int (keyword), value (identifier), = (operator), 100 (constant) and ; (symbol).

Характеристики токенов

Давайте разберемся, как теория языка использует следующие термины:

Алфавиты

Любой конечный набор символов {0,1} - это набор двоичных алфавитов, {0,1,2,3,4,5,6,7,8,9, A, B, C, D, E, F} - это набор шестнадцатеричных алфавитов, {az, AZ} - набор английских языковых алфавитов.

Струны

Любая конечная последовательность алфавитов называется строкой. Длина строки - это общее количество вхождений алфавитов, например, длина строки tutorialspoint равна 14 и обозначается как | tutorialspoint | = 14. Строка без алфавитов, т.е. строка нулевой длины, называется пустой строкой и обозначается ε (эпсилон).

Специальные символы

Типичный язык высокого уровня содержит следующие символы: -

Язык

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

Регулярные выражения

Лексическому анализатору необходимо сканировать и идентифицировать только конечный набор действительных строк / токенов / лексем, принадлежащих рассматриваемому языку. Он ищет шаблон, определенный правилами языка.

Регулярные выражения могут выражать конечные языки, определяя шаблон для конечных строк символов. Грамматика, определяемая регулярными выражениями, известна какregular grammar. Язык, определяемый регулярной грамматикой, известен какregular language.

Регулярное выражение - важная нотация для определения шаблонов. Каждый шаблон соответствует набору строк, поэтому регулярные выражения служат именами для набора строк. Токены языка программирования можно описать обычными языками. Спецификация регулярных выражений - это пример рекурсивного определения. Обычные языки просты для понимания и имеют эффективную реализацию.

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

Операции

Различные операции с языками:

• Союз двух языков L и M записывается как

  LUM = {s | s находится в L или s находится в M}

• Конкатенация двух языков L и M записывается как

  LM = {st | s находится в L, а t находится в M}

• Замыкание Клини языка L записывается как

  L * = Ноль или более случаев языка L.

Обозначения

Если r и s - регулярные выражения, обозначающие языки L (r) и L (s), то

• Union : (r) | (s) - регулярное выражение, обозначающее L (r) UL (s)

• Concatenation : (r) (s) - регулярное выражение, обозначающее L (r) L (s)

• Kleene closure : (r) * - регулярное выражение, обозначающее (L (r)) *

• (r) - регулярное выражение, обозначающее L (r)

Приоритет и ассоциативность

• *, конкатенация (.) и | (знак трубы) левоассоциативны
• * имеет высший приоритет
• Конкатенация (.) Имеет второй по важности приоритет.
• | (знак вертикальной черты) имеет самый низкий приоритет из всех.

Представление действительных токенов языка в регулярном выражении

Если x - регулярное выражение, то:

• x * означает ноль или более случаев появления x.

  т.е. он может генерировать {e, x, xx, xxx, xxxx,…}

• x + означает одно или несколько вхождений x.

  т.е. он может генерировать {x, xx, xxx, xxxx…} или xx *

• Икс? означает не более одного вхождения x

  т.е. он может генерировать либо {x}, либо {e}.

[az] - это все строчные буквы английского языка.

[AZ] - это все буквы английского языка в верхнем регистре.

[0-9] - все натуральные числа, используемые в математике.

Представление появления символов с помощью регулярных выражений

буква = [a - z] или [A - Z]

цифра = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 или [0-9]

знак = [+ | -]

Представление языковых токенов с помощью регулярных выражений

Десятичный = (знак) ^? (цифра) ⁺

Идентификатор = (буква) (буква | цифра) *

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

Конечные автоматы

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

Математическая модель конечных автоматов состоит из:

• Конечный набор состояний (Q)
• Конечный набор входных символов (Σ)
• Одно состояние запуска (q0)
• Набор конечных состояний (qf)
• Функция перехода (δ)

Функция перехода (δ) отображает конечный набор состояний (Q) в конечный набор входных символов (Σ), Q × Σ ➔ Q

Конструкция конечных автоматов

Пусть L (r) - регулярный язык, распознаваемый некоторыми конечными автоматами (FA).

• States: Состояния FA представлены кружками. Названия государств написаны внутри кружков.

• Start state: Состояние, с которого запускается автомат, называется начальным состоянием. На начальное состояние указывает стрелка.

• Intermediate states: Все промежуточные состояния имеют как минимум две стрелки; один указывает на них, а другой указывает от них.

• Final state: Если входная строка успешно проанализирована, ожидается, что автомат находится в этом состоянии. Конечное состояние представлено двойными кружками. Он может иметь любое нечетное количество стрелок, указывающих на него, и четное количество стрелок, указывающих из него. Количество нечетных стрелок на единицу больше четных, т.е.odd = even+1.

• Transition: Переход из одного состояния в другое происходит, когда на входе найден желаемый символ. При переходе автоматы могут либо перейти в следующее состояние, либо остаться в том же состоянии. Движение из одного состояния в другое показано направленной стрелкой, где стрелки указывают на состояние назначения. Если автомат остается в том же состоянии, отображается стрелка, указывающая из состояния на себя.

Example: Мы предполагаем, что FA принимает любое трехзначное двоичное значение, заканчивающееся цифрой 1. FA = {Q (q ₀ , q _f ), Σ (0,1), q ₀ , q _f , δ}

Правило самого длительного совпадения

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

For example:

int intvalue;

При сканировании обеих лексем до int лексический анализатор не может определить, является ли это ключевым словом int или инициалами значения идентификатора int.

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

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

Анализ синтаксиса или синтаксический анализ - это вторая фаза компилятора. В этой главе мы изучим основные концепции, используемые при создании синтаксического анализатора.

Мы видели, что лексический анализатор может идентифицировать токены с помощью регулярных выражений и шаблонных правил. Но лексический анализатор не может проверить синтаксис данного предложения из-за ограничений регулярных выражений. Регулярные выражения не могут проверять токены балансировки, такие как скобки. Таким образом, на этом этапе используется контекстно-свободная грамматика (CFG), которая распознается автоматами.

CFG, с другой стороны, представляет собой надмножество регулярной грамматики, как показано ниже:

Это означает, что каждая регулярная грамматика также не зависит от контекста, но существуют некоторые проблемы, которые выходят за рамки обычной грамматики. CFG - полезный инструмент для описания синтаксиса языков программирования.

Контекстно-свободная грамматика

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

Контекстно-свободная грамматика состоит из четырех компонентов:

• Набор из non-terminals(V). Нетерминалы - это синтаксические переменные, которые обозначают наборы строк. Нетерминалы определяют наборы строк, которые помогают определить язык, созданный грамматикой.

• Набор жетонов, известный как terminal symbols(Σ). Терминалы - это основные символы, из которых образуются строки.

• Набор из productions(П). Продукция грамматики определяет способ, которым терминалы и нетерминалы могут быть объединены для образования строк. Каждая постановка состоит изnon-terminal называется левая сторона производства, стрелка и последовательность жетонов и / или on- terminals, называется правой стороной производства.

• Один из нетерминалов обозначен как начальный символ (S); откуда начинается производство.

Строки получаются из начального символа путем многократной замены нетерминального символа (изначально начального символа) правой стороной продукции для этого нетерминального символа.

пример

Возьмем проблему языка палиндромов, который нельзя описать с помощью регулярных выражений. То есть L = {w | w = w ^R } не является обычным языком. Но это можно описать с помощью CFG, как показано ниже:

G = ( V, Σ, P, S )

Где:

V = { Q, Z, N }
Σ = { 0, 1 }
P = { Q → Z | Q → N | Q → ℇ | Z → 0Q0 | N → 1Q1 }
S = { Q }

Эта грамматика описывает язык палиндромов, например: 1001, 11100111, 00100, 1010101, 11111 и т. Д.

Анализаторы синтаксиса

Синтаксический анализатор или синтаксический анализатор принимает входные данные от лексического анализатора в виде потоков токенов. Парсер анализирует исходный код (поток токенов) на соответствие производственным правилам, чтобы обнаружить любые ошибки в коде. Результатом этой фазы являетсяparse tree.

Таким образом, синтаксический анализатор выполняет две задачи: синтаксический анализ кода, поиск ошибок и создание дерева синтаксического анализа в качестве выходных данных фазы.

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

Вывод

Деривация - это в основном последовательность производственных правил для получения входной строки. Во время синтаксического анализа мы принимаем два решения для некоторой предполагаемой формы ввода:

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

Чтобы решить, какой нетерминал заменить производственным правилом, у нас может быть два варианта.

Крайний левый вывод

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

Самая правая производная

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

Example

Правила производства:

E → E + E
E → E * E
E → id

Строка ввода: id + id * id

Самый левый вывод:

E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id

Обратите внимание, что крайний левый нетерминал всегда обрабатывается первым.

Самый правый вывод:

E → E + E
E → E + E * E
E → E + E * id
E → E + id * id
E → id + id * id

Дерево разбора

Дерево синтаксического анализа - это графическое изображение производной. Удобно видеть, как строки выводятся из начального символа. Начальный символ вывода становится корнем дерева синтаксического анализа. Убедимся в этом на примере из прошлой темы.

Возьмем крайний левый вывод a + b * c

Самый левый вывод:

E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id

Шаг 1:

E → E * E

Шаг 2:

E → E + E * E

Шаг 3:

E → id + E * E

Шаг 4:

E → id + id * E

Шаг 5:

E → id + id * id

В дереве синтаксического анализа:

• Все листовые узлы являются терминалами.
• Все внутренние узлы не являются терминалами.
• Обход по порядку дает исходную входную строку.

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

Типы парсинга

Анализаторы синтаксиса следуют производственным правилам, определенным с помощью контекстно-свободной грамматики. Способ реализации производственных правил (вывод) делит синтаксический анализ на два типа: синтаксический анализ сверху вниз и синтаксический анализ снизу вверх.

Анализ сверху вниз

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

• Recursive descent parsing: Это распространенная форма анализа сверху вниз. Он называется рекурсивным, поскольку он использует рекурсивные процедуры для обработки ввода. Синтаксический анализ рекурсивного спуска страдает от возврата.

• Backtracking: Это означает, что в случае сбоя одной производной продукции анализатор синтаксиса перезапускает процесс, используя другие правила той же продукции. Этот метод может обрабатывать входную строку более одного раза, чтобы определить правильную продукцию.

Анализ снизу вверх

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

Example:

Строка ввода: a + b * c

Правила производства:

S → E
E → E + T
E → E * T
E → T
T → id

Приступим к восходящему разбору

a + b * c

Прочтите ввод и проверьте, совпадает ли какое-либо производство с вводом:

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S

Двусмысленность

Грамматика G называется неоднозначной, если она имеет более одного дерева синтаксического анализа (левое или правое происхождение) хотя бы для одной строки.

Example

E → E + E
E → E – E
E → id

Для строки id + id - id приведенная выше грамматика генерирует два дерева синтаксического анализа:

Язык, порожденный неоднозначной грамматикой, называется inherently ambiguous. Двусмысленность в грамматике не годится для конструкции компилятора. Ни один метод не может автоматически обнаруживать и удалять неоднозначность, но ее можно удалить, либо переписав всю грамматику без неоднозначности, либо установив и соблюдая ограничения ассоциативности и приоритета.

Ассоциативность

Если у операнда есть операторы с обеих сторон, сторона, на которой оператор принимает этот операнд, определяется ассоциативностью этих операторов. Если операция левоассоциативная, то операнд будет взят левым оператором, а если операция правоассоциативна, то правый оператор примет операнд.

Example

Такие операции, как сложение, умножение, вычитание и деление, остаются ассоциативными. Если выражение содержит:

id op id op id

он будет оцениваться как:

(id op id) op id

Например, (id + id) + id

Такие операции, как возведение в степень, являются правоассоциативными, т. Е. Порядок вычисления в одном и том же выражении будет следующим:

id op (id op id)

Например, id ^ (id ^ id)

Приоритет

Если два разных оператора используют общий операнд, приоритет операторов определяет, какой операнд будет использоваться. То есть 2 + 3 * 4 может иметь два разных дерева синтаксического анализа, одно из которых соответствует (2 + 3) * 4, а другое - 2+ (3 * 4). Установив приоритет среди операторов, эту проблему можно легко устранить. Как и в предыдущем примере, математически * (умножение) имеет приоритет над + (сложение), поэтому выражение 2 + 3 * 4 всегда будет интерпретироваться как:

2 + (3 * 4)

Эти методы уменьшают вероятность двусмысленности в языке или его грамматике.

Левая рекурсия

Грамматика становится леворекурсивной, если в ней есть какой-либо нетерминальный 'A', чье происхождение содержит сам 'A' в качестве самого левого символа. Леворекурсивная грамматика считается проблемной ситуацией для нисходящих синтаксических анализаторов. Нисходящие парсеры начинают синтаксический анализ с символа Start, который сам по себе не является терминальным. Итак, когда синтаксический анализатор встречает тот же нетерминал в своем выводе, ему становится трудно судить, когда прекратить синтаксический анализ левого нетерминала, и он переходит в бесконечный цикл.

Example:

(1) A => Aα | β

(2) S => Aα | β 
    A => Sd

(1) является примером немедленной левой рекурсии, где A - любой нетерминальный символ, а α представляет собой строку нетерминальных символов.

(2) является примером косвенной левой рекурсии.

Нисходящий синтаксический анализатор сначала проанализирует A, который, в свою очередь, выдаст строку, состоящую из самого A, и синтаксический анализатор может навсегда войти в цикл.

Удаление левой рекурсии

Один из способов удалить левую рекурсию - использовать следующую технику:

Производство

A => Aα | β

конвертируется в следующие постановки

A => βA’
A => αA’ | ε

Это не влияет на строки, полученные из грамматики, но удаляет немедленную левую рекурсию.

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

Algorithm
START
Arrange non-terminals in some order like A1, A2, A3,…, An
for each i from 1 to n
{
for each j from 1 to i-1
   {
   replace each production of form Ai⟹Aj
   with Ai ⟹ δ1  | δ2 | δ3 |…|  
   where Aj ⟹ δ1 | δ2|…| δn  are current Aj productions
}
   }
   eliminate immediate left-recursion
END

Example

Производственный набор

S => Aα | β 
A => Sd

после применения вышеуказанного алгоритма должен стать

S => Aα | β 
A => Aαd | βd

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

A => βdA’
A => αdA’ | ε

Теперь ни у одной продукции нет ни прямой, ни косвенной левой рекурсии.

Левый факторинг

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

Example

Если нисходящий синтаксический анализатор встречает продукцию вроде

A ⟹ αβ | α | …

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

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

Example

Вышеупомянутые постановки можно записать как

A => αA’
A’=> β |  | …

Теперь синтаксический анализатор имеет только одну продукцию на префикс, что упрощает принятие решений.

Первые и последующие наборы

Важной частью построения таблицы парсера является создание первого и последующего наборов. Эти наборы могут предоставить фактическое положение любого терминала в деривации. Это делается для создания таблицы синтаксического анализа, в которой принимается решение о замене T [A, t] = α некоторым продукционным правилом.

Первый сет

Этот набор создан для того, чтобы знать, какой символ терминала получен в первой позиции нетерминалом. Например,

α → t β

То есть α выводит t (терминал) в самой первой позиции. Итак, t ∈ FIRST (α).

Алгоритм расчета первого набора

Взгляните на определение ПЕРВОГО (α) множества:

• если α - терминал, то FIRST (α) = {α}.
• если α нетерминал и α → ℇ продукция, то FIRST (α) = {ℇ}.
• если α нетерминал и α → 1 2 3… n и любой FIRST () содержит t, то t находится в FIRST (α).

Первый набор можно увидеть как: ПЕРВЫЙ (α) = {t | α → ^* t β} ∪ {ℇ | α → ^* ε}

Follow Set

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

Алгоритм расчета Follow set:

• если α - начальный символ, то FOLLOW () = $

• если α нетерминал и имеет продукцию α → AB, то FIRST (B) принадлежит FOLLOW (A), кроме ℇ.

• если α нетерминал и имеет продукцию α → AB, где B ℇ, то FOLLOW (A) находится в FOLLOW (α).

Следующее множество можно увидеть как: FOLLOW (α) = {t | S * αt *}

Стратегии устранения ошибок

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

• Lexical : неверно набрано имя некоторого идентификатора

• Syntactical : отсутствует точка с запятой или несбалансированные круглые скобки

• Semantical : несовместимое присвоение значений

• Logical : код недоступен, бесконечный цикл

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

Панический режим

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

Режим выписки

Когда синтаксический анализатор обнаруживает ошибку, он пытается принять меры по исправлению, чтобы остальные входные данные оператора позволяли синтаксическому анализатору выполнить синтаксический анализ заранее. Например, вставка отсутствующей точки с запятой, замена запятой точкой с запятой и т. Д. Разработчики парсеров должны быть осторожны здесь, потому что одно неверное исправление может привести к бесконечному циклу.

Производство ошибок

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

Глобальная коррекция

Синтаксический анализатор рассматривает текущую программу в целом и пытается выяснить, для чего предназначена программа, и пытается найти для нее наиболее близкое соответствие, что не вызывает ошибок. Когда подается ошибочный ввод (оператор) X, он создает дерево синтаксического анализа для ближайшего безошибочного оператора Y. Это может позволить синтаксическому анализатору внести минимальные изменения в исходный код, но из-за сложности (время и пространство) Эта стратегия пока не реализована на практике.

Абстрактные синтаксические деревья

Компилятору нелегко проанализировать представления дерева синтаксического анализа, поскольку они содержат больше деталей, чем фактически необходимо. В качестве примера возьмем следующее дерево синтаксического анализа:

Если внимательно присмотреться, мы обнаружим, что большинство листовых узлов являются дочерними по отношению к своим родительским узлам. Эту информацию можно удалить перед тем, как передать ее на следующий этап. Скрывая дополнительную информацию, мы можем получить дерево, как показано ниже:

Абстрактное дерево можно представить в виде:

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

Ограничения синтаксических анализаторов

Анализаторы синтаксиса получают свои входные данные в виде токенов от лексических анализаторов. Лексические анализаторы отвечают за достоверность токена, предоставленного анализатором синтаксиса. У анализаторов синтаксиса есть следующие недостатки:

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

Эти задачи выполняет семантический анализатор, который мы изучим в разделе «Семантический анализ».

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

Например

E → E + T

Вышеупомянутая продукция CFG не имеет связанного с ней семантического правила, и она не может помочь понять смысл продукции.

Семантика

Семантика языка придает значение его конструкциям, таким как токены и структура синтаксиса. Семантика помогает интерпретировать символы, их типы и их отношения друг с другом. Семантический анализ определяет, имеет ли синтаксическая структура, созданная в исходной программе, какое-либо значение или нет.

CFG + semantic rules = Syntax Directed Definitions

Например:

int a = “value”;

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

• Разрешение прицела
• Проверка типа
• Проверка с привязкой к массиву

Семантические ошибки

Мы упомянули некоторые семантические ошибки, которые должен распознавать семантический анализатор:

• Несоответствие типов
• Необъявленная переменная
• Неправильное использование зарезервированного идентификатора.
• Множественное объявление переменной в области видимости.
• Доступ к переменной вне области видимости.
• Несоответствие фактических и формальных параметров.

Грамматика атрибутов

Грамматика атрибутов - это особая форма контекстно-свободной грамматики, в которой некоторая дополнительная информация (атрибуты) добавляется к одному или нескольким нетерминалам для предоставления контекстно-зависимой информации. Каждый атрибут имеет четко определенную область значений, например целое число, число с плавающей запятой, символ, строку и выражения.

Грамматика атрибутов - это среда, обеспечивающая семантику контекстно-свободной грамматики, и она может помочь определить синтаксис и семантику языка программирования. Грамматика атрибутов (если рассматривать ее как дерево синтаксического анализа) может передавать значения или информацию между узлами дерева.

Example:

E → E + T { E.value = E.value + T.value }

Правая часть CFG содержит семантические правила, определяющие, как следует интерпретировать грамматику. Здесь значения нетерминальных E и T складываются вместе, и результат копируется в нетерминальный E.

Семантические атрибуты могут быть присвоены их значениям из их домена во время синтаксического анализа и оценены во время назначения или условий. В зависимости от того, как атрибуты получают свои значения, их можно в общих чертах разделить на две категории: синтезированные атрибуты и унаследованные атрибуты.

Синтезированные атрибуты

Эти атрибуты получают значения из значений атрибутов своих дочерних узлов. Для иллюстрации предположим следующее производство:

S → ABC

Если S принимает значения из своих дочерних узлов (A, B, C), то говорят, что это синтезированный атрибут, поскольку значения ABC синтезируются в S.

Как и в нашем предыдущем примере (E → E + T), родительский узел E получает свое значение от своего дочернего узла. Синтезированные атрибуты никогда не принимают значения от своих родительских узлов или любых родственных узлов.

Унаследованные атрибуты

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

S → ABC

A может получать значения из S, B и C. B может принимать значения из S, A и C. Точно так же C может принимать значения из S, A и B.

Expansion : Когда нетерминал расширяется до терминалов в соответствии с грамматическим правилом

Reduction: Когда терминал сокращается до соответствующего нетерминала в соответствии с правилами грамматики. Синтаксические деревья анализируются сверху вниз и слева направо. Всякий раз, когда происходит редукция, мы применяем соответствующие семантические правила (действия).

Семантический анализ использует переводы, направленные на синтаксис, для выполнения вышеуказанных задач.

Семантический анализатор получает AST (абстрактное синтаксическое дерево) со своего предыдущего этапа (синтаксический анализ).

Семантический анализатор присоединяет атрибутивную информацию с AST, которые называются Attributed AST.

Атрибуты - это два значения кортежа, <имя атрибута, значение атрибута>

Например:

int value  = 5;
<type, “integer”>
<presentvalue, “5”>

К каждой постановке мы прилагаем семантическое правило.

S-атрибутное SDT

Если SDT использует только синтезированные атрибуты, он называется SDT с S-атрибутами. Эти атрибуты оцениваются с помощью SDT с S-атрибутами, семантические действия которых записаны после производства (правая часть).

Как показано выше, атрибуты в SDT с S-атрибутами оцениваются при восходящем синтаксическом анализе, поскольку значения родительских узлов зависят от значений дочерних узлов.

L-атрибутированное SDT

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

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

S → ABC

S может принимать значения из A, B и C (синтезировано). A может принимать значения только из S. B может принимать значения от S и A. C может получать значения от S, A и B. Ни один нетерминал не может получать значения от родственного брата справа.

Атрибуты в SDT с L-атрибутами оцениваются методом анализа в глубину и слева направо.

Мы можем заключить, что если определение является S-атрибутированным, то оно также является L-атрибутированным, поскольку определение L-атрибута включает определения с S-атрибутами.

В предыдущей главе мы поняли основные концепции, связанные с синтаксическим анализом. В этой главе мы изучим различные типы доступных методов построения синтаксического анализатора.

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

Анализ сверху вниз

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

Рекурсивный спуск

Рекурсивный спуск - это метод синтаксического анализа сверху вниз, при котором дерево синтаксического анализа строится сверху, а входные данные читаются слева направо. Он использует процедуры для каждого оконечного и нетерминального объекта. Этот метод анализа рекурсивно анализирует входные данные для создания дерева синтаксического анализа, которое может потребовать или не потребовать обратного отслеживания. Но связанная с ним грамматика (если не учтена) не может избежать обратного отслеживания. Форма анализа с рекурсивным спуском, не требующая обратного отслеживания, известна какpredictive parsing.

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

Обратное отслеживание

Нисходящие синтаксические анализаторы начинают с корневого узла (начальный символ) и сопоставляют входную строку с производственными правилами, чтобы заменить их (если они совпадают). Чтобы понять это, возьмите следующий пример CFG:

S → rXd | rZd
X → oa | ea
Z → ai

Для входной строки: read нисходящий синтаксический анализатор будет вести себя следующим образом:

Он будет начинаться с S из правил производства и будет соответствовать его доходности самой левой букве ввода, то есть 'r'. Само производство S (S → rXd) совпадает с ним. Таким образом, нисходящий синтаксический анализатор переходит к следующей входной букве (например, «е»). Синтаксический анализатор пытается раскрыть нетерминальный 'X' и проверяет его результат слева (X → oa). Он не соответствует следующему входному символу. Таким образом, нисходящий синтаксический анализатор возвращается назад, чтобы получить следующее правило продукции X, (X → ea).

Теперь синтаксический анализатор упорядоченно сопоставляет все введенные буквы. Строка принята.

Предиктивный парсер

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

Для выполнения своих задач прогнозный синтаксический анализатор использует упреждающий указатель, который указывает на следующие входные символы. Чтобы синтаксический анализатор не выполнял обратное отслеживание, прогнозирующий синтаксический анализатор накладывает некоторые ограничения на грамматику и принимает только класс грамматики, известный как грамматика LL (k).

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

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

LL парсер

LL Parser принимает грамматику LL. Грамматика LL - это подмножество контекстно-свободной грамматики, но с некоторыми ограничениями, чтобы получить упрощенную версию, чтобы добиться легкой реализации. Грамматика LL может быть реализована с помощью обоих алгоритмов, а именно рекурсивного спуска или управляемого таблицей.

Парсер LL обозначается как LL (k). Первый L в LL (k) анализирует ввод слева направо, второй L в LL (k) обозначает крайний левый вывод, а сам k представляет количество упреждающих запросов. Обычно k = 1, поэтому LL (k) также можно записать как LL (1).

Алгоритм анализа LL

Мы можем придерживаться детерминированного LL (1) для объяснения парсера, поскольку размер таблицы растет экспоненциально с увеличением значения k. Во-вторых, если данная грамматика не является LL (1), то обычно она не является LL (k) для любого данного k.

Ниже приведен алгоритм анализа LL (1):

Input: 
string ω 
parsing table M for grammar G
Output:
   If ω is in L(G) then left-most derivation of ω,
   error otherwise.

Initial State : $S on stack (with S being start symbol) ω$ in the input buffer

SET ip to point the first symbol of ω$.
repeat
let X be the top stack symbol and a the symbol pointed by ip.
if X∈ Vt or $
if X = a
   POP X and advance ip.
	else
   error()
 	endif
else	/* X is non-terminal */
   if M[X,a] = X → Y1, Y2,... Yk    
POP X
PUSH Yk, Yk-1,... Y1 /* Y1 on top */
   Output the production X → Y1, Y2,... Yk 
   else
   error()
   endif
	endif
until X = $	/* empty stack */

Грамматика G является LL (1), если A-> alpha | b - две различные продукции группы G:

• без терминала и альфа, и бета выводят строки, начинающиеся с.

• максимум одна из альфа- и бета-версий может выводить пустую строку.

• если beta => t, то alpha не выводит строку, начинающуюся с терминала в FOLLOW (A).

Анализ снизу вверх

Анализ снизу вверх начинается с листовых узлов дерева и работает в восходящем направлении, пока не достигнет корневого узла. Здесь мы начинаем с предложения, а затем применяем производственные правила в обратном порядке, чтобы достичь начального символа. На приведенном ниже изображении показаны доступные восходящие парсеры.

Парсинг Shift-Reduce

Синтаксический анализ Shift-уменьшение использует два уникальных шага для анализа снизу вверх. Эти шаги известны как шаг сдвига и шаг уменьшения.

• Shift step: Шаг сдвига относится к перемещению указателя ввода к следующему символу ввода, который называется сдвинутым символом. Этот символ помещается в стек. Сдвинутый символ рассматривается как единственный узел дерева синтаксического анализа.

• Reduce step: Когда синтаксический анализатор находит полное правило грамматики (RHS) и заменяет его на (LHS), это называется шагом сокращения. Это происходит, когда вершина стека содержит дескриптор. Чтобы уменьшить, в стеке выполняется функция POP, которая отрывается от ручки и заменяет ее нетерминальным символом LHS.

LR Parser

Анализатор LR - это нерекурсивный анализатор снизу вверх с уменьшением сдвига. Он использует широкий класс контекстно-свободной грамматики, что делает его наиболее эффективным методом синтаксического анализа. Парсеры LR также известны как парсеры LR (k), где L обозначает сканирование входящего потока слева направо; R обозначает построение крайнего правого вывода в обратном порядке, а k обозначает количество опережающих символов для принятия решений.

Для построения LR-парсера доступны три широко используемых алгоритма:

• SLR (1) - Простой парсер LR:
  • Работает на младшем классе грамматики
  • Небольшое количество состояний, поэтому очень маленькая таблица
  • Простое и быстрое строительство
• LR (1) - Парсер LR:
  • Работает по комплектации LR (1) Grammar
  • Создает большую таблицу и большое количество состояний
  • Медленное строительство
• LALR (1) - Look-Ahead LR Parser:
  • Работает над промежуточным размером грамматики
  • Количество состояний такое же, как в SLR (1)

Алгоритм анализа LR

Здесь мы опишем скелетный алгоритм LR-парсера:

token = next_token()
repeat forever
   s = top of stack
   if action[s, token] = “shift si” then
   PUSH token
   PUSH si 
   token = next_token()
else if action[s, tpken] = “reduce A::= β“ then 
   POP 2 * |β| symbols
   s = top of stack
   PUSH A
	PUSH goto[s,A]
else if action[s, token] = “accept” then
	return
	else
   error()

LL против LR

Программа как исходный код представляет собой просто набор текста (кода, операторов и т. Д.), И для его оживления требуется выполнение действий на целевой машине. Программе требуются ресурсы памяти для выполнения инструкций. Программа содержит имена для процедур, идентификаторов и т. Д., Которые требуют сопоставления с фактической ячейкой памяти во время выполнения.

Под средой выполнения мы понимаем выполняемую программу. Среда выполнения - это состояние целевой машины, которое может включать в себя программные библиотеки, переменные среды и т. Д., Чтобы предоставлять услуги процессам, запущенным в системе.

Система поддержки времени выполнения - это пакет, в основном генерируемый самой исполняемой программой и облегчающий взаимодействие процесса между процессом и средой выполнения. Он заботится о выделении и освобождении памяти во время выполнения программы.

Деревья активации

Программа - это последовательность инструкций, объединенных в несколько процедур. Инструкции в процедуре выполняются последовательно. У процедуры есть начальный и конечный разделители, и все внутри нее называется телом процедуры. Идентификатор процедуры и последовательность конечных инструкций внутри него составляют тело процедуры.

Выполнение процедуры называется ее активацией. Запись активации содержит всю необходимую информацию, необходимую для вызова процедуры. Запись активации может содержать следующие единицы (в зависимости от используемого исходного языка).

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

Мы предполагаем, что управление программой протекает последовательно, и когда процедура вызывается, ее управление передается вызываемой процедуре. Когда вызываемая процедура выполняется, она возвращает управление вызывающей стороне. Этот тип потока управления упрощает представление серии активаций в виде дерева, известного какactivation tree.

Чтобы понять эту концепцию, мы возьмем в качестве примера фрагмент кода:

. . .
printf(“Enter Your Name: “);
scanf(“%s”, username);
show_data(username);
printf(“Press any key to continue…”);
. . .
int show_data(char *user)
   {
   printf(“Your name is %s”, username);
   return 0;
   }
. . .

Ниже представлено дерево активации данного кода.

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

Распределение памяти

Среда выполнения управляет требованиями к оперативной памяти для следующих объектов:

• Code: Это текстовая часть программы, которая не изменяется во время выполнения. Его требования к памяти известны во время компиляции.

• Procedures: Их текстовая часть статична, но они вызываются случайным образом. Вот почему хранилище стека используется для управления вызовами процедур и активациями.

• Variables: Переменные известны только во время выполнения, если они не являются глобальными или постоянными. Схема распределения памяти кучи используется для управления выделением и освобождением памяти для переменных во время выполнения.

Статическое размещение

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

Размещение стека

Вызов процедур и их активация управляются посредством выделения памяти стека. Он работает в методе «последним пришел - первым ушел» (LIFO), и эта стратегия распределения очень полезна для рекурсивных вызовов процедур.

Выделение кучи

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

За исключением статически выделенной области памяти, память стека и кучи может увеличиваться и уменьшаться динамически и неожиданно. Следовательно, им нельзя предоставить фиксированный объем памяти в системе.

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

Передача параметров

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

r-значение

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

l-значение

Место в памяти (адрес), где хранится выражение, называется l-значением этого выражения. Он всегда появляется слева от оператора присваивания.

Например:

day = 1;
week = day * 7;
month = 1;
year = month * 12;

Из этого примера мы понимаем, что постоянные значения, такие как 1, 7, 12, и переменные, такие как день, неделя, месяц и год, имеют r-значения. Только переменные имеют l-значения, так как они также представляют назначенную им ячейку памяти.

Например:

7 = x + y;

является ошибкой l-значения, поскольку константа 7 не представляет какой-либо ячейки памяти.

Формальные параметры

Переменные, которые принимают информацию, передаваемую вызывающей процедурой, называются формальными параметрами. Эти переменные объявлены в определении вызываемой функции.

Фактические параметры

Переменные, значения или адреса которых передаются в вызываемую процедуру, называются фактическими параметрами. Эти переменные указываются в вызове функции как аргументы.

Example:

fun_one()
{
   int actual_parameter = 10;
   call fun_two(int actual_parameter);
}
   fun_two(int formal_parameter)
{
   print formal_parameter;
}

Формальные параметры содержат информацию о фактическом параметре в зависимости от используемого метода передачи параметров. Это может быть значение или адрес.

Переход по значению

В механизме передачи по значению вызывающая процедура передает r-значение фактических параметров, и компилятор помещает его в запись активации вызываемой процедуры. Формальные параметры затем содержат значения, переданные вызывающей процедурой. Если значения, содержащиеся в формальных параметрах, изменяются, это не должно влиять на фактические параметры.

Пройти по ссылке

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

Пройти копированием-восстановлением

Этот механизм передачи параметров работает аналогично «передаче по ссылке», за исключением того, что изменения фактических параметров вносятся при завершении вызываемой процедуры. При вызове функции значения фактических параметров копируются в запись активации вызываемой процедуры. Формальные параметры, если ими манипулируют, не влияют в реальном времени на фактические параметры (поскольку l-значения передаются), но когда вызываемая процедура завершается, l-значения формальных параметров копируются в l-значения фактических параметров.

Example:

int y; 
calling_procedure() 
{
   y = 10;     
   copy_restore(y); //l-value of y is passed
   printf y; //prints 99 
}
copy_restore(int x) 
{     
   x = 99; // y still has value 10 (unaffected)
   y = 0; // y is now 0 
}

Когда эта функция завершается, l-значение формального параметра x копируется в фактический параметр y. Даже если значение y изменяется до завершения процедуры, l-значение x копируется в l-значение y, заставляя его вести себя как вызов по ссылке.

Пройти по имени

Такие языки, как Algol, предоставляют новый вид механизма передачи параметров, который работает как препроцессор в языке C. В механизме передачи по имени имя вызываемой процедуры заменяется ее фактическим телом. Передача по имени текстуально заменяет выражения аргументов в вызове процедуры на соответствующие параметры в теле процедуры, так что теперь она может работать с фактическими параметрами, так же как передача по ссылке.

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

В зависимости от используемого языка таблица символов может служить следующим целям:

• Хранить имена всех сущностей в структурированной форме в одном месте.

• Чтобы проверить, была ли объявлена ​​переменная.

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

• Чтобы определить область действия имени (разрешение области).

Таблица символов - это просто таблица, которая может быть линейной или хеш-таблицей. Он поддерживает запись для каждого имени в следующем формате:

<symbol name,  type,  attribute>

Например, если таблица символов должна хранить информацию о следующем объявлении переменной:

static int interest;

тогда он должен сохранить запись, например:

<interest, int, static>

Предложение атрибута содержит записи, относящиеся к имени.

Реализация

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

• Линейный (отсортированный или несортированный) список
• Дерево двоичного поиска
• Хеш-таблица

Среди всего прочего, таблицы символов в основном реализованы как хэш-таблицы, где сам символ исходного кода рассматривается как ключ для хеш-функции, а возвращаемое значение - это информация о символе.

Операции

Таблица символов, линейная или хеш-функция, должна обеспечивать следующие операции.

вставить ()

Эта операция чаще используется на этапе анализа, то есть на первой половине компилятора, где маркеры идентифицируются, а имена сохраняются в таблице. Эта операция используется для добавления информации в таблицу символов об уникальных именах, встречающихся в исходном коде. Формат или структура, в которой хранятся имена, зависят от используемого компилятора.

Атрибут символа в исходном коде - это информация, связанная с этим символом. Эта информация содержит значение, состояние, область действия и тип символа. Функция insert () принимает символ и его атрибуты в качестве аргументов и сохраняет информацию в таблице символов.

Например:

int a;

должен обрабатываться компилятором как:

insert(a, int);

искать()

Операция lookup () используется для поиска имени в таблице символов, чтобы определить:

• если символ существует в таблице.
• если он объявлен до его использования.
• если имя используется в области видимости.
• если символ инициализирован.
• если символ объявлен несколько раз.

Формат функции lookup () зависит от языка программирования. Базовый формат должен соответствовать следующему:

lookup(symbol)

Этот метод возвращает 0 (ноль), если символ не существует в таблице символов. Если символ существует в таблице символов, он возвращает его атрибуты, хранящиеся в таблице.

Управление содержанием

Компилятор поддерживает два типа таблиц символов: global symbol table к которому можно получить доступ с помощью всех процедур и scope symbol tables которые создаются для каждой области в программе.

Чтобы определить объем имени, таблицы символов организованы в иерархическую структуру, как показано в примере ниже:

. . . 
int value=10;

void pro_one()
   {
   int one_1;
   int one_2;
   
      {              \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
      }              /
      
   int one_5; 
   
      {              \   
      int one_6;      |_  inner scope 2
      int one_7;      |
      }              /
   }
   
void pro_two()
   {
   int two_1;
   int two_2;
   
      {              \
      int two_3;      |_  inner scope 3
      int two_4;      |
      }              /
      
   int two_5;
   }
. . .

Вышеуказанная программа может быть представлена ​​в виде иерархической структуры таблиц символов:

Таблица глобальных символов содержит имена для одной глобальной переменной (значение int) и двух имен процедур, которые должны быть доступны для всех дочерних узлов, показанных выше. Имена, упомянутые в таблице символов pro_one (и всех ее дочерних таблицах), недоступны для символов pro_two и ее дочерних таблиц.

Эта иерархия структуры данных таблицы символов хранится в семантическом анализаторе, и всякий раз, когда необходимо найти имя в таблице символов, поиск выполняется с использованием следующего алгоритма:

• сначала будет выполняться поиск символа в текущей области, т.е. в текущей таблице символов.

• если имя найдено, то поиск завершен, иначе он будет искать в родительской таблице символов до тех пор, пока,

• либо имя найдено, либо глобальная таблица символов была найдена для поиска имени.

Исходный код можно напрямую транслировать в его целевой машинный код, тогда зачем вообще нам нужно переводить исходный код в промежуточный код, который затем транслируется в его целевой код? Давайте посмотрим, почему нам нужен промежуточный код.

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

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

• Вторая часть компилятора, синтез, изменяется в зависимости от целевой машины.

• Становится проще применять модификации исходного кода для повышения производительности кода, применяя методы оптимизации кода к промежуточному коду.

Промежуточное представление

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

• High Level IR- Представление промежуточного кода высокого уровня очень близко к самому исходному языку. Их можно легко сгенерировать из исходного кода, и мы можем легко применить модификации кода для повышения производительности. Но для оптимизации целевой машины это менее предпочтительно.

• Low Level IR - Он близок к целевой машине, что делает его подходящим для распределения регистров и памяти, выбора набора команд и т. Д. Это хорошо для машинно-зависимых оптимизаций.

Промежуточный код может быть либо специфичным для языка (например, байтовый код для Java), либо независимым от языка (трехадресный код).

Трехадресный код

Генератор промежуточного кода принимает входные данные от предшествующей ему фазы, семантического анализатора, в виде аннотированного синтаксического дерева. Это синтаксическое дерево затем может быть преобразовано в линейное представление, например, в постфиксную нотацию. Промежуточный код обычно машинно-независимый. Поэтому генератор кода предполагает наличие неограниченного количества хранилищ памяти (регистров) для генерации кода.

Например:

a = b + c * d;

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

r1 = c * d;
r2 = b + r1;
a = r2

r используется в качестве регистров в целевой программе.

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

Четверки

Каждая инструкция в четверном представлении разделена на четыре поля: оператор, аргумент 1, аргумент 2 и результат. Приведенный выше пример представлен ниже в четверном формате:

Тройки

Каждая инструкция в тройном представлении имеет три поля: op, arg1 и arg2. Результаты соответствующих подвыражений обозначаются позицией выражения. Тройки представляют собой сходство с DAG и синтаксическим деревом. Они эквивалентны DAG при представлении выражений.

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

Косвенные тройки

Это представление является улучшением представления троек. Он использует указатели вместо позиции для хранения результатов. Это позволяет оптимизаторам свободно перемещать подвыражение для создания оптимизированного кода.

Декларации

Перед использованием переменная или процедура должны быть объявлены. Объявление включает выделение места в памяти и запись типа и имени в таблице символов. Программа может быть написана и разработана с учетом структуры целевой машины, но не всегда может быть возможно точно преобразовать исходный код на целевой язык.

Принимая всю программу как набор процедур и подпроцедур, становится возможным объявить все имена локальными для процедуры. Распределение памяти выполняется последовательно, а имена выделяются в памяти в той последовательности, в которой они объявлены в программе. Мы используем переменную смещения и устанавливаем ее на ноль {offset = 0}, что обозначает базовый адрес.

Исходный язык программирования и архитектура целевой машины могут различаться по способу хранения имен, поэтому используется относительная адресация. В то время как первое имя выделяется памятью, начиная с ячейки памяти 0 {смещение = 0}, следующее имя, объявленное позже, должно располагаться в памяти рядом с первым.

Example:

Мы возьмем пример языка программирования C, в котором целочисленной переменной назначается 2 байта памяти, а переменной с плавающей запятой назначается 4 байта памяти.

int a;
float b;
Allocation process:
{offset = 0}
int a;
id.type = int
id.width = 2
offset = offset + id.width 
{offset = 2}
float b;
   id.type = float
   id.width = 4
   offset = offset + id.width 
{offset = 6}

Чтобы ввести эту деталь в таблицу символов, можно использовать процедуру ввода . Этот метод может иметь следующую структуру:

enter(name, type, offset)

Эта процедура должна создать запись в таблице символов для имени переменной , для которой задан тип и относительное смещение адреса в области данных.

Генерацию кода можно рассматривать как завершающую фазу компиляции. Посредством генерации пост-кода процесс оптимизации может быть применен к коду, но это можно рассматривать как часть самого этапа генерации кода. Код, сгенерированный компилятором, представляет собой объектный код некоторого языка программирования нижнего уровня, например языка ассемблера. Мы видели, что исходный код, написанный на языке более высокого уровня, преобразуется в язык более низкого уровня, в результате чего получается объектный код более низкого уровня, который должен иметь следующие минимальные свойства:

• Он должен нести точное значение исходного кода.
• Он должен быть эффективным с точки зрения использования ЦП и управления памятью.

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

Направленный ациклический граф

Направленный ациклический график (DAG) - это инструмент, который отображает структуру базовых блоков, помогает увидеть поток значений, перемещающихся между базовыми блоками, а также предлагает оптимизацию. DAG обеспечивает легкое преобразование базовых блоков. DAG можно понять здесь:

• Листовые узлы представляют собой идентификаторы, имена или константы.

• Внутренние узлы представляют операторов.

• Внутренние узлы также представляют результаты выражений или идентификаторов / имен, где значения должны быть сохранены или присвоены.

Example:

t0 = a + b
t1 = t0 + c
d = t0 + t1

[t 0 = a + b]

[t 1 = t 0 + c]

[d = t 0 + t 1 ]

Оптимизация глазка

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

Устранение избыточных инструкций

На уровне исходного кода пользователь может делать следующее:

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }

int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }

int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }

int add_ten(int x)
   {
   return x + 10;
   }

На уровне компиляции компилятор ищет инструкции, избыточные по своей природе. Многократная загрузка и сохранение инструкций могут иметь одно и то же значение, даже если некоторые из них удалены. Например:

• MOV x, R0
• MOV R0, R1

Мы можем удалить первую инструкцию и переписать предложение как:

MOV x, R1

Недостижимый код

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

Example:

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

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

Оптимизация потока управления

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

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

В этом коде метка L1 может быть удалена, поскольку она передает управление L2. Таким образом, вместо перехода к L1, а затем к L2, элемент управления может напрямую достигать L2, как показано ниже:

...		
MOV R1, R2
GOTO L2
...
L2 :   INC R1

Упрощение алгебраических выражений

Бывают случаи, когда алгебраические выражения можно сделать простыми. Например, выражениеa = a + 0 можно заменить на a само себя и выражение a = a + 1 можно просто заменить на INC a.

Снижение силы

Есть операции, которые требуют больше времени и места. Их «силу» можно уменьшить, заменив их другими операциями, которые требуют меньше времени и места, но дают тот же результат.

Например, x * 2 можно заменить на x << 1, который включает только один сдвиг влево. Хотя вывод a * a и a ² одинаков, ² гораздо эффективнее реализовать.

Доступ к машинным инструкциям

Целевая машина может развертывать более сложные инструкции, которые могут иметь возможность выполнять определенные операции более эффективно. Если целевой код может выполнять эти инструкции напрямую, это не только улучшит качество кода, но и даст более эффективные результаты.

Генератор кода

Предполагается, что генератор кода должен понимать среду выполнения целевой машины и ее набор команд. Генератор кода должен учитывать следующие моменты для создания кода:

• Target language: Генератор кода должен знать природу целевого языка, для которого необходимо преобразовать код. Этот язык может облегчить выполнение некоторых машинно-ориентированных инструкций, чтобы помочь компилятору сгенерировать код более удобным способом. Целевая машина может иметь архитектуру процессора CISC или RISC.

• IR Type: Промежуточное представление имеет разные формы. Это может быть структура абстрактного синтаксического дерева (AST), обратная польская нотация или трехадресный код.

• Selection of instruction: Генератор кода принимает промежуточное представление в качестве входных данных и преобразует (отображает) его в набор команд целевой машины. Одно представление может иметь много способов (инструкций) для его преобразования, поэтому ответственность за правильный выбор соответствующих инструкций ложится на генератор кода.

• Register allocation: Программа имеет ряд значений, которые необходимо поддерживать во время выполнения. Архитектура целевой машины может не позволять хранить все значения в памяти или регистрах ЦП. Генератор кода решает, какие значения хранить в регистрах. Кроме того, он решает, какие регистры будут использоваться для хранения этих значений.

• Ordering of instructions: Наконец, генератор кода определяет порядок, в котором инструкция будет выполняться. Он создает расписания для инструкций по их выполнению.

Дескрипторы

Генератор кода должен отслеживать как регистры (на предмет наличия), так и адреса (расположение значений) при генерации кода. Для них обоих используются следующие два дескриптора:

• Register descriptor: Дескриптор регистра используется для информирования генератора кода о доступности регистров. Дескриптор регистра отслеживает значения, хранящиеся в каждом регистре. Когда во время генерации кода требуется новый регистр, этот дескриптор запрашивает доступность регистра.

• Address descriptor: Значения имен (идентификаторов), используемых в программе, могут храниться в разных местах во время выполнения. Дескрипторы адресов используются для отслеживания ячеек памяти, где хранятся значения идентификаторов. Эти ячейки могут включать в себя регистры ЦП, кучи, стеки, память или комбинацию упомянутых ячеек.

Генератор кода обновляет оба дескриптора в режиме реального времени. Для оператора загрузки LD R1, x генератор кода:

• обновляет дескриптор регистра R1, который имеет значение x и
• обновляет дескриптор адреса (x), чтобы показать, что один экземпляр x находится в R1.

Генерация кода

Базовые блоки состоят из последовательности трехадресных инструкций. Генератор кода принимает эту последовательность инструкций в качестве входных данных.

Note: Если значение имени находится более чем в одном месте (регистр, кеш или память), значение регистра будет предпочтительнее, чем кэш и основная память. Точно так же значение кеша будет предпочтительнее основной памяти. Основной памяти практически не отдается предпочтение.

getReg: Генератор кода использует функцию getReg для определения состояния доступных регистров и расположения значений имени. getReg работает следующим образом:

• Если переменная Y уже находится в регистре R, она использует этот регистр.

• В противном случае, если доступен какой-либо регистр R, он использует этот регистр.

• В противном случае, если оба вышеуказанных параметра невозможны, он выбирает регистр, который требует минимального количества инструкций загрузки и сохранения.

Для инструкции x = y OP z генератор кода может выполнять следующие действия. Предположим, что L - это место (предпочтительно регистр), где должен быть сохранен вывод y OP z:

• Вызовите функцию getReg, чтобы определить местонахождение L.

• Определите текущее местоположение (регистр или память) y обращаясь к дескриптору адреса y. Еслиy в настоящее время нет в реестре L, затем сгенерируйте следующую инструкцию, чтобы скопировать значение y к L:

  MOV y ', L

  где y’ представляет собой скопированное значение y.

• Определите текущее местонахождение z используя тот же метод, что и на шаге 2 для y и сгенерируйте следующую инструкцию:

  OP z ', L

  где z’ представляет собой скопированное значение z.

• Теперь L содержит значение y OP z, которое предназначено для присвоения x. Итак, если L - регистр, обновите его дескриптор, чтобы указать, что он содержит значениеx. Обновите дескрипторx чтобы указать, что он хранится в месте L.

• Если y и z больше не используются, их можно вернуть в систему.

Другие конструкции кода, такие как циклы и условные операторы, преобразуются в язык ассемблера общим способом ассемблера.

Оптимизация - это метод преобразования программы, который пытается улучшить код, заставляя его потреблять меньше ресурсов (т.е. ЦП, память) и обеспечивать высокую скорость.

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

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

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

• Оптимизация должна быть быстрой и не должна задерживать общий процесс компиляции.

Попытки оптимизировать код могут быть предприняты на различных уровнях компиляции процесса.

• Вначале пользователи могут изменить / переставить код или использовать лучшие алгоритмы для написания кода.

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

• При создании целевого машинного кода компилятор может использовать иерархию памяти и регистры ЦП.

Оптимизацию можно разделить на два типа: машинно-независимую и машинно-зависимую.

Машинно-независимая оптимизация

В этой оптимизации компилятор принимает промежуточный код и преобразует часть кода, которая не включает регистры ЦП и / или абсолютные ячейки памяти. Например:

do
{
   item = 10;
   value = value + item; 
}while(value<100);

Этот код включает в себя повторное присвоение элемента идентификатора, который, если мы выразимся так:

Item = 10;
do
{
   value = value + item; 
} while(value<100);

не только экономит циклы ЦП, но и может использоваться на любом процессоре.

Машинно-зависимая оптимизация

Машинно-зависимая оптимизация выполняется после того, как целевой код был сгенерирован и когда код преобразован в соответствии с архитектурой целевой машины. Он включает регистры ЦП и может иметь абсолютные ссылки на память, а не относительные. Машинно-зависимые оптимизаторы стараются максимально использовать преимущества иерархии памяти.

Основные блоки

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

Программа может иметь различные конструкции в качестве базовых блоков, такие как условные операторы IF-THEN-ELSE, SWITCH-CASE и циклы, такие как DO-WHILE, FOR, REPEAT-UNTIL и т. Д.

Базовая идентификация блока

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

• Операторы заголовка поиска всех базовых блоков, с которых начинается базовый блок:

  • Первая инструкция программы.
  • Заявления, являющиеся целью любой ветви (условные / безусловные).
  • Заявления, следующие за любым оператором ветвления.

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

• Базовый блок не включает в себя какой-либо заголовок любого другого базового блока.

Базовые блоки - важные концепции как с точки зрения генерации кода, так и с точки зрения оптимизации.

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

График потока управления

Базовые блоки в программе могут быть представлены в виде графов управления. График потока управления показывает, как управление программой передается между блоками. Это полезный инструмент, который помогает в оптимизации, помогая обнаруживать любые нежелательные петли в программе.

Оптимизация цикла

Большинство программ запускаются в системе как цикл. Становится необходимым оптимизировать циклы, чтобы сэкономить циклы процессора и память. Циклы можно оптимизировать с помощью следующих методов:

• Invariant code: Фрагмент кода, который находится в цикле и вычисляет одно и то же значение на каждой итерации, называется инвариантным к циклу кодом. Этот код можно вывести из цикла, сохранив его для однократного вычисления, а не для каждой итерации.

• Induction analysis : Переменная называется индукционной переменной, если ее значение изменяется внутри цикла на инвариантное значение.

• Strength reduction: Есть выражения, которые потребляют больше циклов ЦП, времени и памяти. Эти выражения следует заменить более дешевыми выражениями без ущерба для вывода выражения. Например, умножение (x * 2) дороже с точки зрения циклов ЦП, чем (x << 1), и дает тот же результат.

Устранение мертвого кода

Мертвый код - это один или несколько операторов кода, а именно:

• Либо никогда не казнен, либо недоступен,
• Или, если выполняется, их вывод никогда не используется.

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

Частично мертвый код

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

На приведенном выше графике потока управления изображен фрагмент программы, в котором переменная 'a' используется для присвоения выходных данных выражения 'x * y'. Предположим, что значение, присвоенное 'a', никогда не используется внутри цикла. Сразу после того, как элемент управления выходит из цикла, 'a' присваивается значение переменной 'z', которое будет использоваться позже в программе. Мы заключаем здесь, что код присваивания 'a' нигде не используется, поэтому он может быть исключен.

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

Частичное резервирование

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

[повторяющееся выражение]

[частично повторяющееся выражение]

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

Другим примером частично избыточного кода может быть:

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

Мы предполагаем, что значения операндов (y и z) не изменяются от присвоения переменной a изменять c. Здесь, если утверждение условия истинно, то y OP z вычисляется дважды, в противном случае - один раз. Движение кода можно использовать для устранения этой избыточности, как показано ниже:

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

Здесь, является ли условие истинным или ложным; y OP z следует вычислять только один раз.