MemoryError when loading model

Question

When I try to load the model (input, not meta-model), it returns a MemoryError about 30 seconds after executing.

Expected: List of tree: [{'type':'func', 'callee':'print', 'args':[['Hello']]}] Actual: MemoryError

Output

Traceback (most recent call last):
  File "C:/Users/kenxs/PycharmProjects/program/program/parser.py", line 103, in <module>
    main()
  File "C:/Users/kenxs/PycharmProjects/program/program/parser.py", line 97, in main
    program.do_it(True, True, True)
  File "C:/Users/kenxs/PycharmProjects/program/program/parser.py", line 80, in do_it
    if cont and intp:   cont, err = self.interpret()
  File "C:/Users/kenxs/PycharmProjects/program/program/parser.py", line 67, in interpret
    self.model = self.mm.model_from_file(os.path.abspath('program.program'))
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\textx\metamodel.py", line 574, in model_from_file
    return self.internal_model_from_file(file_name, encoding, debug)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\textx\metamodel.py", line 613, in internal_model_from_file
    model = self._parser_blueprint.clone().get_model_from_str(
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\textx\model.py", line 262, in get_model_from_str
    self.parse(model_str, file_name=file_name)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 1493, in parse
    self.parse_tree = self._parse()
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\textx\model.py", line 221, in _parse
    return self.parser_model.parse(self)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 286, in parse
    result = self._parse(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 365, in _parse
    result = e.parse(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 286, in parse
    result = self._parse(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 365, in _parse
    result = e.parse(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 286, in parse
    result = self._parse(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 481, in _parse
    result = p(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 286, in parse
    result = self._parse(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 404, in _parse
    result = e.parse(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 286, in parse
    result = self._parse(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 365, in _parse
    result = e.parse(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 286, in parse
    result = self._parse(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 365, in _parse
    result = e.parse(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 286, in parse
    result = self._parse(parser)
  File "C:\Program Files (x86)\Python38-32\lib\site-packages\arpeggio\__init__.py", line 484, in _parse
    append(result)
MemoryError

Grammar

Program:
  commands*=Command
;

Command:
  Statement | Function | Definition
;

Statement:
  callee=ID '(' checker=Checker ')' '=' effect=Collection Ending
;

Checker:
  a=Object sign=CheckerSign b=Object
;

CheckerSign:
  '==' | '!='
;

Collection:
  '[' objs*=PseudoObject ']'
;

PseudoObject:
  Object Ending
;

Function:
  callee=ID '(' args=Arguments ')' Ending
;

Arguments:
  arg*=Argument
;

Argument:
  NamedArgument | UnnamedArgument
;

NamedArgument:
  a=Object '=' b=Object
;

UnnamedArgument:
  a=Object
;

Definition:
  a=Object '=' b=Object
;

Object:
  a*=ObjectChild
;

ObjectChild:
  ObjectChildChild ( '.' | '' )
;

ObjectChildChild:
  String | ID | INT | STRICTFLOAT | BOOL | Collection | Function
;

String:
  '"' ID '"'
;

Comment:
  /#.*/ Ending
;

Ending:
  '' *Newline
;

Newline:
  ( '\n' | ';' )
;

Program

import os
from textx import *
from textx.export import *


class Parser(object):

  def __init__(self, meta_model_path='grammar.tx', model_str='print("Hello")'):
    self.tree = []
    self.meta_model_path = os.path.abspath(meta_model_path)
    self.model_str = model_str
    self.mm = None
    self.model = None

  def __str__(self):
    return str(self.tree)

  def _interpret_function(self, c):
    result = {}
    result['type'] = 'func'
    result['callee'] = c.callee
    result['args'] = []
    for arg in c.args.arg:
      if arg.__class__.__name__ == 'UnnamedArgument':
        result['args'].append([arg.a.a])
      elif arg.__class__.__name__ == 'NamedArgument':
        result['args'].append([arg.a.a, arg.b.a])
    return result

  def _interpret_definition(self, c):
    result = {}
    result['type'] = 'defi'
    result['a'] = c.a.a
    result['b'] = c.b.a
    return result

  def _interpret_statement(self, c):
    result = {}
    result['type'] = 'stat'
    result['callee'] = c.callee
    result['checker_a'] = c.checker.a
    result['checker_b'] = c.checker.b
    result['checker_sign'] = c.checker.sign
    result['effect'] = c.effect.objs
    return result

  def _interpret(self, model):
    for c in model.commands:
      if c.__class__.__name__ == 'Statement':
        self.tree.append(self._interpret_statement(c))
      elif c.__class__.__name__ == 'Function':
        self.tree.append(self._interpret_function(c))
      elif c.__class__.__name__ == 'Definition':
        self.tree.append(self._interpret_definition(c))

  def export_meta_model(self, mm):
    metamodel_export(self.mm, os.path.abspath('grammar.dot'))
    return [True, None]

  def export_model(self, model):
    model_export(self.model, os.path.abspath('program.dot'))
    return [True, None]

  def interpret(self):
    print(-1)
    self.mm = metamodel_from_file(self.meta_model_path, debug=False)
    print(0)
    try:
      self.model = self.mm.model_from_str(self.model_str)
      # self.model = self.mm.model_from_file(os.path.abspath('program.prg'))
    except TextXSyntaxError as err:
      print('Syntax Error @ {}:{}'.format(err.line, err.col))
      print('{}'.format(err.message))
      return [False, err]
    print(1)
    self._interpret(model)
    print(2)
    return [True, None]

  def do_it(self, exp_mm=False, exp_m=False, intp=True):  # My naming skills :)
    cont = True
    err = None
    if cont and intp:   cont, err = self.interpret()
    if cont and exp_mm: cont, err = self.export_meta_model()
    if cont and exp_m:  cont, err = self.export_model()


def main(debug=False):
  print('Program')
  program = Parser()
  print('Inp Done')
  program.do_it(True, True, True)
  print('Done')
  print(program)


if __name__ == "__main__":
  main()

Answer 1

Rule Ending has zero or more empty string match ''* that is essentially an infinite loop building a parse tree node with an infinite number of empty match terminals. Eventually, the parse tree eats up all the memory and you get MemoryError.

In general, repetitions ('*', '+') over a parsing expression that could potentially be an empty match could lead to an infinite loop.

I suggest that you register an issue in the issue tracker for this as it should be fairly easy to at least detect it at runtime without to much overhead.