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