Parse structure of a range concatenation grammar (RCG)

Question

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?

EDIT

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'. :-/

EDIT 2

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...

EDIT 3

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$:

1. $A(x) \rightarrow B(xc)$
2. $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.

EDIT 4

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.

EDIT 5

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.

Answer 1

So, I'm actually going to reply to your edits first, then come back to your original question.

re: Edit 1

In your first edit, you express some confusion over what a parse emitted by an Earley parser is; to explain that I'll jump into a quick refresher on the difference between parsers for deterministic context-free grammars (such as LR parsers) and an Earley parser (or other parsers, such as GLL or GLR) which can handle nondeterministic context-free grammars.

Fundamentally, a parser for a deterministic context-free grammar is one that, for any input, will parse it in at most one way: It can either give a unique parse, or fail to parse. As a result, its output is either nothing, or a valid parse tree.

A parser for a nondeterministic context-free grammar, on the other hand, may admit multiple valid parses. Grammars which can actually give rise to such situations are said to be ambiguous, though determining whether a given context-free grammar is ambiguous is undecidable. Because of this, its output is a potentially-empty set of parse trees. This is generally referred to as a "parse forest".

The shared parse forest, then, is merely a compact representation of such a set. Because the grammar is still context-free, a rule $R$ matching a subrange of the input $x$ will always result in the same parse forest - regardless of what sequence of rules led to applying $R$ at $x$. As a result, those two parse trees can share the parse forest generated by $R$ at $x$, drastically reducing the space and time requirements. (Another phrasing might be that, as $R(x)$ is a pure function, it can be memoized.)

re: Edit 2

As far as the interpretation of the predicate clause, I feel that the usual notation of range concatenation grammars somewhat obscures their nature.

Fundamentally, a range concatenation grammar is:

• A set of predicates
  • Taking some number $n$ of arguments
  • Consisting of a disjunction of clauses
    • Splitting the arguments into ranges
    • Consisting of a conjunction of predicates
      • Queried at concatenations of ranges

The usual notation (as used in your original question) of $A(xay) → B(xy)$ can thus be desugared into:

$$ A(text) :=\\ let\ (x, a, y) := split(text, 3)\ in\\ B(concatenate(x, y)) \wedge a = ``a" $$

re: Edit 3

I don't know if it's a requirement that the ranges present on the RHS be within the ranges of the LHS

This is almost exactly the case. The "almost" comes from the concatenation behavior: If I have the example rule I used above, and I apply it at $A(``cbabc")$, I will arrive at $B(``cbbc")\wedge ``a" = ``a"$. If $B$ is defined as $B(xbby) → \epsilon$, then it will succeed - despite "bb" appearing nowhere in the original input. Thus, terminals match not against ranges, but against concatenations thereof.

re: Edit 4

The ranges spanning "anywhere in the original string" is as a result of the concatenation, rather than them being free to span arbitrary parts of the original string.

re: Edit 5

I presume you mean where Boullier says (found in the standalone paper (PS))

The arguments of a given predicate may denote discontinuous or even overlapping ranges.

However, this does not mean they can be "anywhere freely" (introduced on the RHS), merely that they may "have come from anywhere". Consider the following rule: $A(xyz) → B(xy, yz)$ - here, $B$ takes two overlapping ranges as arguments.

re: Question

In a context-free grammar, a single parse tree is a recursive data structure, consisting of:

• The rule name
• The range of the input it matched at
• The index of the matching clause
• The parse trees of the rules the clause refers to

We can extend this bit by bit, and thus arrive at what a single parse tree for a range concatenation grammar looks like, and then apply the same optimization as Earley grammars do to recover a shared parse forest.

First, let's extend it to support concatenation. To do this, we'll move from ranges represented as $(start, end)$ pairs to lists of such ranges - the classic rope data structure.

Next, let's extend it to support splitting. This is a single additional member in the node: a list of positions the input rope was split at.

The third step is to support multiple arguments. Now, we will store an $n$-tuple of ropes, where $n$ is the predicate's arity. In addition, we need to store split information for each argument, making it a tuple of lists.

At this point, a node in our parse tree looks like this:

• the predicate name
• the $n$-tuple of ropes it was matched at
• the index of the matching clause
• the $n$-tuple of lists of split points
• the parse trees of the predicates the matching clause refers to

That's it - a single parse tree of a range concatenation grammar.

Now, there are two members of the node that could differ between two parse trees matching the same input. The first is the same as for a CFG: the index of the matching clause. If two clauses can match, then we get two parse trees; one for each.

The second is the list of split points. Let's go back to the example rule $A(xay) → B(xy)$ for a minute, and ask it to match "cbabcacb". There are two points it could split at: $(``cb", ``bcacb")$ or $(``cbabc", ``cb")$. Each of these, then, also generates a distinct parse tree - assuming $B$ succeeds.

However, the predicates of a range concatenation grammar - like those of a context-free grammar - have bodies that refer only to the inputs to the predicate. They are thus context free (i.e. pure functions), and can be memoized.

Thus, one can follow a relatively simple evaluation strategy when parsing:

procedure match_A(args, already_matched) if contains(already_matched, ("A", args)) return reference_to(already_matched[("A", args)]) else results = [] for C in clauses(A) SPLIT: for split_tuple in valid_splits(args) pred_results = {} for P in predicates(C) pred_results[P] = P.match(split_tuple) if empty(pred_results[P]) next SPLIT push(results, { name: "A", matched: arg, clause: C, splits: split, subforests: pred_results }) already_matched[("A", args)] = results return reference_to(already_matched[("A", args)])