Что это

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

Зачем

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

Преимущества

Этот парсер генератор имеет следующие преимущества (не всё реализовано, но многое уже работает).

Поддержка нескольких видов парсеров (LL(*), LR(1), LALR, LR(*)). Сейчас я работаю над LL(*) парсером, LR и т.д реализованы, прошли тесты, но не готовы для полного использования т.к. требуют доработки.
Поддержка нескольких языков. Пока что только С++, как только все реализую планирую TypeScript и Python.
Полная, автоматическая конструкция AST + возможность определить специфичную для языка структуру (только автоматическая конструкция AST реализована).
CLL (Common Language Logic) - общая логика языка, дает возможность вставлять в парсер семантические действия при этом не делая парсер генерируемым на конкретный язык. Она более абстрактная ну и вообще синтаксически красивее. Сейчас больше реализовано теоретически чем практически (осталось протестировать ну и готово).
Вложенные правила, инкапсуляция. Можно определять правило (или токен) внутри другого правила (или токена). Полностью реализовано.
Встроенная библиотека, шаблоны, наследование. Почему я всё перечислил в одном пункте? Потому-что шаблоны и наследование сделаны только для создания стандартной библиотеки (или даже сторонних библиотек). Суть шаблонов в том, что можно определить имя и место него позже подставить какое-нибуть правило или токен. Что вобщем то присутствует во многих языках. Суть наследвствия в том, что можно видоизменить уже существующее правило. Вспомните наследствие классов, это похожая штука. Таким образом можно спокойно создавать парсинг библиотеки. Пока-что ничто из этого не реализовано.
Context Sensitive Lexing - Работаю над этим. Вообще лексинг использует DFA, и этот генератор тоже, но может генерировать Advanced DFA (я так назвал), что дает возможность добавлять функции или ссылки на другие DFA. То-есть оптимизация на высоком уровне, возможности не ограничены. Сейчас реализованно на где-то 70%, а завтра уже может быть сделано). Видел человек упоминал это в посте Почему я не использую парсер генераторы.
Modifiers - по сути возможность обозначить правило как inline - не создавать для правила отдельную структуру, а все его данные напрямую вставить при ссылке на него или skip - пропускать токен если он встречается. Позже могут быть другие modifiers.
Автоматические токены - много генераторов делают автоматические токены если они встречаются в правиле. Этот тоже.
Возможность добавлять правила восстановления при ошибках и делать кастомные сообщения ошибок (реализован только IR)
Автоматический пропуск пробелов.

Как выглядит "real world" правило

rule:
    @ ID ':' @ #member+ @ #data_block? @ #nested_rule* ';'

    @{ name, rule, data_block, nested_rules }

    #member:

        @(keyvalue | value)? @ name | group | CSEQUENCE | STRING | HEX | BIN | NOSPACE | ESCAPED | DOT | OP | LINEAR_COMMENT | cll @ quantifier?

        @{ prefix, val, quantifier }
    ;
    #name:
        @ '#'? @ ID (DOT @ ID)*

        @{ is_nested, name, nested_name }
    ;
    #group:
        '(' @ member* ')'

        {@}
    ;
    #keyvalue:
        AT (\s0 @ ID)?
        {@}
    ;
    #value:
        '&' @ ID
        {@}
    ;
    #nested_rule: 
        '#' \s0 @ rule
        {@}
    ;
    #data_block:
        @ #templated_datablock | #regular_datablock
        {@}
        #regular_datablock:
            '{' @ cll.expr | #key+ '}'
            {@}
            #key:
                @ ID '=' @ cll.expr
                @{name, dt}
            ;
        ;
        #templated_datablock:
            AT '{' (@ ID (',' @ ID)*)? '}'
            @{ first_name, second_name }
        ;
    ;
    #OP:
        '|'
    ;
    #quantifier:
        @ QUESTION_MARK | PLUS | MULTIPLE
        {@}
    ;

    #CSEQUENCE:
        '[' @ '^'? @ ( #DIAPASON | #ESCAPE | #SYMBOL )* ']'
        @{_not, val}
        #SYMBOL:
            @ '\\' | [^\]]
            {@}
        ;
        #ESCAPE:
            '\\' \s0 @ .
            {@}
        ;
        #DIAPASON:
            ( @ SYMBOL \s0 '-' \s0 @ SYMBOL)
            @{from, to}
        ;
    ;
    #NOSPACE:
        '\\s0'
    ;
    #ESCAPED:
        '\\' \s0 @ . \s0
        {@}
    ;
    #HEX:
        '0x' @[0-9A-Fa-f]+
        {@}
    ;
    #BIN:
        '0b' @[01]+
        {@}
    ;
