from typing import Iterator, List, Any, Union
QUOTE = "quote"
COMMAND = "command"
ESCAPE = "escape"

def parse(string: str) -> Iterator[List[List[Union[int, str]]]]:
    state_stack: List[Any] = []
    state = COMMAND
    fragments: List[List[Union[int, str]]] = []
    fragment: List[Union[int, str]] = []
    fragment_piece: Union[int, str] = ""
    subsh_ctr = 0
    for c in string:
        if c == '\\' and state != ESCAPE:
            state_stack.append(state)
            state = ESCAPE
            continue
        if state == ESCAPE:
            fragment_piece += c  # type: ignore
            state = state_stack.pop()
            continue
        if c == '(' and state != QUOTE:
            if not fragment:
                raise SyntaxError("interpolation at start of command?")
            state_stack.append(state)
            state_stack.append((fragments, fragment, fragment_piece))
            fragments = []
            fragment = []
            fragment_piece = ""
            state = COMMAND
            subsh_ctr += 1
            continue
        if c == ')' and state != QUOTE:
            if state != COMMAND:
                raise SyntaxError("end of interpolation but not in command state?")
            if not isinstance(state_stack[-1], tuple):
                raise SyntaxError("end of interpolation that was never entered?")
            if not fragment_piece:
                raise SyntaxError("no command or trailing symbols")

            fragment.append(fragment_piece)

            if (state == QUOTE):
                raise SyntaxError("EOL while scanning string literal")

            fragments.append(fragment)
            yield fragments
            (fragments, fragment, fragment_piece) = state_stack.pop()
            state = state_stack.pop()
            fragment_piece = subsh_ctr
            continue

        if c == '"':
            state = QUOTE if (state == COMMAND) else COMMAND
            continue
        if c == "|" and state == COMMAND:
            fragments.append(fragment)
            fragment = []
            continue
        if c == ' ' and state == COMMAND:
            if fragment_piece != '':
                fragment.append(fragment_piece)
                fragment_piece = ""
            continue

        fragment_piece += c  # type: ignore


    if not fragment_piece:
        raise SyntaxError("no command or trailing symbols")

    fragment.append(fragment_piece)

    if (state == QUOTE):
        raise SyntaxError("EOL while scanning string literal")

    fragments.append(fragment)

    yield fragments