Парсеры Пратта для чайников27.03.2020 15:48

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

Картину портят выражения: постфиксные, инфиксные и прочие. Проблема: вы не можете понять, какого типа выражение вы обрабатываете до тех пор, пока не разберёте его первую половину. Зачастую для вас также важны приоритет операции и её ассоциативность, чтобы построенное AST имело правильную структуру.

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

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

giegjidcnqpsbkpiwlbrj9evce4.png


Go++ и ++Go

Чтобы не тратить время на лексический анализ, мы возьмём всё нужное из стандартной библиотеки:


  • go/scanner позволяет получать из текста набор токенов
  • go/token определяет те самые токены, которые нам даёт scanner

Для удобства, мы введём свой тип токена, чтобы не разделять теги и значения: 

type Token struct {
    kind  token.Token
    value string
}

scanner мы обернём в свой тип lexer, в котором будет два основных метода:


  • Peek() — возвращает следующий токен, но не извлекает его из потока
  • Consume() — возвращает следующий токен, извлекая его

Мы не будем использовать пакет go/ast, потому что это уже напрямую относится к парсингу.

Поскольку в Go нет right-associative операторов, в своём диалекте мы определим оператор побитового сдвига влево как таковой.

В настоящем Go инкремент и декремент — это statement, а не expression. Но в нашем диалекте это выражения. Более того, мы также добавим префиксные варианты этих операций.


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


Начнём с простого

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

// exprNode описывает произвольное выражение в AST.
type exprNode interface {
    expr()
}

type nameExpr struct {
    Value string
}

type prefixExpr struct {
    Op  token.Token // Тип операции, например, + или -
    Arg exprNode    // Операнд унарной операции
}

func (e *nameExpr) expr()    {}
func (e *prefixExpr) expr()  {}

Основной метод парсера выражений, parseExpr(), может выглядеть так: 

func (p *exprParser) parseExpr() exprNode {
    tok := p.lexer.Consume()
    switch tok.kind {
    case token.IDENT:
        return p.parseName(tok)
    case token.ADD, token.SUB:
        return p.parsePrefixExpr(tok)
    case token.LPAREN:
        return p.parseParenExpr(tok)
    // ... и так далее
    }
}

func (p *exprParser) parseName(tok Token) exprNode {
    return &nameExpr{Value: tok.value}
}

func (p *exprParser) parsePrefixExpr(tok Token) exprNode {
    arg := p.parseExpr()
    return &prefixExpr{Op: tok.kind, Arg: arg}
}

При такой структуре кода мы рискуем получить спагетти-код когда реализуем все нужные конструкции языка.

Если бы мы могли более декларативно описать отношения токенов и методов их обработки, код стал бы более наглядным. Сделать это можно, поместив методы-обработчики, типа parsePrefixExpr(), в map или прочую структуру, которая позволяет получить по token.Token метод для обработки. Для большей производительности стоит использовать массивы, поскольку часто разнообразие токенов не очень велико, но для простоты реализации мы возьмём map.

Поскольку у всех наших методов одинаковая сигнатура, заведём для них тип prefixParselet: 

type prefixParselet func(Token) exprNode

В сам парсер нужно добавить map[token.Token]prefixParselet. При создании парсера мы инициализируем эту таблицу: 

func newParser() *parser {
    p := &parser{
        prefixParselets: make(map[token.Token]prefixParselet),
    }

    prefixExpr := func(kinds ...token.Token) {
        for _, kind := range kinds {
            p.prefixParselets[kind] = p.parsePrefixExpr
        }
    }

    p.prefixParselets[token.IDENT] = p.parseName
    prefixExpr(token.ADD, token.SUB)

    return p
}

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

func (p *exprParser) parseExpr() exprNode {
  tok := p.lexer.consume()
  prefix, ok := p.prefixParselets[tok.kind]
  if !ok {
    // Parse error: unexpected token
  }
  return prefix(tok)
}


Вы, наверное, заметили, что в примере выше отсутствует обработка ошибок. В целом, я довольно часто использую panic+recover внутри парсеров. На верхнем уровне парсера ловим панику и возвращаем как error. Вы можете возвращать , однако в этом случае код парсера будет более многословным.


Застряв посередине

Попробуем научить парсер работать с инфиксными выражениями, вроде x+y.

Текущая реализация вернёт нам nameExpr{Value:"x"}, остановившись на токене +. Этот токен как раз говорит нам о том, как парсить дальше.

Введём новый тип infixParselet, который отличается от prefixParselet тем, что принимает на вход Expr, идущий перед ним. В случае с x+y это будет x.

type infixParselet func(left exprNode, tok Token) exprNode

Для всех инфиксных парслетов мы заведём отдельную map. Заполняется она аналогичным образом, в конструкторе парсера.

Бинарные операторы, типа + и - будем выражать типом binaryExpr: 

func (p *exprParser) parseBinaryExpr(left exprNode, tok token) exprNode {
    right := p.parseExpr()
    return &binaryExpr{Op: tok.kind, Left: left, Right: right}
}

Добавим в метод parseExpr() использование инфиксных парслетов: 

func (p *exprParser) parseExpr() exprNode {
    tok := p.lexer.Consume()
    prefix, ok := p.prefixParselets[tok.kind]
    if !ok {
        // Parse error: unexpected token
    }
    left := prefix(tok)
    tok = p.lexer.Peek()
    infix, ok := p.infixParselets[tok.kind]
    if !ok {
        return left
    }
    p.lexer.Consume() // Делаем skip/discard для токена
    return infix(left, tok)
}

