Лексический и синтаксический анализ и генерация кода.

Лексический анализ — процесс аналитического разбора входной последовательности символов (например, такой как исходный код на одном из языков программирования) с целью получения на выходе последовательности символов, называемых «токенами» (подобно группировке букв в слова). Группа символов входной последовательности, идентифицируемая на выходе процесса как токен, называется лексемой. В процессе лексического анализа производится распознавание и выделение лексем из входной последовательности символов.

Как правило, лексический анализ производится с точки зрения определённого формального языка или набора языков. Язык, а точнее его грамматика, задаёт определённый набор лексем, которые могут встретиться на входе процесса.

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

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

Каждый токен можно представить в виде структуры, содержащей идентификатор токена (или идентификатор класса токена) и, если нужно, последовательность символов лексемы, выделенной из входного потока (строку, число и т. д.).

Цель такой конвертации обычно состоит в том, чтобы подготовить входную последовательность для другой программы, например для грамматического анализатора, и избавить его от определения лексических подробностей в контекстно-свободной грамматике (что привело бы к усложнению грамматики).

Лексический анализатор (англ. lexical analyzer или коротко lexer) — это программа или часть программы, выполняющая лексический анализ. Лексический анализатор обычно работает в две стадии: сканирование и оценка.

На первой стадии, сканировании, лексический анализатор обычно реализуется в виде конечного автомата, определяемого регулярными выражениями. В нём кодируется информация о возможных последовательностях символов, которые могут встречаться в токенах . Например, токен «целое число» может содержать любую последовательность десятичных цифр. Во многих случаях первый непробельный символ может использоваться для определения типа следующего токена, после чего входные символы обрабатываются один за другим пока не встретится символ, не входящий во множество допустимых символов для данного токена. В некоторых языках правила разбора лексем несколько более сложные и требуют возвратов назад по читаемой последовательности.

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

Токен с типом и соответственно подготовленным значением передаётся на вход синтаксического анализатора.

Рисунок .3.3

Синтакси́ческий ана́лиз (па́рсинг) — это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Синтаксический анализатор (парсер) — это программа или часть программы, выполняющая синтаксический анализ.

Пример разбора выражения в дерево

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

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

Синтаксический анализ – это процесс, который определяет, принадлежит ли некоторая последовательность лексем языку, порождаемому грамматикой. В принципе, по любой грамматике можно построить синтаксический анализатор, но грамматики, используемые на практике, имеют специальную форму. Например, известно, что для любой контекстно-свободной грамматики может быть построен анализатор, сложность которого не превышает O(n3) для входной строки длины n, но в большинстве случаев по заданному языку программирования мы можем построить такую грамматику, которая позволит сконструировать и более быстрый анализатор. Анализаторы реально используемых языков обычно имеют линейную сложность; это достигается, например, за счет просмотра исходной программы слева направо с заглядыванием вперед на один терминальный символ (лексический класс).

Вход синтаксического анализатора – последовательность лексических и таблицы, например, таблица внешних представлений, которые являются выходом лексического анализатора.

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

Большинство известных методов анализа принадлежат одному из двух классов, один из которых объединяет нисходящие (top-down) алгоритмы, а другой – восходящие (bottom-up) алгоритмы. Происхождение этих терминов связано с тем, каким образом строятся узлы синтаксического дерева: либо от корня (аксиомы грамматики) к листьям (терминальным символам), либо от листьев к корню.

Нисходящие анализаторы строят вывод, начиная от аксиомы грамматики и заканчивая цепочкой терминальных символов. С нисходящими анализаторами связаны так называемые LL-грамматики, которые обладают следующими свойствами:

Они могут быть проанализированы без возвратов.

Первая буква L означает, что мы просматриваем входную цепочку слева направо (leftto- right scan)

Вторая буква L означает, что строится левый вывод цепочки (leftmost derivation).

Популярность нисходящих анализаторов связана с тем, эффективный нисходящий анализатор достаточно легко может быть построен вручную, например, методом рекурсивного спуска. Кроме того, LL-грамматики легко обобщаются: грамматики, не являющиеся LL-грамматиками, обычно могут быть проанализированы методом рекурсивного спуска с возвратами.

