Структура транслятора

1. Примеры грамматик
2. Структура компилятора
3. Лексический анализ
4. Синтаксический анализ
5. Контекстный анализ
6. Генерация промежуточного кода
7. Оптимизация
8. Генерация объектного кода
9. Интерпретация промежуточного кода
Продолжить читать "Структура транслятора"

Бэкуса — Наура формы (БНФ)
Широко используемой формой записи правил КС-грамматик является БНФ. В ней вместо символа →-используется символ ::==, а металингвистические переменные представляют собой слова или группы русских (или других) слов, заключенные в специальные кавычки <>, например: <арифметическое выражение>. Правила грамматики, записанные в БНФ, обычно называются (металингвистическими) формулами.
Продолжить читать "Бэкуса — Наура формы (БНФ)"

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

Набор допустимых преобразований.

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

Однозначность грамматики и языка.
Одним из важных свойств грамматики с точки зрения трансляции является ее однозначность, означающая то, что не существует предложения, являющегося кроной двух или более деревьев вывода в данной грамматике. (Неоднозначность грамматики нельзя путать с неоднозначностью языка, порождаемого грамматикой. Язык неоднозначен, если его нельзя породить ни одной однозначной грамматикой. Таков, например, язык, состоящий из всех цепочек аnbmck, в которых либо п = т, либо т = k.)

Продолжить читать "Однозначность грамматики и языка"

Преобразования грамматик
1. Эквивалентные преобразования грамматик
2. Однозначность грамматики и языка.
3. Набор допустимых преобразований.
4. Достижимые свойства грамматик.
5. Автоматные языки
6. Бэкуса — Наура формы (БНФ)

Продолжить читать "Преобразования грамматик"

Контекстно-свободные языки
Из четырех классов грамматик Хомского наиболее важным с точки зрения приложений к языкам программирования является класс контекстно-свободных грамматик (или КС-грамматик). Это связано с тем, что средствами КС-грамматик удается достаточно полно описать синтаксические структуры существующих языков программирования, а также с тем, что имеются достаточно хорошо разработанные алгоритмы распознавания КС-языков, которые составляют важную часть транслятора — этап синтаксического анализа.
КС-грамматики обладают свойством локальности и независимости подстановок в том смысле, что подстановка, выполняемая в некоторой области (подцепочке) данной цепочки, никак не зависит от подстановок, выполняемых вне этой области, а результаты подстановки остаются внутри этой же области. Это свойство позволяет построение предложений и их анализ разбивать на подчасти, независимые друг от друга, а также приводит к существованию выводов в КС-грамматиках, эквивалентных в том смысле, что во всех них применяются одни и те же правила в одних и тех же местах, но в различном порядке.
Применение к цепочке правил подстановки по существу является двумерным процессом из-за независимости порядка выполнения подстановок в различных частях цепочки, поэтому удобным является использование графического представления класса всех эквивалентных выводов, называемое деревом вывода (или деревом разбора, когда все висячие вершины дерева помечены терминалами и символом е).
Дерево вывода в КС-грамматике — это помеченное упорядоченное дерево, удовлетворяющее следующим свойствам: вершины дерева помечены символами из V U W U {е}, причем корень дерева помечен символом Е, для любой внутренней вершины q0 дерева и списка ее сыновей q1, q2, . . ., qr,, перечисленных в порядке их упорядоченности, множество правил грамматики Р содержит такое правило А → a1 a2 . . .ar ,
что A, a1, a2, . . . , ar являются пометками вершин q1, q2, . . ., qr соответственно.
В качестве примера рассмотрим грамматику ({a, +, *, (,)}, {F, Е, Т}, Е, Р), в которой Р состоит из правил
Е → Е + Т|Т
T → T*F|F
F → (E)|a.
Вот примеры двух эквивалентных выводов в этой грамматике:
Е  Е + Т  Е + Т * F  Т + Т * F и Е  Е + Т  Т + T  T + T * F. Эти эквивалентные выводы цепочки Т + Т * F представляются в виде дерева вывода, изображенного на рис. 2.2. Здесь и в дальнейших примерах упорядочение сыновей вершин отражается их расположением слева направо. Грамматика, рассмотренная в данном примере, не раз еще будет использоваться при дальнейшем изложении; мы всегда будем обозначать ее через Г0.
Поскольку любое дерево вывода является упорядоченным, то для его висячих вершин существует единственное линейное упорядочение. Выписывая пометки висячих вершин в их упорядоченности, мы получаем цепочку, выводы которой представлены этим деревом. Эту цепочку мы будем называть кроной дерева. Часть кроны дерева, являющейся кроной некоторого его поддерева, называется фразой. Основа — самая левая фраза, не содержащая других (не совпадающих с ней) фраз. Например, изображенное выше дерево вывода в грамматике Г0 имеет три фразы: Т, Т * F и Т+Т * F, из которых фраза Т является основой.
Среди множества эквивалентных выводов одной и той же цепочки обычно выделяют так называемые правый и левый выводы.
Вывод α 1  α 2  …  α r называется левым (соответственно правым), если для любого i цепочка ai+1 получается из . ai применением правила к ее самому левому (соответственно к самому правому) вхождению нетерминала — левой (соответственно правой) подстановкой

Классификация Хомского
Грамматики можно классифицировать но виду их правил. Пусть Г == (V, W, Е, Р) — некоторая грамматика.
Продолжить читать "Классификация Хомского"

Грамматики составляющих
Терминальными символами (терминалами) называют символы, которые встречаются в множестве допустимых конструкций, т.е. входящими в ∑.
Нетерминальными символами (нетерминалами) называют символы, введенные в грамматику искусственно и используемыми для вывода и  ∑. До этого мы их называли понятиями (выражение, процедура, описание переменных, программа и т.д.).  
Продолжить читать "Грамматики составляющих"

Алфавитом называется любое конечное множество символов, называемых буквами, или знаками алфавита. Если написать последовательность символов, располагая их один за другим, то получается цепочка (а также слово, или строка) символов. Например, 001111 — цепочка в бинарном алфавите {0, 1}. Через е будет обозначаться пустая цепочка, т. е. цепочка, которая не содержит ни одного символа. ∑* обозначает множество всех цепочек в алфавите ∑, включая е, а ∑+ == ∑* — {е}. Длина цепочки х (обозначаем |x|) — это число символов в ней.
Продолжить читать "Цепочки и языки"