ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР. ТЕОРИЯ.

КУРСОВОЙ ПРОЕКТ

 

По дисциплине «Средства разработки и проектирования компонент операционных систем»

Тема: «Построение лексического анализатора»

 

 

Автор курсового проекта:                                                                    Бишлеев В. М.

                                                                                        

 

 

Группа:                                                                                                          821-ПРИ

                             

Направление:                                                                       Программная инженерия

 

Руководитель проекта:                                                                         А.С. Родионов

 

 

 

 

Ростов – на – Дону

 2020

СОДЕРЖАНИЕ

 

Введение…………………………………………………………………………………3

 

ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР. ТЕОРИЯ…………………… …………………….4

 

Роль лексического анализатора……………………………………………………...…4

 

Токены, шаблоны и лексемы………………………………………………………...…8

 

Лексические ошибки…………………………………………………………………..10

 

Словарь определений……………………………………………………………….…11

 

МОДЕЛИРОВАНИЕ ПРОЦЕССА ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА………......13

 

ПРОЕКТИРОВАНИЕ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА………………...............23

 

Заключение……………………………………………………………………….…….32

 

Библиографический список…………………………………………………………...33

 

 

       Введение

 

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

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

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

анализаторов.

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

 

 

ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР. ТЕОРИЯ.

  1.1 Роль лексического анализатора

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

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

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

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

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

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

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

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

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

 

Рисунок 1 – Взаимодействие лексического анализатора с синтаксическим.

 

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

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

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

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

Иллюстрацией такого случая может служить пример оператора присваивания из языка программирования Си++:

 

k = i+++++j;

 

Который имеет только одну верную интерпретацию (если операции разделить пробелами):

k = i++ + ++j;

 

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

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

Чтобы избежать параллельной работы лексического и синтаксического анализаторов, разработчики компиляторов и языков программирования часто идут на разумные ограничения синтаксиса входного языка. Например, для языка Си++ принято соглашение, что при возникновении проблем с определением границ лексемы всегда выбирается лексема максимально возможной длины. Для рассмотренного выше оператора присваивания это приводит к тому, что при чтении четвертого знака + из двух вариантов лексем (+ – знак сложения, ++ – оператор инкремента) лексический анализатор выбирает самую длинную, т.е. ++, и в целом весь оператор будет разобран как k = i++ +++j;, что неверно. Любые неоднозначности  при анализе данного оператора присваивания могут быть исключены только в случае правильной расстановки пробелов в исходной программе.

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

Вот пример фрагмента текста программы на языке Паскаль и соответствующей ему таблицы лексем:

...

begin

 for i:=1 to N do

fg := fg * 0.5

...

Таблица 1 – Таблица лексем программы.

 

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