in reply to Multidimensional regular expressions
You could, I beleive, code functions for your primitives that indeed access data in different parts of a data structure and return pass/fail, but then string them together in a Rule to provide for the backtracking.
Second, consider expanding out any non-cyclic data structure into a long string, like what Dumper does. Armed with regex tools that include Ballanced Parens etc., this can be parsed with grammer rules, right? So where's the other dimentions, exactly?