Antlr4 "примитивная" рекурсия - PullRequest
Новая
       13

Antlr4 "примитивная" рекурсия

0 голосов
/ 09 октября 2019

В продолжение http://blog.ptsecurity.com/2016/06/theory-and-practice-of-source-code.html#java--and-java8-grammars, Я пытаюсь уменьшить левую рекурсию в моей довольно сложной грамматике. Из того, что я понимаю, не примитивная форма рекурсии может привести к проблемам с производительностью как с точки зрения памяти, так и времени процесса.

Поэтому я пытаюсь реорганизовать эти правила в моей грамматике, чтобы использовать только "примитивную" рекурсию,Конечно, это сообщение в блоге - единственный раз, когда я видел фразу «примитивная» рекурсия по отношению к Antlr. Так что я просто догадываюсь о его значении / намерении. Мне кажется, это означает, что правило относится к самому себе как к lhs не более чем для одной ветви правила. Правильно?

На данный момент у меня есть правило выражения вроде: 

expression
    : expression DOUBLE_PIPE expression         # ConcatenationExpression
    | expression PLUS expression                # AdditionExpression
    | expression MINUS expression               # SubtractionExpression
    | expression ASTERISK expression            # MultiplicationExpression
    | expression SLASH expression               # DivisionExpression
    | expression PERCENT expression             # ModuloExpression
    ...
    ;

* ... включает в себя довольно много подправил, которые также ссылаются на expression. Но это единственные с прямой рекурсией.

Если я правильно понимаю, рефакторинг их как "примитивной" рекурсии будет выглядеть примерно так: 

expression
    : binaryOpExpression                        # BinaryOpExpression
    ...
    ;

binaryOpExpression
    : expression DOUBLE_PIPE expression         # ConcatenationExpression
    | expression PLUS expression                # AdditionExpression
    | expression MINUS expression               # SubtractionExpression
    | expression ASTERISK expression            # MultiplicationExpression
    | expression SLASH expression               # DivisionExpression
    | expression PERCENT expression             # ModuloExpression
    ;

Во-первых, это правильный рефакторинг?

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

Спасибо

1 Ответ

0 голосов
/ 10 октября 2019

Ранее я не слышал «примитивную рекурсию» в этом контексте, и автор, вероятно, имеет в виду только назвать конкретную форму рекурсии в ANTLR4.

Факт в том, что в ANTLR4 есть 3 соответствующие формы рекурсии:

  • Прямая левая рекурсия: рекурсия из первой ссылки на правило в правиле (к тому же правилу). Например: a: ab | c;
  • Косвенная левая рекурсия: левая рекурсия не напрямую из того же правила. Например: a: b | c; b: c | d; c: a | e; (не разрешено в ANTLR4)
  • Правая рекурсия: любая другая рекурсия в правиле. Например: a: ba | c;. Однако имя «правая рекурсия» является правильным только в случаях двоичного выражения, но часто используется для отличия от левых рекурсий в целом.

Сказав, что становится ясно, что ваше переписывание неверно, так какэто создаст косвенную левую рекурсию, которую ANLTR4 не поддерживает. Прямая левая рекурсия обычно не является проблемой (с точки зрения памяти или производительности), поскольку ANTLR4 преобразует их в нерекурсивные графы правил ATN.

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

Единственное решение для последнего случая, которое я нашел полезным, - это уменьшить количество правил синтаксического анализа в грамматике, которые вызывают друг друга. Конечно, это вопрос структуры, читабельности и т. Д. Для помещения определенных элементов выражения в разные правила (например, andExpression, orExpression, bitExpression и т. Д.), Но это может привести к довольно глубоким стекам вызовов, которые могут исчерпать ресурсы. стек процессора и / или требует много времени для их обработки.

...