 |
Особенности построения интерпретаторов
|
|
|
|
Интерпретатор − это программа, которая воспринимает входную программу на исходном языке и выполняет её.
Термин «интерпретатор», как и «транслятор» означает «переводчик». Но с точки зрения формальных языков, отличаются они принципиально.
Большинство интерпретаторов последовательно исполняют исходную программу по мере поступления ее на вход интерпретатора. При этом пользователю нет смысла ждать завершения компиляции всей исходной программы. Исходя из этой особенности (исполнение команд по мере их поступления) в интерпретаторах отсутствует фаза оптимизации. А также на последнем этапе − этапе генерации кода − машинные команды не записываются в объектный файл, а выполняются.
Кроме того, далеко не все языки программирования допускают построение интерпретаторов, которые выполняли бы исходные программы по мере поступления команд.
Последнее требование предусматривает существование компилятора, разбирающего исходную программу за один проход.
Основное требование интерпретаторов − обработка программы по мере поступления − нарушается, если язык допускает обращения к функциям и структурам данных раньше их непосредственного описания. По этой причине не могут интерпретироваться такие языки, как Си и Паскаль.
Из-за отсутствия в интерпретаторах фазы оптимизации выполнение программы с помощью интерпретатора менее эффективно, чем с помощью аналогичного компилятора. В добавок, интерпретируемая программа должна разбираться каждый раз при выполнении, а при компиляции она разбирается единожды. Затем используется объектный код или файл. Поэтому интерпретаторы всегда уступают компиляторам в производительности.
|
|
|
Преимуществом интерпретаторов является независимость выполнения программы от архитектуры целевой вычислительной системы. При переходе на другую архитектуру в случае компилятора требуется откомпилировать программу заново, т.к. объектный код всегда ориентируется на определенную архитектуру.
Долгое время интерпретаторы были менее распространены, чем компиляторы, и существовали для относительно простых языков программирования (Basic). Профессиональные средства разработки ПО с высокими требованиями к производительности строились на базе компиляторов.
Такое положение существовало до момента широкого распространения глобальных вычислительных сетей. Как правило, такие сети представляют собой набор ЭВМ различной архитектуры. Из-за этого на первый план выходит требование единообразного выполнения на каждой ЭВМ сети исходной программы.
Многие языки программирования, которые используются в сети Интернет, предусматривают механизм интерпретации исходного текста программы вместо компиляции. В качестве примера интерпретируемого языка широкого распространения выступает HTML (Hypertext Markup Language) язык описания гипертекста. Он лежит в основе функционирования большинства структур сети Интернет. Языки Java и Java Script сочетают функции компиляции и интерпретации. На первом этапе исходная программа компилируется в некоторый двоичный код, который является промежуточным и не зависит от архитектуры целевого компьютера. Этот код передается по сети и выполняется принимающим компьютером в виде интерпретации.
1
Постановка задачи
Требуется написaть прoграмму-трaнслятор, выполняющую трансляцию с языка программирования Пaскaль нa язык прoгрaммирoвaния Си. Прогрaммa дoлжнa быть нaписaнa нa языке Си и транслировать лишь некоторые конструкции, такие кaк:
- integer
repeat … until Le
procedure
type
record (для type)
Так же программа должна обрабатывать арифметическое и логическое выражения, схемы которых представлены ниже.
|
|
|
Арифметическое выражение Ae2:
Рисунок 1.1 - Схема разбора арифметического выражения Ае2
Логическое выражение Le2:
Рисунок 1.2 - Схема разбора логического выражения Le2
Представим ниже таблицу того, как программа должна переводить конструкции.
Таблица 1.1 - Таблица значений для перевода
| Конструкции Pascal | Конструкции C |
| Oператoрные скoбки begin…еnd | {...} |
| Оператoр vаr | |
| vаr <nаme>:<type>; <name>,<nаme>:<type>; label <nаme>; | <type> <nаme>,<nаme>; <type> <nаmе>; |
| Тип переменнoй | |
| <name>:intеgеr; | Int <namе>; |
| repeat <operator> until <Le> | do { <operator> } while(!<Le>) |
| <name> record <name>: <type >; <name>: <type>; … end; | Struct <name> { <type> <nаme>; <type> <nаme>; … } |
| { комментарий 1 } (*комментарий 2*) | /*комментарий 1*/ /*комментарий 2*/ |
| <name>:<type>; | <type> <name>; |
| Procedure <pname>(<vars>); | void <pname>(<vars>) |
Пример обработки программы
Таблица 1.2 - Пример обработки программы
| Паскаль | Си |
| (* New Programm *) { Variant 5 } var f:boolean; r: integer; procedure testpr(var a:integer); var i,j:integer; begin repeat r:=i+3*8; r:=r+3*8; until ((a<9 and a<3) or true); end; begin f:= r=1; end. | #include <stdio.h> /* New Programm */ /* Variant 5 */ int f; int r; void testpr(int & a) { int i,j; { do { r=i+3*8; r=r+3*8; } while (((a<9&&a<3)||1)); } void main() { f=r==1; } |
Внешняя спецификация
Нa вхoд прoгрaммa будет зaпрaшивaть фaйл с рaзрeшeниeм.pas или любым другим. На экране будет следующее сooбщение:
Выберите файл для трансляции:
Если файл, имя которого введет пользователь найден не будет, то программа выдаст сообщение об ошибке, которое будет выглядеть на экране следующим образом:
Произошла ошибка при открытии!
Поскольку файл в который будет записан результат так же выбирается пользователем, то после обработки и транслирования программа задаст вопрос о том, куда записывать результат:
Введите имя для записи результата:
Так же как и в прошлом случае, требуется предусмотреть невозможность записать в файл информацию, тогда будет выведено сообщение:
Произошла ошибка при создании файла!
К aппaрaтным средствaм ПО не требовательно, подойдет процессор более мощный чем 500Гц, а сам компьютер должен иметь в наличии оперативную память, объемом больше чем 32 Мб.
Описание алгоритма
|
|
|
В целом процесс работы программы состоит в фазах лексического и синтаксического анализа. Для упрощения программы по заданию, мы будем эти две фазы смешивать, и таким образом программа будет представлять собой однофазный транслятор. Однако стоит рассмотреть подробнее что такое лексический и синтаксический анализ, а так же где они применяются.
Оснoвная зaдaча лексического анализа - разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, т.е. выделить эти слова из непрерывной последовательности символов. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители). В некоторых случаях между лексемами может и не быть разделителей. С другой стороны, в некоторых языках лексемы могут содержать незначащие символы (например, символ пробела в Фортране). В Си разделительное значение символов-разделителей может блокироваться ("\" в конце строки внутри "...").
Обычно все лексемы делятся на классы. Примерами таких классов являются числа (целые, восьмеричные, шестнадцатеричные, действительные и т.д.), идентификаторы, строки. Отдельно выделяются ключевые слова и символы пунктуации (иногда их называют символы-ограничители). Как правило, ключевые слова - это некоторое конечное подмножество идентификаторов. В некоторых языках (например, ПЛ/1) смысл лексемы может зависеть от ее контекста и невозможно провести лексический анализ в отрыве от синтаксического.
С точки зрения дальнейших фаз анализа лексический анализатор выдает информацию двух сортов: для синтаксического анализатора, работающего вслед за лексическим, существенна информация о последовательности классов лексем, ограничителей и ключевых слов, а для контекстного анализа, работающего вслед за синтаксическим, важна информация о конкретных значениях отдельных лексем (идентификаторов, чисел и т.д.).
Таким образом, общая схема работы лексического анализатора такова. Сначала выделяется отдельная лексема (возможно, используя символы-разделители). Ключевые слова распознаются либо явным выделением непосредственно из текста, либо сначала выделяется идентификатор, а затем делается проверка на принадлежность его множеству ключевых слов.
|
|
|
Если выделенная лексема является ограничителем, то он (точнее, некоторый его признак) выдается как результат лексического анализа. Если выделенная лексема является ключевым словом, то выдается признак соответствующего ключевого слова. Если выделенная лексема является идентификатором - выдается признак идентификатора, а сам идентификатор сохраняется отдельно. Наконец, если выделенная лексема принадлежит какому-либо из других классов лексем (например, лексема представляет собой число, строку и т.д.), то выдается признак соответствующего класса, а значение лексемы сохраняется отдельно.
Лeксичeский aнaлизaтор может быть как самостоятельной фaзой трaнсляции, так и пoдпрoгрaммoй, рaбoтaющей пo принципу "дaй лeксeму*'. В первом случае (рис. 3.1, а) выходом анализатора является файл лексем, во втором (рис. 3.1, б) лексема выдается при каждом обращении к анализатору (при этом, как правило, признак класса лексемы возвращается как результат функции "лексический анализатор", а значение лексемы передается через глобальную переменную). С точки зрения обработки значений лексем, анализатор может либо просто выдавать значение каждой лексемы, и в этом случае построение таблиц объектов (идентификаторов, строк, чисел и т.д.) переносится на более поздние фазы, либо он может самостоятельно строить таблицы объектов. В этом случае в качестве значения лексемы выдается указатель на вход в соответствующую таблицу.
Рисунок 3.1 - Принцип работы лексического анализатора
Синтаксический анализ - это процесс, который определяет, принадлежит ли некоторая последовательность лексем языку, порождаемому грамматикой. В принципе, по любой грамматике можно построить синтаксический анализатор, но грамматики, используемые на практике, имеют специальную форму. Например, известно, что для любой контекстно-свободной грамматики может быть построен анализатор, сложность которого не превышает O(n3) для входной строки длины n, но в большинстве случаев по заданному языку программирования мы можем построить такую грамматику, которая позволит сконструировать и более быстрый анализатор. Анализаторы реально используемых языков обычно имеют линейную сложность; это достигается, например, за счет просмотра исходной программы слева направо с заглядыванием вперед на один терминальный символ (лексический класс).
|
|
|
Вход синтаксического анализатора - последовательность лексем и таблицы, например, таблица внешних представлений, которые являются выходом лексического анализатора.
Выход синтаксического анализатора - дерево разбора и таблицы, например, таблица идентификаторов и таблица типов, которые являются входом для следующего просмотра компилятора (например, это может быть просмотр, осуществляющий контроль типов).
Отметим, что совсем необязательно, чтобы фазы лексического и синтаксического анализа выделялись в отдельные просмотры. Обычно эти фазы взаимодействуют друг с другом на одном просмотре. Основной фазой такого просмотра считается фаза синтаксического анализа, при этом синтаксический анализатор обращается к лексическому анализатору каждый раз, когда у него появляется потребность в очередном терминальном символе. Таким образом, будет работать наш транслятор.
|
|
|