С другой стороны, восходящие анализаторы могут анализировать большее количество грамматик, чем нисходящие, и поэтому именно для таких методов существуют программы, которые умеют автоматически строить анализаторы. С восходящими анализаторами связаны LR-грамматики. В этом обозначении буква L по-прежнему означает, что входная цепочка просматривается слева направо (left-to-right scan), а буква R означает, что строится правый вывод цепочки (rightmost derivation). С помощью LR- грамматик можно определить большинство использующихся в настоящее время языков программирования.

Загрузчик.

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

Большая часть объектного модуля - команды и данные машинного языка именно в той форме, в какой они будут существовать во время выполнения программы. Однако, программа в общем случае состоит из многих модулей. Поскольку транслятор обрабатывает только один конкретный модуль, он не может должным образом обработать те части этого модуля, в которых запрограммированы обращения к данным или процедурам, определенным в другом модуле. Такие обращения называются внешними ссылками. Те места в объектном модуле, где содержатся внешние ссылки, транслируются в некоторую промежуточную форму, подлежащую дальнейшей обработке. Говорят, что объектный модуль представляет собой программу на машинном языке с неразрешенными внешними ссылками.

Разрешение внешних ссылок выполняется на следующем этапе подготовки, который обеспечивается Редактором Связей (Компоновщиком). Редактор Связей соединяет вместе все объектные модули, входящие в программу. Поскольку Редактор Связей "видит" уже все компоненты программы, он имеет возможность обработать те места в объектных модулях, которые содержат внешние ссылки. Результатом работы Редактора Связей является загрузочный модуль.

Загрузочный модуль - программный модуль, представленный в форме, пригодной для загрузки в оперативную память для выполнения.

Загрузочный модуль сохраняется в виде файла на внешней памяти. Для выполнения программа должна быть перенесена (загружена) в оперативную память. Иногда при этом требуется некоторая дополнительная обработка (например, настройка адресов в программе на ту область оперативной памяти, в которую программа загрузилась). Эта функция выполняется Загрузчиком, который обычно входит в состав операционной системы.

Возможен также вариант, в котором редактирование связей выполняется при каждом запуске программы на выполнение и совмещается с загрузкой.

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

Связывание - это связывание двух или более отдельных оттранслированных программ.

Перемещение - это модификация объектной программы так, чтобы она могла загружаться с адреса, отличного от первоначального.

Функции загрузчика:

o распределение ОП;

o перемещение программы;

o связывание модулей;

o загрузка программ в ОП и запуск на выполнение.

Это делает Связывающий Загрузчик. Вариант связывания при запуске более расходный, т.к. затраты на связывание тиражируются при каждом запуске. Но он обеспечивает:

o большую гибкость в сопровождении, так как позволяет менять отдельные объектные модули программы, не меняя остальных модулей;

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

Виды загрузчиков

Загрузчики типа «компиляция-выполнение»

Одним из возможных способов выполнения функции загрузчика может быть такая организация работы ассемблера, при которой ассемблер, работая в одной части памяти, помещает машинные команды и данные по мере ассемблирования непосредственно в выделенные для них ячейки памяти. После завершения компиляции ассемблер передает управление в точку входа полученной программы. Это очень простое решение, позволяющее обойтись без каких-либо дополнительных процедур. Такая схема называется «компиляция-выполнение», а «загрузчик» состоит из одной команды, которая передает управление ассемблированной программе.

Однако эта схема имеет ряд недостатков:

o некоторая часть памяти не может быть использована, т.к. занятая ассемблером память недоступна для объектной программы;

o при каждом новом прогоне приходиться заново транслировать программу пользователя;

o трудно организовать работу нескольких сегментов программы, особенно, если исходные тексты написаны на разных языках, т.к. каждый язык создает свою среду в ОП.

Достоинства:

o распределение памяти выполняется автоматически;

o одна и та же программа-компилятор выполняет функции перемещения и связывания, загрузки и запуска.

Абсолютный загрузчик

Учитывая недостатки загрузчиков типа «компиляция-выполнение», видно, что целесообразным будет организовать хранение результатов трансляции на некотором внешнем носителе с тем, чтобы загрузить их, когда понадобится выполнить полученную программу. При этом ассемблированная программа может быть загружена в ту же область, которую раньше занимал ассемблер. Эта форма вывода называется объектной программой. Тогда работа загрузчика будет заключаться в том, что он принимает на входе ассемблированные команды и информацию, представленную в виде объектной программы, а сам в свою очередь помещает в память машинные команды, данные в выполнимой машинной форме. Этот тип загрузки устраняет основные недостатки рассмотренного ранее типа.

