Support arbitrarily structured filter predicates

[glyn]

The filter syntax currently requires predicates to be expressed in (something close to) disjunctive normal form (OR of ANDs), but this is likely to be inconvenient when the intention of the filter is expressed in a different way (e.g. as an AND or ORs or as a nested predicate with ANDs and ORs at various levels).

The JSONPath comparison project doesn't yet test these more complex predicates, although some, possibly most, implementations allow them.

The standard could allow arbitrarily structured predicates via syntax along these lines:

filter-selector ::= "[?(" boolean-expr ")]"

boolean-expr ::= logical-and-expr |
                 logical-and-expr "||" boolean-expr

logical-and-expr ::= basic-filter |
                     basic-filter "&&" logical-and-expr

basic-filter ::= "!" basic filter |
                 "(" boolean-expr ")" |
                 comp-expr

For example, this would allow filters such as:

?(@.b && (@.c || @.d))

and

?(@.b && (@.c || @.d && @.e))

(where the semantics could, in line with mathematical convention and many programming languages, define && to bind more tightly than ||).

Note: the comparison project's Proposal A restricts the syntax so that brackets are required instead of making && bind more tightly than ||. This is a clever approach but is probably not suitable for the standard because it is rather unconventional.

[cabo]

I don't have a problem with requiring parentheses instead of creating an elaborate precedence hierarchy (or at least partially instead of).

I also don't have a problem with arbitrary nesting here.

[gregsdennis]

where the semantics could, in line with mathematical convention and many programming languages, define && to bind more tightly than ||

For clarity, this is because && is a multiplicative operation whereas || is additive. Standard order of operations then apply.

I don't know any programming language where this is reversed. I'm not opposed to requiring (), however.

[goessner]

If the fact that &&binds more tightly than || must be made explicite in the ABNF, it should be done. Using pairs of parentheses should be arbitrary.

[glyn]

Agreed. Is there a preferred way to specify operator precedence in ABNF? The examples I've seen use a textual ordered list which won't help parser generators...

[gregsdennis]

The C# spec (pdf) doesn't use ANBF, but it is pretty clear by using prose and a table. See section 12.4.2.

When an expression contains multiple operators, the precedence of the operators controls the order in which the individual operators are evaluated. [Note: For example, the expression x + y * z is evaluated as x + (y * z) because the * operator has higher precedence than the binary + operator. end note] The precedence of an operator is established by the definition of its associated grammar production. [Note: For example, an additive-expression consists of a sequence of multiplicative-expressions separated by + or - operators, thus giving the + and - operators lower precedence than the *, /, and % operators. end note]

[Note: The following table summarizes all operators in order of precedence from highest to lowest:

Subclause	Category	Operators
§12.7	Primary	x.y f(x) a[x] x++ x-- new typeof default checked unchecked delegate
§12.8	Unary	+ - ! ~ ++x --x (T)x await x
§12.9	Multiplicative	* / %
§12.9	Additive	+ -
§12.10	Shift	<< >>
§12.11	Relational and type-testing	< > <= >= is as
§12.11	Equality	== !=
§12.12	Logical AND	&
§12.12	Logical XOR	^
§12.12	Logical OR	\|
§12.13	Conditional AND	&&
§12.13	Conditional OR	\|\|
§12.14	Null coalescing	??
§12.15	Conditional	?:
§12.18 and §12.16	Assignment and lambda expression	= *= /= %= += -= <<= >>= &= ^= \|= =>

end note]

There's also a bit more about associativity, but I figured this was enough.

[glyn]

Interesting. Does anyone know if ABNF parser generators infer operator precedence from the structure of the productions?

On Tue, 27 Jul 2021, 11:08 Greg Dennis, @.***> wrote:

The C# spec (pdf) https://www.ecma-international.org/wp-content/uploads/ECMA-334_5th_edition_december_2017.pdf doesn't use ANBF, but it is pretty clear by using prose and table. See section 12.4.2.

When an expression contains multiple operators, the precedence of the operators controls the order in which the individual operators are evaluated. [Note: For example, the expression x + y * z is evaluated as x

• (y z) because the operator has higher precedence than the binary + operator. end note] The precedence of an operator is established by the definition of its associated grammar production. [Note: For example, an additive-expression consists of a sequence of multiplicative-expressions separated by + or - operators, thus giving the + and - operators lower precedence than the , /, and % operators. end note*]

[Note: The following table summarizes all operators in order of precedence from highest to lowest: Subclause Category Operators §12.7 Primary x.y f(x) a[x] x++ x-- new typeof default checked unchecked delegate §12.8 Unary + - ! ~ ++x --x (T)x await x §12.9 Multiplicative / % §12.9 Additive + - §12.10 Shift << >> §12.11 Relational and type-testing < > <= >= is as §12.11 Equality == != §12.12 Logical AND & §12.12 Logical XOR ^ §12.12 Logical OR | §12.13 Conditional AND && §12.13 Conditional OR || §12.14 Null coalescing ?? §12.15 Conditional ?: §12.18 and §12.16 Assignment and lambda expression = = /= %= += -= <<= >>= &= ^= |= =>

end note]

There's also a bit more about associativity, but I figured this was enough.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/ietf-wg-jsonpath/draft-ietf-jsonpath-base/issues/110#issuecomment-887385549, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAAXF2NKFVNLICN7IHHRZ4TTZ2AS5ANCNFSM5A4CRLWA .

[cabo]

On 2021-07-27, at 12:15, Glyn Normington @.***> wrote:

Interesting. Does anyone know if ABNF parser generators infer operator precedence from the structure of the productions?

I would venture to say that is a near-universal property of BNF-based parser generators.

Strictly speaking, BNF provides only a Boolean output: word is in language or it is not. But in reality, people use BNF for parsing, and build the parse tree along the structure of the BNF productions that was used for matching. That may be ambiguous even when the language created by the BNF isn’t, and that’s one reason why we have all these variants like LL(1) and LR(k) etc.

The parse tree is then used to build an “abstract syntax tree”, ast, in many cases by attaching actions to the productions in the grammar.

Grüße, Carsten