Переход к языкам высокого уровня

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

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

Большим шагом к высокоуровневым языкам программирования стала разра­ботка во второй половине 1950-х годов языка программирования Fortran — для научных вычислений, Cobol — для обработки бизнес-данных и Lisp — для сим­вольных вычислений. Философия, стоящая за этими языками, заключается в со­здании высокоуровневой системы обозначений, облегчающей программисту на­писание программ для численных вычислений, бизнес-приложений и символьных программ. Эти языки были столь успешны, что применяются и сегодня.

Пример информационного поиска

В библиотеках многих людей есть толстый том собрания произведений Шекспира Допустим, вы хотите определить, в какой пьесе используются слова Brutus AND Caesar AND NOT Calpumia. Для этого можно, например, прочитать текст от начала до конца, отмечая пьесы, содержащие слова Brutus и Caesar, и исключая из рассмотрения пьесы, в которых встречается слово Calpumia. Простейший компьютерный метод решения этой задачи сводится к последовательному просмотру (linear scanning) всех документов. Этот процесс часто называют прямым поиском или, на английском, grepping (от названия ко­манды grep, которая в операционной системе Unix выполняет этот процесс). Прямой по­иск по тексту может быть очень эффективным, особенно на современных компьютерах. Довольно часто такая обработка допускает поиск по шаблону с джокерами (wildcard pattern matching). На современных компьютерах выполнения простых запросов на коллек­циях данных среднего размера (общий объем тома собрания избранных произведений Шекспира составляет чуть меньше одного миллиона слов) вполне достаточно для рядо­вого пользователя.

Тем не менее во многих случаях необходимо нечто большее.

Булев поиск

Булев поиск

Смысл термина информационный поиск (information retrieval— IR) может быть очень широким. Даже извлечение кредитной карточки из бумажника для того, чтобы узнать ее номер, уже можно трактовать как вид информационного поиска. Тем не менее как научная дисциплина информационный поиск может быть определен следующим образом.
Информационный поиск (IR) — это процесс поиска в большой коллекции (хранящейся, как правило, в памяти компьютеров) некоего неструктурированного материала ("обычно — документа), удовлетворяющего информационные потребности.

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

7. Управление таблицей символов

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

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

Генерация и оптимизация кода

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

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

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

tl = inttofloat(60)  t2 = id3 * tl                       t3 = id2 + t2 idl = t3

(1.3)

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

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

Вторая фаза компилятора — синтаксический анализ или разбор (parsing). Ана­лизатор использует первые компоненты токенов, полученных при лексическом анализе, для создания древовидного промежуточного представления, которое опи­сывает грамматическую структуру потока токенов. Типичным представлением яв­ляется синтаксическое дерево, в котором каждый внутренний узел представляет операцию, а дочерние узлы — аргументы этой операции. Синтаксическое дере­во для потока токенов (1.2)показано на выходе синтаксического анализатора на рис. 1.7.

Структура компилятора

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

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

Синтез строит требуемую целевую программу на основе промежуточного представления и информации из таблицы символов. Анализ часто называют на­чальной стадией, а синтез — заключительной.