[Help-bash] Does the parser backtrack?

[Daniel Martí]

(please keep me in CC as I'm not subbed)

Hello everyone,

I'm writing a shell/bash parser from scratch in Go (don't ask why) and
I've just hit something weird.

Telling the difference between $(( - arithmetic expansion - and $( ( -
subshell inside a command substitution - should be easy:

         $ echo $((1+2))
        3
         $ echo $( (echo foo) | cat)
        foo

But sometimes, bash doesn't treat $(( as the start of an arithmetic
expansion.

         $ echo $((echo foo) | cat)
        foo

This seems weird to me, as $(( is a POSIX Shell token. Surely enough,
this black magic doesn't work elsewhere:

        dash: 1: Syntax error: Missing '))'
        ash: syntax error: missing '))'

The only way I can think bash is doing this is by backtracking if $(( is
not followed by a valid arithmetic expression, or if it's not terminated
with )) as expected, in which case it retries the parsing as if it had
seen $( (. Am I correct in assuming that?

I'm especially confused by this because so far I've written an almost
complete bash parser as a recursive descent parser without backtracking,
i.e. treating bash as LL(k). But if indeed I need to backtrack to retry
$(( as if it were $( (, the number of lookahead tokens is unbounded and
I would be looking at LL(*). I wonder if bash was designed this way on
purpose.

I've filed a bug on my side about this too:
https://github.com/mvdan/sh/issues/30

Any help will be appreciated :)

-- 
Daniel Martí - address@hidden - https://mvdan.cc/