New expression parse syntax

[Krzmbrzl]

We have discovered that the current syntax for expressions that we use in the parse* functions is not flexible enough as it doesn't allow to distinguish operators from tensors.

Hence, I would like to suggest to re-design the input format from scratch in order to tackle this issue without being tied to the current syntax.

Proposition

I would propose the following syntax rules:

Kind	Syntax	Comment	Examples
Constant	constant -> complex | real; complex -> signed_real ('+' | '-') real 'i'; signed_real -> ('-' | '+') real; real -> fraction | float | integer; fraction -> integer '/' integer; float -> integer? '.' integer; integer -> [0-9]+;		1 1/2 1.5 .34
Variable	variable -> id; id -> letter (letter | digit)*		test test2
Index	index -> id '_'? integer;		i1 i_1
Tensor	tensor -> id '[' index_groups ']' (':' symmetry (',' symmetry))?; index_groups -> ';'* group (';' group)*; group -> index (',' index)*; symmetry -> symm_name | cycle; symm_name -> 'A' | 'S' | 'N' | 'bkS' | 'bkC' | 'bkN' | 'pS' |'pN' ; cycle -> side_effect? '(' (integer (',' integer)* )? ')' ; side_effect -> '+' | '-' | '*'	Using `[]` instead of `{}` as index delimiter due to array-like nature of tensors Scalar "tensors" are not allowed as one should use a `Variable` instead Symmetry specification as (disjoint) cycles (with side-effect) will only be implemented once we have general symmetry support	t[i1] t[i1;a1;u1;p1]:pS t[;;i1,i2] t[i1, i2 ; a1, a2]:pN,+(1,2)
Operator	operator -> id '{' index_groups '}' ':' statistic ; statistic -> 'F' | 'B'	{} to resemble normal ordering Symmetry determined via chosen statistic	L{i1;;a1,a2}:F
Symmetrizer	symmetrizer -> 'symm' '(' index_groups ')' ':' symmetry	Using reserved keyword "symm" to never confuse symmetrizer with tensor, etc. Use parenthesis as delimiters in resemblance to a function call Chosen symmetry determined whether it's an symmetric or antisymmetric symmetrization	symm(i1,i2):A symm(a1,a2;i1,i2):S

Composite expressions like sums and products just follow regular mathematical syntax.

So the core of the proposed changes is the ability to ensure that we have uniquely different syntax for tensors, (normal-ordered) operators and things like symmetrizers.

[bimalgaudel]

Some comments:

• This syntax does not allow negative reals.
• Probably allowing floats to start with a . not worth the grammar complexity.

[Krzmbrzl]

This syntax does not allow negative reals.

Good catch 👍
Fixed.

Probably allowing floats to start with a . not worth the grammar complexity.

I don't think it really adds complexity.

[bimalgaudel]

I don't think it really adds complexity.

It may be easy to implement in C++, however, that would be an extra construct to consider if the parsable string generated from our code is to be parsed by a third party, such as, a plugin that exchanges expression by serializing/deserializing them into this grammar.

[bimalgaudel]

Also, in

complex -> real ('+' | '-') real 'i';

the second real could be unsinged so that +|- followed by +|- is avoided.

[Krzmbrzl]

hat would be an extra construct to consider if the parsable string generated from our code is to be parsed by a third party, such as, a plugin that exchanges expression by serializing/deserializing them into this grammar.

I think first and foremost we should make the format easy to use. And just because SeQuant supports reading it that way, doesn't mean we have to use this format in deparsing.
Besides, with a grammar at hand, implementing a parser is super easy and can mostly be automated in either case.

Also, in
complex -> real ('+' | '-') real 'i';
the second real could be unsinged so that +|- followed by +|- is avoided.

I guess it would be mathematically correct, to allow for this, but I agree that it's likely nicer to forbid it.

[Krzmbrzl]

Note to self: The following tools could be used to play around with a formal grammar for the input online:

• http://lab.antlr.org/
• https://n.ethz.ch/~tgassmann/ebnf
• https://matthijsgroen.github.io/ebnf2railroad/try-yourself.html
• https://lexy.foonathan.net/playground/

[Krzmbrzl]

