ANTLR - проблема с настройкой иерархии AST

Question

Я пытаюсь разобраться с операторами построения дерева (^ и!) В ANTLR.

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

Моя проблема связана с деревом, которое генерируется после анализа некоторого ввода.Все, что происходит, - это то, что каждый персонаж является узлом родного брата.Я ожидал, что сгенерированный AST будет похож на дерево, которое вы можете увидеть в окне интерпретатора ANTLRWorks 1.4.Как только я пытаюсь изменить способ создания дерева, используя символ ^, я получаю исключение в форме:

Unhandled Exception: System.SystemException: more than one node as root (TODO: make exception hierarchy)

Вот грамматика (в настоящее время нацелена на C #):

grammar FlexByteArray_HexGrammar;

options 
{
//language = 'Java';
language = 'CSharp2';
output=AST; 
}

expr 
    :   array_length remaining_data
        //the amount of remaining data must be equal to the array_length (times 2 since 2 hex characters per byte)
        // need to check if the array length is zero first to avoid checking $remaining_data.text (null reference) in that situation.
        //{ ($array_length.value == 0 && $remaining_data.text == null) || ($remaining_data.text != null && $array_length.value*2 == $remaining_data.text.Length) }?
    ;

array_length //returns [UInt16 value]
    :   uint16_little //{ $value = $uint16_little.value; }
    ;

hex_byte1 //needed just so I can distinguish between two bytes in a uint16 when doing a semantic predicate (or whatever you call it where I write in the target language in curly brackets)
    :   hex_byte
    ;

uint16_big //returns [UInt16 value]
    :   hex_byte1 hex_byte //{ $value = Convert.ToUInt16($hex_byte.text + $hex_byte1.text); }
    ;

uint16_little //returns [UInt16 value]
    :   hex_byte1 hex_byte //{ $value = Convert.ToUInt16($hex_byte1.text + $hex_byte.text); }
    ;

remaining_data 
    :   hex_byte*
    ;

hex_byte 
    :   HEX_DIGIT HEX_DIGIT
    ;

HEX_DIGIT : ('0'..'9'|'a'..'f'|'A'..'F')
;

Вот то, что я думал, что AST будет:

Вот программа на C #, которую я использовал для получения визуального (на самом деле текстового, но затем я положил егочерез GraphViz для получения изображения) представление AST:

namespace FlexByteArray_Hex
{
    using System;
    using Antlr.Runtime;
    using Antlr.Runtime.Tree;
    using Antlr.Utility.Tree;

    public class Program
    {
        public static void Main(string[] args)
        {
            ICharStream input = new ANTLRStringStream("0001ff");
            FlexByteArray_HexGrammarLexer lex = new FlexByteArray_HexGrammarLexer(input);
            CommonTokenStream tokens = new CommonTokenStream(lex);
            FlexByteArray_HexGrammarParser parser = new FlexByteArray_HexGrammarParser(tokens);

            Console.WriteLine("Parser created.");

            CommonTree tree = parser.expr().Tree as CommonTree;

            Console.WriteLine("------Input parsed-------");

            if (tree == null)
            {
                Console.WriteLine("Tree is null.");
            }
            else
            {
                DOTTreeGenerator treegen = new DOTTreeGenerator();
                Console.WriteLine(treegen.ToDOT(tree));
            }
        }
    }
}

Вот как выглядит вывод этой программы, помещенной в GraphViz:

Та же самая программа на Java (в случаевы хотите попробовать и не использовать C #):

import org.antlr.*;
import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;

public class Program
{
    public static void main(String[] args) throws Exception
    {
        FlexByteArray_HexGrammarLexer lex = new FlexByteArray_HexGrammarLexer(new ANTLRStringStream("0001ff"));
        CommonTokenStream tokens = new CommonTokenStream(lex);
        FlexByteArray_HexGrammarParser parser = new FlexByteArray_HexGrammarParser(tokens);

        System.out.println("Parser created.");

        CommonTree tree = (CommonTree)parser.expr().tree;

        System.out.println("------Input parsed-------");


        if (tree == null)
        {
            System.out.println("Tree is null.");
        }
        else
        {
            DOTTreeGenerator treegen = new DOTTreeGenerator();
            System.out.println(treegen.toDOT(tree));
        }
    }
}

Answer 1

Anssssss писал:

Как только я пытаюсь изменить способ создания дерева, используя символ ^, я получаю исключение из формы:

При попытке сделать правило синтаксического анализатора a корнем дерева внутри p, например:

p : a^ b;
a : A A;
b : B B;

ANTLR не знает, какой из A является корнем правила a. И, конечно, не может быть двух корней.

Операторы встроенного дерева удобны в некоторых случаях, но в этом случае они не соответствуют задаче. Вы не можете назначить корень внутри производственного правила, которое может не иметь содержимого, например, ваше правило remaining_data. В этом случае вам нужно создать «воображаемые жетоны» в разделе tokens { ... } вашей грамматики и использовать правило перезаписи (-> ^( ... )) для создания своего AST.

Демо

Следующая грамматика:

grammar FlexByteArray_HexGrammar;

options {
  output=AST;
}

tokens {
  ROOT;
  ARRAY;
  LENGTH;
  DATA;
}

expr
  :  array* EOF -> ^(ROOT array*)
  ;

array
@init { int index = 0; }
  :  array_length array_data[$array_length.value] -> ^(ARRAY array_length array_data)
  ;

array_length returns [int value]
  :  a=hex_byte b=hex_byte {$value = $a.value*16*16 + $b.value;} -> ^(LENGTH hex_byte hex_byte)
  ;

array_data [int length]
  :  ({length > 0}?=> hex_byte {length--;})* {length == 0}? -> ^(DATA hex_byte*)
  ;

hex_byte returns [int value]
  :  a=HEX_DIGIT b=HEX_DIGIT {$value = Integer.parseInt($a.text+$b.text, 16);}
  ;

HEX_DIGIT
  :  '0'..'9' | 'a'..'f' | 'A'..'F'
  ;

проанализирует следующий вход:

0001ff0002abcd

в следующие AST:

Как вы можете видеть, используя следующий основной класс:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;

public class Main {
    public static void main(String[] args) throws Exception {
        FlexByteArray_HexGrammarLexer lexer = new FlexByteArray_HexGrammarLexer(new ANTLRStringStream("0001ff0002abcd"));
        FlexByteArray_HexGrammarParser parser = new FlexByteArray_HexGrammarParser(new CommonTokenStream(lexer));
        CommonTree tree = (CommonTree)parser.expr().getTree();
        DOTTreeGenerator gen = new DOTTreeGenerator();
        StringTemplate st = gen.toDOT(tree);
        System.out.println(st);
    }
}

Подробнее

• если вы хотите узнать больше о предикатах, которые я использовал в правиле синтаксического анализатора array_data, посмотрите предыдущие вопросы и ответы: Что такое «семантический предикат» в ANTLR?
• , чтобы получить больше информации об операторе перезаписи дерева -> ^( ... ), см. Этот предыдущий Q & A: Как вывести AST, построенный с использованием ANTLR?

EDIT

Чтобы дать краткое объяснение правила array_data:

array_data [int length]
  :  ({length > 0}?=> hex_byte {length--;})* {length == 0}? -> ^(DATA hex_byte*)
  ;

Как вы уже упоминали в комментариях, вы можете передать один или несколько параметров правилам, добавив [TYPE IDENTIFIER] после правила.

Первый (стробированный) семантический предикат, {length > 0}?=>, проверяет, является ли length больше нуля. Если это так, то парсер пытается сопоставить hex_byte, после чего переменная length уменьшается на единицу. Все это останавливается, когда length равно нулю или когда анализатор не имеет больше hex_byte для анализа, что происходит, когда EOF следующий в строке. Поскольку может анализировать меньше обязательного числа hex_byte с, в самом конце правила есть (проверяющий) семантический предикат {length == 0}?, который гарантирует, что правильное количество hex_byte s были проанализированы (не больше и не меньше!).

Надеюсь, это прояснит это немного подробнее.