Почему я получаю OutOfMemoryException при генерации дерева парсеров с ANTLR?

Question

Я построил грамматику «простых», чтобы интерпретировать файл, похожий на json (или xml). Но, когда я пытаюсь разобрать файл и перемещаться по дереву, я получаю System.OutOfMemoryException.

Входной файл имеет только 108 МБ, но содержит почти 5 миллионов строк.

Вот пример файла:

(
    :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); 

На линии ошибок, я понимаю, что рост экспоненциальности.

Answer 1

• Если вход кодируется в кодировке UTF-8 и использует в основном символы ASCII, для преобразования в UTF-16 потребуется приблизительно 216 МБ.
• Каждый токен использует не менее 48 байт памяти.
• Каждый токен, который появляется в дереве разбора, использует как минимум 20 байт памяти (в дополнение к 44).
• Каждый узел правил в дереве разбора использует как минимум 36 байт памяти. Если правило имеет детей, минимальный размер составляет 68 байтов.

Цифры выше не содержат никаких локалей, аргументов, меток или возвращаемых значений, все из которых хранятся в дереве, если вы их используете.

Предполагая 4 символов в знак, половина маркеров в дереве синтаксического анализа, а также в среднем 3 маркеров на синтаксическое узле дерева (полностью произвольные значения здесь), вы получите:

• Вход: 216MB
• ~ 28 миллионов жетонов: ~ 1281MB
• ~ 14 миллионов терминальных узлов в дереве разбора: ~ 267MB
• ~ 4,7 млн ​​синтаксического дерева узлов: ~ 308MB

Это более 2 ГБ памяти и не учитывает никаких накладных расходов, связанных с временем выполнения или динамическим кэшем DFA, созданным внутри ANTLR. Вам явно нужно либо запустить приложение как 64-битный процесс, либо уменьшить размер ваших входов.