Я вже давно хотів спробувати написати щось з допомогою алгоритму рекурсивного спуску.

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

Задача: парсинг bencode.

Бенкодування

Бенкод має лише чотири типи (пробіли лише для читача):

цілочислене i42e
стрічка 5:hello
список l i1e e
словник d 5:hello 5:world e

Спочатку я писав парсер намагаючись відтворити правила побудови значень прямо з наведених прикладів. В результаті мені довелося писати стек, бо визначення рекурсивні. Наприклад список може містити інші типи, тому треба зберігати коли почався список, а на його завершення ще й оновлювати його байтову довжину, але це тільки якщо треба байтові позиції токенів. Хоч після того як я витратив багато часу на відлагодження воно працювало правильно, я не був задоволений кодом. Особливо тим що стек містив посилання на елементи бо їх треба оновлювати, записуючи в них байтову довжину після завершення парсингу.

Граматика

Перше з чого я буду тепер починати писати будь-який парсер це EBNF (Розширена нотація Бекуса — Наура). Дотримуватися правил запису цієї нотації не так важливо, особливо якщо код не буде автозгенерованим з цих правил. Я замінив деякі визначення на більш інтуїтивні, узявши зрозумілі всім *, [0-9], + з регулярних виразів.

any        = integer | string | list | dictionary
integer    = i [0-9]+ e
string     = [0-9]+ : .*
list       = l <any>* e
dictionary = d (<string> <any>)* e

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

Цілочисленні повинні відповідати шаблону: спочатку літерал i потім цифра від 0 до 9, але мінімум один раз, завершуючим має бути літерал e. Я думаю використання синтаксису регулярних виразів спрощує розуміння, бо для більшості людей у цьому нема нічого нового!

У випадку стрічки, її значення може складатися з нуля символів, а тому використання *.

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

Грамматика допомагає писати код

Рекурсивний спуск пропонує визначити на кожен термін з граматики функцію що буде відповідальна за парсинг своєї частини. Мета кожної функції це парсинг лише свого типу, делегуючи роботу взаємно рекурсивним викликом інших функцій. Отже для any це

type Parser struct {
	input  []byte
	offset int
}

func NewParser(input []byte) *Parser {
	return &Parser{
		input:  input,
		offset: 0,
	}
}

func (p *Parser) ParseAny() (any, error) {
	if p.offset >= len(p.input) {
		return nil, io.ErrUnexpectedEOF
	}

	integer, err := p.parseInteger()
	if err == nil {
		return integer, nil
	}

	string, err := p.parseString()
	if err == nil {
		return string, nil
	}

	list, err := p.parseList()
	if err == nil {
		return list, nil
	}

	dictionary, err := p.parseDictionary()
	if err == nil {
		return dictionary, nil
	}

	return nil, fmt.Errorf("could not parse any value: %s", p.input[p.offset:])
}

Попередження

Перше що я бачу в цьому коді це те, що він намагається спарсити значення чотири рази, й тільки потім повідомить про проблему. Обговоримо оптимізацію пізніше.

Код вище працює відповідно правилу any, хоча | досягається шляхом перебору, це цілком непоганий підхід. Уже зараз можна дійти висновку – у цьому випадку рекурсивний парсинг автоматично обробляє відкриваючі й закриваючі теги. Рекурсивні алгоритми елегантні!

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

func (p *Parser) parseInteger() (int64, error) {
	if p.input[p.offset] != 'i' {
		return -1, fmt.Errorf("expected 'i' got %v", p.input[p.offset])
	}

	// ...
}

Першим іде перевірка типу, іншими словами продовжуємо слідувати правилам граматики. Тут можна замінити динамічну помилку на типізовану, щоб у ParseAny можна було розрізнити коли тег не співпав з типом, а коли ми почали парсити, але щось пішло не так.

