4 Лексические анализаторы. Основные функции, проектирование и методы программной реализации.

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

ЛА может представлять собой подпрограмму – функцию, которая возвращает тип очередной выделенной лексемы, а значение заносит в некоторую глобальную переменную. Подпрограмма ЛА может вызывать СА при параллельном взаимодействии, и тип, и значение сразу обрабатываются СА. При последовательном взаимодействии эта подпрограмма вызывается многократно, пока не будет обработан текст программы или не найдена ошибка. На каждом шаге тип лексем и ее значения заносятся в таблицу лексем. Порядок следования лексем в таблице такой же, как в исходной программе. Например, если ЛА обрабатывает цепочку for i:=15 to n*(m-k) do таблица лексем будет иметь следующий вид:

Ла может при его вызове из очередной последовательности символов создать лексемму. Такой анализатор называется прямым. Непрямому ЛА задается тип лексемы, которая определяет действие «распознать» на очередном шаге. Такой анализатор возвращает истину, если очередная последовательность обрабатываемых символов – есть лексемы заданного типа, и ложь иначе. Непрямой ЛА (НЛА) вызывается из СА. Если ЛА возвращает ложь, возможно, СА опять обратиться к ЛА с другим типом лексемы, тогда ЛА будет заново обрабатывать ту же последовательность символов с целью формирования лексемы другого типа. НЛА может быть использован при параллельном взаимодействии с СА, когда одна последовательность символов может представлять собой различные лексемы, в зависимости от ее окружения. Кроме основной задачи выделения лексем, ЛА выполняет также и другие задачи, например: удаление из исходной программы комментариев, удаление пустых символов и тп, также обнаружение ошибок (лексических и синтаксических), например:

1)ЛА проверяет парность лексем (if…then, (), и тп). Для того, чтобы обнаружить такого типа ошибки, используется массив. Индекс массива соответствует паре лексем. Сначала все элементы массива равны 0, далее, если встречается первый элемент пары соответствующий элемент массива увеличивается на 1, если второй элемент пары - уменьшается на 1. Если после обработки всего текста исходной программы все элементы такого массива равны 0, то этого типа синтаксических ошибок в программе нет, если хотя бы один элемент не равен нулю, то может быть выдано сообщение об ошибке, чего и сколько не хватает.

2)Сочетаемость/порядок ключевых слов. (за for – to, за while – do и тп). Для обнаружения таких ошибок используется матрица, в которой строки и столбцы соответствуют ключевым словам. Если за i-тым может следовать j – ое ключевое слово, то табл[i,j] =1 и 0 иначе. Для того,чтобы обнаружить ошибку такого типа, нужно знать предыдущее ключевое слово. После прочтения очередного ключевого слова – обращение к элементу матрицы, и если он равен нулю – есть ошибка.

3)Сочетаемость рядом стоящих лексем. Например, после for может быть идентификатор, но не наоборот. Для обнаружения можно составить матрицу, как в

2.

4)Согласование местоположения ошибки, лексической или синтаксической и текста исходной программы.

5)Можно выполнить простейший синтаксический анализ. Например, распознавание унарного минуса, а не бинарного, так как с точки зрения ЛА – это одна и та же лексема.

Принципы построения ЛА.

Лексемы определенного типа представляют собой множество цепочек, то есть формально – язык.Такие языки являются регулярными языками (РЯ), поэтому каждый тип лексемы может быть распознан КР (конечным распознавателем). При реализации непрямого ЛА задается тип лексемы, который и обнаруживается на каждом шаге. По типу лексемы обращаются к КР и определяют, является ли очередная последовательность символов лексемой заданного типа. Если ЛА – прямой, тогда он должен представлять собой один КР, который обнаруживает все типы лексем. Множество КР можно рассматривать как один недетерминированный конечный распознаватель, и, для того, чтобы использовать, нужно преобразовать в детерминированный. Каждый из распознавателей определенного типа лексем представляет собой детерминированный КР, множество символов которых попарно не имеют пересечения. В распознавателе можно объединить в одно все начальные состояния, чтобы получить один детерминированный распознаватель. Задача ЛА – определение границ лексем. Решение этой задачи нужно начинать с разработки языка. Возможные варианты:

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

2)Использование принципа выбора лексемы наибольшей длины.

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

ЛА может в процессе работы выполнять некоторые действия, например, накапливать имя лексемы, значение константы может вычисляться в процессе анализа или после. Если взаимодействие СА и ЛА последовательное, то ЛА после определения очередной лексемы создает очередной элемент таблицы лексем. ЛА пропускает комментарии.

ЛА выделяет ключевые слова. Способы:

1) может составить таблицу ключевых слов

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

Программная реализация ЛА.

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

Пусть задан РЯ. Если язык содержит конечное число цепочек – точно регулярный. Для такого языка можно построить КР. Граф будет ациклическим, содержать конечный путь от начальной до завершающей вершины, соответствующий цепочкам исходного языка. Если язык содержит бесконечное число цепочек, то граф будет циклическим. Допустим, язык регулярный и КР языка содержит n состояний. Так как количество цепочек конечно, то распознаватель может допускать цепочки большой длины. Пусть КР обрабатывает цепочку, длина которой больше или равна количеству состояний. Тогда хотя бы одна из вершин при обработке встретится дважды.

Нужно доказать регулярность языка.

Выбираемую цепочку нужно разбить на 3 такие части (*). После разбиения определяем, принадлежат ли цепочки исходному языку. Если так разбить нельзя, то язык перерегулярный.

Для распознавания КС языков используются распознаватели с кассетной памятью(МПраспознаватели)