;

Это и другие правила можно найти здесь. Удивительно, но большую часть занимает СLL.

Это граматика правила или токена.
rule: - обьявление правила rule
@ - обозначение, что это нужно добавить в AST
ID - ссылка на другое правило. По сути это правило должно встречаться в текущем правиле
#member - ссылка на вложенное правило текущего правила. Для вложенных правил вложенного правила другие вложенные правила стают глобальными. Да, звучит сложно. По сути для СSEQUENCE #memb

er уже глобальный и # перед вызовом не требуеться
?, +, \* - quantifiers. ? означает найти 0 или 1 раз, + означает найти 1+ раз, \* означает найти 0+ раз
';' - "здесь должна быть эта строка"
() - группа. К группе также можно применять ?, +, \*
| - найти один из вариантов
Много из этого чистый regex.
\s0 - специальная конструкция означающая не пропускать здесь пробел

Конструкция AST

Часть правила можно сохранить в переменную, которую потом можно задействовать в СLL или для построения финальной структуры. Создания части дерева выглядит так:
@{key1, key2} сокращение для { key1: @ key2: @ }
1. Для сохранения значения можно напрямую определить ключ посредством @Name. Если вы хотите дать имя ключу ниже, то оставляете просто @ (с пробелом обязательно если следующей идет ссылка на другое правило).
2. Для построения дерева (если не дали имя ключу при присвоении значения) используеться конструкция
@{a, b, c} если все что вам нужно - присвоить имена сохраненным значениям
{ a: 1 + b c: d }
если вы хотите настроить ключи с выражением СLL.
{<выражение>} - если значение только одно и вам не нужно создавать структуру ключ-значение. Например {@}, или {a + 1}

Подробное обьяснение как определить и использовать кастомную структуру могу описать в следующем посте если вам будет интересно

CLL

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

rule:
  $var a = 10;
  $var b = 20;
  $if (a + b == 30) {
    some_rule 
  }
  {
    a: a
    b: b
  }

Это не практичный пример, т.к. СLL в своей грамматике не применял. Но вообще штука очень полезная, особенно для парсинга зависимых от контекста языков как С++.

Шаблоны, унаследования

Планирую сделать что-то типа такого:

json<NUMBER, STRING, ARRAY, OBJECT>:  NUMBER | STRING | ARRAY | OBJECT;

NUMBER: [0-9]+
// ...
// вызов этого правила
my_json = json<NUMBER, STRING, ARRAY, OBJECT>;
some_rule: my_json;

Унаследование смотрите в этом файле (не забудьте переводчик ;) ). Единственное что синтаксис унаследования будет использовать -> а не ':'

Modifiers

[inline]
expr: 
  NUMBER '+' NUMBER
;

[skip]
WHITESPACE: [ ]+;

Восстановление при ошибках

function_body:
  '(' ID %cf (',' ID)* ')'

  fail cf(comma, identifier) {
    if (identifier == ')') {
        rethrow "Trailing comma"
    } else {
        rethrow "Parameter name expected"
    }
  }
;

С помощью % выделяеться место, для которого создаються кастомные ошибки. Далее fail блок. Состоит из fail <имя> (параметры) { инструкции }.
Параметры - это все символы которые находяться в группе которую вы выделили. Если это не группа, то можно обьявить не больше одного параметра. Инструкции это соответственно логика для вывода кастомных ошибок и восстановления

Подсуммирование

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

Если тебе интересно присоединиться к разработке и внести свой вклад — буду рад сотрудничеству. Пиши или открывай issue на GitHub. Собственно github.

ISPA Parser Generator