Б1 В5

 

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

 

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

 

ОПР) Дескриптор – это пара вида (“тип_лексемы”,”указатель”), где “ тип_лексемы ” – это как правило числовой код  класса лексемы, которой означает, что лексика принадлежит одному из конечного множества классов слов, выделенных в языках программирования.

 

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

 

Количество классов лексем (т.е различных видов слов ) в языках программирования может быть различным. Наиболее распространенным классов является

- идентификаторы

- служебные слова

-разделители

-константы

 

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

 

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

 

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

 

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

 

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

 

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

 - метод линейного списка

 - метод упорядоченного списка

 - метод расстановки и др.

 

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

 

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

 

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

 

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

 

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

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

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

 

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

 

НАПРИМЕР

 

ВХОД лексического анализатора

Prjgram primer;

Var x,y,z:real;

Begin

X:=5;

Y:=5;

Z:=x+y;

End.

Коды типов лексем:

10- ключевое слово,

20-разделитель,

30-идентификатор,

40-константа