If you are planning on using this kind of syntax for a real
application requiring a parser, you probably do not want to wander
outside the polynomial realm. So you might be interested by
linear context-fre rewriting systems
which is a hierarchy of grammatical
formalisms parsable in polynomial time. This has been heavily explored
by the community that studies formal syntax for natural languages. You may also look for
mildly context-sensitive languages.
Context-free (CF) languages are at the bootom of that hierarchy, parsable
in tine n^3. The next family is
tree adjoining grammars, parsable in
time n^6. Of course, these are worst case bounds. If you avoid
pathological cases, things often work a lot better. Anything that is
hard for a software parser is also hard for a human reader.
There is a significant body of litterature on all this. And there have
been more recent extensions:
Range concatenation grammars (RCG)
By the way, I suppose one can consider that CF grammars are for nested
words. In the same way,
tree adjoining grammars are for nested trees.
linear context-fre rewriting systems are for increasingly
complex forms of nesting (nesting is what context-free stands for in
But I honestly doubt you want that much expressive power.
You should also be aware that you can express a lot of things with
context-free languages when you do not restrict yourself to languages
that are deterministically parsable from left to right with a push-down memory stack. Actually,
depending on the application, ambiguous context-free syntax may be a
perfectly reasonnable choice.
I wonder why you seem so interested in
tree automata, though you do not say which variety.
Side note : I doubt there is much insight to be gained from the
Chomsky hierarchy. It is more a historical curiosity than a useful