Сборник по задачам и примерам Assembler


Лексический анализ - часть 4


  • уникальный номер — номер, который на последующих этапах трансляции

    будет идентифицировать данное символьное имя;

  • указатель на список, содержащий символы идентификатора;
  • указатель на список с номерами строк, в которых встретился данный идентификатор.

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

тивности процесса распознавания стоит все терминальные символы — ключевые слова языка, разделители и т. п. (за исключением id, chint и ch_rea1) — также свести в отдельное лексикографическое дерево или организовать хеш-таблицу.

Можно поступить по-другому. Этот вариант, который можно использовать для анализа ввода в командной строке и т. д., работает в случае, если сканер вызывается из синтаксического анализатора. Суть его в том, что сканер вызывается из синтаксического анализатора, когда последнему нужна очередная лексема. Сканер выделяет ее во входном потоке и выдает синтаксическому анализатору кортеж из двух элементов: кода лексемы и строки, содержащей саму лексему.

А как организовать сам процесс распознавания лексем входной программы? Для этого попробуем сформулировать некий обобщенный алгоритм построения сканера.

  1. 1. Выделить классы лексем.

    2. Определить классы литер.

    3. Определить условия выхода из сканера для каждого класса лексем.

    4. Для каждого класса лексем поставить в соответствие грамматику класса 3.

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

    6. Выполнить объединение («склеивание») конечных автоматов для всех классов лексем.

    7. Составить матрицу переходов для «склеенного» конечного автомата.

    8. «Навесить» семантику на дуги «склеенного» конечного автомата.

    9. Выбрать коды лексической свертки для терминалов грамматики и формат таблицы идентификаторов.

    10. Разработать программу сканера.

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




- Начало -  - Назад -  - Вперед -