Упражнение 33: Парсеры

Оригинал: Exercise 33: Parsers

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

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

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

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

Давайте ещё раз взглянем на мини-код Python из упражнения 32 и обсудим парсер с трёх разных углов:

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

hello(10, 20)

Когда вы смотрите на этот код, что видите? Я вижу дерево, похожее на BSTree или TSTree, которые мы создали ранее. Вы видите дерево? Мы начинаем с верха файла и учимся превращать последовательность символов в дерево.Сначала, когда мы загружаем .py файл, это всего лишь "поток символов" — фактически это байты, но Python использует Unicode, поэтому нам приходится работать с символами. Эти символы находятся в одной строке, без какой-либо структуры, и задача сканера состоит в том, чтобы добавить первый уровень смысла. Сканер использует регулярные выражения для извлечения значений из потока строк, создавая список токенов. Мы уже преобразовали последовательность символов в список токенов, но обратите внимание на функцию def hello(x, y):. Это функция, содержащая блок кода. Это указывает на некоторую форму "включения" или "вещи внутри вещи". Один из самых простых способов представления включения — это использование дерева. Мы можем использовать таблицы, как в вашем электронном листе, но они не так удобны, как деревья. Давайте рассмотрим часть hello(x, y). У нас есть метка NAME(hello), но нам нужно выделить содержимое внутри ( ... ) и знать, что это находится внутри скобок. Вновь, мы можем использовать дерево, и будем "вкладывать" части x, y внутри ( ... ) как подузлы или ветви дерева. В конечном итоге, у нас будет дерево, которое начинается с корня этого Python-кода, а каждый блок кода, print, определение функции и вызов функции являются ветками от корня, и у каждой из этих веток могут быть свои подветки, и так далее. Почему мы это делаем?Нам нужно знать структуру кода на Python, основываясь на его синтаксисе, чтобы мы могли анализировать его позже. Если мы не будем преобразовывать линейный список токенов в дерево, то нам будет непонятно, где заканчиваются функции, блоки кода, ветвления или выражения. Мы должны определять границы "на лету" в линейной форме, что затрудняет надёжность этого процесса. Многие ранние плохие языки были линейными языками, но теперь мы знаем, что они не обязательно таковыми являются. Мы можем использовать парсер для создания структуры дерева.Задача парсера — получить список токенов от сканера и преобразовать его в более значимое синтаксическое дерево. Вы можете представить парсер как применение другого регулярного выражения к потоку токенов. Регулярные выражения сканера помещают большое количество символов в токены. «Регулярные выражения» парсера помещают эти токены в коробки, внутри которых могут находиться еще коробки, и так далее до тех пор, пока токены больше не будут линейными.

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

* root
  * Function
    - имя = hello
    - параметры = x, y
    - код:
      * Вызов
        - имя = print
        - параметры =
            * Выражение
              - Сложение
                - а = x
                - б = y
  * Вызов
    - имя = hello
    - параметры = 10, 20

Рекурсивный спускный парсерСуществует несколько установленных методов для создания парсера для такой грамматики, но самый простой называется рекурсивным спускным парсером (RDP). На самом деле, я объяснил эту тему в упражнении 49 моего руководства "Простой способ изучить Python". Вы создали простой RDP парсер для обработки вашего маленького игрового языка, даже не зная об этом. В этом упражнении я предоставлю более формальное описание того, как писать RDP парсер, а затем попрошу вас попробовать его с использованием нашего маленького фрагмента кода на Python выше. RDP использует несколько взаимно рекурсивных вызовов функций, что позволяет реализовать деревянную структуру для заданной грамматики. Код парсера RDP выглядит так, словно вы работаете с реальной грамматикой, при условии следования некоторым правилам, они легко пишутся. Два недостатка парсеров RDP заключаются в том, что они могут не быть очень эффективными и обычно требуют ручного написания, поэтому они содержат больше ошибок по сравнению с сгенерированными парсерами. Теоретически есть некоторые ограничения относительно того, что может распарсить парсер RDP, но поскольку вы ручным образом его пишете, вы обычно можете преодолеть многие из этих ограничений. Чтобы создать парсер RDP (Recursive Descent Parser), вам потребуются три основных операции для работы с токенами сканера:> peek

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

