Курсовая Лексический анализатор. Краткий курс лекций. Курс лекций по спецкурсу Методы трансляции
 Скачать 0.64 Mb.
|
|
Краткий курс лекций по спецкурсу «Методы трансляции» Назначение и структура трансляторов. Задачи лексического анализа Компиляторы с языков программирования являются неотъемлемой частью инструментальных систем разработки программного обеспечения. Знания о принципах работы компиляторов позволяют ускорить и упростить процесс отладки программ. Методы и алгоритмы анализа программ могут быть использованы для построения эффективных алгоритмов анализа текстовой информации в самых различных приложениях. Любая ЭВМ имеет систему машинных команд. Программа, написанная на любом из языков программирования, не может быть непосредственно выполнена на ЭВМ. Предварительно она должна быть переведена на язык машинных команд, чем и занимаются трансляторы. Таким образом, транслятор – это программа, которая переводит исходную программу, записанную на каком-либо языке программирования, в объектную программу на языке машинных команд. По уровню входного языка трансляторы делятся на ассемблеры для машинно-ориентированных языков и компиляторы для языков высокого уровня. Кроме этого существует еще один вид программ, обеспечивающих выполнение программ, написанных на языках программирования. Это интерпретаторы, которые анализируют операторы программы и немедленно их реализуют. Они появились для слабых машин, чтобы не тратить время на компиляцию, которая занимала много времени. С развитием техники интерпретаторы потеряли свою актуальность, а сейчас появились в виде Java-машин, например. Задача трансляции: анализ исходной программы с выявлением синтаксических и семантических ошибок и синтез объектной программы. Трансляция с языка высокого уровня является весьма сложной задачей. Поэтому, как правило, процесс трансляции разбивается на несколько этапов. На каждом из них производится полный просмотр транслируемой программы, в связи с чем эти этапы называют проходами транслятора. На некоторых проходах производится перевод программы из одного представления в другое эквивалентное, но более удобное для дальнейшей трансляции. Количество проходов в трансляторах бывает различным. На первых ЭВМ оно зачастую определялось доступным объемом памяти ЭВМ: из-за малого объема памяти требовался многократный просмотр транслируемой программы. В настоящее время этой проблемы нет, и количество проходов в основном определяется сложностью входного языка и требованиями к качеству получаемой объектной программы. Кроме того, в компиляторы зачастую включают дополнительные проходы для оптимизации получаемой объектной программы. Будет рассматриваться классическая трехпроходная схема компиляции, включающая в себя следующие этапы: лексический анализ; синтаксический и семантический анализ; генерация объектной программы (генерация кодов). Логическую схему такого компилятора можно представить следующим образом:         В процессе лексического анализа исходная программа переводится в некоторое внутреннее представление, удобное для дальнейшей обработки синтаксическим анализатором. Задачи лексического анализа: 1. Построение информационных таблиц транслятора. Состав и структура этих таблиц во многом определяются входным языком. Основные таблицы: таблица идентификаторов и таблица констант. Таблица идентификаторов (ТИД) обычно содержит: имя переменной, размерность для массива, тип и длину, номер блока, в котором она описана, и др. Таблица очень активно используется в ходе лексического анализа. Поэтому, для ускорения поиска в ТИД обычно используют различные функции расстановки, определяющие зависимость между идентификатором и его номером в таблице. Элемент таблицы констант содержит тип, длину и значение константы во внутримашинном представлении. Тип и длина обычно определяются из формы записи константы. При заполнении таблицы избегают дублирования элементов. Часто формируются несколько таблиц констант по типам констант. 2. Перевод исходной программы во внутреннее представление. В языках высокого уровня обычно выделяются три типа лексических единиц: служебные слова и ограничители, идентификаторы и константы. Каждой из лексических единиц исходной программы во внутреннем представлении сопоставляется код, определяющий тип этой единицы и номер среди лексических единиц данного типа. Для служебных слов номера фиксируются заранее, для идентификаторов и констант являются ссылками на соответствующие таблицы. Достоинства внутреннего представления: нет необходимости работать со словами переменной длины. Вместо них – коды фиксированной длины; нет необходимости распознавать служебные слова, коды однозначно их определяют; по диапазону, в который попадает код, однозначно определяется тип лексической единицы, что достаточно для последующего синтаксического разбора. 3. Простейший синтаксический анализ корректности записи лексических единиц (констант, идентификаторов) и парности символов (скобки и т.п.). Последнее обычно достигается путем введения счетчика, увеличивающегося на 1 при распознавании открывающей скобки и уменьшающегося на 1 по закрывающей скобке. Понятие грамматики, порождаемого языка Ранние методы трансляции базировались на особенностях конкретного входного языка и особенностях конкретной машины, для которой создавался транслятор. Поэтому при разработке транслятора с нового языка или для новой машины почти вся работа выполнялась заново. Большая трудоемкость разработки трансляторов вынудила искать методы трансляции, независимые от конкретной машины. Это привело к разработке методов, ориентированных на определенный способ описания синтаксиса входного языка (формальное описание). Методы синтаксического анализа, которые будут далее рассматриваться, основаны на теории формальных грамматик и языков. Любой язык можно неформально определить как подмножество множества всех предложений из слов или символов некоторого основного словаря. Слова объединяются в предложения, но только очень малая часть из всех возможных сочетаний слов является допустимой с точки зрения синтаксиса языка. Язык программирования состоит из программ, которые являются последовательностями операторов, состоящих из служебных слов (if, else и т.п.), знаков пунктуации, идентификаторов и констант. Одной из основных задач компилятора является синтаксический анализ исходной программы, написанной на каком-либо языке программирования. Реализация этой функции в компиляторах основана на теории формальных грамматик и языков. Перейдем к формальному описанию языка. Алфавит – это непустое конечное множество элементов, называемых символами. Всякая последовательность символов алфавита называется цепочкой или строкой. Если A = {a, b, c} – алфавит языка, то цепочками являются a, abc, bbaa. Пустую цепочку, не содержащую ни одного символа, будем обозначать λ. Правилом подстановки называется упорядоченная пара (U, x), где U – символ, x – конечная цепочка символов. U называется левой частью, x – правой частью правила подстановки. Грамматикой G[Z] называется конечное, непустое множество правил. Z – это символ, который должен встретиться в левой части хотя бы одного правила. Он называется начальным символом грамматики. Все символы, которые встречаются в левых и правых частях правил образуют словарь грамматики – V. Множество всех конечных цепочек из V, включая λ, обозначается V*. При написании грамматик будет использоваться некоторая нотация, называемая бэкусовой нормальной формой, в которой правила подстановки имеют вид U → x, а правила с одинаковыми левыми частями собираются в одно, с использованием в качестве разделителя правых частей знака | (или). Например, правила U → x, U → y записываются в виде U → x | y. В заданной грамматике G символы, которые встречаются в левой части правил, называются нетерминальными. Они образуют множество нетерминальных символов VN. Остальные символы называются терминальными и образуют множество VT (V=VN U VT). Нетерминальные символы в дальнейшем будут обозначаться большими латинскими буквами или заключаться в скобки <>. Пример грамматики: <предложение> → <подлежащее> <сказуемое> <обстоятельство> <подлежащее> → ОН | ОНА <сказуемое> → ИДЕТ <обстоятельство> → В_КИНО | НА_ЛЕКЦИЮ Здесь VN={<предложение>,<подлежащее>,<сказуемое>,<обстоятельство>} VT={ОН,ОНА,ИДЕТ,В_КИНО,НА_ЛЕКЦИЮ}, V=VN U VT, Z=<предложение>. Формальная грамматика порождает формальный язык, состоящий из предложений, удовлетворяющий правилам грамматики. Дадим определение такого языка. Цепочка x прямо порождает цепочку y (x |