Многократные запросы на совпадение по запросу

В вашей функции simplify() параметр n является ссылкой на некоторый конкретный узел, и вы можете изменить, к какому узлу он относится; но переназначение n не изменяет никакой другой структуры. В качестве конкретного примера этот цикл фактически ничего не делает:

for c in n.children:
  # simplify has no side effects and leaves the input structure unchanged
  c = simplify(c)
  # c is never used again so the simplified result is lost

Существует два разумных подхода к решению этого. Один из них состоит в том, чтобы построить новое дерево в результате simplify:

def simplify(n):
  if len(n.children) > 1:
    new_children = [simplify(c) for c in n.children]
    return Node(n.symbol, n.rule, new_children)
  # and other cases

Это имеет то преимущество, что ваша структура данных неизменяема : если у вас есть две ссылки на дерево висит вокруг, вы знаете, что переписывание одного не разрушит другого; если у вас есть ссылка на узел в середине дерева, нет никакого риска, что он неожиданно станет «осиротевшим».

Тем не менее, достаточно распространять данные mutable структуры, и вы можете добавить свой метод simplify в класс Node, чтобы переписать узел на место:

class Node:
  def simplify(self):
    if len(self.children) == 1:
      return self.children[0].simplify()
    if len(self.children) > 1:
      self.children = [c.simplify() for c in self.children]
    return self