Force whitespace around primitives inside parentheses while allowing contiguous parenthesis w/o whitespaces

[slavistan]

Hi! I'm trying to write a simple grammar to parse sets of numbers which allows to apply simple set operations such as conjunction &&, disjunction || and complement (with respect to some superset) !. When applying parentheses to construct more complex structures I want the primitive terms to be surrounded by whitespaces.

Here's a simplified version of what I have (ignoring actions and parsing of sets from comma-sep'd lists of numbers):

Expr
  = Expr0 (_+ '||' _+ Expr0)*

Expr0
  = Expr1 (_+ '&&' _+ Expr1)*

Expr1
  = '!' Expr1
  / Expr2

Expr2
  = "(" _+ Expr _+ ")"
  / Term

Term
  = [A-Za-z0-9]+
  //^^^^^^^^^^^^ simplified primitive terms for the sake of clarity
  
_ "whitespace"
  = [ \t\n\r]

This almost does the job, except that nested parentheses require whitespaces as well, as per Expr2, and this is precisely what I want to change: loosen up Expr2 to allow for contiguous nested parentheses without forced whitespces. E.g. what I want is

(( abc || def ) && ghi ) || jkl

which, however, does not work, as there's no whitespace in between the first two parentheses. What works with the above grammar is ( ( abc || def ) && ghi ) || jkl.

I've been trying to solve this surprisingly elusive problem for hours but I just can't get hold of it. The greedy parsing always comes to bite me in the butt. May I kindly ask you to have a look at this?

Thank you!

[Mingun]

Try to literally follow your description: include spaces to the Term rule and make them optional (or remove altogether) in all other places:

Term
  = _+ [A-Za-z0-9]+ (_+ / EOF)
  
_ "whitespace"
  = [ \t\n\r]

EOF = !.

[slavistan]

Thanks for your reply. Following your suggestions I've come up with this:

Expr
  = Expr0 ('||' Expr0)*

Expr0
  = Expr1 ('&&' Expr1)*

Expr1
  = '!' Expr1
  / Expr2

Expr2
  = "(" Expr ")"
  / Term
  
Term
  = _+ [A-Za-z0-9]+ (_+ / EOF)
  
_ "whitespace"
  = [ \t\n\r]

EOF = !.

Unfortunately, this now forces whitespaces around the terms (e.g. a simple abc won't do and has to have a leading whitespace character) and forbits whitespaces between contiguous parentheses (e.g. ( ( abc )) doesn't match; I want people to be able to use whitespaces, if they so chose).

Did I misinterpret your instructions?

[Mingun]

I've also say, that you could make spaces optional in other places ;) (highlight code with pegjs hint).

Actually it is not hard to convert your current grammar into one that you want. Just follow hints from parsing errors of your example input:

• allow spaces before logical operators: add $_* '||' ...
• allow spaces between ((: if you just add spaces after (, then this breaks things like ( Term ), so just try without spaces first, and then with spaces: '(' (Expr / _* Expr) ')'
• to make lone term possible without spaces just add this as a separate alternative to the start rule

In the end this grammar should cover your needs (note, that it allows things like (...)&&(...), but I think that you understand and accept that):

start
  = Expr
  / _* @Term

Expr
  = Expr0 (_* @'||' @Expr0)*

Expr0
  = Expr1 (_* @'&&' @Expr1)*

Expr1
  = '!' Expr1
  / Expr2

Expr2
  = "(" (Expr / _* @Expr) ")"
  / _+ @Term (_+ / EOF)

Term 'Term'
  = $[A-Za-z0-9]+
  
_ "whitespace"
  = [ \t\n\r]

EOF = !.

[slavistan]

that it allows things like (...)&&(...)

Unfortunately I must have whitespaces between the dyadic operators and the operands (e.g. ( abc || def ) && ghi). I've mentioned in another comment that the grammar I'm building is a little bit more complex and demands the use of whitespaces as separators when using operators and inside non-nested parentheses. Otherwise, the use of whitespaces is permitted, but not mandatory.

To give another example, consider this input:

((( abc || def ) && ghi ) || jkl ) && mno

Removing any whitespaces from this input makes it invalid, whereas adding whitespaces inbetween parentheses, terms and operators is valid (e.g. ( ( ( abc || def ) && ghi ) || jkl ) && mno is just fine).

I'm unable to adjust the grammar you suggested to account for these things, as has been my problem all along. A grammar that seems very close to the solution may have to be rewritten completely to account for that little thing that's missing.

I'll keep trying to find some other way, I think I may need to distinguish between nested parenthesized expressions and their unnested counterparts. Thank you for your help.

[reverofevil]

There are two approaches, depending on whether you want better performance of better error messages.

Performant version:

• entrypoint rule (first one) starts with whitespace: start = _ expr eof
• every terminal token ends with whitespace:
  • braced = "(" _ expr ")" _ -- just _ after every "..."
  • expr0 = expr1 ("+" _ expr1)* -- same
  • number = @$[0-9]+ _ -- every complex terminal token only ends with _

Better error messages:

• entrypoint rule has whitespace outside: start = _ expr _ eof
• non-terminals handle whitespace inside:
  • braced = "(" _ expr _ ")" -- _ goes only inside the rule, but not outside
  • expr0 = expr1 (_ "+" _ expr1)* -- _ only show up between expr1s, but either of expr1 that end up as leftmost or rightmost match don't match whitespact on the left and on the right correspongly
  • number = @$[0-9]+ -- nothing can be inside

Then you should never try to use grammar as a linter: if you make whitespace as " "+, you'll only get unreadable error messages, and probably they will go not where you expect them to go. Programs without spaces are grammatically correct. In general, grammar should be as permissive as possible, and more precise error messages should be generated on the next step.

Notation:

• _ = [ \r\n]*
• eof = !.

[slavistan]

never try to use grammar as a linter

The example I gave is a simplified version of a more complex grammar, whose "terms" may involve arbitrary characters except whitespaces (and ! characters, which serve as the complement operator). Thus whitespaces are syntactically necessary here. I just gave parsing lists of numbers as a surrogate, easy to understand problem. I should have explained my problem in more detail, my apologies.

I've tried to apply your instructions and came up with this grammar (performant version):

Start
  = _ Expr EOF

Expr
  = Expr0 ('||' _ Expr0)*

Expr0
  = Expr1 ('&&' _ Expr1)*

Expr1
  = '!' Expr1
  / Expr2

Expr2
  = "(" _ Expr _ ")" _
  / Term

Term
  = [A-Za-z0-9]+ _

_ "whitespace"
  = [ \t\n\r]*

EOF	= !.

This, however, does not force inner whitespaces for parentheses around terms (e.g. (abc) will parse just fine, whereas it should be illegal). The "better error messages" suggestions froze my browser tab when playing around with it in the peggy sandbox. It's likely that I misunderstood something.