为什么使用ANTLR生成解析树时会出现OutOfMemoryException

本文关键字:OutOfMemoryException ANTLR 为什么 | 更新日期: 2023-09-27 18:29:47

我构建了一个"simples"语法来解释一个看起来像json(或xml)的文件。但是,当我尝试解析文件并在树上导航时,我会得到一个System.OutOfMemoryException

输入文件只有108MB,但包含近500万行。

以下是文件示例:

(
    :field ("ObjectName"
        :field (
            :field ("{6BF621F9-A0E2-49BB-A86B-3DE4750954F4}")
            :field (Value)
            :field (Value)
            :field (
                :Time ("Sun Jan 26 10:08:33 2014")
                :last_modified_utc (1390730913)
                :By ("Some text")
                :From (localhost)
            )
            :field ("text/text")
            :field (false)
            :field (false)
        )
        :field ()
        :field ()
        :field ()
        :field (0)
        :field (true)
        :field (true)
    )
.
.
.
.
.
)

遵循语法:

grammar Objects;
/*
 * Parser Rules
 */

compileUnit
    : obj
    ;

obj
    : OPEN ID? (field)* CLOSE
    ;
field
    : ':'(ID)? obj
    ;

/*
 * Lexer Rules
 */

OPEN 
    : '(' 
    ;
CLOSE 
    : ')' 
    ;
ID
    : (ALPHA | ALPHA_IN_STRING)
    ;

fragment
INT_ID
    : ('0'..'9')
    ;
fragment
ALPHA_EACH
    : 'A'..'Z' | 'a'..'z' | '_' | INT_ID | '-' | '.' | '@'
    ;
fragment
ALPHA
    : (ALPHA_EACH)+
    ;
fragment
ALPHA_IN_STRING
    : ('"' ( ~['r'n] )+ '"')
    ;

WS
    // :    ' ' -> channel(HIDDEN)
    : [ 't'r'n]+ -> skip  // skip spaces, tabs, newlines
    ;

和解析器:

var input = new Antlr4.Runtime.AntlrInputStream(text);
var lexer = new ObjectsLexer(input);
var tokens = new Antlr4.Runtime.CommonTokenStream(lexer);
var parser = new ObjectsParser(tokens);
// Context for the compileUnit rule
// ERROR: Here I got the error. When start the to build the tree for compileUnit rule
var ctx = parser.compileUnit();

// The following line is not executed
new ObjectsVisitor().Visit(ctx);

在误差线上,我意识到记忆呈指数级增长。

为什么使用ANTLR生成解析树时会出现OutOfMemoryException

  • 如果输入是UTF-8编码的,并且主要使用ASCII字符,则转换为UTF-16将需要大约216MB
  • 每个令牌至少使用48字节的内存
  • 出现在解析树中的每个令牌使用至少20个字节的内存(除了44个)
  • 解析树中的每个规则节点使用至少36个字节的内存。如果规则有任何子项,则最小值为68字节

上面的数字不包括任何局部变量、参数、标签或返回值,如果使用它们,所有这些都存储在树中。

假设每个令牌有4个字符,解析树中有一半的令牌,每个解析树节点平均有3个令牌(这里的值完全是任意的),则可以得到:

  • 输入:216MB
  • 约2800万个代币:约1281MB
  • 解析树中约1400万个终端节点:约267MB
  • 约470万个解析树节点:约308MB

这超过了2GB的内存,并且不包括与运行时或ANTLR内部构建的动态DFA缓存相关的任何开销。您显然需要将应用程序作为64位进程运行,或者减少输入的大小。

相关文章:
  • 没有找到相关文章