ANTLR - 无法获得AST层次结构设置

Question

我试图让我的头围绕ANTLR中的树构造运算符(^和!).

我有一个flex字节数组的语法(一个UINT16,用于描述数组中的字节数,后跟那么多字节).我已经注释掉所有语义谓词及其相关代码,这些代码确实证明了数组中的字节数与前两个字节所指示的一样多......那部分不是我遇到的问题.

我的问题是解析一些输入后生成的树.所有发生的事情是每个角色都是兄弟节点.我期望生成的AST与您在ANTLRWorks 1.4的Interpreter窗口中可以看到的树类似.一旦我尝试使用^字符更改树的制作方式,我就会得到一个例外:

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#中的程序我用来获取AST的视觉效果(实际上是文本,但后来我通过GraphViz来获取图片):

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中的"语义谓词"是什么？
• 要获得有关树重写运算符的更多信息-> ^( ... ),请参阅前面的问答:如何输出使用ANTLR构建的AST？

编辑

简要解释一下array_data规则:

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

正如您在评论中已经提到的,您可以通过在规则[TYPE IDENTIFIER]之后添加将一个或多个参数传递给规则.

第一个(门控)语义谓词{length > 0}?=>检查是否length大于零.如果是这种情况,解析器会尝试匹配变量减1 hex_byte之后的length变量.这一切都在length为零时停止,或者当解析器不再hex_byte需要解析时,当EOF在下一行时发生.因为它可以解析少于强制数量的hex_bytes,所以在规则的最后有一个(验证)语义谓词{length == 0}?,它确保hex_byte已经解析了正确数量的s(不多也不少!).

希望能更清楚一点.