Okay, I sat down and created a grammar file that seems to be working alright for the inputs I have tested. The grammar mostly uses standard PEG syntax with a few sprinkles of syntactic sugar on top of it as provided by the cpp-peglib library:

Integer <- < [0-9]+ >
Float <- < Integer? '.' Integer >
Real <- Float / Integer
Imaginary <- Real 'i'
Complex <- Imaginary / Real
Constant <- Complex

# This is a very liberal rule that simply tries to exclude the most important
# non-ID characters (in ASCII range) and then allows everything else
Identifier <- ( [^\u0000-\u002f\u003a-\u0040\u005b-\u0060\u007b-\u00a0] / '_' )+

Variable <- < Identifier ('^*')? >

Index <- < Identifier >

Indices <- ','* Index (','+ Index)*

IndexGroups <- ';'* Indices (';'+ Indices)* ';'*

PredefinedSymm <- 'A' / 'S' / 'N' / 'bkS' / 'bkC' / 'bkN' / 'pS' / 'pN'

Symmetry <- PredefinedSymm

Tensor <- Identifier ('^*')? '[' IndexGroups ']' ( ':' Symmetry (',' Symmetry)* )?

Statistic <- 'F' / 'B'

NormalOrderedOperator <- Identifier '{' IndexGroups '}' (':' Statistic)?

Function <- '~' Identifier '(' [^)]* ')'


Nullary <- '(' Expression ')' / Function / Constant / Tensor / NormalOrderedOperator / Variable

UnaryOperator <- '+' / '-'

Unary <- UnaryOperator Nullary

BinaryOperator <- '+' / '-' / '*' / '/'

ExprAtom <- Unary / Nullary

InfixExpression <- ExprAtom ( BinaryOperator ExprAtom )* {
  precedence
    L - +
    L * /
}

Expression <- ExprAtom Expression / InfixExpression Expression?

Result <- Tensor / Variable

ResultExpression <- Result '=' Expression

%whitespace  <-  [ \t\r\n]*

You can try the grammar out by going to https://yhirose.github.io/cpp-peglib/, pasting the grammar on the left side and enter stuff on the right side (Enter ResultExpression as start rule before clicking Parse). If you want to, you can even inspect the abstract syntax tree (AST).

An example input that should contain more or less all features of the grammar is

Res = -1/2i * δ * γ * t{i1;a1} + ~symm(a1,i2) 2 * A[i1;a1] B[,a1;i1;␣;k3]:pN (4 - 5) * C^*[;;k3]:A - test Op{i1,i2;i3;i4,i5;;a9}:F bla^*

Please check whether you find valid inputs that the parser fails on or syntactically wrong inputs the parser accepts.

Note that contrary to the original suggestion in my post above, I decided to force function-like objects (symmetrizers) to be prefixed by a ~ in order to disambiguate them from a variable implicitly multiplied with an expression in parenthesis.

@evaleev I would suggest we switch from using Boost.Spirit to the abovementioned cpp-peglib library as I believe the parser implementation will be much more readable and a lot easier to work with (adapt). Additionally, this allows us to write the grammar in a file so that other programs could (in theory) use the PEG grammar and use it for their own purposes (though the grammar isn't fully standard PEG as whitespace and precedence handling would be a PITA).
This would introduce another dependency but I would consider that worth it (and the library consists only of a single header file).

[evaleev]

@Krzmbrzl I'm fine switching, but would like to talk this over during a SeQuant meetup. I will have a look in more detail when the ongoing trip(s) is over (2 weeks or so).

[evaleev]

@Krzmbrzl fyi, see #353 ... current parse does not support blanks in bras/kets (trying to add that required too much spirit voodoo).

[Krzmbrzl]

@evaleev Do you already have a syntax in mind for how to encode this? I guess we could do something like t{I1, , I2;...} though I don't think I like that given how subtle it is (and hence easy to miss). Maybe adding an explicit null might work though this isn't really elegant either.

[evaleev]

Yes, I thought commas are the most straightforward. Pedantic ppl can use ␣ to make the meaning more explicit.

[Krzmbrzl]

Extended grammar and example in #280 (comment) to allow for empty/null indices and for conjugated tensors.