# A Basic Pyth-like Syntax Checker

Pyth 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(""))
• Shouldn't the tree for 20100100 (in the first unbounded example) be [( [2 [0] [1 [0] ] ] [0] [1 [0]] [0] ]? The one you have has branches of 2, 0, 0, 1 and 0 - the second one shouldn't be there. Mar 15 '15 at 14:55
• @bcsb1001 Thanks and corrected. I wanted to show that unboundeds can go above 4. Mar 15 '15 at 14:57
• @Ypnypn there are test cases saying that its valid to have multiple roots Mar 15 '15 at 20:04
• Would you please add the test case for ())2)1))0"3())")) (which should be true, I think). Mar 16 '15 at 4:30
• @n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Added - it is indeed true (since it's basically ()210"" with a lot of no-ops) Mar 16 '15 at 4:55

# 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";

# Regex, PCRE flavor, 83 bytes

^(?3)*\)*$(()((?(2)|\)*)($$(?1)*($$|$)|0|"[^"]*.?|(1|(2|(3|4(?3))(?3))(?3))(?3))))?

Try it here.

# Regex, PCRE flavor, 85 bytes

^((?(3)|\)*)(?>$$(?2)*(()(?1))?($$|$)|0|"[^"]*.?|(1|(2|(3|4(?1))(?1))(?1))(?1)))*\)*$

Try it here.

Used some ideas in this dan1111's answer.

• (?2)*(()(?1))? is the final puzzle piece I was looking for. Nice find! ;) Mar 16 '15 at 8:09
• If I understand the (?2)*(()(?1))? part correctly, the (()(?1))? part never matches anything, since (?2)* already eats up everything that (()(?1))? can match, and this construct is used to set capturing group 3 when we enter ( and unset capturing group 3 when we are outside () construct (to allow for matching unpaired )). Mar 16 '15 at 9:20

# 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;
}

# 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
• I guess I should have been a bit clearer - you can assume that either the newline is never there, or is always there. Does that help? Mar 16 '15 at 3:34
• Would it be possible to use the fixed size stack program, but to set the size of the stack to the length of the input? Mar 16 '15 at 5:46
• @isaacg Since the input is stdin, we have no idea until it is read. I could easily have written a driver which uses a command line arg or string but golf has other priorities. The dynamic stack in 25 chars isn't bad by c standards, but I'm sure it can still be golfed.
– rici
Mar 16 '15 at 5:53

# 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)]
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
• Nice (ab)use of exceptions! You can save some spaces by swapping the order of the operands to == in the tests--putting the strings first means you can do if')'==q. I believe one of the break statements could be replaced with f=0, since that will get you out of the while f loop just as well. Finally, instead of assert x==y you can use 1/(x==y) for a ZeroDivisionError. ;) May 14 '15 at 23:21
• @DLosc, thanks for some very useful golfing tips. If I was among the leaders in the golfing competition, I would use your ideas to compete. As my entry is far from competitive (golf-wise), I would rather leave it as a mostly readable example. I have noted your clever techniques though for future use ;-) May 16 '15 at 11:02

# Pip, 88 72 bytes

Idea taken from Optimizer's CJam. 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 Replace 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.

# Javascript (ES6), 289288285282278244241 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,""))