Основные принципы построения трансляторов

Лекция 2: Основные принципы построения трансляторов 1 Основные принципы построения трансляторов Транслятор – это программа, которая переводит входную программу на исходном (входном) языке в эквивалентную ей выходную программу на результирующем (выходном) языке. Сам транслятор является программой – обычно он входит в состав системного программного обеспечения вычислительной системы. То есть транслятор – это часть программного обеспечения, он представляет собой набор машинных команд и данных и выполняется компьютером, как и все прочие программы в рамках операционной системы. Все составные части транслятора представляют собой фрагменты или модули программы со своими входными и выходными данными. Исходными данными для работы транслятора служит текст входной программы – некоторая последовательность предложений входного языка программирования, удовлетворяющая его синтаксическим и семантическим требованиям. Выходными данными транслятора является текст результирующей программы. Результирующая программа строится по синтаксическим правилам, заданным в выходном языке транслятора, а ее смысл определяется семантикой выходного языка. Результатом работы транслятора будет результирующая программа, но только в том случае, если текст исходной программы является правильным – не содержит ошибок с точки зрения синтаксиса и семантики входного языка. Если исходная программа неправильная, то результатом работы транслятора будет сообщение об ошибке. 14 Кроме понятия «транслятор» широко употребляется также близкое ему по смыслу понятие «компилятор». Компилятор – это транслятор, который осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или на языке ассемблера. Таким образом, компилятор отличается от транслятора лишь тем, что его результирующая программа всегда должна быть написана на языке машинных кодов или на языке ассемблера. В целом процесс компиляции состоит из двух основных этапов – синтеза и анализа (Рис. 2.1). На этапе анализа выполняется распознавание текста исходной программы, создание и заполнение таблиц идентификаторов. Результатом его работы служит некое внутреннее представление программы, понятное компилятору. На этапе синтеза на основании внутреннего представления программы и информации, содержащейся в таблице идентификаторов, порождается текст результирующей программы. Результатом этого этапа является объектный код. Кроме того, в составе компилятора присутствует часть, ответственная за анализ и исправление ошибок, которая при наличии ошибки в тексте исходной программы должна максимально полно информировать пользователя о типе ошибки и месте ее возникновения. Эти этапы состоят из более мелких этапов, называемых фазами компиляции. Основные этапы трансляции: 1 Анализ – это распознавание текста исходной программы, создание и заполнение таблиц для хранения данных, необходимых для дальнейших преобразований. − Лексический анализ – это проверка лексический цепочек в соответствии с заданной грамматикой на основе регулярных языков. В результате получается таблица идентификаторов и таблица лексем. − Синтаксический разбор – анализирует проверку синтаксической правильности программы на основе таблицы лексем и таблиц идентификаторов. − Семантический анализ – реализует проверку правильности программы с точки зрения семантики входного языка и выполняет преобразование текста в соответствии с текстами правила входного языка. 2 Синтез – на основе данных, полученных на первом этапе, выполняется создание текста выходной программы (если это будет компилятор, то это объектный код). − Подготовка к генерации кода – выполнение действий по созданию среды преобразования исходных данных, необходимых для дальнейшей генерации кода. − Генерация кода – непосредственное выполнение действия по созданию команд на выходном языке с выполнением при необходимости шагов по оптимизации выходного кода. Лексический анализатор – это часть компилятора, которая читает литеры программы на исходном языке и строит из них лексемы исходного языка. Синтаксический разбор – это основная часть компилятора на этапе анализа. Она выполняет выделение синтаксических конструкций в тексте исходной программы, 15 обработанном лексическим анализатором. На этой же фазе компиляции проверяется синтаксическая правильность программы. Рис. 2.1 Схема работы компилятора Семантический анализ – это часть компилятора, проверяющая правильность текста исходной программы с точки зрения семантики входного языка. Кроме непосредственно проверки, семантический анализ должен выполнять преобразования текста, требуемые семантикой входного языка (например, функции неявного преобразования типов). Подготовка к генерации кода – это фаза, на которой компилятором выполняются предварительные действия, непосредственно связанные с синтезом текста результирующей программы, но еще не ведущие к порождению текста на выходном языке. Обычно в эту фазу входят действия, связанные с идентификацией элементов языка, распределением памяти и т. п. Генерация кода – это фаза, непосредственно связанная с порождением команд, составляющих предложения выходного языка и в целом текст результирующей программы. Это основная фаза на этапе синтеза результирующей программы. Также обычно включает в себя оптимизацию – процесс, связанный с обработкой уже порожденного текста. Иногда оптимизацию выделяют в отдельную фазу компиляции, так как она оказывает существенное влияние на качество и эффективность результирующей программы. Таблица идентификаторов – это одна или несколько таблиц, в которой организуется хранение идентификаторов, необходимых для трансляции. Таблица лексем – это запись всех обнаруженных лексем в порядке их появления. 16 Проход – это процесс чтения транслятором программы из памяти и помещение полученных результатов в промежуточные блоки в память. 2.2.2 Современные компиляторы и интерпретаторы Компиляция — трансляция программы, составленной на исходном языке высокого уровня, в эквивалентную программу на низкоуровневом языке, близком машинному коду (абсолютный код, объектный модуль, иногда на язык ассемблера). Входной информацией для компилятора (исходный код) является описание алгоритма или программа на проблемно-ориентированном языке, а на выходе компилятора — эквивалентное описание алгоритма на машинно-ориентированном языке (объектный код). Первые компиляторы были разработаны для языка . Они являются более простыми в реализации, так как разрабатываются для конкретных ЭВМ (1951 г.). На следующем этапе развития в 1953 были разработаны компиляторы для языков высокого уровня, которые позволяли абстрагироваться от знаний особенностей конкретных ЭВМ. Для задания языка программирования необходимо решить задачи: 1 Определить множество допустимых цепочек языка. 2 Определить множество правильных программ языка. 3 Задать смысл для каждой правильной программы. Основной проблемой является третья задача. Ее решают двумя способами: 1 Смысл программы излагается на другом языке, который может воспринимать пользователь или ЭВМ (блок-схемный последовательный алгоритм). 2 Использовать для проверки смысл некую идеальную машину, который служит для выполнения программы на данном языке. Первый подход используется больше человеком. Второй используется для проверки программы на этапе отладки. При выполнении отладки компилятором выделяется большая часть ошибок, устраняющиеся человеком, при этом обязательно остается небольшая часть ошибок. Для устранения этих ошибок могут использоваться программные среды, которые эмулируют работу с разработанной программой и фиксирует возникшие при этом проблемы. Эти проблемы в дальнейшем устраняет человеком. Для облегчения работы по программированию в 90х года стали специально разрабатывать интегрированные среду программирования, которые позволяли выполнить всю цепочку действий необходимых для создания программ. Макроязык – это набор готовых функций для получений того или иного результата. Препроцессор – макрокоманды, которые выполняются на этапе подготовки исходного когда к компиляции. На сегодняшнем этапе развития языков программирования наиболее используемыми являются следующие: 1 PHP - Язык программирования с открытым кодом, использующий интерпретатор на стороне сервера, кросс-платформенный язык HTML скриптов, особенно подходящий для веб-разработок, так как легко может встраиваться в HTML страницы. Он имеет очень широкую область применения. Основой является интерпретатор, который может выполняться в виде: a. В качестве модуля к веб-серверу. 17 b c 2 3 4 5 6 7 В качестве CGI («скрипта»). В качестве скрипта командной строки, являющегося исполняемым файлом. С# - Объектно-ориентированный язык общей направленности, код в котором компилируется. Это язык разработанный, Майкрософт как часть платформы .Net на основе языков C и С++. Изучение C# необходимо, если ориентируетесь на использование технологий Майкрософт. Существует несколько реализаций C#: a Реализация C# в виде компилятора csc.exe включена в состав .NET Framework. b В составе проекта Rotor (Shared Source Common Language Infrastructure) компании Microsoft. c Проект Mono включает в себя реализацию C# с открытым исходным кодом. d Проект DotGNU также включает компилятор C# с открытым кодом. e DotNetAnywhere - ориентированная на встраиваемые системы реализация CLR, поддерживает практически всю спецификацию C# 2.0. JavaScript - JavaScript - это объектно-ориентированный язык скриптов, который выполняется на стороне клиента веб-браузером. Язык встроенный в HTML, который используется в миллионах веб-страниц для обработки форм, работы с cookie и множества других задач. Поддержку JavaScript обеспечивают современные версии всех наиболее часто используемых браузеров: Internet Explorer, Mozilla Firefox, Safari, Google Chrome, Opera. Perl - Язык программирования с открытым кодом, кросс-платформенный, выполняется на стороне сервера. Код интерпретируется. Получил широкое распространение, как удобное средство для обработки текста в CGI программах. Возможности по обработке текстов сделали его очень популярным при написании программ для веб-серверов и самых разнообразных задач. С - Стандартный язык программирования, предназначенный для самых разнообразных задач. Это один из самых распространенных языков, ставший основой для нескольких других, например, C++. C - это основа, которая позволит легко перейти на Java или C#. Известные компиляторы: a BDS C b Borland C++ c C++ Builder d Clang e Digital Mars f DJGPP g GNU Compiler Collection h Intel C++ compiler i LCC j Microsoft Visual Studio k MinGW l Open Watcom m Oracle Solaris Studio n Pelles C o Portable C Compiler p Tiny C Compiler q Topspeed JPI C Ruby и Ruby on Rails - это динамичный, объектно-ориентированный язык с открытым кодом. Ruby on Rails - инструментарий разработчика с открытым кодом для вебпрограммирования, написанный на Ruby. Достоинства: простота и эффективность. Java - Объектно-ориентированный язык программирования, разработанный Джеймсом Гослингом и группой разработчиков из Sun Microsystems в начале 1990. Многие разработчики признают его очень хорошим языком. Основой трансляции является Java Development Kit (сокращенно JDK) — бесплатно распространяемый компанией Oracle Corporation (ранее Sun Microsystems) комплект разработчика приложений на языке Java, включающий в себя компилятор Java (javac), стандартные библиотеки классов Java, примеры, документацию, различные утилиты и исполнительную систему Java (JRE). 18 8 9 Python Интерпретируемый динамичный объектно-ориентированный язык программирования с открытым кодом, который использует механизмы автоматического управления памятью. Разработанный, чтобы быть хорошо читаемым минималистским языком программирования. Реализацией Python является интерпретатор CPython, поддерживающий большинство активно используемых платформ. Он распространяется под свободной лицензией Python Software Foundation License. VB.Net (Visual Basic .Net) - Объектно-ориентированный язык программирования, который входит в комплект средств разработки от Майкрософт. 3 Трансляторы с языка ассемблера Ассемблер – язык низкого уровня. Структура и взаимосвязь цепочек этого языка близки к машинным командам целевой вычислительной системы, где должна выполняться результирующая программа. Применение ассемблера позволяет разработчику управлять ресурсами целевой вычислительной системы на уровне машинных команд. Каждая команда исходной программы на языке ассемблера в результате компиляции преобразуется в одну машинную команду. Язык ассемблера, как правило, содержит мнемонические коды машинных команд. Чаще всего используется англоязычная мнемоника команд, но существуют и другие варианты языков ассемблера. Все возможные команды в каждом языке ассемблера можно разбить на две группы: ƒ в первую группу входят обычные команды языка, которые в процессе трансляции преобразуются в машинные команды; ƒ вторую группу составляют специальные команды языка, которые в машинные команды не преобразуются, но используются компилятором для выполнения задач компиляции (таких, например, как задача распределения памяти). Синтаксис языка может быть описан с помощью регулярной грамматики. Поэтому построение распознавателя для языка ассемблера не представляет труда. По этой же причине в компиляторах с языка ассемблера лексический и синтаксический разбор, как правило, совмещены в один распознаватель. Семантический анализ в компиляторе с языка ассемблера также прост, как и синтаксический. Основной его задачей является проверить допустимость операндов для каждого кода операции, а также проверить, что все идентификаторы и метки, встречающиеся во входной программе, описаны и обозначающиеих идентификаторы не совпадают с предопределенными идентификаторами, используемыми для обозначения кодов операции и регистров процессора. Схемы синтаксического и семантического анализа в компиляторе с языкаассемблера могут быть реализованы на основе обычного конечного автомата. Именно эта особенность определила тот факт, что компиляторы с языкаассемблера исторически явились первыми компиляторами, созданными дляЭВМ. Существует также ряд других особенностей, которые присущи именноязыкам ассемблера и упрощают построение компиляторов для них. Во-первых, в компиляторах с языка ассемблера не выполняетсядополнительная идентификация переменных – все переменные языкасохраняют имена, присвоенные им пользователем. За уникальность имен висходной программе отвечает ее разработчик, семантика языка никакихдополнительных требований на этот процесс не накладывает. Во-вторых, вкомпиляторах с языка ассемблера предельно упрощено распределение памяти.Компилятор с языка ассемблера работает только со статической памятью. Еслииспользуется динамическая память, то для работы с нею нужно использоватьсоответствующую библиотеку или функции ОС, а за ее распределение отвечаетразработчик исходной программы. За передачу параметров и организациюдисплея памяти процедур и функций также отвечает разработчик исходнойпрограммы. Он же должен позаботиться и об отделении данных от кодапрограммы – компилятор с языка ассемблера автоматически такого разделенияне выполняет. 19 И в-третьих, на этапе генерации кода в компиляторе с языкаассемблера не производится оптимизация , поскольку разработчик исходнойпрограммы сам отвечает за организацию вычислений, последовательностьмашинных команд и распределение регистров процессора. Компиляторы с языка ассемблера реализуются чаще всего подвухпроходной схеме. На первом проходе компилятор выполняет разборисходной программы, ее преобразование в машинные коды и одновременнозаполняет таблицу идентификаторов. Но остаются незаполненными адреса техоперандов, которые размещаются в оперативной памяти. На втором проходекомпилятор заполняет эти адреса и одновременно обнаруживает неописанныеидентификаторы. Это связано с тем , что операнд может быть описан впрограмме после того, как он первый раз был использован, поэтому его адресеще не известен на момент построения машинной команды. Поскольку разработка программ на языке ассемблера – достаточнотрудоемкий процесс, требующий зачастую простого повторения одних и тех жемногократно встречающихся операций, для облегчения труда разработчикабыли созданы так называемые макрокоманды. Макрокоманда представляет собой текстовую подстановку, в ходевыполнения которой каждый идентификатор определенного вида заменяется нацепочку символов из некоторого хранилища данных. Процесс выполнениямакрокоманды называется макрогенерацией, а цепочка символов, получаемаяв результате выполнения макрокоманды, – макрорасширением. Процесс выполнения макрокоманд заключается в последовательномпросмотре текста исходной программы, обнаружении в нем определенныхидентификаторов и их замене на соответствующие строки символов. Такаязамена называется макроподстановкой. Чтобы указать, какие идентификаторы на какие строки необходимозаменять, служат макроопределения. Макроопределения присутствуютнепосредственно в тексте исходной программы и выделяются специальнымиключевыми словами или разделителями. В процессе обработки всемакроопределения исключаются из текста входной программы, а содержащаясяв них информация запоминается для обработки при выполнении макрокоманд.Макрокоманды и макроопределения обрабатываются специальныммодулем, называемым макрогенератором. Макрогенератор получает на входтекст исходной программы, содержащий макроопределения и макрокоманды, ана выходе его появляется текст макрорасширения исходной программы, несодержащий макроопределений и макрокоманд. Именно макрорасширениеисходного текста поступает на вход компилятора. Макрогенератор чаще всего не существует в виде отдельного программного модуля, а входит в состав компилятора. Макрорасширение исходнойпрограммы обычно недоступно ее разработчику. Кроме того, макроподстановки могут выполняться последовательно при разборе исходного текста на первомпроходе компилятора вместе с разбором всего текста программы, и тогдамакрорасширение исходной программы может быть исключено как отдельныйэтап. Литература: [1]; [2].