про парсинг ничего не знаю, но если речь бы шла о машинах, которые ограничиваются арифметиками, то арифметика Пресбургера разрешима, но находится где-то между 2-EXP и 2-EXPSPACE, когда как сложность контекстно-зависимых/чувствительных языков (и грамматик) — это NLINSPACE, который равен NSPACE(O(n)).
NSPACE(O(n)), если я не туплю, будет ниже в иерархии, чем NSPACE(n²). В свою очередь NSPACE(n²) ⊂ PSPACE, так как PSPACE = ∪NSPACE(n^k). В свою очередь, PSPACE ⊆ EXP, а 2-EXP выше, чем EXP.