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

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

1. Задача синтаксического анализатора
2. Распознающие грамматики
3. Дерево разбора
4. Стратегии разбора
5. Разбор рекурсивным спуском
6. Ограниченные грамматики
7. Магазинные автоматы

Задача синтаксического анализатора

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

Программирование лексических анализаторов
Рассмотрим для примера следующую схему лексического анализа.
Исходные данные и структуры
Имеется входная цепочка символов. Пустая таблица имен. И 3 множества символов
• LA – множество символов латинского алфавита.
• TZ – Множество знаков, являющихся терминалами языка
• SP – Множество пробельных символов
• ZPR – Множество знаков препинания (ZPR=SP U TZ).

Общая схема работы лексического анализатора такова.
• Сначала выделяем отдельную лексему (используя множества ZPR и TZ).
• Если выделенная лексема – ограничитель, то он выдается как результат лексического анализа.
• Если это идентификатор, то делается проверка на принадлежность его множеству ключевых слов. Если да, то выдается признак соответствующего ключевого слова, если нет – выдается лексема идентификатора. Сам идентификатор сохраняется в таблице имен, если его еще там нет. В лексему помещается ссылка на таблицу имен.
• Если выделенная лексема принадлежит какому-либо из других классов лексем (число, строка и т.д.), то выдается признак лексема соответствующего класса, а значение лексемы сохраняется в качестве признака или в таблице имен.
Продолжить читать "Программирование лексических анализаторов"

Лексический анализ
План
1. Основная задача
2. Классы лексем
3. Построение анализатора
4. Требования к таблице имен
5. Структуры данных
6. Реализация сканера
7. Блок-схема
Основная задача лексического анализа – разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, т.е. выделить эти слова из непрерывной последовательности символов.
Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители). В некоторых случаях между лексемами может и не быть разделителей. С другой стороны, в некоторых языках лексемы могут содержать незначащие символы (пробелы и комментарии). 
Продолжить читать "Лексический анализ"

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

Лексический анализ
На фазе лексического анализа (ЛА) входная программа, представляющая собой поток символов, разбивается на лексемы – слова в соответствии с определениями языка. Основным формализмом, лежащим в основе реализации лексических анализаторов, являются конечные автоматы и регулярные выражения. Лексический анализатор может работать в двух основных режимах:
• Как подпрограмма, вызываемая синтаксическим анализатором за очередной лексемой;
Продолжить читать "Лексический анализ"

Генератор промежуточного кода
Затем программа может быть переведена во внутреннее представление. Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор. Тогда только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другое.
Оптимизация
Оптимизация призвана улучшить характеристики программы. Скажем, уменьшить длину объектного кода или увеличить быстродействие.
Фаз оптимизации может быть несколько. Оптимизации обычно делят на
• Машинно-зависимые.и машинно-независимые,
• Локальные и глобальные.

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

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

Лексический анализ
На фазе лексического анализа (ЛА) входная программа, представляющая собой поток символов, разбивается на лексемы – слова в соответствии с определениями языка. Основным формализмом, лежащим в основе реализации лексических анализаторов, являются конечные автоматы и регулярные выражения. Лексический анализатор может работать в двух основных режимах:
• Как подпрограмма, вызываемая синтаксическим анализатором за очередной лексемой;
• Как полный проход, результатом которого является файл лексем.

В процессе выделения лексем ЛА может, как самостоятельно строить таблицы имен и констант, так и выдавать значения для каждой лексемы при очередном обращении к нему. В этом случае таблица имен строится совместно в нескольких фазах (например, в лексическом анализе делается попытка добавить новое имя, а синтаксический анализ разрешает или отвергает попытку и присваивает лексеме некоторые атрибуты, которые уточняются контекстным анализатором).
На этапе ЛА обнаруживаются некоторые (простейшие) ошибки (недопустимые символы, неправильная запись чисел, идентификаторов и др.).
Синтаксический анализ
Основная задача синтаксического анализа – разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в
контекстно-свободной грамматике языка. В настоящее время чаще всего используется следующие виды анализа:
Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора
• LL(1)-анализ (и его вариант – рекурсивный спуск)
• LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие)., LR(1) – при использовании систем автоматизации построения синтаксических анализаторов.
• Анализ простого предшествования
Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицу имен. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы.
Контекстный анализ
На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно-свободным синтаксисом. Это в основном связи “описание-использование”, в частности анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие.
В процессе контекстного анализа строится таблица символов, которую можно рассматривать как таблицу имен, пополненную информацией об описаниях (свойствах) объектов. Основным формализмом, использующимся при контекстном анализе, являются атрибутные грамматики.
Результатом работы фазы контекстного анализа является снабженное атрибутами дерево разбора программы или.
Информация об объектах может быть, как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах символов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов.

Обобщенная структура компилятора и основные фазы компиляции
Продолжить читать "Структура компилятора"