CONSCOMP (Материалы к контрольным работам), страница 6

состоит только из состояний из f, либо не имеет состояний из

f.

Шаг 5. Если М' имеет мертвое состояние, т.е. состояние d,

которое не является допускающим и которое имеет переходы в

себя по любому символу, удалим его из М'. Удалим также все

состояния, не достижимые из начального.

2.5. Программирование лексических анализаторов

Лексический анализатор, как правило, вызывается как

подпрограмма. В результате обращения к ЛА вырабатываются как

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

указатель на значение) для классов лексем (идентификаторов,

чисел, строк и т.д.). Само значение передается, если ЛА не

работает с таблицей имен. Если же ЛА сам формирует таблицу

имен, то он выдает указатель на имя. Обычно ЛА оформляется как

процедура-функция, вырабатывающая тип лексемы и заносящая в

некоторую глобальную переменную значение лексемы, если это

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

может содержать некоторую дополнительную информацию: номер

текущей строки, номер символа в строке и другую. Эта

информация может использоваться в различных целях, например,

для диагностики.

Тело ЛА представляет собой диаграмму переходов

соответствующего конечного автомата. Отдельная проблема -

анализ ключевых слов. Как правило, ключевые слова - это

выделенные идентификаторы. Поэтому возможны два основных

способа выделения ключевых слов: либо очередная лексема

сначала диагностируется на совпадение с каким-либо ключевым

словом и в случае неуспеха делается попытка выделить лексему

из какого-либо класса, либо, наоборот, после выборки лексемы

идентификатора требуется заглянуть в таблицу ключевых слов на

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

будет сказано ниже (гл. 7), здесь отметим только, что поиск

ключевых слов может вестись либо в основной таблице имен и в

этом случае в нее до начала работы ЛА загружаются ключевые

слова, либо в отдельной таблице. При первом способе все

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

лексического анализатора, во втором конечный автомат содержит

только разбор идентификаторов.

В некоторых языках (например, ПЛ/1 или Фортран) ключевые

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

В этом случае работа ЛА не может идти независимо от работы

синтаксического анализатора. В Фортране возможны, например,

следующие строки:

do 10 i=1,25 и

do 10 i=1.25

В первом случае строка - это заголовок цикла do, во втором -

оператор присваивания. Поэтому, прежде чем можно будет

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

довольно далеко.

Еще сложнее дело в ПЛ/1. Здесь возможны такие операторы:

if then then then = else; else else = then или

declare (arg1, arg2, ...., argn) ...

и только в зависимости от того, что стоит после ")", можно

определить, является ли declare именем подпрограммы или

объявлением. Длина такой строки может быть сколь угодно

большой и уже невозможно отделить фазу синтаксического анализа

от фазы лексического анализа.

Рассмотрим несколько подробнее вопросы программирования ЛА.

Основная операция лексического анализатора, на которую уходит

большая часть времени его работы, - это взятие очередного

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

Например, основной цикл при выборке числа в простейшем случае

может выглядеть следующим образом:

while (insym<='9' & insym>='0') do

...

end;

Проверки на принадлежность диапазону сравнениями можно

заменить проверками на принадлежность диапазону множества:

while (insym in ['0'..'9']) do

...

end;

Однако с точки зрения качества кода эти программы примерно

эквивалентны. Программу можно значительно улучшить следующим

образом [2]. Пусть letter, digit, blank, sless - элементы

перечислимого типа. Введем массив map, входами которого будут

символы, значениями - типы символов. Инициализируем массив map

следующим образом:

map['a']:=letter;

........

map['z']:=letter;

map['0']:=digit;

........

map['9']:=digit

map[' ']:=blank;

map['<']:=sless;

........

Тогда приведенный выше цикл примет следующую форму:

while (map[insym]=digit) do

...

end;

Выделение ключевых слов может осуществляться после выделения

идентификаторов. ЛА работает быстрее, если ключевые слова

выделяются непосредственно.

+----------+

------------------->| ключевое |

+---+ f +---/не буква и не цифра | слово if |

| i |--->| | +----------+

+---\ +---\буква или цифра +---------------+

| \ ---------------->| Идентификатор |

n| \ +---------------+

| \ ^ ^ ^

| \ Не f и не t | | |

v --------------------------+ | |

+---+ Не t | |

| |--------------------------------+ |

+---+ |

t| |

v |

+---+ Буква или цифра |

| |-----------------------------------+

+---+

| Не буква и не цифра

v

+--------------------+

| Ключевое слово int |

+--------------------+

Рис. 2.12

Для этого строится конечный автомат, описывающий множество

ключевых слов. На рис. 2.12 приведен фрагмент такого автомата.

Рассмотрим пример программирования этого конечного автомата на

языке Си, приведенный в [3]:

case 'i':

if (cp[0]=='f' &&!(map[cp[1]] & (digit | letter)))

{cp++; return if;}

if (cp[0]=='n' && cp[1]=='t'

&&!(map[cp[2]] & (digit | letter)))

{cp+=2; return int;}

Здесь cp - указатель текущего символа. В массиве map классы

символов кодируются битами.

Поскольку ЛА анализирует каждый символ входного потока, его

скорость существенно зависит от скорости выборки очередного

символа входного потока. В свою очередь, эта скорость во

многом определяется схемой буферизации. Рассмотрим несколько

возможных эффективных схем буферизации.

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

длина блока обмена n (рис. 2.13).

n n

+----------------+ +-------------------+

| | | | # | # |

+----------------+ +-------------------+

^ ^ ^ ^

| |Продвижение | |Продвижение

|Начало лексемы (cp) |Начало лексемы

Рис. 2.13 Рис. 2.14

Чтобы не читать каждый символ отдельно, в каждую из половин

буфера одной командой чтения считывается n символов. Если на

входе осталось меньше n символов, в буфер помещается

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

продвижение и начало. Между указателями размещается текущая

лексема. Вначале они оба указывают на первый символ выделяемой

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

не будет выделена лексема, и устанавливается на ее конец.

После обработки лексемы оба указателя устанавливаются на

символ, следующий за лексемой. Если указатель продвижение

переходит середину буфера, правая половина заполняется новыми

n символами. Если указатель продвижение переходит правую