Fully Modular C: Grading

Question

You are a Computer Science professor teaching the C programming language. One principle you seek to impart to the students is modularity. Unfortunately, past classes have tended not to get the message, submitting assignments with the entire program inside main(). Therefore, for this semester you have issued strict modularity guidelines upon which students will be graded.

A subset of C grammar and rules for "well-formed" translation unit are defined below. Code that follows these rules should be valid C89, UNLESS an identifier that is a keyword is used.

Task

You will receive as input a string purportedly containing C code. You may assume that this string contains only spaces, newlines, and the characters abcdefghijklmnopqrstuvwxyz123456789(){},+-*/%;=.

Your code must output the number of points the student's assignment should receive according to the following rubric:

• Input is not a valid translation-unit according to the grammar: 0 points
• Input follows the grammar but is not "well-formed" according to the rules below: 1 point
• Input is a well-formed translation unit but not fully modular: 2 points
• Input is a fully modular well-formed translation unit: 3 points

Token definitions

• identifier: Any sequence of 1 or more lowercase English letters. If an identifier is a C89 reserved word¹, you may optionally return 0 instead of whatever the result would have been ignoring reserved words. You do not have to be consistent about detecting the use of reserved words as identifiers; you may flag them in some instances and let them pass in others.

• integer-literal: A sequence of 1 or more of the digits 1-9 (recall that the character 0 is guaranteed not to appear in the input)

• Other valid tokens are defined literally in the grammar.
• A character must belong to a token if and only if it is not whitespace.
• Two consecutive alphanumeric characters must be part of the same token.

EBNF grammar

var-expr = identifier
literal-expr = integer-literal
binary-op = "+" | "-" | "*" | "/" | "%"
binary-expr = expr binary-op expr
paren-expr = "(" expr ")"
call-expr = identifier "(" [ expr ( "," expr )* ] ")"
expr = var-expr | literal-expr | binary-expr | paren-expr | call-expr
assign-stmt = var-expr "=" expr ";"
if-stmt = "if" "(" expr ")" assign-stmt
return-stmt = "return" expr ";"
function-body = ( assign-stmt | if-stmt )* return-stmt
argument-list = [ identifier ( "," identifier )* ]
function-definition = identifier "(" argument-list ")" "{" function-body "}"
translation-unit = function-definition*

Well-formed program requirements

• No two function definitions may have the same function name.
• No two identifiers in an argument-list may be identical.
• No identifier in an argument-list may be identical to a function name (whether from a function-definition or a call-expr).
• The identifier in a var-expr must be included in the enclosing function's argument-list.
• For a given function, all call-exprs and the function-definition (if any) must agree in number of arguments.

Fully modular

• No more than 1 binary operator per function
• No more than 1 assignment statement per function
• No more than 1 function call per function

Examples (one per line)

Score 0

}}}}}
return 2;
f() { return -1; }
f() {}
f(x,) { return 1; }
f(x) { return 1 }
f(x) { returnx; }
f(x) { return1; }
f() { g(); return 1;}
f() { if(1) return 5; }
f(x) { if(1) if(1) x = 2; return x; }
f(x, y) { x = y = 2; return x; }

Score 1

f(){ return 1; } f(){ return 1; }
g(x, x) { return 1; }
g(f) { return 1; } f() { return 1; }
f(x) { x = write(); x = write(1); return 1; }
f() { return f(f); }
f() { return 1; } g() { return f(234567); }
f() { return(x); }
f() { j = 7; return 5; }

Score 2

f(x,y,zzzzz) { return x + y + zzzzz; }
f(x,a,b) { if(a) x = foo(); if(b) x = bar(); return x; }
f(j) { return g(h( i() / j, i() ), 1) ; }

Score 3

mod(x, y) { return ((x % y)); }
f() { return f(); }
f(c) { if(c) c = g(c) + 2; return c; }
fib(i){return bb(i,0,1);}aa(i,a,b){return bb(i,b,a+b);}bb(i,a,b){if(i)a=aa(i-1,a,b);return a;}

Score 0 or 1

h(auto, auto) { return 1; }

Score 0 or 3

if() { return 1; }

---

¹ _{Reserved word list: auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while}

Answer 1

JavaScript (ES6), 599 _{^{598 593 581 580 576}} 574 593 _{^{591 579 565 563 562 524 521 515 513 511 506 503}} 502 bytes

After over 3 years I finally noticed "some" further golfs. I also found an edge case while re-golfing… +19 bytes. Sigh. That helped me notice a 38 byte golf. :P

M=p=>(P=I[i++])==p&&7
J=_=>/^[a-z]+$/.test(R=P)*7
O=(Z,a,n=R)=>M`)`?(L[n]|=2)&1|U[n]-(U[n]=a)?1:7:(a++?P==",":i--)&&Z()&O(Z,a,n)
E=_=>(M`(`?E()&M`)`:P-~P?7:J()&(M`(`?O(E,!++z):A[i--,R]|1))&(/[+*/%-]/.test(I[i])?E(++y+i++):7)
S=_=>M`return`?E()&M`;`&M`}`&((x|y|z)>1?3:7):P&&(P=="if"?M`(`&E()&M`)`+M():7)&J()&(A[R]|1)&M`=`&E()&M`;`&S(++x)
Q=_=>M()||J(A={})&(L[F=R]&5?1:7)&M`(`&O(_=>J(M())&(A[R]|(L[R]|=1)&6?1:A[R]=7),x=y=z=0)&M`{`&S()&Q(L[F]=6)
f=c=>Math.log2(Q(U={},L={},i=0,I=c.match(/\w+|\S/g)||[])+1)

