Обзор сканирования текста

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

Как работают сканеры?

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

Сканеры работают, находя шаблон, который принимает текущий символ. Затем сканер будет обрабатывать узор до тех пор, пока текст не перестанет совпадать. На данный момент лексема идентифицирована. Затем в списке записывается расположение каждой лексемы, и создается токен для шаблонов, которые имеют отношение к дальнейшей обработке. Затем сканер повторит процесс поиска шаблона. Это продолжается до тех пор, пока не будет отсканирован весь текст.

Узоры

Шаблон определяет допустимую последовательность символов. Шаблон может искать явный порядок символов: int это i + n + t. Он также может искать общую последовательность, например регулярное выражение. На рисунке 1 показан образец чисел в JSON.

Регулярные выражения и конечные автоматы

Регулярное выражение определяет шаблон, используя набор правил, хранящихся в строке. Регулярное выражение «[0–9]» будет соответствовать любому числу от 0 до 9.

Однако при создании сканеров регулярные выражения обычно не используются. Это связано со сложностью допустимых шаблонов. Возьмем пример числа JSON на рис. 1. Создание для него регулярного выражения возможно, но, безусловно, будет нелегко. Регулярные выражения также требуют дополнительных затрат времени.

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

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

Номера обработки

Сначала давайте рассмотрим, как создать детерминированный конечный автомат для чисел. В качестве руководства мы будем использовать шаблон, показанный на рисунке 1. При обработке числа он может иметь несколько форм. Это может быть целое число - 123. Это может быть десятичное число - 4.2. Или это может быть показатель степени - 0,987e6.

Первым делом нужно наблюдать повторы в узоре. Мы видим, что десятичная дробь или показатель степени будут содержать целые числа. Десятичным числом будет integer.integer. Показателем степени будет integer.integer(e|E)[+|-]integer. Обладая этими знаниями, мы можем создать многоуровневый узор.

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

Как только становится известно, что число присутствует, вызывается целочисленный шаблон. Целое число может состоять из чисел от 0 до 9. Кроме того, в числах разрешены подчеркивания, которые служат разделителями. Например, большое число можно записать как 1_000_000. В отличие от шаблона JSON, знаки перед числом не проверяются.

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

При проверке экспоненты очень важно убедиться, что образец завершен. Число 12.3e- неполное. Когда это происходит, шаблон должен откатиться. Он будет принимать наибольшее количество символов, которые соответствуют состоянию принятия в шаблоне. В этом случае это будет 12,3. Если вы знаете, что другой приемлемый шаблон не может последовать, сканер может сообщить об ошибке. Для компиляторов важно обработать как можно больше вводимых данных перед остановкой. Таким образом, за один проход можно выявить больше ошибок.

Сканирование строк

Строки - один из самых простых в обработке компонентов. «Строка выглядит так». Все символы, содержащиеся в кавычках, объединяются для создания строки. Единственная сложность возникает, когда «строка содержит« внутри строки ». Обычное решение - избежать цитаты. Это влечет за собой установку обратной косой черты перед цитатой. Теперь строка будет выглядеть так: «строка содержит \» внутри строки ».

Все, что должен сделать шаблон, - это проверить, что начальный символ - это кавычка. Затем он ищет неэкранированную цитату позже во входном тексте. Шаблон также проверяет, является ли последний символ обратной косой чертой. Если это так, строка продолжается до следующей строки. Отдельный шаблон обрабатывает строки, пересекающие несколько линий. Также следует отметить, что действительность цитаты не проверяется. Шаблон не обнаруживает незавершенные котировки. Как и в случае с числовым шаблоном, эта проверка опускается, чтобы задержать идентификацию ошибок.

Идентификация операторов

Операторы - это математические символы, которые могут состоять из одного или нескольких символов. Чтобы понять, как работает операторское сканирование, давайте посмотрим на +, ++ и +=. Наименее эффективный способ заключается в поиске в первую очередь самых длинных операторов. Лучше использовать иерархию операторов.

Иерархия операторов записывает отношения между операторами. У каждого оператора есть символ и тег. Он также имеет список операторов, которые идут после него в иерархии. Первый оператор будет < + : PLUS >. Под плюсом будет еще два оператора: < + : INCREMENT > и < = : PLUS_EQUAL >.

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

Определение ключевых слов (или быстрое сопоставление текста)

Определение конкретных слов - будь то ключевые слова, имена или идентификаторы - имеет простое решение. Извлеките слово из входящего текста, создав новую строку. Затем сравните эту строку со всеми возможными ключевыми словами / именами / что у вас есть!

Ждать? Вы думаете, что это будет медленно и неэффективно?

Ну, это потому, что это так. Итак, что было бы лучше для сравнения текста?

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

Для вычисления хэша я полагаюсь на функцию CRC32 (циклический контроль избыточности - 32 бита). Функция была создана для обнаружения ошибок в потоках данных. Основное преимущество использования CRC32 перед другой функцией хеширования - это встроенная аппаратная поддержка. CRC32 - это внутренняя функция оборудования. Его можно использовать на любой машине, поддерживающей расширения набора инструкций SSE4.2. Согласно Обзор оборудования Steam, 96,15% процессоров в их отчете поддерживают SSE4.2.

Использование встроенной функции, к сожалению, не так красиво. Во-первых, функция помещается в заголовок intrin.h C. Существует четыре различных формы алгоритма CRC32, которые изначально поддерживаются. Поскольку мы хешируем строку, лучший вариант - использовать _mm_crc32_u8(hash, u8_char). hash - текущее значение результата CRC, а u8_char - текущий байт текста, преобразованный в беззнаковый байт.

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

Петля сканера

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

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

Затем сканер перезапускает цикл с первым DFA. При перезапуске цикла сохраняется порядок важности правил DFA. Это также позволяет создавать более простые DFA с меньшим количеством ветвей.

Примеры вывода сканера

Теперь, когда мы рассмотрели, как построить сканер. Давайте посмотрим на результат, который он выдаст. Рассмотрим следующий пример:

let x = 3
let y = x + 2 * (9 - x)

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

По мере того как сканер производил лексемы, он также решал, какие из них имеют отношение к более поздним этапам. В языке программирования, который я реализую, пробелы не нужны для синтаксического анализа. Поэтому он исключен из набора токенов. Чтобы отследить, где заканчивается одна строка и начинается другая, в конце каждого выражения вставляется специальный маркер EOL (конец строки). В итоге сканер произвел 18 токенов из 28 лексем.

Тесты производительности

При обработке большого количества текста важно делать это как можно быстрее. Чтобы протестировать сканер, я использовал серию длинных заголовочных файлов C. Заголовки взяты из библиотеки STB.

Тест производительности не является строгим эталоном, но он дает приблизительную оценку производительности сканера. Все время измеряется с помощью настенных часов. На моем компьютере были запущены другие вещи, и не было предпринято никаких усилий для определения приоритета сканера. Для каждого файла было проведено 30 тестов для определения среднего и стандартного отклонения. Тест проводился на процессоре Intel I7 с тактовой частотой 2,60 ГГц.

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

Следующее в серии: Реализация таблицы символов с ограниченной областью видимости (скоро)
Предыдущая в серии: Внутри компилятора
Обзор серии: Создание безопасного языка

Код для этой статьи и серии компиляторов доступен на GitHub.