Trailing VALUES should be the last translation step.

[afs]

Sections 18.2.4.3 VALUES and 18.2.4.4 SELECT Expressions look to be in the wrong order.

The SELECT clause is composite and, for example, any the aggregation steps should be before joining with VALUES as should assignments. Only solution modifiers should apply. (Ideally, apply projection, then VALUES then the other solution modifiers.)

P := Join(P, ToMultiSet(data))

would become

X := Join(X, ToMultiSet(data))

when 18.2.4.3 VALUES is moved after 18.2.4.4 SELECT Expressions.

[hartig]

I agree that the join with the VALUES clause needs to be moved after applying the Extend operators created for assignments in the SELECT clause.

But I am not sure that simply swapping the order of the two subsections is sufficient. According to the grammar, the trailing VALUES clause comes after all of the solution modifiers (see the Query production). In that sense, I would expect that the join with the data from that VALUES clause is the very last thing, after all solution modifiers have been applied. Swapping the order of the two subsections does not give us that because the translation algorithm converts the solution modifiers after converting the trailing VALUES clause, which means that the solution modifiers would be applied after the join with the data of the trailing VALUES clause. It is possible to do it this way, but it may lead to a behavior that users might not expect (see below). I see three options:

Option 1:
Simply swap the two subsections.

Option 2:

@afs: (Ideally, apply projection, then VALUES then the other solution modifiers.)

This would mean moving Section 18.2.4.3 VALUES further below, directly after Section 18.2.5.2 Projection. Notice that this may make a difference for queries in which the trailing VALUES clause provides bindings for a variable that is also in the WHERE clause but projected away by the SELECT clause. As a concrete example, consider the query

SELECT ?s
WHERE { ?s :p ?o }
VALUES ?o { "a" }

and the data

:s :p "b" .

In this case, Option 1 would produce the empty result set (no solution mapping) because it joins the solution mapping from the WHERE clause with the solution mapping from the VALUES clause before projection, and this join is empty because the two solution mappings are incompatible (the solution mapping from the WHERE clause is m1 = {?s -> :s, ?o -> "b"}, the one from the VALUE clause is m2 = { ?o -> "a"}). In contrast, Option 2 would produce a nonempty result set, containing the solution mapping m3 = {?s -> :s, ?o -> "a"}, because after projecting away ?o from the solution mapping that came from the WHERE clause, the solution mapping coming out of this projection (i.e., m4 = {?s -> :s}) is compatible with the solution mapping from the VALUES clause.

Option 3:
As mentioned above, I would actually expect that the join with the data from that VALUES clause is the very last thing, after all solution modifiers have been applied, not just after projection. This would mean to move Section 18.2.4.3 VALUES right before Section 18.2.5.6 Final Algebra Expression. Of course, for the example above, this option would behave as Option 2. But, there are also cases in which this option is different from Option 2; namely, for queries that use OFFSET or LIMIT. As an example, consider the query

SELECT *
WHERE { :s :p ?o }
ORDER BY ?o
LIMIT 1
VALUES ?o { "b" }

and the data

:s :p "a" .
:s :p "b" .

In this case, if the LIMIT is applied before the join with the data from the VALUE clause---as per Option 3 (and as the order of the clauses in the query seems to suggest)---then the result of the query is the empty result set. In contrast, Option 2 would produce a nonempty result set, containing the solution mapping m = {?o -> "b"}, because it applies the LIMIT after the join.

[afs]

But I am not sure that simply swapping the order of the two subsections is sufficient.

Yes - I came to that conclusion afterwards; option 3 is actually what was intended. The intent is to be able to send data with (remote) queries to a join to restrict the output in the evaluation. It is reflected in the syntax.
(This intent is not SPARQL specific - the original work was from SQL a long time ago when networks were slow.)

[hartig]

option 3 is actually what was intended

Okay. So, Section 18.2.4.3 VALUES should be moved right before Section 18.2.5.6 Final Algebra Expression. However, in this case, we also need to adapt the content of Section 18.2.4.3 VALUES because, at that point in the process, the corresponding algebra operators are not any longer dealing with multisets but with sequences of solution mappings. So, we need an order-preserving version of the join operator (order-preserving at least for one of the two inputs, namely the one that comes from the solution modifiers).