У этой реализации есть две проблемы:


  1. Все выражения разбираются как право-ассоциативные: x-y-z => x-(y-z)
  2. Все операции имеют одинаковый приоритет: x*y+z => x*(y+z)


Приоритет и ассоциативность операций

Чтобы решить обе проблемы, нам нужно дать парсеру информацию об приоритетах операций.

Делать мы это будем через таблицы token.Token => priority. Эти таблицы можно сделать глобальными и переиспользовать между парсерами, но нам проще разместить их прямо в конструкторе парсера, для локальности кода: 

p.prefixPrecedenceTab = map[token.Token]int{
    token.ADD: 4,
    token.SUB: 4,
}

p.infixPrecedenceTab = map[token.Token]int{
    token.ADD: 2,
    token.SUB: 2,
    token.MUL: 3,
    token.QUO: 3,
    // ... и так далее
}

Метод parseExpr() теперь будет принимать аргумент precedence: 

func (p *exprParser) parseExpr(precedence int) exprNode {
    tok := p.lexer.Consume()
    prefix, ok := p.prefixParselets[tok.kind]
    if !ok {
        // Parse error: unexpected token
    }
    left := prefix(tok)

    for precedence < p.infixPrecedenceTab[p.lexer.Peek().kind] {
        tok := p.lexer.Consume()
        infix := p.infixParselets[tok.kind]
        left = infix(left, tok)
    }

    return left
}

Теперь парсер знает, когда остановиться, а когда продолжать, что позволяет правильно связать итоговое AST.

Каждый парслет теперь должен передать свой precedence (приоритет) при вызове parseExpr(): 

func (p *exprParser) parseBinaryExpr(left exprNode, tok Token) exprNode {
    right := p.parseExpr(p.infixPrecedenceTab[tok.kind])
    return &binaryExpr{Op: tok.kind, Left: left, Right: right}
}

parseBinaryExpr() связывает выражения как лево-ассоциативные. Чтобы разобрать право-ассоциативные выражения, нужно вычесть 1 из приоритета операции: 

func (p *exprParser) rparseBinaryExpr(left exprNode, tok Token) exprNode {
    right := p.parseExpr(p.infixPrecedenceTab[tok.kind] - 1)
    return &binaryExpr{Op: tok.kind, Left: left, Right: right}
}

В начале статьи мы уточнили, что << у нас будет право-ассоциативный, поэтому обрабатываться побитовый сдвиг будет с помощью rparseBinaryExpr().


Добавляем остальные операторы

Вызов функций — это infixParselet, который обрабатывает токен ( и собирает все аргументы через parseExpr(0) до тех пор, пока не найдёт ).

Группирующий оператор (скобочки) — это prefixParselet, который обрабатывает токен ( и единственный аргумент через parseExpr(0), а затем ожидает ).

func (p *exprParser) parseParenExpr(tok Token) exprNode {
    x := p.parseExpr(0)
    p.expect(token.RPAREN)
    return x
}

Постфиксные операции — это infixParselet: 

func (p *exprParser) parsePostfixExpr(left exprNode, tok Token) exprNode {
    return &postfixExpr{Op: tok.kind, Arg: left}
}


Финальные штрихи

Вместо того, чтобы отдельно заполнять таблицу приоритетов, мы можем добавить в каждую helper-функцию внутри конструктора аргумент precedence: 

prefixExpr := func(precedence int, kinds ...token.Token) {
    for _, kind := range kinds {
    p.prefixParselets[kind] = p.parsePrefixExpr
        p.prefixPrecedenceTab[kind] = precedence
    }
}

Это позволит нам сделать инициализацию парсера ещё более наглядной: 

prefixExpr(6,
    token.ADD,
    token.SUB,
    token.INC,
    token.DEC,
)
postfixExpr(7,
    token.INC,
    token.DEC,
)
leftAssocBinaryExpr(3,
    token.ADD,
    token.SUB,
)
leftAssocBinaryExpr(4,
    token.MUL,
    token.QUO,
    token.REM,
)
rightAssocBinaryExpr(3,
    token.SHL,
)

Вместо магических констант можно ввести именованные группы, например, PrecAdd=3, PrecMult=4 и так далее.

Для улучшения производительности стоит уйти от использования map.

Чтобы сделать создание парсера менее дорогой операцией, стоит инициализировать «грамматику» один раз, а потом передавать её в newParser входным аргументом. Вам придётся переделать сигнатуры prefixParselet и infixParslet так, чтобы они принимали один дополнительный аргумент — *exprParser.

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


Заключение

Изначально эта статья планировалась как перевод Pratt Parsers: Expression Parsing Made Easy (Bob Nystrom). Но в ходе написания я в нескольких местах изменил структуру материала, переписал все примеры, расширил концовку и стало не очень очевидно, насколько это перевод, а не «материал, основанный на».

Я очень рекомендую почитать оригинал, если вы владеете английским. Язык повествования там гораздо лучше, а ещё есть красивое введение, которое я почти полностью вырезал из-за прагматичной направленности текущей статьи.

Весь код можно найти в репозитории github.com/quasilyte/pratt-parsers-go.

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


Похожие статьи на хабре:


© Habrahabr.ru