match

Соответствует следующему токену и удаляет его из потока.

skip

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

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

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

def function_definition(tokens):
    skip(tokens) # игнорируем ключевое слово "def"
    имя = match(tokens, 'NAME') # получаем имя функции
    match(tokens, 'LPAREN') # проверяем наличие открывающей скобки
    параметры = parameters(tokens) # рекурсивно вызываем парсер параметров
    match(tokens, 'RPAREN') # проверяем наличие закрывающей скобки
    match(tokens, 'COLON') # проверяем наличие двоеточия
    return {'type': 'FUNCDEF', 'name': имя, 'params': параметры} # возвращаем словарь с информацией о функции

Здесь видно, что мы просто принимаем токены и используем match и skip, чтобы обрабатывать их. Также стоит отметить, что есть функция parameters, которая является "рекурсивной" частью нашего парсера RDP. Когда она требуется для анализа параметров функции, function_definition вызывает parameters.## Грамматика ABNF

Попытаться создать парсер RDP сначала, не имея какой-либо формы грамматического описания, довольно сложно. Вы помните, когда я просил вас преобразовать одно регулярное выражение в автомат конечных состояний (FSM)? Это было сложно, потому что требовалось больше кода, а не несколько символов в регулярном выражении. Аналогично, когда вы пишете парсер RDP для этого упражнения, вы делаете то же самое, поэтому полезно использовать язык, который можно назвать "регулярным выражением для грамматики".

Наиболее распространённой формой "регулярного выражения для грамматики" является форма Backus-Naur Form (BNF), названная в честь её создателей Джона Бэкуса и Петера Ноара. BNF описывает необходимые токены и способы их повторения для формирования грамматики языка. BNF также использует те же символы, что и регулярные выражения, поэтому *, + и ? имеют похожие значения.Для этого упражнения я буду использовать расширенную версию BNF, указанную на https://tools.ietf.org/html/rfc5234, чтобы описать грамматику вышеупомянутого мини-кода Python. Операторы ABNF в большинстве случаев совпадают с регулярными выражениями, за исключением того, что они помещают знак повторения перед объектом, который нужно повторять. Кроме того, прочитайте спецификацию и попробуйте понять значение ниже:

root = *(funccall / function_definition)
function_definition = DEF name LPAREN params RPAREN COLON body
funccall = name LPAREN params RPAREN
params = expression *(COMMA expression)
expression = name / plus / integer
plus = expression PLUS expression
PLUS = "+"
LPAREN = "("
RPAREN = ")"
COLON = ":"
COMMA = ","
DEF = "def"
```Мы используем `def function_definition(tokens)` для начала этого раздела синтаксиса.

`DEF`

Определено в синтаксисе как `DEF = "def"`, а в Python-коде мы используем `skip(tokens)` для пропуска его.

`name`

Необходимо использовать `name = match(tokens, 'NAME')` для его совпадения. В BNF используется соглашение CAPITALS для обозначения того, что следует пропустить.

`LPAREN`

Проверяем наличие `(` после `def`. Пропускаем его с помощью `match(tokens, 'LPAREN')`.

`params`

Здесь `params` определяется как новый "синтаксический продукт", то есть новая функция в Python-коде. Мы вызываем её через `params = parameters(tokens)`, где `parameters` — это отдельная функция для обработки запятых между параметрами.

`RPAREN`

Пропускаем закрывающую скобку `)` с помощью `match(tokens, 'RPAREN')`.

`COLON`

Пропускаем двоеточие `:` с помощью `match(tokens, 'COLON')`.

`body`

Функциональное тело пропускается, так как детализация Python-синтаксиса слишком сложна для данного примера. Для практики можно пропустить этот шаг.

Это основной принцип преобразования ABNF-спецификаций в код. Начинаем с корневого элемента и реализуем каждый синтаксический продукт в виде функции, позволяя сканнеру обрабатывать простые токены (CAPITALS).

## Пример простой магической парсера

Это быстрый хак для RDP-парсера, который можно использовать как базовый шаблон для более строгих и компактных парсеров.

```py
from scanner import *
from pprint import pprint
``````python
def root(tokens):
    """root = *(funccall / function_definition)"""
    first = peek(tokens)

    if first == 'DEF':
        return function_definition(tokens)
    elif first == 'NAME':
        name = match(tokens, 'NAME')
        second = peek(tokens)

        if second == 'LPAREN':
            return function_call(tokens, name)
        else:
            assert False, "Не FUNCDEF или FUNCCALL"

