Что это
Не будем разбирать что такое парсер, но в целом это код, который разбирает ваш текст на структуру из массивов и обьектов (ключ-значение) или на классы с наследованием. Соответственно я создаю программу, которая генерирует такой код автоматически на основе грамматики (что когда в тексте должно встречаться).
Зачем
Хочеться иметь парсер генератор с максимальной гибкостью да бы в большинстве случаях не пришлось писать парсер вручную. Моя цель - сделать инструмент, который автоматизирует эту работу, сохраняя удобство, мощь и скорость разработки
Преимущества
Этот парсер генератор имеет следующие преимущества (не всё реализовано, но многое уже работает).
Поддержка нескольких видов парсеров (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.