#!/bin/bash : <<'````````bash' # Programming Exercise 2: Parser Remark: this exercise is part of a series, which will continue for the following weeks. ## Language Specification We will cover a B-like subset of C, with the minor addition of a sized dereference. Some parts of the language are optional for the homework, see below. program: function* function: ident "(" paramlist? ")" block paramlist: ident ("," ident)* block: "{" declstmt* "}" declstmt: ("auto" | "register") ident "=" expr ";" | statement statement: "return" expr? ";" | block | "while" "(" expr ")" statement | "if" "(" expr ")" statement ("else" statement)? | expr ";" expr: "(" expr ")" | ident "(" arglist? ")" | ident | number | "-" expr | "!" expr | "~" expr | "&" expr | expr "[" expr sizespec? "]" | expr "+" expr | expr "-" expr | expr "*" expr | expr "/" expr | expr "%" expr | expr "<<" expr | expr ">>" expr | expr "<" expr | expr ">" expr | expr "<=" expr | expr ">=" expr | expr "==" expr | expr "!=" expr | expr "&" expr | expr "|" expr | expr "^" expr | expr "&&" expr | expr "||" expr | expr "=" expr arglist: expr ("," expr)* sizespec: "@" number ident: r"[a-zA-Z_][a-zA-Z0-9_]*" number: r"[0-9]+" Additional specifications: - Comments start with `//`, where the rest of the line is ignored. - Whitespace is ignored, except to separate tokens (as in C). - Multi-char operators like `||` are never treated as `|` `|`, unless there is whitespace in between (as in C). - Keywords are `auto` `register` `if` `else` `while` `return`; they are never identifiers. - The callee of function calls must be an unparenthesized identifier and never refers to a variable, even if a variable with the same name exists (NOT as in C). For example, `fn(a)` is always a function call, `(fn)(a)` is illegal. - For identifiers used to refer to variables, the variable must be declared in the current or a parent block; parameters are accessible in the entire function. Parameters belong to the outermost block of the function. Variable shadowing in nested scopes is permitted (as in C); identifiers always reference the variable in the most inner scope. - Declarations make their variable visible at their end, i.e. `f(){register a = a;}` is illegal while `f(a){{register a=a;}}` assigns the parameter to the variable. (NOT as in C) - Operator precedence and associativity: 14, left-assoc: [] 13, right-assoc: all unary operators (- ! ~ &) 12, left-assoc: * / % 11, left-assoc: + - 10, left-assoc: << >> 9, left-assoc: < > <= >= 8, left-assoc: == != 7, left-assoc: & 6, left-assoc: ^ 5, left-assoc: | 4, left-assoc: && 3, left-assoc: || 1, right-assoc: = - The left-hand side of the assignment operator (`=`) and the operand of the address-of operator (unary `&`) must be a subscript (`a[b]`) or an identifier. - Variables declared with `register` and parameters are not permitted as operand of the address-of operator (unary "&"). - Valid size specifiers for subscripts are 1, 2, 4, and 8; if omitted, it defaults to 8. - Defining multiple functions of the same name is illegal, as is defining or calling a function with a different number of parameters. For example, defining `foo(a)` and calling `foo(1, 2)` shall yield an error. Optional operators: - The following binary operators are optional. While it is suggested to implement them, you do not need to and can also stop implementing them in subsequent homeworks. Operator list: `* / % << >> <= >= & ^ |` Behavioral specification: - The signed integer datatype is 64-bit sized, other data types do not exist. - One byte has 8 bits; the byte order is little endian. - A subscript interprets the left operand as address and the right operand inside the brackets as offset, which is scaled by the size specifier. I.e., `&a[b@X]` refers to the X bytes at address `a + X*b`. When loading from a reduced size (i.e., 1/2/4), as many bytes as specified are loaded from memory and sign-extend to a full integer; stores truncate. Note that therefore `a[b]` is not equivalent to `b[a]` (different than in C). - Integer overflow is defined as in two's complement (like -fwrapv in GCC). - Everything else is handled as in ANSI C, including short-circuiting behavior for `&&` and `||`. ## Example program gauss(x) { register res = -0; while (x > 0) { res = res + x; x = x - 1; } return res; } ifTest(x) { if (x < -5) return; x = x + 3; } isBool(x) { return !!x == x; } callTest(a, b) { register c = foo(a, b); return bar(c, a) + baf(a) + baz(c); } baz(a) { return; } unreachableCode(a) { if (a > 0) return a; else return -a; return a + 1; } foo(a, b) { a[b] = b; return a[b] + a[b@1]; } addrof(ptr) { auto var = 1; ptr[1] = &var; register ptr2 = &ptr[1]; ptr2[0] = 2; return var; } ## Implementation Implement a parser for the specified language, which creates a full in-memory AST if, and only if, the input program is valid. Dump the AST to standard output for verification in form of S-expressions. You can replace variable names with other identifiers (e.g., numbers), as long as the same variable is represented by the same identifier (otherwise, testing is difficult). When printing, use the following naming scheme for the first member: - Expressions use use their operator symbol (e.g., `+`, `[]`), except unary minus, which uses `u-` to disambiguate. - Block: `block`; return: `return`; if: `if`. - All others are not tested and therefore have no requirements. Example: // Input: fn(a,b,c) { return a + (b + c); } // Ok: (program (func "fn" (paramlist "a" "b" "c") (block (return (+ "a" (+ "b" "c")))))) // Also ok: (func fn (params (param x1) (param x2) (param x3)) (block (return (+ x1 (+ x2 x3)))))) You can write a tokenizer and parser by hand (probably easiest, but needs more code) or use tools like Flex/Bison (probably more effort). Design an AST data structure, which you construct while parsing. (Hint: an AST node might have a fixed or dynamic number of children and perhaps also store an additional number or string.) Verify the semantic soundness (see above) of the AST during or after parsing. ## Command Line Interface usage: ./bc0 (-a|-c) program_file B compiler. Exit with non-zero status code on invalid input. -a: print AST as S-Expressions. -c: syntax/semantic check only (build AST nonetheless). No output other than the exit code. program_file: file that contains the input program Note that `program_file` is not necessarily a regular file, but can also be a pipe as used in the tests below, where you cannot determine the input size without reading it. The option `-c` is intended for benchmarking the parser. You can add extra options, e.g., to control optimizations or for debugging, but do not assign `-l`, `-i`, `-r`, and `-S`, which will be used in subsequent homework. ## Analysis (write answers as comment in your code) Analyze the execution time of your parser and the size of the final AST for a large input program. What is the asymptotic run-time of your parser? Can you find an example, where the total memory footprint of the AST grows super-linear with the input program size? ## Submission - Submission deadline: 2024-11-06 23:59 - Submit using `curl --data-binary "@" 'https://db.in.tum.de/teaching/ws2425/codegen/submit.py?hw=2&matrno='` - Write your solution in a single C++ file. - Include answers to theory questions as comments at the top of the source file. - Make sure your submission passes as many tests as possible from this test script. - Avoid dependencies, no build systems other than Makefile, etc. - If you need more than just the C++ file (e.g., for a parser generator), combine all files s.t. this command sequence works: `split-file somedir || cp somedir/bc0.cc; cd somedir; bash ` ````````bash set -euo pipefail FAILED=0 testcase_ok() { ./bc0 -c "$2" >/dev/null || { echo "FAILED: $1 (erroneously rejected)"; FAILED=1; }; } testcase_chk() { ./bc0 -a "$2" | "${@:3}" || { echo "FAILED: $1"; FAILED=1; }; } testcase_err() { ! ./bc0 -c "$2" 2>/dev/null || { echo "FAILED: $1 (erroneously accepted)"; FAILED=1; }; } CXX=g++ CXXFLAGS="-O3 -Wall -Wextra -std=c++20" make bc0 # NOTE: testcase_ok = should accept; testcase_err = should fail with an error. # Parameters testcase_ok "empty program" <(echo "") testcase_ok "simple function" <(echo "fn(){}") testcase_ok "params 1" <(echo "fn(a){}") testcase_ok "params 2" <(echo "fn(a,b){}") testcase_err "params 3 (duplicate)" <(echo "fn(a,a){}") testcase_err "params 4 (duplicate)" <(echo "fn(a,b,a){}") # Invalid tokens testcase_err "invalid token 1" <(echo '`') testcase_err "invalid token 2" <(echo '\') testcase_err "invalid token 3" <(echo -e '\1') testcase_err "unexpected token 1" <(echo '% fn(){}') testcase_err "unexpected token 2" <(echo '! fn(){}') testcase_err "unexpected token 3" <(echo '* fn(){}') testcase_err "unexpected token 4" <(echo '{} fn(){}') testcase_err "unexpected token 5" <(echo '( fn(){}') testcase_err "unexpected token 6" <(echo '+ fn(){}') testcase_err "unexpected token 7" <(echo 'fn(){} %') testcase_err "unexpected token 8" <(echo 'fn(){} !') testcase_err "unexpected token 9" <(echo 'fn(){} *') testcase_err "unexpected token 10" <(echo 'fn(){} {}') testcase_err "unexpected token 11" <(echo 'fn(){} (') testcase_err "unexpected token 12" <(echo 'fn(){} +') testcase_err "unexpected token 13" <(echo 'fn 0(){}') testcase_err "unexpected token 14" <(echo '0(){}') # Identifiers testcase_ok "valid ident 1" <(echo 'f(){}') testcase_ok "valid ident 2" <(echo 'fffffffff(){}') testcase_ok "valid ident 3" <(echo 'f_(){}') testcase_ok "valid ident 4" <(echo 'f0(){}') testcase_ok "valid ident 5" <(echo 'f0_9A(){}') testcase_ok "valid ident 6" <(echo '_09(){}') testcase_ok "valid ident 7" <(echo '_01234567889(){}') testcase_ok "valid ident 8" <(echo 'abcdefghijklmnopqrstuvwxyz(){}') testcase_ok "valid ident 9" <(echo 'ABCDEFGHIJKLMNOPQRSTUVWXYZ(){}') testcase_err "invalid ident 1" <(echo 'f1+(){}') testcase_err "invalid ident 2" <(echo 'f1-(){}') testcase_err "invalid ident 3" <(echo 'f1#(){}') testcase_err "invalid ident 4" <(echo 'f1$(){}') testcase_err "invalid ident 5" <(echo 'f1[(){}') testcase_err "invalid ident 6" <(echo 'f1=(){}') testcase_err "invalid ident 7" <(echo '1(){}') testcase_err "invalid ident 8" <(echo '1_(){}') # Comments testcase_ok "comment 1" <(echo -e "//comment") testcase_ok "comment 2" <(echo -e "f(){}//comment {") testcase_ok "comment 2" <(echo -e "f()//comment {\n{}") testcase_err "comment 2" <(echo -e "f(){//}") testcase_err "comment 2" <(echo -e "f(){//}\n{//}}") testcase_ok "comment 2" <(echo -e "f(){//}\n{//}}\n}}") # Return testcase_ok "return with value 1" <(echo "f() { return 1; }") testcase_ok "return with value 2" <(echo "f(a) { return a; }") testcase_ok "return with value 3" <(echo "f(b) { return b; }") testcase_ok "return without value" <(echo "f() { return; }") # Block testcase_ok "block 1" <(echo "fn(){{return 1;} return 1;}") testcase_ok "block 2" <(echo "fn(){{{} return 1; {return 1;} return 1; 1; 2; {} {1;} return 1;} return 2;}") testcase_err "block extra brace 1" <(echo "fn(){{return 1;} } return 1;}") testcase_err "block extra brace 2" <(echo "fn(){{return 1;} }}") # If/else testcase_ok "if 1" <(echo "fn(){if(1){}}") testcase_ok "if 2" <(echo "fn(){if(1)return 1;}") testcase_ok "if 3" <(echo "fn(){if(1)return 1;else return 2;}") testcase_ok "if 4" <(echo "fn(){if(1)return 1;else{return 2;}}") testcase_ok "if 5" <(echo "fn(){if(1){}else{return 2;}}") testcase_ok "if 6" <(echo "fn(){if(1){}else{}}") testcase_ok "if 7" <(echo "fn(){if(1){}else if(2)return 2;}") testcase_ok "if 8" <(echo "fn(){if(1){}else if(2)return 2;else return 3;}") testcase_ok "if 9" <(echo "fn(){if(1){}else if(2){}else{}}") testcase_ok "if 10" <(echo "fn(){if(1){}else {if(2){}else{}}}") testcase_ok "if 11" <(echo "fn(){if(1)if(2)return 2;else return 3;else return 4;}") testcase_err "if 12" <(echo "fn(){if(1)if(2)return 2;else return 3;else return 4;else return 5;}") testcase_chk "if nest 1" <(echo "fn(){if(1)if(2)return 2;else return 3;}") grep -q '(if 1 (if 2 (return 2) (return 3)))' testcase_chk "if nest 2" <(echo "fn(){if(1){if(2)return 2;}else return 3;}") grep -q '(if 1 (block (if 2 (return 2))) (return 3))' # While testcase_ok "while 1" <(echo "fn(){while(1){}}") testcase_ok "while 2" <(echo "fn(){while(1)return 1;}") testcase_ok "while 3" <(echo "fn(){while(1)while(1)return 1;}") testcase_ok "while 4" <(echo "fn(){while(1)if(1)return 1;}") testcase_ok "while 5" <(echo "fn(){while(1)if(1)return 1;else return 2;}") testcase_ok "while 6" <(echo "fn(){if(1)while(1)return 1;else return 2;}") testcase_ok "while 7" <(echo "fn(){if(1)while(1)if(1)return 1;else return 2;else return 3;}") testcase_ok "while 8" <(echo "fn(){if(1)while(1)if(1)return 1;else return 2;else while(1)if(1)return 1;else return 2;}") testcase_ok "while 9" <(echo "fn(){if(1)while(1)if(1)return 1;else return 2;while(1)if(1)return 1;else return 2;}") # Function calls testcase_ok "call is no ident" <(echo "f(fn) { fn(fn); }") testcase_ok "call decl" <(echo "f(x) { return x; } g(x) { return f(x); }") testcase_ok "call imp decl 1" <(echo "g(x) { return f(x + 1); } f(x) { return x; }") testcase_ok "call imp decl 2" <(echo "g(x) { return f(x + 1); }") testcase_err "call only on ident 1" <(echo "fn(x) { fn(x)(x); }") testcase_err "call only on ident 2" <(echo "fn(x) { (fn)(x); }") testcase_err "call only on ident 3" <(echo "fn(x) { (x)(x); }") testcase_err "call param count mismatch 1" <(echo "fn(x) { f(1); f(2, 3); }") testcase_err "call param count mismatch 2" <(echo "fn(x) { f(1, 3); f(2); }") testcase_err "call param count mismatch 3" <(echo "f(a) {} fn(x) { f(1, 3); }") testcase_err "call param count mismatch 4" <(echo "f(a, b) {} fn(x) { f(1); }") testcase_err "call param count mismatch 5" <(echo "f() {} fn(x) { f(1); }") testcase_err "call param count mismatch 6" <(echo "fn(x) { f(1, 3); } f(a) {}") testcase_err "call param count mismatch 7" <(echo "fn(x) { f(1); } f(a, b) {}") testcase_err "call param count mismatch 8" <(echo "fn(x) { f(1); } f() {}") # Declarations testcase_ok "decl 1" <(echo "fn(a){register b = a;}") testcase_ok "decl 2" <(echo "fn(a){auto b = a;}") testcase_ok "decl 3" <(echo "fn(a){{register a = a;}}") testcase_ok "decl 4" <(echo "fn(a){{auto a = a;}}") testcase_err "decl 5" <(echo "fn(a){{auto a = &a;}}") testcase_err "if decl 1" <(echo "fn(){if(1)register a = 1;}") testcase_err "if decl 2" <(echo "fn(){if(1){}else register a = 1;}") testcase_ok "if decl 3" <(echo "fn(){if(1){}else{register a = 1;}}") # Subscript testcase_ok "subscript 1" <(echo "f(a, b) { return a[b]; }") testcase_ok "subscript 2" <(echo "f(a, b) { return a[b@1]; }") testcase_ok "subscript 3" <(echo "f(a, b) { return a[b@2]; }") testcase_err "subscript 4" <(echo "f(a, b) { return a[b@3]; }") testcase_ok "subscript 5" <(echo "f(a, b) { return a[b@4]; }") testcase_err "subscript 6" <(echo "f(a, b) { return a[b@5]; }") testcase_err "subscript 7" <(echo "f(a, b) { return a[b@6]; }") testcase_err "subscript 8" <(echo "f(a, b) { return a[b@7]; }") testcase_ok "subscript 9" <(echo "f(a, b) { return a[b@8]; }") testcase_err "subscript 10" <(echo "f(a, b) { return a[b@9]; }") testcase_err "subscript 11" <(echo "f(a, b) { return a[b@10]; }") testcase_err "subscript 12" <(echo "f(a, b) { return a[b@a]; }") testcase_err "subscript 13" <(echo "f(a, b) { return a[b@]; }") # Address of (&) testcase_ok "addrof auto" <(echo "f() { auto a = 0; return &a; }") testcase_ok "addrof subscript 1" <(echo "f(a, b) { return &a[b]; }") testcase_ok "addrof subscript 2" <(echo "f(a, b) { return &a[b@1]; }") testcase_ok "addrof subscript 3" <(echo "f(a, b) { return &a[b@2]; }") testcase_ok "addrof subscript 4" <(echo "f(a, b) { return &a[b@4]; }") testcase_ok "addrof subscript 5" <(echo "f(a, b) { return &a[b@8]; }") testcase_err "addrof param" <(echo "f(a) { return &a; }") testcase_err "addrof reg" <(echo "f() { register a = 0; return &a; }") # Scoping testcase_ok "scope 1" <(echo "f(a) { return a; }") testcase_ok "scope 2" <(echo "f(a) { { register b = a; return b; } }") testcase_err "scope 3" <(echo "f(a) { { register b = a; } return b; }") testcase_ok "scope 4" <(echo "f(a) { { register b = a; } { auto b = a; return &b; } }") testcase_err "scope 4" <(echo "f(a) { { register b = a; } { auto b = a; } return &b; }") # Variable shadowing testcase_err "shadow 1" <(echo "f() { register a = 1; { auto a = 2; } return &a; }") testcase_err "shadow 2" <(echo "f() { register a = 1; register a = 2; }") testcase_err "shadow 3" <(echo "f() { register a = 1; auto a = 2; }") testcase_err "shadow 4" <(echo "f() { auto a = 1; auto a = 2; }") testcase_err "shadow 5" <(echo "f() { auto a = 1; register a = 2; }") testcase_ok "shadow 6" <(echo "f() { auto a = 1; { auto a = 2; return a; } }") testcase_ok "shadow 7" <(echo "f() { auto a = 1; { auto a = 2; } return a; }") testcase_ok "shadow 8" <(echo "f() { auto a = 1; { register a = 2; return a; } }") testcase_ok "shadow 9" <(echo "f() { register a = 1; { auto a = 2; } return a; }") testcase_ok "shadow 10" <(echo "f() { register a = 1; { auto a = 2; return &a; } }") testcase_err "shadow param 1" <(echo "f(a) { register a = 1; }") testcase_err "shadow param 2" <(echo "f(a) { auto a = 1; }") testcase_ok "shadow param 3" <(echo "f(a) { { register a = 1; } }") testcase_ok "shadow param 4" <(echo "f(a) { { auto a = 1; } }") testcase_ok "shadow param 5" <(echo "f(a) { { auto a = 1; } return a; }") testcase_err "shadow param 6" <(echo "f(a) { { auto a = 1; } return &a; }") # Expression precedence and associativity testcase_chk "unary 1" <(echo "f(a) { return !a; }") grep -q '(! [^ )]\+)' testcase_chk "unary 2" <(echo "f(a) { return ~a; }") grep -q '(~ [^ )]\+)' testcase_chk "unary 3" <(echo "f(a) { return !!a; }") grep -q '(! (! [^ )]\+))' testcase_chk "unary 4" <(echo "f(a) { return ~!a; }") grep -q '(~ (! [^ )]\+))' testcase_chk "unary 5" <(echo "f(a) { return !~a; }") grep -q '(! (~ [^ )]\+))' testcase_chk "unary call 1" <(echo "f(a) { return !fn(); }") grep -q '(return (!' testcase_chk "unary call 2" <(echo "f(a) { return -fn(); }") grep -q '(return (u-' testcase_chk "add 1" <(echo "f(a,b,c) { return a + b + c; }") grep -q '(+ (+ [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "add 2" <(echo "f(a,b,c,d) { return a + b + c + d; }") grep -q '(+ (+ (+ [^ )]\+ [^ )]\+) [^ )]\+) [^ )]\+)' testcase_chk "add 3" <(echo "f(a,b,c) { return a + b - c; }") grep -q '(- (+ [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "add 4" <(echo "f(a,b,c) { return a - b - c; }") grep -q '(- (- [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "add 5" <(echo "f(a,b,c) { return (a + b) - c; }") grep -q '(- (+ [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "add 6" <(echo "f(a,b,c) { return a + (b - c); }") grep -q '(+ [^ )]\+ (- [^ )]\+ [^ )]\+))' testcase_chk "add unary 1" <(echo "f(a,b,c) { return a + !b + c; }") grep -q '(+ (+ [^ )]\+ (! [^ )]\+)) [^ )]\+)' testcase_chk "add unary 2" <(echo "f(a,b,c) { return !a + !b + c; }") grep -q '(+ (+ (! [^ )]\+) (! [^ )]\+)) [^ )]\+)' testcase_chk "add unary 3" <(echo "f(a,b,c) { return !(a + !b) + c; }") grep -q '(+ (! (+ [^ )]\+ (! [^ )]\+))) [^ )]\+)' testcase_chk "add unary 4" <(echo "f(a,b,c) { return a + b + - c; }") grep -q '(+ (+ [^ )]\+ [^ )]\+) (u- [^ )]\+))' testcase_chk "add unary 5" <(echo "f(a,b,c) { return a + b - - c; }") grep -q '(- (+ [^ )]\+ [^ )]\+) (u- [^ )]\+))' testcase_chk "add lt 1" <(echo "f(a,b,c) { return a + b < a + c; }") grep -q '(< (+ [^ )]\+ [^ )]\+) (+ [^ )]\+ [^ )]\+))' testcase_chk "add lt 2" <(echo "f(a,b,c) { return a + (b < a + c); }") grep -q '(+ [^ )]\+ (< [^ )]\+ (+ [^ )]\+ [^ )]\+))' testcase_chk "lt lt 1" <(echo "f(a,b,c) { return a < b < c; }") grep -q '(< (< [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "lt lt 2" <(echo "f(a,b,c) { return a > b < c; }") grep -q '(< (> [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "lt lt 3" <(echo "f(a,b,c) { return a < b > c; }") grep -q '(> (< [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "add eq 1" <(echo "f(a,b,c) { return a + b == a + c; }") grep -q '(== (+ [^ )]\+ [^ )]\+) (+ [^ )]\+ [^ )]\+))' testcase_chk "add eq 2" <(echo "f(a,b,c) { return a + (b == a + c); }") grep -q '(+ [^ )]\+ (== [^ )]\+ (+ [^ )]\+ [^ )]\+))' testcase_chk "lt eq 1" <(echo "f(a,b,c) { return a < b == a < c; }") grep -q '(== (< [^ )]\+ [^ )]\+) (< [^ )]\+ [^ )]\+))' testcase_chk "lt eq 2" <(echo "f(a,b,c) { return a < (b == a < c); }") grep -q '(< [^ )]\+ (== [^ )]\+ (< [^ )]\+ [^ )]\+))' testcase_chk "eq eq 1" <(echo "f(a,b,c) { return a == b == c; }") grep -q '(== (== [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "eq eq 2" <(echo "f(a,b,c) { return a != b == c; }") grep -q '(== (!= [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "eq eq 3" <(echo "f(a,b,c) { return a == b != c; }") grep -q '(!= (== [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "eq eq 4" <(echo "f(a,b,c) { return a != b != c; }") grep -q '(!= (!= [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "and and 1" <(echo "f(a,b,c) { return a && b && c; }") grep -q '(&& (&& [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "and and 2" <(echo "f(a,b,c) { return a == b && c; }") grep -q '(&& (== [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "and and 3" <(echo "f(a,b,c) { return a && b == c; }") grep -q '(&& [^ )]\+ (== [^ )]\+ [^ )]\+))' testcase_chk "or or 1" <(echo "f(a,b,c) { return a || b || c; }") grep -q '(|| (|| [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "or or 2" <(echo "f(a,b,c) { return a && b || c; }") grep -q '(|| (&& [^ )]\+ [^ )]\+) [^ )]\+)' testcase_chk "or or 3" <(echo "f(a,b,c) { return a || b && c; }") grep -q '(|| [^ )]\+ (&& [^ )]\+ [^ )]\+))' testcase_chk "assign 1" <(echo "f(a,b,c) { return a = b = c; }") grep -q '(= [^ )]\+ (= [^ )]\+ [^ )]\+))' testcase_err "assign 2" <(echo "f(a,b,c) { return a && b = c; }") testcase_chk "assign 3" <(echo "f(a,b,c) { return a && (b = c); }") grep -q '(&& [^ )]\+ (= [^ )]\+ [^ )]\+))' testcase_chk "assign 4" <(echo "f(a,b,c) { return a = b && c; }") grep -q '(= [^ )]\+ (&& [^ )]\+ [^ )]\+))' testcase_ok "subscript nested 1" <(echo "f(a, b) { return a[b][b]; }") testcase_ok "subscript nested 2" <(echo "f(a, b) { return a[b@2][b@1]; }") testcase_chk "subscript call" <(echo "f(a) { return fn()[a]; }") grep -q '(return (\[\]' testcase_chk "unary subscript 1" <(echo "f(a,b) { return -a[b]; }") grep -q '(u- (\[\]' testcase_chk "unary subscript 2" <(echo "f(a,b) { return -a[b=a]; }") grep -q '(u- (\[\]' testcase_chk "unary subscript 3" <(echo "f(a,b) { return -a[b=a][b]; }") grep -q '(u- (\[\]' testcase_chk "unary subscript call" <(echo "f(a) { return -fn()[a]; }") grep -q '(return (u- (\[\]' # Expressions lvalue-ness testcase_err "assign lvalue 1" <(echo "f(a, b) { -a = b; }") testcase_err "assign lvalue 2" <(echo "f(a, b) { a + 1 = b; }") testcase_ok "assign lvalue 3" <(echo "f(a, b) { a[b] = b; }") testcase_err "assign lvalue 4" <(echo "f(a, b) { a - b = b; }") testcase_err "assign lvalue 5" <(echo "f(a, b) { g(a) = b; }") testcase_ok "assign lvalue 6" <(echo "f(a, b) { g(a)[0] = b; }") testcase_err "addrof lvalue 1" <(echo "f(a) { auto b = a; return &-a; }") testcase_err "addrof lvalue 2" <(echo "f(a) { auto b = a; return &a + 1; }") testcase_ok "addrof lvalue 3" <(echo "f(a) { auto b = a; return &a[b]; }") testcase_err "addrof lvalue 4" <(echo "f(a) { auto b = a; return &a - b; }") testcase_err "addrof lvalue 5" <(echo "f(a) { auto b = a; return &g(a); }") testcase_ok "addrof lvalue 6" <(echo "f(a) { auto b = a; return &g(a)[0]; }") # Performance test. Reduce n (nesting) and r (repeat) for smaller workload. testcase_ok "bignest1000r10" <(python3 -c "n=1000;r=10;print(''.join(f'func{j}(a){{' + ''.join(f'{{register a{i}=a{(i-1)//2 if i>1 else \"\"}; ' for i in range(n)) + f'return a+a{n//2}+a{n-1};' + '}'*(n+1) for j in range(r)))") exit $FAILED