func (p *Parser) parseInteger() (int64, error) {
	// ...

	integerStr := p.input[p.offset+1:][:closingIndex]

	integer, err := strconv.ParseInt(string(integerStr), 10, 64)
	if err != nil {
		return -1, fmt.Errorf("parse integer: %w", err)
	}

	p.offset += len(integerStr) + 2

	return integer, nil
}

Тут нічого особливого. Зауважу патерн p.input[p.offset+1:][:closingIndex]. Щоб не повторювати p.offset+1 додаючи його до closingIndex, можна слайснути результат першого слайсу. Із важливого тут ще те що p.offset змінюється лише коли далі вже не буде помилок.

func (p *Parser) parseString() (string, error) {
	marker := p.input[p.offset]
	if marker < '0' || marker > '9' {
		return "", fmt.Errorf("expected ascii digit but got %v", marker)
	}

	lenEndIndex := bytes.IndexByte(p.input[p.offset+1:], ':')
	if lenEndIndex < 0 {
		return "", errors.New("could not find end of a string length")
	}

	stringLengthStr := p.input[p.offset:][:lenEndIndex+1]

	length, err := strconv.ParseInt(string(stringLengthStr), 10, 64)
	if err != nil {
		return "", fmt.Errorf("parse string length: %w", err)
	}

	str := p.input[p.offset+len(stringLengthStr)+1:][:length]

	p.offset += len(stringLengthStr) + 1 + int(length)

	return string(str), nil
}

Знову метод парсингу повертає конкретний тип і помилку. Перевірка тегу трохи більш проблемна, нічого критичного. Як тільки перші байти виглядають цифрами можна шукати двокрапку – роздільник довжини стрічки й її значення. Тут уже треба бути уважними з додаванням довжин, можна легко зробити помилку.

func (p *Parser) parseList() ([]any, error) {
	if p.input[p.offset] != 'l' {
		return nil, fmt.Errorf("expected 'l' but got %v", p.input[p.offset])
	}

	p.offset += 1
	// ...
}

Підвищуємо складність імлементуючи парсинг списку. Копіюємо перевірку тегу, але далі ParseAny не буде працювати без зміни зміщення. ParseAny перевіряє те на що зараз показує p.offset, тому змінюємо позицію на один, іншими словами зміщення тепер показує на перший елемент або кінець списку.

func (p *Parser) parseList() ([]any, error) {
	// ...

	var list []any
	for {
		item, err := p.ParseAny()
		if err != nil {
			// TODO
		}

		list = append(list, item)
	}

	p.offset += 1

	return list, nil
}

Трохи є коду. Так як кількість елементів списку завчасно невідома, використовуємо нескінченний цикл. Елементом списку може бути any – викликаємо p.ParseAny() у циклі. Виникає питання, а як зупинитися після останнього елемента?

func (p *Parser) parseList() ([]any, error) {
	// ...
loop:
	for {
		item, err := p.ParseAny()
		if err != nil {
			switch {
			case p.input[p.offset] == 'e':
				break loop
			default:
				return nil, err
			}
		}

		// ...
	}

	// ...
}

Один з варіантів це перевірити поточнє зміщення p.offset, якщо це символ кінця то можна вважати парсинг елементів списку завершеним. Але краще створити тип помилку type TokenErr struct{Token byte} і використати його в співставленні помилок з допомогою errors.As.

Парсинг словника дуже схожий на інші типи. Перевірка тегу, у нескінченному циклі спроба парсити стрічковий ключ, а потім і значення. Відмінність полягає в тому що на стадії парсингу ключа цикл може закінчитися, а якщо помилка значення – повернути помилку.

Fi

any        = (i <integer>) | ([0-9] <string>) | (l <list>) | (d <dictionary>)
integer    = [0-9]+ e
string     = [0-9]+ : .* // або [0-9]* : .*
list       = <any>* e
dictionary = (<string> <any>)* e

