ISPA Parser Generator / forpes.ru

Главная
ISPA Parser Generator

ISPA Parser Generator +3

28.06.2025 09:17

Yuriy200 20 569 Источник

Что это

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

Зачем

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

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

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

Поддержка нескольких видов парсеров (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.

Комментарии (20)

Adler3D
29.06.2025 08:28
#28500696
Сравните пожалуйста с QapDSL на примере парсинага

"if(some_expr){some_stat();}else{some_stat2();}".

Мой вариант можно найти в комментарии:

https://habr.com/ru/articles/916006/#comment_28403544
1. Yuriy200 Автор
  29.06.2025 08:28
  #28501314
  с QapDSL я не знаком совсем, но по тому, что я вижу могу сказать следующее:
  он достаточно низкоуровневый по сравнению с EBNF. Пример правила в ispa:
  
  condition: // name "if" for rule is prohibited 'if' '(' @ expr ')' @ stmt 'else' @ stmt @{expression, true_stmt, false_stmt} ; expr: logical #logical: @ compare (@ LOGICAL_OP @ compare)* @{left, op, right} ; #compare: @ arithmetic (@ COMPARE_OP @ arithmetic)* @{first, operators, sequence} ; // ... see https://github.com/Sinfolke/ispa-parser/blob/main/parser/parser/cll.isc #value: @ group | _variable | function_call | method_call | rvalue {@} ; ; stmt: ( '{' @ #value '}' ) | @ #value {@} #value: // here what stmt could contain ; ;
  
  Похоже на ANTRL.
  
  Этот парсер генератор может генерировать LR парсеры. Конструкция дерева может не отличаться с LL парсером как только я реализую PLL алгоритм (мой собственный алгоритм который добавляет левую рекурсию в LL парсерах)
  
  Все достаточно абстрактно, хотя вообще вы можете матчить текст самостоятельно в СLL. Достаточно просто добавить для этого возможность читать текущий символ и токен. То-есть абстракция есть, но можно делать что-то специфичное если нужно. Именно поэтому я хочу сделать возможность создавать свое дерево на конкретном языке (пункт 3 в посте).
  
  В QapDSL похоже нету токенизации
  
  ISPA как отдельный язык, в то время как QapDSL больше похож на утилиту для существующего языка
  
  ISPA пока что поддерживает только C++, но его архитектура позволяет генерацию на несколько языков.
  
  QapDSL как ассемблер, гибкий, низкоуровневый, но из-за этого сложный.
  
  Bison как C с инлайн ассемблером - декларативный, с возможностью низкоуровневого контроля
  
  ISPA, ANTRL как C++ - высокоуровневые, удобные, но не теряющие контроль
  1. Adler3D
    29.06.2025 08:28
    #28501730
    мне вот EBNF/BNF и подобное не нравиться из-за того что AST приходиться делать отдельно, если я ничего не путаю.
    
    QapDSL как ассемблер, гибкий, низкоуровневый, но из-за этого сложный.
    
    я уже поработал над этим и теперь в QapDSL v2 описание стало в два раза короче. осталось только написать статью про это.
    
    вот как парсин условий выглядит в новой версии:
    
    t_if_body_one=>i_if_body{ TAutoPtr<i_stat> stat; } t_if_body_two=>i_if_body{ t_block_stat bef; "else" TAutoPtr<i_stat> aft; } t_if_stat=>i_stat{ "if(" TAutoPtr<i_expr> cond; ")" TAutoPtr<i_if_body> body; }
    
    как вам такой новый синтаксис? неужели всё ещё сложно?
    
    Yuriy200 Автор
    29.06.2025 08:28
    #28501840
    Сам принцип парсера - низкоуровненове взаимодействие (низкоуровневое в нашем случае будет означать прямое обьявление переменных, условий и т.д). ISPA парсер даёт этому абстракцию давая добавлять низкоуровневые елементы только когда это необходимо. Именно в этом и преимущество. Это не значит, что какой-то из вариантов лучше, просто каждый подходит больше под свою задачу. Например QapDSL лучше подходит для парсинга JSON, XML, INI, где прямое взаимодействие обычно необходимо, а EBNF для новых языков или других комплексных текстов.
    
    Насчет самостотельного создания дерева, это правда для ANTRL, но не для ISPA. В ISPA вы просто выделяете что захватить, а далее определяете каким типом данных оно будет (int, bool, string, array, object) и что из захваченного туда поместить. Хотя можно и редактировать данные перед созданием дерева посредством CLL.
    
    Ещё одна важная проблема для парсер генераторов это ошибки. Я стараюсь её решить посредством fail блоков. В QapDSL это опять же низкоуровневое (что вообще может быть и отлично)
    
    В целом QapDSL имеет смысл и вам нужно над этим работать.
    
    Adler3D
    29.06.2025 08:28
    #28502048
    В ISPA вы просто выделяете что захватить, а далее определяете каким типом данных оно будет (int, bool, string, array, object) и что из захваченного туда поместить
    
    Если я правильно понял то тогда у вас при обходе получившегося AST придётся вручную определять типы лексем(обычного разделения типов на array/object недостаточно) и имена полей/узлов по содержимому и его положения в дереве. А это всё лишняя работа, которую можно автоматизировать и потом наслаждаться всеми удобствами(посетителями/интерпретаторами/строителями) при обходе дерева. Не понимаю как от этого можно отказаться и ради собственно чего. Или я чего-то не замечаю, вроде скорости парсинга и компактности реализации? Кстати как у вас дела с исходниками генератора? У меня например всё open source.
    
    Yuriy200 Автор
    29.06.2025 08:28
    #28503122
    Да, думаю переходить с этой структуры на другую (основанную на std::variant и структурах для каждого правила/токена) или возможно полностью на структуру из классов но она вроде бы считаеться устаревшой.
    Вообще в своем проекте я сделал TreeAPI (сейчас AST.API), который определяет дерево в удобной, фиксированной структуре, которая не будет изменяться и конвертирует дерево из парсера в эту структуру. Это даёт возможность редактировать вывод дерева парсера с минимальными затратами т.к таких изменений будет много в будущем
    
    У меня все также open source, проект на C++20/C++23 с использованием модулей
    
    Adler3D
    29.06.2025 08:28
    #28504222
    struct Array { stdu::vector<CllExpr> value; private: friend struct ::uhash; auto members() const { return std::tie(value); } }; struct Object { std::unordered_map<std::string, CllExpr> value; private: friend struct ::uhash; auto members() const { return std::tie(value); } };
    
    Вот тут у вас опять всё упрётся в неправильную архитектуру AST, т.к далее вы заворачиваете это в rvalue, а затем в CllExprValue. В итоге у вас будет только один вид объектов - Object и один вид массивов - Array. И если я всё правильно понял, и нигде не ошибся, то тогда вам(или пользователям вашего генератора парсеров) придётся всё равно вручную преобразовывать Object`ы в пользовательские типы объектов. А в QapDSL все пользовательские типы пробрасываются прямиком в С++ со всеми полями и даже с пользовательским кодом(последнее я не очень приветствую). Могу помочь переписать парсер вашего DSL на QapDSL v2 если вам интересно. QapDSL v2 уже почти полностью(95%) переписан/описан на QapDSL v2 и похоже может использоваться для чего угодно.
    
    Yuriy200 Автор
    29.06.2025 08:28
    #28504532
    Мой парсер генератор использует также структуры а не обьекты если только пользователь самостоятельно не создаст обьект как тип данных:
    
    some_rule: @ key ';' @ value $obj<str, var> obj; $obj[@] = @; {obj} ;
    
    Если сохранить это следующим образом то будет структура:
    
    some_rule: @ key ';' @ value @{key, value} ;
    
    То-есть это создаёт структуру:
    
    { a: a b: b }
    
    Это создает обьект:
    
    obj<str, str> obj {obj}
    
    Переписывать мой парсер на QapDSL мне не поможет т.к я уже успешно сделал bootstrap своей грамматики.
    
    Adler3D
    29.06.2025 08:28
    #28505212
    плохо понимаю что у вас происходит в коде, но я попробовал перевести некоторые штуки на QapDSL v2:
    
    t_group:i_val{ '(' vector<t_member> members; ')' t_ast_node make_ast_node(){return ast_node(members);} } t_keyvalue:i_prefix{...} t_value:i_prefix{...} emit_polymorphic_type_foreach_pice( arr=split("name | CSEQUENCE | STRING | HEX | BIN | NOSPACE | ESCAPED | DOT | OP | LINEAR_COMMENT | cll"," | "), parent="i_val" ); t_member{ TAutoPtr<i_prefix> prefix?; " "? TAutoPtr<i_val> val; " "? t_quantifier quantifier?; " "? t_ast_node make_ast_node(){return ast_node({make_ast_node(prefix),make_ast_node(val),make_ast_node(quantifier)});} }
    
    не знаю насколько правильно я понял как у вас храниться AST.
    
    Yuriy200 Автор
    29.06.2025 08:28
    #28505334
    AST храниться с помощью структуры node (уже считаю устаревшим). Состоит из информации о позиции в тексте и std::any data. Этот дата хранит саму информацию правила, что обычно или структура или прямой тип данных. Сами типы находяться здесь.
    
    Adler3D
    29.06.2025 08:28
    #28505430
    что обычно или структура или прямой тип данных
    
    ну тогда ваш генератор парсеров пока круче моего по количеству фич и мало в чём ему уступает, если вообще уступает хоть в чём-то.
    
    могу посоветовать в следующей статье про ваши проекты указывать все 5 возможных хабов, так будет больше просмотров. а эту статью уже не спасти, слишком старая для таких оптимизаций просмотров.
    
    Yuriy200 Автор
    29.06.2025 08:28
    #28506424
    Спасибо, мы кстати можем работать над этим генератором вместе. Мне хотелось бы найти команду т.к проект стает достаточно большим для реализации в одиночку. Тем не менее ваш генератор по описанию не плох как я упоминал для JSON, XML. Если бы мне нужно было парсить эти структуры, я бы либо писал парсер вручную либо использовал подобный вашему генератор.
    
    Я думаю в следующей статье описать СLL подробно, укажу больше хабов (думал в начале здесь как на редите нельзя постить если пост не подходит под тему поэтому указал только подходящие хабы)
    
    Adler3D
    29.06.2025 08:28
    #28507396
    ваш генератор по описанию не плох как я упоминал для JSON, XML
    
    с XML у меня проблемы - там есть тэги которые не закрываются из-за дизайна/ошибок, это приводит к тому что максимум что можно - это разбить всё на токены/плоские_лексемы. дерево построить очень сильно как не всегда получается. с JSON дела получше, но скорость парсинга пока конечно не такая крутая как у заточенных под это дело монстров подобных rapidjson.
    
    я бы либо писал парсер вручную либо использовал подобный вашему генератор
    
    а почему не своим собственным генератором? у вас же всё должно быть круто с производительностью, не понимаю.
    
    мы кстати можем работать над этим генератором вместе. Мне хотелось бы найти команду т.к проект стает достаточно большим для реализации в одиночку.
    
    интересно, но я не представляю чем могу помочь. показать как круто можно обходить строго типизированное AST? это можно посмотреть прямо сейчас в моих исходниках. могу даже дать прямую ссылку на QapGen:
    
    https://github.com/adler3d/QapGen/blob/33349ad9b14e3230e8bd7dab0df7174f4aa9fcb5/src/QapGenV2025/QapGen/visitor_gen.h#L344
    
    вот от этой строки и дальше вся круто-та: посетители/строители/интерпретаторы в одном месте строят интерпретируют и посещают строго типизированное дерево. с небольшими костылями(для нескольких разнотипных обходов), но всё работает.
    
    описывать ваш DSL на QapDSL v2 вам не очень интересно, как я понял. что ещё остаётся?
    
    Yuriy200 Автор
    29.06.2025 08:28
    #28507500
    Мой генератор делает токенизацию, что в этом случае не всегда еффективно. Прямой матчинг может быть лучше чем использование DFA таблиц. Низкоуровневый контроль часто необходим чтобы построить лучшее дерево. А так да, можно
    
    Помочь мне можно именно с backend, frontend уже сделан. Но для этого нужно разбирать мой код. Поэтому я просто предлагаю)
    
    Yuriy200 Автор
    29.06.2025 08:28
    #28507526
    можете еще кстати почитать недавно опубликованную статью о CLL

Adler3D
29.06.2025 08:28
#28504172
а я правильно понимаю что вот это(это генерированный код вашим же генератором парсеров, если да то скажите сколько на это тратиться времени): https://github.com/Sinfolke/ispa-parser/blob/main/parser/Parser.cpp
1. Yuriy200 Автор
  29.06.2025 08:28
  #28504556
  Это старая реализация, но сгенерированная этим парсером и сейчас используеться для парсинга грамматики. Новая реализация использует DFA для лексера и парсера в месте опциональных правил
  
  Parser.h
  
  Parser.cpp
1. Yuriy200 Автор
  29.06.2025 08:28
  #28504918
  на генерацию старой версии уходило около 700 мс, на генерацию новой версии около 1с
  1. Adler3D
    29.06.2025 08:28
    #28505120
    крутой у вас генератор, таблицы переходов, круто всё. я до такой оптимизации ещё не дошёл. у меня пока генератор простой и со своей грамматикой справляется за 143.02 ms. выхлоп 5700 строк С++ кода(197kb). вот он:
    
    https://github.com/adler3d/QapGen/blob/master/src/QapGenV2025/QapGen/meta_lexer.inl
    
    а вот исходник(749 строк и 12.4кб):
    
    https://github.com/adler3d/QapGen/blob/22004f97ba6136d85ad4a13dcd099402311fe1af/src/QapGenV2025/Release/input.qapdsl.hpp#L270
    
    Yuriy200 Автор
    29.06.2025 08:28
    #28505288
    Вывод достаточно сложный, полный макросов, но ок для авто генерированного кода. Сам DSL я тоже не понимаю :)

ISPA Parser Generator +3

Что это

Зачем

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

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

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

CLL

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

Modifiers

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

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

Комментарии (20)

Yuriy200 Автор

Yuriy200 Автор

Yuriy200 Автор

Yuriy200 Автор

Yuriy200 Автор

Yuriy200 Автор

Yuriy200 Автор

Yuriy200 Автор

Yuriy200 Автор

Yuriy200 Автор

Yuriy200 Автор