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

Я пытаюсь разобраться в операторах построения дерева (^ и!) В 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:

Вывод интерпретатора ANTLRWorks 1.4 для ввода 0001ff

Вот программа на 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: graph viz output

Та же программа на 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));
        }
    }
}

person Anssssss    schedule 27.04.2011    source источник


Ответы (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:

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 было проанализировано (нет больше и не меньше!).

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

person Bart Kiers    schedule 28.04.2011
comment
Спасибо за очень обстоятельный ответ! Я оставил закомментированные предикаты, но не удалил их, потому что у меня была небольшая надежда, что гуру ANTLR сообщит мне, если с ними возникнет проблема ... вы определенно улучшили их (я не знаю, что вы можете передавать параметры в правила, мне есть чему поучиться)! Оператор перезаписи дерева, я обязательно рассмотрю это тоже (только что купил ссылку на Definitive ANTLR на PragProg.com). Один вопрос ... что такое оператор = ›? Вы использовали его сразу после предусловия в правиле array_data. - person Anssssss; 28.04.2011
comment
@Anssssss, { ... }?=> называется стробированным семантическим предикатом. Перейдите по первой ссылке в разделе Дополнительная информация, чтобы узнать, как это работает. И, конечно же, добро пожаловать, вы разместили очень хороший, подробный вопрос, включая примеры кода Java и C #. Желаю, чтобы все вопросы были похожи на ваши! - person Bart Kiers; 28.04.2011
comment
@Anssssss, также см. ИЗМЕНИТЬ в моем ответе. - person Bart Kiers; 28.04.2011