ANTLR - 配置AST层次结构出现问题

Question

我试图理解ANTLR中的树构造运算符（^和！）。

我有一个用于灵活字节数组（一个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#编写的程序，可以通过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));
        }
    }
}

- Anssssss

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是否大于零。如果是这种情况，解析器尝试匹配一个hex_byte，然后将length变量减少一。当length为零时，所有这些都停止，或者当解析器没有更多要解析的hex_byte时，即EOF接下来。因为它可能解析的hex_byte数量少于强制的数量，所以在规则的最后有一个（验证）语义谓词{length == 0}?，确保已解析正确数量的hex_byte（既不多也不少！）。

希望这能更加清楚地解释。

- Bart Kiers

---

感谢您提供如此详尽的答案！我已经将谓词注释掉了，但是没有删除它们，因为我有一点希望ANTLR大师能告诉我它们是否存在问题...您肯定对它们进行了改进（我不知道您可以将参数传递到规则中，我还有很多东西要学习）！关于树重写操作符，我一定会研究一下的（刚从PragProg.com购买了《Definitive ANTLR参考手册》）。还有一个问题... "=>" 运算符是什么？您在 array_data 规则的前置条件之后使用了它。 - Anssssss

@Anssssss，{ ... }?=> 被称为 _门控语义谓词_。请查看 更多信息 下的第一个链接以了解其工作原理。当然欢迎你，你发布了一个非常好的、详细的问题，包括 Java 和 C# 代码示例。我希望所有的问题都像你的一样！ - Bart Kiers

@Anssssss，还请查看我回答中的EDIT。 - Bart Kiers