Комментарии 5

Если есть сложности с ANTLR, возможно вам проще сделать парсер вручную с простым рекурсивным спуском, без разделения на лексер и парсер? У меня про это есть статья, это не так уж сложно, пример про Heredoc как раз есть в статье. Можно сделать либо универсальный парсер, который будет парсить любую грамматику, но медленно, либо генератор парсера для конкретной грамматики, это работает довольно быстро.

Мой коллега для этого использует javacc, там файл грамматики как бы смешан с джава-кодом, в чем есть как минусы (не такое красивое разделение, как в ANTLR), так и плюсы (гибкость, и, если все сделать правильно, производительность)

Для их построения мы пользуемся оптимизированной версией ANTLR4

По факту оптимизированный рантайм оказался тыквой.


Например, с левой рекурсией он справляется намного хуже стандартного. Я создал репозиторий AntlrBenchmarks специально для того, чтобы тестировать производительность различных рантаймов.


Работа еще не закончена, но вот что уже получается для леворекурсивных и нелеворекурсивных правил (LeftRecursionGrammar.g4) на стандартном и оптимизированном рантаймах (писал уже об этом в компиляторном Telegram чате):


|               Method | Mode |   Runtime |       Mean |    Error |   StdDev | Ratio |
|--------------------- |----- |---------- |-----------:|---------:|---------:|------:|
|    LeftRecursionTest |   LL | Optimized | 1,433.2 us | 22.36 us | 20.91 us |  1.00 |
| NotLeftRecursionTest |   LL | Optimized |   375.2 us |  3.70 us |  3.28 us |  0.26 |
|                      |      |           |            |          |          |       |
|    LeftRecursionTest |   LL |  Standard |   552.9 us |  4.60 us |  4.07 us |  1.00 |
| NotLeftRecursionTest |   LL |  Standard |   382.2 us |  4.25 us |  3.98 us |  0.69 |
|                      |      |           |            |          |          |       |
|    LeftRecursionTest |  SLL | Optimized | 1,427.7 us | 15.61 us | 14.60 us |  1.00 |
| NotLeftRecursionTest |  SLL | Optimized |   373.3 us |  3.20 us |  3.00 us |  0.26 |
|                      |      |           |            |          |          |       |
|    LeftRecursionTest |  SLL |  Standard |   550.6 us |  4.02 us |  3.76 us |  1.00 |
| NotLeftRecursionTest |  SLL |  Standard |   382.4 us |  4.00 us |  3.74 us |  0.69 |

Т.е. нелеворекрусивная версия в 4 раза быстрее леворекурсивной на Optimized рантайме. Для Standard разница поменьше, но все равно есть.


Поэтому советую не использовать левую рекурсию, если производительность важна.


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

Такое решение выглядит не очень чисто, т.к. дерево разбора становится мутабельным. Не рассматривали возможность преобразование дерева ANTLR в свое собственное представление с использованием Listener? Во-первых, таковое будет занимать меньше памяти, во-вторых, обработка лишних WS и NL упростится. Правда строить такое дерево сложнее — снизу вверх, сворачивая токены и узлы, приходящие снизу.


Ну и последнее: планируете ли вы выложить грамматику в Open Source? По ней получилось бы легче и детальней оценить грамматику.

Не рассматривали возможность преобразование дерева ANTLR в свое собственное представление с использованием Listener?

С помощью листенеров дерево ANTLR перегоняется в XML, но это происходит без всяких оптимизаций, дерево трансформируется один в один — это не то, что нам нужно. Таких возможностей не рассматривали.
планируете ли вы выложить грамматику в Open Source?

пока не планируем, но следите за обновлениями)
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.