C completamente modular: calificación

8

Eres un profesor de informática que enseña el lenguaje de programación C. Un principio que busca impartir a los estudiantes es la modularidad . Desafortunadamente, las clases pasadas han tendido a no recibir el mensaje, enviando tareas con todo el programa dentro main(). Por lo tanto, para este semestre usted ha emitido pautas estrictas de modularidad sobre las cuales los estudiantes serán calificados.

A continuación se define un subconjunto de la gramática C y las reglas para la unidad de traducción "bien formada". El código que sigue estas reglas debe ser válido C89, A MENOS QUE se use un identificador que sea una palabra clave.

Tarea

Recibirá como entrada una cadena que supuestamente contiene el código C. Puede suponer que esta cadena contiene solo espacios, líneas nuevas y los caracteres abcdefghijklmnopqrstuvwxyz123456789(){},+-*/%;=.

Su código debe generar el número de puntos que la asignación del estudiante debe recibir de acuerdo con la siguiente rúbrica:

  • La entrada no es válida translation-unitsegún la gramática: 0 puntos
  • La entrada sigue la gramática pero no está "bien formada" de acuerdo con las siguientes reglas: 1 punto
  • La entrada es una unidad de traducción bien formada pero no completamente modular: 2 puntos
  • Input es una unidad de traducción bien modular y bien formada: 3 puntos

Definiciones de tokens

  • identifier: Cualquier secuencia de 1 o más letras minúsculas en inglés. Si un identificador es una palabra reservada C89 1 , opcionalmente puede devolver 0 en lugar de lo que el resultado hubiera estado ignorando palabras reservadas. No tiene que ser coherente para detectar el uso de palabras reservadas como identificadores; puede marcarlos en algunos casos y dejarlos pasar en otros.

  • integer-literal: Una secuencia de 1 o más de los dígitos 1-9 (recuerde que 0se garantiza que el carácter no aparecerá en la entrada)

  • Otros tokens válidos se definen literalmente en la gramática.
  • Un personaje debe pertenecer a un token si y solo si no es un espacio en blanco.
  • Dos caracteres alfanuméricos consecutivos deben ser parte del mismo token.

Gramática EBNF

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*

Requisitos de programa bien formados

  • No hay dos definiciones de función que puedan tener el mismo nombre de función.
  • No hay dos identificadores en un argument-listpueden ser idénticos.
  • Ningún identificador en un argument-listpuede ser idéntico al nombre de una función (ya sea de a function-definitiono a call-expr).
  • El identificador en a var-exprdebe incluirse en la función de cierre argument-list.
  • Para una función dada, todos los call-exprsy function-definition(si los hay) deben estar de acuerdo en varios argumentos.

Totalmente modular

  • No más de 1 operador binario por función
  • No más de 1 declaración de asignación por función
  • No más de 1 llamada a función por función

Ejemplos (uno por línea)

Puntuación 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; }

Puntuación 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; }

Puntuación 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) ; }

Puntuación 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;}

Puntuación 0 o 1

h(auto, auto) { return 1; }

Puntuación 0 o 3

if() { return 1; }

1 Lista de palabras reservadas: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

Feersum
fuente
¿Puede la cadena de entrada estar vacía? (Si es así, creo que debería marcar 3.)
Arnauld
@Arnauld Sí, eso es correcto.
fiesta
¿Cómo se supone que debemos verificar el número de argumentos de funciones no declaradas? ¿El cuarto ejemplo en "Puntaje 1" no está bien formado porque writese llamó una vez sin argumento y una vez con un argumento?
Arnauld
@Arnauld Sí, verifica que cada llamada a una función que no está definida tiene el mismo número de argumentos.
fiesta
Veo. Bueno, actualmente esto no es compatible con mi analizador, así que estoy borrando mi respuesta por ahora. Puedo intentarlo más tarde.
Arnauld

Respuestas:

3

JavaScript (ES6), 599 bytes

T=_=>P=I.shift()
B=v=>I.unshift(P)&&v
J=_=>/^[a-z]+$/.test(T())*7
M=p=>T()==p&&7
C=(n,a)=>n in U?U[n]==a?7:1:(U[n]=a,7)
E=(m,O=n=>E()&(M`,`?O(n+1):P==")"&&C(m,n)))=>(M`(`?E()&M`)`:P==+P?7:J(m=B(P))&(M`(`?++z&&M`)`?C(m,0):O(B(1)):B(A[m]|1)))&(/[+*/%-]/.test(T())?E(++y):B(7))
S=_=>I[0]?M`return`?E()&M`;`&M`}`&C(F,N)&((x|y|z)>1?3:7):(P=="if"?M`(`&E()&M`)`:B(7))&J(++x)&(A[P]|1)&M`=`&E()&M`;`&S():0
G=_=>J(++N)&(A[P]|L[P]&8?1:A[P]=L[P]=7)&(M`,`?G():P==")"&&M`{`&S())
Q=_=>I[N=x=y=z=0]?J(A={})&(L[F=P]?1:L[F]=15)&M`(`&(M`)`?M`{`&S():G(B()))&Q():7
f=c=>Math.log2(Q(U={},L={},I=c.match(/\w+|\S/g)||[])+1)

Pruébalo en línea! (viene con casos de prueba)

Define una función fque toma el código como argumento.

(Alguna) explicación

Esta monstruosidad es esencialmente un enorme Y recursivo a nivel de bits Y, que de alguna manera funciona como un analizador para este subconjunto C. Las puntuaciones se almacenan como 0137para 0123respectivamente y se convierten al final como log2(score+1); Si alguna fase detecta un problema en el código, devuelve una puntuación inferior a 7, que a su vez desarma los bits de la salida final y da como resultado una puntuación más baja. Todas las funciones excepto Ty Bdevuelven una puntuación.

Los identificadores usados ​​se rastrean Ly el argumento de función cuenta U. El recuento de argumentos de la función actual es Ny los nombres están en A. Las asignaciones, operadores binarios y llamadas se rastrean x, yy zrespectivamente.

Si el código se queda sin entrada, continuará felizmente sacando undefineds del token deque. Esto está bien, ya que la única función que coincide undefinedes J, y cualquier cosa eventualmente terminará de recurrir y devolverá 0 debido a que no coincide con un cierre }. (Excepto por Sy Qque tienen comprobaciones explícitas para el final de la entrada.) Incluso presionar undefinedhacia atrás en el deque es inofensivo, ya que estallar undefinedes lo mismo que estallar una matriz vacía.

PurkkaKoodari
fuente