Inverse parentheses 2025-12-20
Have you ever noticed that lots of programming languages let you use parentheses to group operands, but none use them to ungroup them? No? Well let’s pretend this is a normal thing to be thinking about, and see what we can do about it.
Grouping with parentheses is relatively easy to add to a language grammar. The rule that accepts atomic things like 37 simply needs to also accept an opening paren, at which point it will recursively parse an entire expression, and then eat a closing paren.
def parse_atom ( lex ): r = next ( lex ) if r [ 0 ] == 'integer' : return int ( r [ 1 ]) elif r [ 0 ] == '(' : expr = parse_expr ( lex ) s = next ( lex ) if s [ 0 ] != ')' : raise ParseError ( "missing close paren" ) return expr else : raise ParseError ( f "unexpected { r [ 0 ] } " )
Anti-grouping isn’t quite as straightforward. Our parser can’t follow the structure of the parentheses, because then it wouldn’t be following the structure of the expression—the whole point is that these are dissimilar.
I don’t know if it’s possible to write a pure parser that does this. But purity is overrated anyway. I decided to take inspiration from another language with a weird grouping system.
Python
Did you know that Python’s grammar has braces? You just don’t type them. The tokeniser keeps track of the indentation level and inserts special tokens when it changes. The parser itself doesn’t need to worry about counting whitespace; it just sees blocks of statements bracketed by INDENT and DEDENT , which are easy to parse.
As it happens, Python’s tokeniser also knows when it’s inside a parenthesised expression. Indentation inside parens is not significant, and this is implemented by tracking the paren nesting depth and suppressing INDENT and DEDENT while it’s non-zero.
What if we used the same trick? Instead of trying to do all this in the parser somehow, the tokeniser could track its nesting depth, and emit a “friendliness” score for each token. Then we can simply parse operators in ascending order of friendliness.
... continue reading