Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Формальные языки и грамматики.doc
Скачиваний:
159
Добавлен:
01.05.2014
Размер:
1.51 Mб
Скачать

1. Формальные языки и грамматики

1.1. Введение

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

1.1.1. Трансляторы , интерпретаторы и компиляторы

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

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

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

1.1.2. Стадии работы компилятора

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

Первая стадия работы компилятора называетсялексическим анализом,а программа, её реализующая, -лексическим анализатором(ЛА). На вход лексического анализатора подаётся последовательность символов входного языка. ЛА выделяет в этой последовательности простейшие конструкции языка, которые называют лексическими единицами. Примерами лексических единиц являются идентификаторы, числа, символы операций, служебные слова и т.д. ЛА преобразует исходный текст, заменяя лексические единицы их внутренним представлением -лексемами. Лексема может включать информацию о классе лексической единицы и её значении. Кроме того, для некоторых классов лексических единиц ЛА строит таблицы, например, таблицу идентификаторов, констант, которые используются на последующих стадиях компиляции.

Вторую стадию работы компилятора называютсинтаксическим анализом, а соответствующую программу -синтаксическим анализатором (СА). На вход СА подается последовательность лексем, которая преобразуется в промежуточный код,представляющий собой последовательность символов действия или атомов. Каждый атом включает описание операции, которую нужно выполнить, с указанием используемых операндов. При этом последовательность расположения атомов, в отличие от лексем, соответствует порядку выполнения операций, необходимому для получения результата.

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

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

Соседние файлы в предмете Теория языков программирования