def function_definition(tokens):
    """
    funcdef = DEF имя LPAREN params RPAREN COLON body
    Я игнорирую body в этом примере, так как это сложно.
    То есть, чтобы вы могли узнать, как это сделать.
    """
    skip(tokens)  # игнорируем def
    name = match(tokens, 'NAME')
    match(tokens, 'LPAREN')
    params = parameters(tokens)
    match(tokens, 'RPAREN')
    match(tokens, 'COLON')
    return {'type': 'FUNCDEF', 'name': name, 'params': params}

def parameters(tokens):
    """params = expression *(COMMA expression)"""
    params = []
    start = peek(tokens)
    while start != 'RPAREN':
        params.append(expression(tokens))
        start = peek(tokens)
        if start != 'RPAREN':
            assert match(tokens, 'COMMA')
    return params

def function_call(tokens, name):
    """funccall = имя LPAREN params RPAREN"""
    match(tokens, 'LPAREN')
    params = parameters(tokens)
    match(tokens, 'RPAREN')
    return {'type': 'FUNCCALL', 'name': name, 'params': params}

def expression(tokens):
    """expression = имя / плюс / целое"""
    start = peek(tokens)

    if start == 'NAME':
        name = match(tokens, 'NAME')
        if peek(tokens) == 'PLUS':
            return plus(tokens, name)
        else:
            return name
    elif start == 'INTEGER':
        number = match(tokens, 'INTEGER')
        if peek(tokens) == 'PLUS':
            return plus(tokens, number)
        else:
            return number
    else:
        assert False, "Синтаксическая ошибка %r" % start

def plus(tokens, left):
    """plus = expression PLUS expression"""
    match(tokens, 'PLUS')
    right = expression(tokens)
    return {'type': 'PLUS', 'left': left, 'right': right}


def main(tokens):
    results = []
    while tokens:
        results.append(root(tokens))
    return results
```parsed = main(scan(code))
pprint(parsed)

```markdown
## Упражнение

Ваш следующий вызов состоит в том, чтобы объединить ваш класс `Scanner` с новым классом `Parser`, который вы напишете. Вы должны будете расширить его и переопределить, чтобы создать простой парсер. Ваш базовый класс `Parser` должен:

+ принимать объект класса `Scanner` и выполнять себя. Вы можете предположить, что любая функция по умолчанию является началом грамматики.
+ иметь код обработки ошибок, более продвинутый, чем моя простая проверка `assert`.

Вы должны реализовать `PunyPythonPython`, который может анализировать этот мини-язык Python и выполнять следующие действия:

+ вместо того, чтобы просто создавать список словарей, вам следует создавать класс для каждого результата грамматического продукта. Эти классы затем становятся объектами в списке.
+ эти классы должны хранить токены, которые были проанализированы, но они также должны быть подготовлены для выполнения большего количества действий.
+ вам нужно анализировать только этот мини-язык, но вы должны попробовать решить проблему отступов в Python. Вам, возможно, придется модифицировать сканнер, чтобы он был более умным, чтобы соответствовать пробелам `INDENT` в начале строки и игнорировать их в других местах. Также вам потребуется отслеживать количество отступов и записывать нулевые отступы, чтобы вы могли "сжать" блоки кода.
```Для универсального набора тестов можно использовать больше образцов этого мини-Python, но сейчас достаточно одного маленького файла для анализа. Попробуйте добиться хорошей покрытия тестами и найти как можно больше ошибок.

## Исследовательское обучение

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

## Глубокое изучение

Просмотрите [генератор парсеров SLY](http://sly.readthedocs.io/en/latest/) Дэвида Бицлея, чтобы узнать, как ваш компьютер может создать ваши парсеры и сканеры (также известные как лексеры) для вас. Вы можете попробовать повторить это упражнение с помощью SLY для сравнения.