Try it online! (comes with test cases)

Defines a function f that takes the code as argument.

Explanation

This monstrosity is essentially a huge recursive bitwise AND, which somehow happens to work as a parser for this C subset. Scores are stored as 0137 for 0123 respectively and converted in the end as log2(score+1); if any phase detects a problem in the code, it returns a score lower than 7, which in turn unsets bits from the final output and results in a lower score. All functions return a score.

If the code runs out of input, it will just continue happily reading undefineds from the token array. This is fine, since the only function that matches undefined is J, and anything will eventually finish recursing and return 0 due to not matching a closing }. (Except for S and Q which have explicit checks for end of input.)

// Globals:
//   I = input tokens
//   i = input position
//   P = last token consumed
//   R = last identifier consumed
//   x,y,z = number of assignments, binary ops, func calls
//   A = current function args
//   F = current function name
//   L = used identifiers as bitfields: 1=argument, 2=call, 4=definition
//   U = function arg counts

// M(p): Consume a token, store it in P, return 7 if P == p, otherwise false (0).
M = p => (P = I[i++]) == p && 7
// J(): Copy P to R, return 7 if valid identifier, otherwise 0.
J = _ => /^[a-z]+$/.test(R = P) * 7
// O(Z, 0): Parse args for R() using the function Z.
O = (Z, a, n = R) =>  // a = arg count, n = name of function (for nested calls)
  M`)` ?              // consume token, is it ")"?
    (L[n] |= 2)         // if yes, mark n() as a called function
    & 1                 // and see if n has been used as an arg
    | U[n] - (U[n] = a) // see if n() already has a different arg count, store new count
    ? 1 : 7             // if yes to either, cap score at 1
  :                   // token wasn't ")"
    (a++                // increment arg count, is this first arg?
    ? P == ","            // if not, truthy only if token was ","
    : i--)                // else, push token back & be truthy
    && Z()              // if truthy, parse the actual arg
    & O(Z,a,n)          // and recurse
// E(): Parse expression.
E = _ =>
                      // first, parse a primary expression:
  (M`(`                 // consume token, is it "("?
  ? E() & M`)`            // if yes, parse expr + ")"
  : P-~P ?              // else, is it numeric?
  7                       // if yes, it's a valid primary expr
  :                     // else,
  J() &                   // parse identifier into R
  (M`(`                   // consume token, is it "("?
  ? O(E, !++z)              // if yes, parse args for R()
  : A[i--, R] | 1)          // else, push token back and see if R is a valid variable
  ) & (               // now, handle infix operators:
  /[+*/%-]/.test(I[i])  // is the next token an operator?
  ? E(++y + i++)          // if yes, consume & parse another expr
  : 7)                    // else, we're done

// S(): Parse statement.
S = _ =>
  M`return` ?                // consume token, is it "return"?
  E() & M`;` & M`}`            // if yes, parse expr + expect ";}"
  & ((x | y | z) > 1 ? 3 : 7)  // and check modularity
  : P &&                     // else, if EOF, return undefined
  (P == "if"                 // else, is it "if"?
  ? M`(` & E() & M`)`          // if yes, parse "(" + expr + ")"
  + M()                        // and consume another token to P
  :                          // else,
  7)                           // just a normal assignment
  & J()                      // parse identifier into R
  & (A[R] | 1)               // check if R is a valid variable
  & M`=` & E() & M`;`        // parse "=" + expr + ";"
  & S(++x)                   // parse next statement

// Q(): Parse function.
Q = _ =>
  M() ||          // consume token, return undefined if EOF
  J(A = {})       // parse identifier into R
  & (L[F = R] & 5 ? 1 : 7)  // see if it's been used as arg or defined
  & M`(`          // expect "("
  & O(_ =>        // parse arg list with O(), name parsing func:
    J(M()) &        // consume & parse identifier into R
    (A[R] |         // see if R is already in this func's args
    (L[R] |= 1)     // mark R as a used arg name
    & 6             // see if R() is a called or defined func
    ? 1             // if yes to either, cap score to 1
    : A[R] = 7),    // else, add R to this func's args
  x = y = z = 0)  // reset modularity counters
  & M`{` & S()    // parse "{" + statement(s)
  & Q(L[F] = 6)   // parse next function, mark F() as defined

// f(c): Parse & score code c.
f = c =>
  Math.log2(Q(
    U = {}, L = {}, i = 0,
    I = c.match(/\w+|\S/g) || [])  // C lexer (:D)
  + 1)

Some of my favorites:

• (L[n]|=2)&1|U[n]-(U[n]=a)?1:7 simultaneously exploits undefined, NaN and left-to-right evaluation order
• There turned out to be a shorter "is numeric" check than x==+x, when used only as truthy/falsy: x-~x.