Упражнение 32: сканнер

Оригинал: Exercise 32: Scanners

Переводчик: Феликс Ли

Лицензия: CC BY-NC-SA 4.0

Гордо использует Google Translate

Моя первая книга случайно затронула тему сканнеров в упражнении 48, но теперь мы будем более формальны. Я объясню концепцию сканирования текста, связанную с регулярными выражениями, а также как создать небольшой сканнер для маленького отрезка кода Python.

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

def hello(x, y):
    print(x + y)

hello(10, 20)

Вы уже достаточно практиковались на Python, чтобы ваш мозг скорее всего быстро прочитал этот код, но вы действительно понимаете его? Когда я (или кто-то другой) учил вас Python, я заставил вас запомнить все "символы". def и () — это каждый символ, но Python нуждается в надёжном и последовательном способе работы с ними. Python также должен быть способен читать hello, понять, что это "имя" чего-то, и знать различие между def hello(x, y) и hello(10, 20). Как это реализуется?Первый шаг состоит в том, чтобы просканировать текст и найти "токены" (tokens). На этапе сканирования язык, такой как Python, не заботится о том, что является символом (def) или именем (hello). Он просто пытается преобразовать входной текст в последовательность "токенов", применяя серию регулярных выражений. Эти регулярные выражения "соответствуют" каждому возможному входу, который понимает Python. В упражнении 31 вы помните, что регулярное выражение — это способ сказать Python, какие последовательности символов он должен соответствовать или принимать. Все интерпретаторы Python используют множество регулярных выражений для соответствия каждому токену, который они понимают.Если вы посмотрите на вышеуказанный код, вы можете составить набор регулярных выражений для его обработки. Для def требуется простое регулярное выражение, которое просто "def". Для символов ()+:, вам потребуется больше регулярных выражений. Затем остаётся вопрос того, как обрабатывать print, hello, 10 и 20. Как только вы определили все символы в приведённых выше примерах кода, вам потребуется назвать их. Вы не можете просто ссылаться на них через их регулярные выражения, так как это снижает производительность поиска и вызывает путаницу. Впоследствии вы заметите, что предоставление уникального имени (или номера) каждому символу упрощает процесс парсинга. Однако сейчас давайте придумаем некоторые названия для этих регулярных выражений. Например, я могу назвать def как DEF, а ()+:, — как LPAREN RPAREN PLUS COLON COMMA. Затем я могу называть регулярные выражения для слов, таких как hello и print, как NAME. Делая это, я нашёл способ преобразования исходного потока текста в последовательность одиночных символьных (или именованных) токенов для использования позднее. Python также может быть сложной, так как она требует регулярное выражение с начальным пробелом для обработки отступов в блоках кода и сжатия. В настоящее время мы используем довольно простое ^\s+, а затем притворяемся, что оно также захватывает количество пробелов в начале строки.В конечном итоге вы получите набор регулярных выражений, который сможет обрабатывать вышеуказанный код, он может выглядеть следующим образом:

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

DEF NAME(hello) LPAREN NAME(x) COMMA NAME(y) RPAREN COLON
INDENT(4) NAME(print) LPAREN NAME(x) PLUS NAME(y) RPAREN
NAME(hello) RPAREN INTEGER(10) COMMA INTEGER(20) RPAREN

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

Микро Python-сканнер

Я создал микро Python-сканнер, демонстрирующий работу этого микроскопического Python-языка:

import re

code = [
"def hello(x, y):",
"    print(x + y)",
"hello(10, 20)",
]
```TOKENS = [
    (re.compile(r"^def"),                    "ОПЕРАТОР_ОПРЕДЕЛЕНИЯ"),
    (re.compile(r"^[a-zA-Z_][a-zA-Z0-9_]*"), "ИМЯ"),
    (re.compile(r"^[0-9]+"),                 "ЦЕЛОЕ_ЧИСЛО"),
    (re.compile(r"^\()"),                     "НАЧАЛЬНАЯ_CКОБКА"),
    (re.compile(r"^\)"),                     "Конечная_скобка"),
    (re.compile(r"^\+"),                     "Плюс"),
    (re.compile(r"^:"),                      "Двоеточие"),
    (re.compile(r"^,"),                      "Запятая"),
    (re.compile(r"^\s+"),                    "Отступ"),
]```md
При печати сценария выводится следующий код:

```python
print(сценарий)

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

[('DEF', 'def', 3, 3), ('INDENT', ' ', 4, 1), ('NAME', 'hello', 9, 5),
('LPAREN', '(', 10, 1), ('NAME', 'x', 11, 1), ('COMMA', ',', 12, 1),
('INDENT', ' ', 13, 1), ('NAME', 'y', 14, 1), ('RPAREN', ')', 15, 1),
('COLON', ':', 16, 1), ('INDENT', '    ', 4, 4), ('NAME', 'print', 9, 5),
('LPAREN', '(', 10, 1), ('NAME', 'x', 11, 1), ('INDENT', ' ', 12, 1),
('PLUS', '+', 13, 1), ('INDENT', ' ', 14, 1), ('NAME', 'y', 15, 1),
('RPAREN', ')', 16, 1), ('NAME', 'hello', 5, 5), ('LPAREN', '(', 6, 1),
('INTEGER', '10', 8, 2), ('COMMA', ',', 9, 1), ('INDENT', ' ', 10, 1),
('INTEGER', '20', 12, 2), ('RPAREN', ')', 13, 1)]

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

Упражнения

```Ваша задача — исследовать этот пример кода сканера и преобразовать его в универсальный класс Scanner, который можно будет использовать позже. Цели этого класса `Scanner` заключаются в том, чтобы принимать входной файл, сканировать его до списка токенов и позволять последовательно извлекать эти токены. API должен иметь следующие методы:> `init`

Настройка сканера с помощью аналогичного списка кортежей (без использования re.compile).

scan

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

match

Предоставляет возможные токены, возвращает первый токен из списка и удаляет его.

peek

Предоставляет возможные токены, возвращает первый токен из списка, но не удаляет его.

push

Возвращает токен обратно в поток токенов, чтобы он был возвращён следующими вызовами peek или match.

Также вам следует создать универсальный класс Token, заменив используемые мной кортежи. Этот класс должен отслеживать найденные токены, соответствующую строку, а также начальную и конечную позицию совпадения в исходной строке.

Исследование

• Установите библиотеку pytest-cov и используйте её для измерения охвата автоматическими тестами.
• Используйте результаты pytest-cov для улучшения автоматических тестов.

Дополнительное обучениеЛучший способ создания сканера основан на трёх фактах о регулярных выражениях:

• Регулярные выражения представляют собой конечные автоматы.
• Можно точно объединять маленькие конечные автоматы в более крупные и сложные конечные автоматы.
• Конечные автоматы, совмещённые для соответствия множества небольших регулярных выражений, работают так же, как каждое отдельное регулярное выражение, но с большей эффективностью.Многие инструменты используют этот факт для принятия определений сканера, преобразования каждого маленького регулярного выражения в конечный автомат, а затем объединения их для создания большого количества кода, которое может надёжно соответствовать всем токенам. Преимущество такого подхода заключается в том, что вы можете предоставлять каждому генерируемому сканеру независимо последовательность символов, позволяющую им быстро распознавать токены. Это лучше, чем то, что я делаю здесь, где я собираю строки и пробую серию регулярных выражений до тех пор, пока не найду подходящее.

Изучите работу генератора сканеров и сравните его с вашим кодом.