Простейший загрузчик, работающий по общей схеме, называется абсолютным. При этом ассемблер выводит результаты трансляции исходной программы почти в такой же форме как при схеме «компиляция-выполнение», за исключением того, что результаты помещаются не непосредственно в память, а выводятся на носитель. Загрузчик просто воспринимает текст программы на машинном языке и помещает его в память по адресу, указанному ассемблером.

Абсолютные загрузчики просты в реализации, но имеют ряд особенностей:

o задачу распределения ОП выполняет программист (с помощью директивы установки начального значения ОП);

o задачу перемещения программы выполняет компилятор;

o связывание модулей - решается программистом (call 600);

o загрузка программ в ОП и запуск на выполнение.

Достоинства:

o меньший объем загрузчика (по величине памяти);

o разделение фазы компиляции и загрузки, что сокращает время на обработку модулей;

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

Недостатки:

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

Жизненный цикл программы.

Жизненный цикл программного обеспечения (ПО) — период времени, который начинается с момента принятия решения о необходимости создания программного продукта и заканчивается в момент его полного изъятия из эксплуатации. Этот цикл — процесс построения и развития ПО.

Этапы жизненного цикла:

1. Анализ

2. Проектирование

3. Реализация

4. Сборка, тестирование, испытание

5. Внедрение (выпуск)

6. Сопровождение

Анализ

Различают 2 случая производства ПО: 1) ПО делается для конкретного заказчика. В этом случае нужно прикладную задачу преврашать в программистскую. Нужно понять как функционирует та среда, которую нужно автоматизировать (анализ бизнес-процессов). В результате появляется документация-спецификация требования, где указаны какие именно задачи д.б. решены и при каких условиях. Эту работу выполняет системный аналитик (аналитик бизнес-процессов).

2) ПО разрабатывается для рынка. Нужно проводить маркетинговые исследования и найти какого продукта на рынке нет. Это связано с большим риском. Цель – разработка спецификации требований.

Проектирование

Цель – определение общей структуры (архитектуры) ПО. Результат – спецификация ПО. Эту работу выполняет системный программист.

Реализация

Написание программного кода. Реализация включает и разработку, и тестирование, и документацию.

Сборка, тестирование, испытние

Сборка всего, что сделано разными программистами. Тестирование всего программного комплекса. Отладка – поиск и устранение причин ошибок. Испытание – уточнение технических характеристик. В результате – гарантия работоспособносит программы.

Внедрение (выпуск)

Внедрение – когда работают на одного заказчика. Включает постановку программы у заказчика, обучение заказчика, консультации, устранение ошибок и явных недостатков. Должно произойти отчуждение ПО – пользователь может работать с ПО без участия автора.

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

Если на рынок выпускается принципиально новый ПО, то возможно несколько бета-тестирований. После бета-тестирование – выпуск коммерческой версии.

Сопровождение

Устранение замеченных в ходе эксплуатации ошибок. Внесение непринципиальных усовершенствований. Накопление предложений для разработки следующей версии.

Модели жизненного цикла

1. Waterfall («водопад», каскадная модель)

Модель не предусматривает обратные связи (каждый элемент д.б. полностью закончен до перехода к следующему). При решении сложных задач это невозможно. Модель применима когда: 1) решается очень простая задача, 2) разрабоатывается очередная версия ПО

2. Прототипирование

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

3. Итерационная модель

Задача разделяется на подзадачи и определяется очередность их реализации т.о., чтобы каждая следующая подзадачи расширяла возможности ПО. Успех существенно зависит от того сколь удачно разделены задачи на подзадачи и как выбрана очередность. Преимущества: 1) возможность активного участия заказчика в разработке, он имеет возможность уточнить свои требования в ходе разработки; 2) возможность тестирования вновь разрабатываемых частей совместно с ранее разработанными, это уменьшит затраты на комплексную отладку; 3) во время разработки можно начинать внедрение по частям.

4. Жизненный цикл «спираль»

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