Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

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

Транслирующие программы делятся на две категории: интерпретаторы и компиляторы.

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

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

Каждый из этих способов преобразования имеет свои достоинства и недостатки.

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

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

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

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

Шаги преобразования программ

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

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

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

  • Исходная программа. Программа должна описывать логику решения задачи и удовлетворять правилам записи, в соответствии с которыми интерпретатор или компилятор осуществляют трансляцию.
  • Интерпретатор. Трансляция интерпретируемой исходи ой программы проходит в четыре этапа. На первом этапе - лексического анализа - группы литер исходного языка преобразуются в символы, понятные интерпретатору. Затем следует этап синтаксического анализа, когда символы размещаются в иерархическом порядке, отражающем логику программы. На третьем этапе - контроля типов проверяется согласованность символов друг с другом, что позволяет выявить ошибки в программе. И наконец, генератор кода посылает машинные команды в процессору, где они немедленно выполняются.
  • Компилятор. Подобно интерпретатору, компилятор также пропускает программу через этапы лексического анализа, синтаксического анализа, контроля типов и генерации кода. Но в этом случае оттранслированная программа не выполняется немедленно, а сохраняется в памяти компьютера; дополнительный этап в работе компилятора - так называемая оптимизация - улучшает результат трансляции, повышая эффективность полученной программы.
  • Целевой код. На выходе компилятора можно получить либо последовательность машинных команд низкого уровня, называемую объектным кодом, либо последовательность команд языка ассемблера. Если целевой код является языком ассемблера, то перед выполнением его следует оттранслировать ассемблером.
 
На каждом этапе информация, полученная от предыдущего этапа, обрабатывается и передается дальше. Если какое-либо правило языка оказывается нарушенным, запускается подпрограмма обработки ошибок, которая сообщает программисту о найденной ошибке.

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

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

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

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

Большинство лексем, создаваемых сканером, имеют фиксированный смысл. Ключевые слова (например, begin, if, end) указывают на действия, задаваемые синтаксисом языка программирования.

Операции (типа + и : = , т. е. присвоить значение переменной) указывают на арифметические, логические действия или пересылку данных. Числа задают реальные числовые значения, скажем 5 или 7.

Знаки пунктуации помогают транслятору разобраться в структуре программы.

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

Синтаксический анализ. Составление синтаксического дерева из кусочков

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

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

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

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

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

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

Контроль типов и обнаружение ошибок

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

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

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

Если типы сыновей одного отца не совпадают, то транслятор использует правило: позволяющее ему продолжить работу. Например, если один из сыновей имеет целый, а другой - вещественный тип, то такое правило может указывать, что отец должен иметь вещественный тип. Однако возможны неразрешимые сочетания типов. На рисунке показан случай, когда один сын имеет целый (I) тип, а второй литерный (C). Для такой комбинации типов не существует правила разрешения, и поэтому транслятор выдает программисту сообщение об ошибке.

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

Генерация кода: разборка дерева для получения команд

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

Как и на предыдущих этапах трансляции, обход дерева совершается в соответствии с правилами языка, используемого для написания исходной программы. Обход начинается с верхушки дерева и продолжается в направлении вниз и вправо по его периметру. Когда встречается узел «отец», перебираются по очереди все его «сыновья»; если «сын» является также и «отцом», то перебираются и его «сыновья». Так происходит спуск по дереву, пока не встретится узел, не имеющий «сыновей». Из такого узла берется лексема и рассматривается следующий «сын». В конце концов перебираются все «сыновья» на самом низком уровне в этой ветке дерева. Тогда происходит возврат к «отцу», который теперь обрабатывается. Обойдя дерево, соответствующее одному выделенному фрагменту, интерпретатор вызывает подпрограмму на машинном языке, которая и выполняет нужную операцию, прежде чем приступить к разбору следующего фрагмента. Компилятор же обходит дерево всей программы, генерируя код и записывая его в память для последующего выполнения или обработки.

Оптимизация кода для повышения эффективности

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

В интерпретаторе с этим приходится мириться, но в компиляторе предусмотрено специальное средство ликвидации такой неэффективности.

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

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

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