Як щодо таких правил? Тепер any знає з якого тега починається кожний тип і тому можна перестати перебирати всі типи підряд. Хоча тут уже треба більше кмітливості. Чи буде any поглинати перший символ зі вхідних байтів? Якщо ні то кожна інша функція повинна відповідно першою лінією збільшувати зміщення p.offset += 1, але у випадку стрічки цього навпаки не треба робити.

Повний код

package recdes

import (
	"bytes"
	"errors"
	"fmt"
	"io"
	"strconv"
)

type Parser struct {
	input  []byte
	offset int
}

func NewParser(input []byte) *Parser {
	return &Parser{
		input:  input,
		offset: 0,
	}
}

func (p *Parser) ParseAny() (any, error) {
	if p.offset >= len(p.input) {
		return nil, io.ErrUnexpectedEOF
	}

	integer, err := p.parseInteger()
	if err == nil {
		return integer, nil
	}

	string, err := p.parseString()
	if err == nil {
		return string, nil
	}

	list, err := p.parseList()
	if err == nil {
		return list, nil
	}

	dictionary, err := p.parseDictionary()
	if err == nil {
		return dictionary, nil
	}

	return nil, fmt.Errorf("could not parse any value: %s", p.input[p.offset:])
}

func (p *Parser) parseInteger() (int64, error) {
	if p.input[p.offset] != 'i' {
		return -1, fmt.Errorf("expected 'i' got %v", p.input[p.offset])
	}

	closingIndex := bytes.IndexByte(p.input[p.offset+1:], 'e')
	if closingIndex < 0 {
		return -1, errors.New("could not find end of an integer")
	}

	integerStr := p.input[p.offset+1:][:closingIndex]

	integer, err := strconv.ParseInt(string(integerStr), 10, 64)
	if err != nil {
		return -1, fmt.Errorf("parse integer: %w", err)
	}

	p.offset += len(integerStr) + 2

	return integer, nil
}

func (p *Parser) parseString() (string, error) {
	marker := p.input[p.offset]
	if marker < '0' || marker > '9' {
		return "", fmt.Errorf("expected ascii digit but got %v", marker)
	}

	lenEndIndex := bytes.IndexByte(p.input[p.offset+1:], ':')
	if lenEndIndex < 0 {
		return "", errors.New("could not find end of a string length")
	}

	stringLengthStr := p.input[p.offset:][:lenEndIndex+1]

	length, err := strconv.ParseInt(string(stringLengthStr), 10, 64)
	if err != nil {
		return "", fmt.Errorf("parse string length: %w", err)
	}

	str := p.input[p.offset+len(stringLengthStr)+1:][:length]

	p.offset += len(stringLengthStr) + 1 + int(length)

	return string(str), nil
}

func (p *Parser) parseList() ([]any, error) {
	if p.input[p.offset] != 'l' {
		return nil, fmt.Errorf("expected 'l' but got %v", p.input[p.offset])
	}

	p.offset += 1

	var list []any
loop:
	for {
		item, err := p.ParseAny()
		if err != nil {
			switch {
			case p.input[p.offset] == 'e':
				break loop
			default:
				return nil, err
			}
		}

		list = append(list, item)
	}

	p.offset += 1

	return list, nil
}

func (p *Parser) parseDictionary() (map[string]any, error) {
	if p.input[p.offset] != 'd' {
		return nil, fmt.Errorf("expected 'd' but got %v", p.input[p.offset])
	}

	p.offset += 1

	dict := make(map[string]any)
loop:
	for {
		key, err := p.parseString()
		if err != nil {
			switch {
			case p.input[p.offset] == 'e':
				break loop
			default:
				return nil, err
			}
		}

		value, err := p.ParseAny()
		if err != nil {
			return nil, err
		}

		dict[key] = value
	}

	if p.input[p.offset] != 'e' {
		return nil, fmt.Errorf("expected 'e' but got %v", p.input[p.offset])
	}

	p.offset += 1

	return dict, nil
}

Сайт Данила

Парсер з рекурсивним спуском у Go

Бенкодування

Граматика

Грамматика допомагає писати код

Попередження

Fi