Идентификация слов: метод индексов

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

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

Пример:

Рассмотрим задачу распознавания идентификаторов языка MiniBasic:

Идентификатор::= БЦ | Б

Б::= a | b | c…z

Ц::= 0 | 1…9

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

а ® 1

b ® 2

…

z ® 26

a0 ® 27

…

z9 ® 286

Если следующий символ – цифра, то к индексу прибавляется число: 26*(Ц+1).

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

Данный метод применим в следующих случаях:

1) Количество слов не должно быть слишком большим. Это условие, например, исключает множество переменных Си, так как содержит более миллиарда элементов.

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

3) Объем множества слов фиксируется при построении, так как метод вычисления индекса неудобно изменять во время компиляции.

Таким образом, методом можно пользоваться нечасто, но если он применим, то идентификация осуществляется с минимальными затратами времени.

Замечание:

Индекс может указывать на таблицу указателей, содержащую указатели на таблицу имен. Чтобы найти элемент таблицы имен для слова с индексом i, необходимо взять указатель из i-го элемента таблицы указателей. Этот метод позволяет заводить элементы таблицы имен только для тех слов, которые действительно имеются в данной программе. Для этого таблицу указателей инициализируют нолями, которые означают. что ни один элемент в таблице имен еще не отведен. Когда слово встречается впервые. об этом свидетельствует ноль в соответствующей ячейке таблицы указателей. Для этого слова заводится элемент таблицы имен, а указатель на него помещается в таблицу указателей.

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

Вопросы и упражнения

В чем главная сложность применения метода индексов?