[Question]
  [
[Pyth](https://pyth.herokuapp.com/) is a golfing language based on Python. It uses prefix notation, with each command having a different arity (number of arguments it accepts).
Your task is to write a syntax checker for a (non-existent) Pyth-like language, Pith.
## Pith's syntax
Pith only has 8 single-char commands:
```
01234()"
```
`01234` each have arity of the corresponding number, and hence expect that many arguments after it. For example,
```
400010
```
is a correct Pith program because `4` is followed by four arguments `0` `0` `0` and `10`, the last of which is a `1` followed by the single argument `0`. To visualise this, we can look at the following tree:
```
      R
      |
      4
      |
-------------
|   |   |   |
0   0   0   1
            |
            0
```
where `R` is the root node. An alternative way to think about this is that each number refers to the number of children the corresponding node has in the tree above.
Here's another valid Pith program, with more than one base command:
```
210010
```
corresponding to
```
           R
           |
     -------------
     |           |
     2           1
     |           |
 ---------       0
 |       |
 1       0
 |
 0
```
On the other hand,
```
3120102100
```
is *not* a correct Pith program because the initial `3` only has two arguments, which we can see by looking at the tree below:
```
                R
                |
                3
                |
     ------------------------ ??
     |          |
     1          2
     |          |
     2        ------
     |        |    |
   ------     1    0
   |    |     |
   0    1     0
        |
        0
```
Next `(` starts an unbounded, and `)` ends an unbounded. An unbounded takes any number of arguments (greedily), and counts as a single argument to any parent command. Any unboundeds still open by the end of the program are automatically closed. A `)` command is not an error if no unboundeds are open — it just does nothing.\*
For instance, the Pith program
```
)31(0)0(201000100
```
corresponds to the tree
```
            R
            |
            3
            |
    ------------------------------
    |       |                    |
    1       0                    (
    |                            |
    (              -----------------------------
    |              |      |      |      |      |
    0              2      0      0      1      0
                   |                    |
                -------                 0
                |     |
                0     1
                      |
                      0
```
Empty unboundeds are okay, so `()` is a valid Pith program.
An invalid Pith program with an unbounded is
```
12(010
```
since the `2` only receives one argument (the unbounded).
Finally, `"` starts and ends a string, which is always 0 arity and counts as a single argument, e.g.
```
2"010""44)()4"
```
which is just a `2` being passed two string arguments `"010"` and `"44)()4"`. Like unboundeds, strings may also be empty, and any unclosed strings by the end of the program are automatically closed.
\*This part is different from the original Pyth which actually *does* do something in a case like `1)`, ending the 1-arity and raising an error.
## Input/output
Input will be a single non-empty string consisting of only the characters `01234()"`. You may optionally assume that an additional trailing newline is always present. You may write a function or a full program for this challenge.
You should output a truthy value if the input is syntactically valid Pith, or a falsy value otherwise. The truthy and falsy values must be fixed, so you can't output `1` for one valid program and `2` for another.
## Scoring
This is code-golf, so the code in the fewest bytes wins.
## Test cases
Truthy:
```
0
)
(
"
()
""
10
400010
210010
("")00
3"""""
(0)))0)1)0
2(2(2(0)0)0)0
2"010""44)()4"
)31(0)0(201000100
())2)1))0"3())"))
3("4321("301(0)21100"4")"123"00)40"121"31000""01010
```
Falsy:
```
1
1(310
(1)0)
12(010
4"00010"
3120102100
20(2((0)(0)))
2(2(2(0)0)0)01)
4(0102)00)00000
2"00"("00"2(""))
```
  
[Answer]
# CJam, 65 bytes
```
q'"/La+2%{0s*}:Z~_,:L')*+{L{4{)_Z+s/Z}/L{'(\Z')++/Z}/}*')-}2*0s-!
```
*Gosh, I wish CJam had Regex, this could have been completed in less than 50 bytes then*
The main idea is to keep reducing stuff to `0` i.e. `10` to `0`, `200` to `0` and so on. Once that is done, we reduce all matched brackets to `0`, i.e. `()` to `0`, `(0)` to `0`, `(00)` to `0` and so on. The we repeat the cycle `L` times, where `L` is the input length.
The input string initially goes through extra processing where we adjust for unmatched `"` and add lots of `)` to compensate for unmatched `(`
This ensures that after all the iterations, we should only have `0` (and no-op `)`) left in the string.
*Update - fixed a bug where top level `)` no-op are considered harmful*
**Code expansion**
```
q'"/La+2%{0s*}:Z~_,:L')*      "Part 1 - Preprocessing";
q'"/                          "Read the input and split it on quote";
    La+                       "Add an extra empty array to the split array to compensate";
                              "for unmatched ending quote";
        2%                    "Take every other splitted part, ignoring the contents";
                              "of the strings in the code";
          {0s*}:Z~            "Join the parts by string 0. Also create a function Z";
                              "that does that for future use. We are now done with";
                              "reducing "XYZ" to 0 ";
                  _,:L        "Store the length of the remaining code in L";
                      ')*     "Append L ) to the string to compensate for unmatched (";
{L{4{)_Z+s/Z}/L{'(\Z')++/Z}/}*')-}2*   "Part 2 - the reducing loop";
 L{                         }*         "Run the reduction logic L times";
   4{)_Z+s/Z}/                         "Part 2a - reducing arities";
   4{       }/                         "Run the iteration for 0, 1, 2 and 3";
     )_                                "Increment the iteration number and make a copy";
       Z+s                             "Get that many 0 and append it to the number";
          /Z                           "Split the code onto this number and convert it";
                                       "to 0. This successfully reduces 10, 200, ";
                                       "3000 and 4000 to 0";
              L{'(\Z')++/Z}/           "Part 2b - reducing groups";
              L{          }/           "Run the iteration for 0 through L - 1";
                '(\Z')++               "Get the string '(<iteration number of 0>)'";
                        /Z             "split on it and join by 0. This successfully";
                                       "reduces (), (0), (00) and so on .. to 0";
                              ')-      "After running the part 2 loop L times, all";
                                       "reducible arities and brackets should be reduced";
                                       "except for cases like '30)00' where the no-op )";
                                       "breaks the flow. So we remove ) from the code";
                                       "and run Part 2 L times again";
0s-!                          "Now, if the code was valid, we should only have 0 in the";
                              "remaining code. If not, the code was invalid";
```
[Try it online here](http://cjam.aditsu.net/#code=q'%22%2FLa%2B2%25%7B0s*%7D%3AZ~_%2C%3AL')*%2B%7BL%7B4%7B)_Z%2Bs%2FZ%7D%2FL%7B'(%5CZ')%2B%2B%2FZ%7D%2F%7D*')-%7D2*0s-!&input=3(%224321(%22301(0)21100%224%22)%22123%2200)40%22121%2231000%22%2201010) or [run the whole suite](http://cjam.aditsu.net/#code=qN%2F%7B_'%22%2FRa%2B2%25%7B0s*%7D%3AZ~_%2C%3AL')*%2B%7BL%7B4%7B)_Z%2Bs%2FZ%7D%2FL%7B'(%5CZ')%2B%2B%2FZ%7D%2F%7D*')-%7D2*0s-!%22%20-%3E%20%22%5CN%7D%2F&input=0%0A2)00%0A)%0A(%0A%22%0A()%0A%22%22%0A10%0A400010%0A210010%0A(%22%22)00%0A3%22%22%22%22%22%0A2(2(2(0)0)0)0%0A2%22010%22%2244)()4%22%0A)31(0)0(201000100%0A3(%224321(%22301(0)21100%224%22)%22123%2200)40%22121%2231000%22%2201010%0A1%0A1(310%0A12(010%0A4%2200010%22%0A3120102100%0A20(2((0)(0)))%0A2(2(2(0)0)0)01)%0A4(0102)00)00000%0A2%2200%22(%2200%222(%22%22)))
[Answer]
# Regex, PCRE flavor, 83 bytes
```
^(?3)*\)*$(()((?(2)|\)*)(\((?1)*(\)|$)|0|"[^"]*.?|(1|(2|(3|4(?3))(?3))(?3))(?3))))?
```
[Try it here.](https://regex101.com/r/vL2eY0/4)
# Regex, PCRE flavor, 85 bytes
```
^((?(3)|\)*)(?>\((?2)*(()(?1))?(\)|$)|0|"[^"]*.?|(1|(2|(3|4(?1))(?1))(?1))(?1)))*\)*$
```
[Try it here.](https://regex101.com/r/vL2eY0/1)
Used some ideas in [this dan1111's answer](https://codegolf.stackexchange.com/a/47571/25180).
[Some explanations about `(?2)*(()(?1))?`](https://codegolf.stackexchange.com/a/47826/25180).
[Answer]
# 80386 Assembler, 97 bytes
Hex dump:
```
0000000: 8b54 2404 5589 e531 c96a ff8a 022c 303c  .T$.U..1.j...,0<
0000010: f275 04f6 d530 c084 ed75 263c f875 0141  .u...0...u&<.u.A
0000020: 3cf9 750f 84c9 7419 4958 3c00 7c03 50eb  <.u...t.IX<.|.P.
0000030: 2430 c084 c075 0958 483c ff7f 0140 ebf3  $0...u.XH<...@..
0000040: 5042 8a02 84c0 75c5 4a84 edb0 2275 be84  PB....u.J..."u..
0000050: c9b0 2975 b85a 31c0 39e5 7501 4089 ec5d  ..)u.Z1.9.u.@..]
0000060: c3                                       .
```
This runs through the input once, pushing numbers greater than zero onto the stack and decrementing them when a zero is processed. Unboundeds are processed as a -1.
Function prototype (in C) (function returns 0 if invalid and 1 if valid):
```
int __cdecl test(char *in);
```
Equivalent assembly (NASM):
```
bits 32
; get input pointer into edx
mov edx, [esp+4]                ; 8B 54 24 04
; save ebp; set ebp = esp
push ebp                        ; 55
mov ebp, esp                    ; 89 E5
; clear ecx
xor ecx, ecx                    ; 31 C9
; push base -1
push byte(-1)                   ; 6A FF
; get top char
mov al, [edx]                   ; 8A 02
    sub al, 0x30                ; 2C 30
    ; if al == quote
    cmp al, 0xF2                ; 3C F2
    jne $+6                     ; 75 04
        ; set ch (in quote?) to opposite
        not ch                  ; F6 D5
        ; set value to 0
        xor al, al              ; 30 C0
    ; if in quote, continue
    test ch, ch                 ; 84 ED
    jnz $+40                    ; 75 26
    cmp al, 0xF8                ; 3C F8
    jne $+3                     ; 75 01
        ; increment cl=depth
        inc ecx                 ; 41
    cmp al, 0xF9                ; 3C F9
    jne $+17                    ; 75 0F
        ; check depth = 0
        test cl, cl             ; 84 C9
        jz $+27                 ; 74 19
        ; decrement cl=depth
        dec ecx                 ; 49
        ; pop and check -1
        pop eax                 ; 58
        cmp al, 0               ; 3C 00
        jl $+5                  ; 7C 03
            push eax            ; 50
            jmp $+38            ; EB 24
        xor al, al              ; 30 C0
    test al, al                 ; 84 C0
    jnz $+11                    ; 75 09
        pop eax                 ; 58
        dec eax                 ; 48
        cmp al, -1              ; 3C FF
        jg $+3                  ; 7F 01
            inc eax             ; 40
        jmp $-11                ; EB F3
    push eax                    ; 50
    inc edx                     ; 42
    mov al, [edx]               ; 8A 02
    test al, al                 ; 84 C0
    jnz $-57                    ; 75 C5
    dec edx                     ; 4A
    ; in quote?
    test ch, ch                 ; 84 ED
    mov al, 0x22                ; B0 22
    jnz $-64                    ; 75 BE
    ; depth not zero?
    test cl, cl                 ; 84 C9
    mov al, 0x29                ; B0 29
    jnz $-70                    ; 75 B8
; pop base -1
pop edx                         ; 5A
; set return value based on ebp/esp comparison
xor eax, eax                    ; 31 C0
cmp ebp, esp                    ; 39 E5
jne $+3                         ; 75 01
inc eax                         ; 40
; restore esp
mov esp, ebp                    ; 89 EC
; restore ebp
pop ebp                         ; 5D
; return
ret                             ; C3
```
The following code in C can be used with GCC on a POSIX system to test:
```
#include <sys/mman.h>
#include <stdio.h>
#include <string.h>
int main(){
    char code[] = {
        0x8b, 0x54, 0x24, 0x04, 0x55, 0x89, 0xe5, 0x31, 0xc9, 0x6a, 0xff,
        0x8a, 0x02, 0x2c, 0x30, 0x3c, 0xf2, 0x75, 0x04, 0xf6, 0xd5, 0x30, 
        0xc0, 0x84, 0xed, 0x75, 0x26, 0x3c, 0xf8, 0x75, 0x01, 0x41, 0x3c, 
        0xf9, 0x75, 0x0f, 0x84, 0xc9, 0x74, 0x19, 0x49, 0x58, 0x3c, 0x00, 
        0x7c, 0x03, 0x50, 0xeb, 0x24, 0x30, 0xc0, 0x84, 0xc0, 0x75, 0x09, 
        0x58, 0x48, 0x3c, 0xff, 0x7f, 0x01, 0x40, 0xeb, 0xf3, 0x50, 0x42, 
        0x8a, 0x02, 0x84, 0xc0, 0x75, 0xc5, 0x4a, 0x84, 0xed, 0xb0, 0x22, 
        0x75, 0xbe, 0x84, 0xc9, 0xb0, 0x29, 0x75, 0xb8, 0x5a, 0x31, 0xc0, 
        0x39, 0xe5, 0x75, 0x01, 0x40, 0x89, 0xec, 0x5d, 0xc3,
    };
    void *mem = mmap(0, sizeof(code), PROT_WRITE|PROT_EXEC, MAP_ANON|MAP_PRIVATE, -1, 0);
    memcpy(mem, code, sizeof(code));
    int __cdecl (*test)(char *) = (int __cdecl (*)(char *)) mem;
    #define TRY(s) printf(s ": %d\n", test(s))
    printf("Truthy tests:\n");
    TRY("0");
    TRY(")");
    TRY("(");
    TRY("\"");
    TRY("()");
    TRY("\"\"");
    TRY("10");
    TRY("400010");
    TRY("210010");
    TRY("(\"\")00");
    TRY("3\"\"\"\"\"");
    TRY("(0)))0)1)0");
    TRY("2(2(2(0)0)0)0");
    TRY("2\"010\"\"44)()4\"");
    TRY(")31(0)0(201000100");
    TRY("())2)1))0\"3())\"))");
    TRY("3(\"4321(\"301(0)21100\"4\")\"123\"00)40\"121\"31000\"\"01010");
    printf("\nFalsy tests:\n");
    TRY("1");
    TRY("1(310");
    TRY("(1)0)");
    TRY("12(010");
    TRY("4\"00010\"");
    TRY("3120102100");
    TRY("20(2((0)(0)))");
    TRY("2(2(2(0)0)0)01)");
    TRY("4(0102)00)00000");
    TRY("2\"00\"(\"00\"2(\"\"))");
    munmap(mem, sizeof(code));
    return 0;
}
```
[Answer]
# lex, 182 bytes (157 w/ fixed-size stack)
These programs require the input to be a single new-line terminated string of valid characters.
```
%%
 int n=0,s=0,*t=0;
[0-4] n+=*yytext-48-!!n;
\( (t=realloc(t,(s+1)*sizeof n))[s++]=n-!!n;n=0;
\) if(s&&n)exit(1);s&&(n=t[--s]);
\"[^"]*.? n-=!!n;
\n while(s)t[--s]&&n++;exit(!!n);
```
The above program will segfault if it runs out of memory, which could theoretically happen if you give it enough `(`. But since a segfault counts as failure, I'm taking that as "falsey", although the problem description doesn't say what to do if resources don't suffice.
I cut it down 157 bytes by just using a fixed-size stack, but that seemed like cheating.
```
%%
 int n=0,s=0,t[9999];
[0-4] n+=*yytext-48-!!n;
\( t[s++]=n-!!n;n=0;
\) if(s&&n)exit(1);s&&(n=t[--s]);
\"[^"]*.? n-=!!n;
\n while(s)t[--s]&&n++;exit(!!n);
```
To compile:
```
flex -o pith.c pith.l    # pith.l is the above file
c99 -o pith pith.c -lfl
```
Test:
```
while IFS= read -r test; do
  printf %-78s "$test"
  if ./pith <<<"$test"; then echo "OK"; else echo "NO"; fi
done <<EOT
0
)
(
"
()
""
10
400010
210010
("")00
3"""""
2(2(2(0)0)0)0
2"010""44)()4"
)31(0)0(201000100
3("4321("301(0)21100"4")"123"00)40"121"31000""01010
1
1(310
12(010
4"00010"
3120102100
20(2((0)(0)))
2(2(2(0)0)0)01)
4(0102)00)00000
2"00"("00"2(""))
EOT
```
Test output:
```
0                                                                             OK
)                                                                             OK
(                                                                             OK
"                                                                             OK
()                                                                            OK
""                                                                            OK
10                                                                            OK
400010                                                                        OK
210010                                                                        OK
("")00                                                                        OK
3"""""                                                                        OK
2(2(2(0)0)0)0                                                                 OK
2"010""44)()4"                                                                OK
)31(0)0(201000100                                                             OK
3("4321("301(0)21100"4")"123"00)40"121"31000""01010                           OK
1                                                                             NO
1(310                                                                         NO
12(010                                                                        NO
4"00010"                                                                      NO
3120102100                                                                    NO
20(2((0)(0)))                                                                 NO
2(2(2(0)0)0)01)                                                               NO
4(0102)00)00000                                                               NO
2"00"("00"2(""))                                                              NO
```
[Answer]
# Python 2, 353 bytes
The parse function steps through the tokens one at a time and builds a tree of the program structure. Invalid programs trigger an exception which causes a zero (Falsy) to be printed, otherwise successful parsing results in a one.
```
def h(f,k=0):
 b=[]
 if k:
  while f:b+=[h(f)]
  return b
 q=f.pop(0)
 if q==')':return[]
 elif q=='"':
  while f:
   q+=f.pop(0)
   if q[-1]=='"':break
 elif q=='(':
  while f:
   if f and f[0]==')':f.pop(0);break
   b+=h(f)
 else:
  for i in range(int(q)):b+=h(f)
  assert len(b)==int(q)
 return[[q,b]]
try:h(list(raw_input()));r=1
except:r=0
print r
```
The output of the tests showing the parser output:
```
------------------------------------------------------------
True: 0
    0
------------------------------------------------------------
True: )
------------------------------------------------------------
True: (
    (
------------------------------------------------------------
True: "
    "
------------------------------------------------------------
True: ()
    (
------------------------------------------------------------
True: ""
    ""
------------------------------------------------------------
True: 10
    1
        0
------------------------------------------------------------
True: 400010
    4
        0
        0
        0
        1
            0
------------------------------------------------------------
True: 210010
    2
        1
            0
        0
    1
        0
------------------------------------------------------------
True: ("")00
    (
        ""
    0
    0
------------------------------------------------------------
True: 3"""""
    3
        ""
        ""
        "
------------------------------------------------------------
True: 2(2(2(0)0)0)0
    2
        (
            2
                (
                    2
                        (
                            0
                        0
                0
        0
------------------------------------------------------------
True: 2"010""44)()4"
    2
        "010"
        "44)()4"
------------------------------------------------------------
True: )31(0)0(201000100
    3
        1
            (
                0
        0
        (
            2
                0
                1
                    0
            0
            0
            1
                0
            0
------------------------------------------------------------
True: 3("4321("301(0)21100"4")"123"00)40"121"31000""01010
    3
        (
            "4321("
            3
                0
                1
                    (
                        0
                2
                    1
                        1
                            0
                    0
            "4"
        "123"
        0
    0
    4
        0
        "121"
        3
            1
                0
            0
            0
        ""
    0
    1
        0
    1
        0
------------------------------------------------------------
False: 1
0
------------------------------------------------------------
False: 1(310
0
------------------------------------------------------------
False: 12(010
0
------------------------------------------------------------
False: 4"00010"
0
------------------------------------------------------------
False: 3120102100
0
------------------------------------------------------------
False: 20(2((0)(0)))
0
------------------------------------------------------------
False: 2(2(2(0)0)0)01)
0
------------------------------------------------------------
False: 4(0102)00)00000
0
------------------------------------------------------------
False: 2"00"("00"2(""))
0
```
The code before the minifier:
```
def parse(tokens, first=False):
    toklist = []
    if first:
        while tokens :
            toklist += [parse(tokens)]
        return toklist
    tok = tokens.pop(0)
    if tok == ')' :
        return []
    elif tok == '"':
        while tokens:
            tok += tokens.pop(0)
            if tok[-1] == '"' :
                break
    elif tok == '(':
        while tokens:
            if tokens and tokens[0] == ')' :
                tokens.pop(0);
                break
            toklist += parse(tokens)
    else:
        for i in range(int(tok)) :
            toklist += parse(tokens)
        assert len(toklist) == int(tok)
    return [[tok, toklist]]
try :
    parse(list(raw_input()));
    r = 1
except :
    r = 0
print r
```
[Answer]
# [Pip](http://github.com/dloscutoff/pip), ~~88~~ 72 bytes
Idea taken from [Optimizer's CJam](https://codegolf.stackexchange.com/a/47809/16766). My original stab at the problem with a recursive descent parser was... rather longer.
```
Qpz:,5.iX,5AL'(.0X,#p.')p^:'"Fj,#pIj%2p@j:0p:Jpp.:')X#pL#ppR:z0!pRM')Rz0
```
Formatted, with explanation:
```
Qp                Query user for p
z:                Store the following list in z:
  ,5 . 0X,5         For x in range(5), concatenate x zeros to it
  AL                (append list)
  '(. 0X,#p .')     For x in range(len(p)), concatenate x zeros inside parens
p^: '"            Split p on " and assign result back to p
Fi,#p             Loop over the indices of the resulting list:
 Ii%2               If index is odd:
  p@i:0               Replace that item with 0
p: Jp             Concatenate the results and assign back to p
p.: ')X#p         Append len(p) closing parens to p
L#p               Loop len(p) times:
 pR:z0              Replace every occurrence in p of items of z with 0
! pRM')Rz0        Remove ) from result and replace z with 0 one more time; then
                  take logical negation, which will be true iff string is empty OR
                  consists only of zeros
```
Interesting tricks:
* Many operators work item-wise on lists and ranges. So `0X,5`, for example, is `0 X [0 1 2 3 4] == ["" "0" "00" "000" "0000"]`.
* As of a few days ago, the ternary `R`eplace operator can take a list for any of its arguments: `"abracadabra" R ["br" "ca"] 'b` gives `ababdaba`, for example. I make good use of this feature with `z` here.
* Falsy values in Pip include the empty string `""`, empty list `[]`, and any scalar that is zero. Thus, `0` is false, but also `0.0` and `"0000000"`. This feature is inconvenient sometimes (to test whether a string is empty, one must test its length because `"0"` is false too), but for this problem it's perfect.
[Answer]
# Javascript (ES6), ~~289~~ ~~288~~ ~~285~~ ~~282~~ ~~278~~ ~~244~~ ~~241~~ 230 bytes
```
c=prompt(k="0"),j=c[l="length"];if((c.match(/"/g)||[])[l]%2)c+='"';c=c[R="replace"](/".*?"/g,k);c+=")".repeat(j);while(j--)c=c[R](/\(0*\)/,k)[R](/10/g,k)[R](/200/g,k)[R](/3000/g,k)[R](/40000/g,k);alert(!c[R](/0/g,"")[R](/\)/g,""))
```
]