Для транслятора исходная программа – это длинная цепочка символов. Транслятор производит анализ структуры программы, разбирая ее текст последовательно, символ за символом.
Лексический анализ или сканирование. Начальный этап любой трансляции состоит в выделении в исходной программе элементарных составляющих: идентификаторов, разделителей, символов операций, чисел, ключевых и необязательных слов, пробелов, комментариев и т.д. Этот этап называется лексическим анализом, а те программные единицы, которые получаются в результате такого анализа, называются лексическими единицами или лексемами.
Происходит идентификация типа каждой лексемы (число, ограничитель, идентификатор, оператор и т.д.) и пометка ее как принадлежащую определенному типу. Идентификаторы заносятся в таблицу символов и затем вместо символов используется адрес строки из этой таблицы.
Формальной моделью, используемой для создания лексического анализатора, являются конечные автоматы.
Хотя концепция лексического анализа достаточно проста, фактически этот этап занимает больше времени, чем любой другой. Это происходит потому, что транслятор должен сканировать и анализировать исходную программу символ за символом. Выделить границу между лексемами иногда довольно трудно и приходиться прибегать к сложным контекстно-зависимым алгоритмам. Например, два оператора FORTRAN
DO 10 I = 1,5 и DO 10 I = 1.5
представляют собой совершенно различные синтаксические структуры, хотя почти одинаковые по написанию. Контекстный анализ позволяет на момент прохождения символа «запятая» ( в первом операторе) и символа «точка» ( во втором операторе) выявить, что первый оператор – это оператор цикла DO, а второй – оператор присваивания значения переменной DO10I. Следует помнить, что в языке FORTRAN пробелы игнорируются.
Синтаксический анализ или разбор. На этом этапе результаты лексического анализа – лексемы – используются для идентификации более крупных программных структур: операторов, объявлений, выражений и т.д.
Синтаксический анализ обычно чередуется с семантическим. Сначала СинА идентифицирует последовательность лексем, формирующих СинЕд – выражение, оператор, вызов подпрограммы или объявление. Затем вызывается СемА для обработки этой СимЕд. Обычно для связи СинА и СемА используется стек.
Основная задача, стоящая перед разработчиками языков в этой области, заключается в том, чтобы найти эффективные методы синтаксического анализа, в частности, использующие теорию формальных грамматик и методы моделирования свойств языка.
Семантический анализ. Является самым важным этапом трансляции. Выполняется обработка структур от СинА и начинается формирование структуры выполняемого объектного кода. Это своего рода мост между частями трансляции анализ и синтез.
На этом этапе есть еще важные функции: поддержка таблицы символов, обнаружение большинства ошибок, замена макросов их определениями, выполнение операторов времени компиляции. Итак, наиболее общие функции:
- Поддержка таблицы символов. Таблица символов – одна из основных структур для каждого транслятора. Таблица символов содержит элементы, каждый из которых соответствует какому-либо идентификатору, имеющемуся в программе. Лексический анализатор создает начальные элементы таблицы по мере того, как он сканирует исходную программу. Но таблица символов содержит не только идентификаторы от лексического анализатора. Элемент таблицы символов хранит также дополнительную информацию об атрибутах этого идентификатора: его тип (проста переменная, имя массива, имя подпрограммы и т.д.), тип значения (целочисленный, вещественный и т.д.) – то есть всю информацию, которую можно извлечь из объявления и применения этого идентификатора в исходной программе. Семантический анализатор заносит эту информацию в таблицу символов по мере обработки объявлений, заголовков подпрограмм и операторов программы.
Таблица символов в трансляторах компилируемых языков обычно уничтожается после окончания трансляции. Но для языков, которые допускают введение новых идентификаторов во время выполнения или отладки, она может сохраняться и во время выполнения программы. Во всех реализациях языков ML, Prolog и LISP таблица символов создается на этапе трансляции и затем используется во время выполнения программы как центральная структура данных, определенная системой.
- Включение неявной информации – перевод так называемых соглашений по умолчанию, когда программист не задает явные спецификации: например, в FORTRAN переменной без явного типа приписывается тип по первому символу имени переменной. Поэтому необходимо, чтобы информация, неявно содержащаяся в исходной программе, стала явной в объектной программе низкого уровня.
- Обнаружение ошибок. СинА и СемА должны обнаруживать некорректные объекты после лексического анализатора. В любой момент лексический анализатор может послать синтаксическому анализатору лексему, которая не вписывается в окружающий контекст (например, разделитель операторов среди последовательности оператора, индексированная переменная с тремя индексами вместо элемента двухмерного массива и т.д.). Семантический анализатор должен распознать подобные ошибки, выдать соответствующее сообщение, а также определить, каким образом можно продолжить синтаксический анализ оставшейся части программы.
- Макрообработки и операции, выполняемые во время компиляции. Эти функции предусмотрены не во всех языках, но если они присутствуют, то обычно соответствующая обработка проводится СемА.
Макрос в простейшей форме - это часть текста программы, которая определена отдельно и должна быть вставлена в программу во время трансляции, когда в программе встречается соответствующий вызов. Таким образом, макрос напоминает подпрограмму, с тем лишь отличием, что подпрограмма транслируется отдельно и вызывается во время выполнения ( то есть связывание имени подпрограммы с ее семантикой происходит во время выполнения), а в случае с макросом вместо каждого вызова во время трансляции просто подставляется его тело ( то есть связывание происходит во время трансляции). Макросы похожи на подпрограммы с параметрами, которые требуется обработать, прежде чем произойдет подстановка в месте вызова макроса. Если макросы в языке допускаются, то СемА должен идентифицировать вызовы макросов в исходной программе и осуществить соответствующую подстановку тела макроса. Тем самым прерывается работа лексического и синтаксического анализаторов, обрабатывается вызов макроса и затем продолжается анализ оставшейся части исходной программы.
Операция, выполняемая во время компиляции – эта операция, которая должна выполняться во время трансляции и осуществлять контроль над трансляцией исходной программы. Например, в языке С операция #define позволяет вычислить значение констант и выражений до начала компиляции программы. Операция #ifdef (if-defined) позволяет транслировать какой-то один из нескольких альтернативных фрагментов кода в зависимости от наличия или отсутствия определенных переменных.
Похожие статьи:
