Токены, шаблоны и лексемы

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

• Шаблон (pattern) — это описание вида, который может принимать лексема токена. В случае ключевого слова шаблон представляет собой просто последовательность символов, образующих это ключевое слово. Для идентификаторов и некоторых других токенов шаблон представляет собой более сложную структуру, которой соответствуют (matched) многие строки.

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

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

‹имя_токена, значение_атрибута›

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

Предположим, например, что исходная программа содержит инструкцию присваивания:

position = initial + rate * 60

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

1. Position представляет собой лексему, которая может отображаться в токен (id 1) где id – абстрактный символ, обозначающий идентификатор, а 1 указывает запись в таблице символов для position. Запись таблицы символов для некоторого идентификатора хранит информацию о нем, такую как его имя и тип.

2. Символ присваивания = представляет собой лексему, которая отображается в токен (=). Поскольку этот токен не требует значения атрибута, второй компонент данного токена опущен. В качестве имени токена может быть использован любой абстрактный символ, например такой, как assign, но для удобства записи в качестве имени абстрактного символа можно использовать саму лексему.

3. Initial представляет собой лексему, которая отображается в токен (id 2) где 2 указывает на запись в таблице символов для initial.

4. + является лексемой, отображаемой в токен (+).

5. Rate – лексема, отображаемая в токен (id 3) где 3 указывает на запись в таблице символов для rate.

6. * – лексема, отображаемая в токен *.

7. 60 – лексема, отображаемая в токен (number 4) где 4 указывает на запись таблицы символов для внутреннего представления целого числа 60.

Пробелы, разделяющие лексемы, лексическим анализатором отбрасываются.

Представление инструкции присваивания после лексического анализа в виде последовательности токенов:

(id, 1) (=) (id, 2) (+) (id, 3) (*) (number, 4)

При этом представлении имена токенов =, + и * представляют собой абстрактные символы для операторов присваивания, сложения и умножения соответственно.

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

printf("Total = %d\n", score);

“Printf” и “score” представляют собой лексемы, соответствующие токену id, a "Total = %d\n" является лексемой, соответствующей токену literal.

Таблица 2 – Примеры токенов.

    Во многих языках программирования описанные далее ситуации охватывают большинство (если не все) токенов.

1. По одному токену для каждого ключевого слова. Шаблон для ключевого слова выглядит так же, как само ключевое слово.

2. Токены для операторов, либо отдельные, либо объединенные в классы, как это сделано в случае токена comparison

3. Один токен, представляющий идентификаторы.

4. Один или несколько токенов, представляющих константы, такие как числа и строковые литералы.

5. Токены для каждого символа пунктуации, такие как левые и правые скобки,

запятые или точки с запятыми.

Лексические ошибки

Без помощи других компонентов компилятора лексическому анализатору сложно обнаружить ошибки в исходном тексте программы. Например, если в программе на языке С строка f i впервые встретится в контексте

fi ( а == f(x)) …

лексический анализатор не сможет определить, что именно представляет собой f i — неверно записанное слово if или необъявленный идентификатор функции. Поскольку f i является корректной лексемой для токена id, лексический анализатор должен вернуть этот токен синтаксическому анализатору и позволить другой фазе компилятора — в данном случае, по всей видимости, синтаксическому анализатору — обработать ошибку перестановки местами двух букв.

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

Существуют и другие возможные действия по восстановлению после ошибки.

1. Удаление одного символа из оставшегося входного потока.

2. Вставка пропущенного символа в оставшийся входной поток.

3. Замена символа другим.

4. Перестановка двух соседних символов.

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

    Словарь определений

    Токены. Лексический анализатор сканирует исходную программу и выдает последовательность токенов, которая обычно передается синтаксическому анализатору по одному токену. Некоторые токены состоят из одного имени токена, в то время как другие могут иметь связанное с ними лексическое значение, несущее информацию о конкретном экземпляре токена, и найденном во входном потоке.

    ♦ Лексемы. Каждый раз, когда лексический анализатор возвращает синтаксическому анализатору токен, с последним связана его лексема — последовательность входных символов, которую представляет токен.

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

    ♦ Шаблоны. Каждый токен имеет шаблон, который описывает, какая последовательность символов может формировать лексему, соответствующую этому токену. Множество слов, или строк символов, которые соответствуют данному шаблону, называется языком.

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

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

    ♦ Расширенная запись регулярных выражений. В регулярных выражениях для упрощения может использоваться ряд дополнительных операторов, представляющих собой сокращения имеющихся регулярных выражений. Примерами таких операторов могут служить оператор (одно или несколько вхождений), ? (нуль или одно вхождение), а также классы символов.

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

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

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

    ♦ Недетерминированные конечные автоматы. Автомат, не являющийся детерминированным, называется недетерминированным. НКА часто существенно проще спроектировать, чем ДКА. Еще одной возможной архитектурой лексического анализатора является табуляция для каждого возможного шаблона всех состояний НКА, в которых он может оказаться при сканировании входного потока.

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