I know that with a context-free grammar, one can represent the results of a parse as a parse-tree. Specifically, each node represents one application of a production rule, is usually named for the LHS nonterminal, and its children are the nonterminals on the RHS.
For a context sensitive grammar, it's arguably possible to do the same thing, and to just decorate each node with its production rule's left and right context (non)terminals (or even ignore them entirely).
I've been staring at range concatenation grammars for a few hours now and am slightly boggled with respect to their parse representation. They're weaker than CSGs, stronger than CFGs, and yet I can't seem to digest how their parses are represented. Yes, I could say, "Oh, for this grammar it's clearly a tree because you can construct a tree of the production rules!" But that seems unsatisfactory to me because with CSGs and with CFGs one can trivially recreate the string by infix walking the parse tree. With an RCG, I don't see that being possible without an excess of bookkeeping due to rules like
$A(xay) \rightarrow B(by)$
(where ASCII symbols $\leq d$ are terminals and $\geq x$ are variables).
Here to recreate the string one would need to crawl back up the parse tree from any unary production rule $B$ just to figure out that some other production rule $A$ added a symbol $b$ (a new instance non-existent in the original string) to what had been 'produced' in $B$.
It makes me uncomfortable in a, "This seems oddly inelegant," sort of way. The feeling is of course unfounded and arbitrary, but it's there.
What's up with range concatenation grammars' parse representations? Is there a more elegant/useful way of representing their parse results than the trivial [production-rule $=$ subtree] intuition?
As I read more into Earley parser designs for RCGs, it seems that there's the shared 'forest' way of representing them in papers by Boullier and Kallmeyer, but that doesn't give a particularly clear intuition for what an individual parse is; they may call it a 'forest' but that doesn't seem to imply the existence of nice and clean 'trees'. :-/
I might be conflating features of literal movement grammars with range concatenation grammars. The interpretation I gave of the predicate clause above may be entirely incorrect...
Okay, a key point to all of this is that a terminal appearing in a predicate on the RHS of a clause is actually just a range that is defined to span a part of the input string that is exactly that terminal. This lends credence to the equivalence of these two clauses in the presence of $C(c) \rightarrow \epsilon$:
- $A(x) \rightarrow B(xc)$
- $A(x) \rightarrow B(xy)C(y)$
Navigating the parse tree still requires bookkeeping, but the rationale behind that bookkeeping makes more sense.
Also, I might still very well be writing invalid rules in this example. I don't know if it's a requirement that the ranges present on the RHS be within the ranges of the LHS or if they may both span anywhere within the original string. If the former, maybe the tree makes a whole lot of sense and that's why I've been misunderstanding this.
If I'm understanding Kallmeyer in 'Parsing Beyond Context-Free Grammars' correctly, the ranges appear to be able to span anywhere in the original string. Maybe. I'm still feeling that's a bit ambiguous.
It is necessarily the case that the ranges are allowed to span anywhere in the input string being recognized by the grammar regardless of the ranges spanned by the arguments on the LHS of a clause, otherwise Boullier's remarks at the top of page 274 in "Recent Developments in Parsing Technology" (doi:10.1007/1-4020-2295-6_13) would make jack little sense.
Which correspondingly means that my original question still stands.