Parse structure of a range concatenation grammar (RCG)
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)])