Информационно-безопасные системы. Анализ проблемы: Учебное пособие, страница 32

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

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

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

Учитывая, что в нашей задаче небольшое количество входных символов, целесооб­разно использовать метод вектора переходов.

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

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

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

3.  Метод линейного списка. Входное слово сравнивается с каждым элементом хранимого в памяти списка до тех пор, пока не произойдет совпадение (если оно возможно).

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

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

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

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

Реализация лексического блока показана в табл. 8.4.

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