Упрощение дерева синтаксического анализа ANTLR4

Question

Есть ли какие-либо средства для получения ANTLR4 для автоматического удаления избыточных узлов в генерируемых деревьях разбора?

Более конкретно, я экспериментировал с грамматикой для GLSL, и вы закончили с длинными линейными последовательностями «выражений» в дереве разбора из-за пересылки правил, необходимых для автоматической обработки приоритета оператора.

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

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

Основная структура грамматики является довольно прямым клоном берется из спецификации Khronos для языка:

https://www.khronos.org/registry/gles/specs/3.1/es_spec_3.1.pdf

Answer 1

ANTLR v4 способен генерировать код из одного рекурсивного правила работы с различными уровнями приоритета , если вы используете грамматику, как это (например, для основной математики):

expr : '(' expr ')' 
    | '-' expr 
    | expr ('*'|'/') expr 
    | expr ('+'|'-') expr 
    | INT 
    ; 

ANTLR v3 не смог сделать это, и в основном требуется вам, чтобы написать одно правило на уровень приоритета. Поэтому я бы посоветовал вам переписать свою грамматику, чтобы избежать этих правил шаблонов.

Тогда, я думаю, вы вводите в заблуждение parse tree (aka concrete syntax tree) с AST (abstract syntax tree). AST похож на упрощенную версию дерева синтаксического анализа, которая сохраняет только то, что необходимо для вашей цели. Например, с приведенным выше правилом expr, AST не будет содержать какой-либо узел для круглых скобок, поскольку приоритет кодируется в самом дереве, и вам обычно не нужно знать, была ли какая-либо часть данного выражения заключена в скобки или нет.

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

Answer 2

Используйте реализацию Visitor для доступа к каждому узлу в последовательности. Создайте свое дерево, добавив узлы к родителям по мере их посещений. Решите во время посещения узла, добавить ли его к новому дереву или нет. Например:

public T visitExpression(@NotNull AcParser.ExpressionContext ctx) { 
     // Expressionable parent = getParent(Expressionable.class, ctx); 
     // Class<? extends AcExpression> expClass = AcExpression.class; 
     AcExpression obj = null; 
     String text = ctx.getText(); 

     //do something with text or children 
     for (int i=0; i<ctx.getChildCount(); i++){ 
      printnl(ctx.getChild(i).getText()+"/"); 
     } 

     return visitChildren(ctx); 
    }