C totalmente modular: Classificação

8

Você é um professor de ciência da computação que ensina a linguagem de programação C. Um princípio que você procura transmitir aos alunos é a modularidade . Infelizmente, as aulas anteriores tendem a não receber a mensagem, enviando tarefas com todo o programa main(). Portanto, para este semestre, você emitiu diretrizes rígidas de modularidade nas quais os alunos serão classificados.

Um subconjunto da gramática C e regras para a unidade de tradução "bem formada" são definidas abaixo. O código que segue essas regras deve ser válido C89, a menos que um identificador que seja uma palavra-chave seja usado.

Tarefa

Você receberá como entrada uma string supostamente contendo o código C. Você pode assumir que essa sequência contém apenas espaços, novas linhas e os caracteres abcdefghijklmnopqrstuvwxyz123456789(){},+-*/%;=.

Seu código deve gerar o número de pontos que a tarefa do aluno deve receber de acordo com a seguinte rubrica:

  • A entrada não é válida de translation-unitacordo com a gramática: 0 pontos
  • A entrada segue a gramática, mas não é "bem formada" de acordo com as regras abaixo: 1 ponto
  • Input é uma unidade de tradução bem formada, mas não totalmente modular: 2 pontos
  • Input é uma unidade de tradução bem formada totalmente modular: 3 pontos

Definições de token

  • identifier: Qualquer sequência de 1 ou mais letras minúsculas em inglês. Se um identificador for uma palavra reservada C89 1 , você pode, opcionalmente, retornar 0 em vez de qualquer resultado que estivesse ignorando palavras reservadas. Você não precisa ser consistente em detectar o uso de palavras reservadas como identificadores; você pode sinalizá-los em alguns casos e deixá-los passar em outros.

  • integer-literal: Uma sequência de 1 ou mais dos dígitos de 1 a 9 (lembre-se de que o caractere 0é garantido para não aparecer na entrada)

  • Outros tokens válidos são definidos literalmente na gramática.
  • Um caractere deve pertencer a um token se, e somente se, não for um espaço em branco.
  • Dois caracteres alfanuméricos consecutivos devem fazer parte do mesmo 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 bem formados

  • Duas definições de função não podem ter o mesmo nome de função.
  • Não há dois identificadores em um argument-listpodem ser idênticos.
  • Nenhum identificador em um argument-listpode ser idêntico ao nome de uma função (seja de a function-definitionou a call-expr).
  • O identificador em a var-exprdeve ser incluído nas funções anexas argument-list.
  • Para uma determinada função, todos call-expros function-definitionse (se houver) devem concordar em número de argumentos.

Totalmente modular

  • Não mais que 1 operador binário por função
  • Não mais que 1 declaração de atribuição por função
  • Não mais que 1 chamada de função por função

Exemplos (um por linha)

Pontuação 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; }

Pontuação 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; }

Pontuação 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) ; }

Pontuação 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;}

Pontuação 0 ou 1

h(auto, auto) { return 1; }

Pontuação 0 ou 3

if() { return 1; }

1 Lista de palavras 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
fonte
A string de entrada pode estar vazia? (Em caso afirmativo, acho que deve marcar 3)
Arnauld
@ Arnauld Sim, está correto.
feersum
Como devemos verificar o número de argumentos de funções não declaradas? O quarto exemplo da "Pontuação 1" não está bem formado porque writefoi chamado uma vez sem argumento e uma vez com um argumento?
Arnauld
@ Arnauld Sim, você verifica se cada chamada para uma função que não está definida tem o mesmo número de argumentos.
feersum
Eu vejo. Bem, no momento, isso não é compatível com meu analisador, então estou excluindo minha resposta por enquanto. Posso tentar outra vez mais tarde.
Arnauld

Respostas:

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)

Experimente online! (vem com casos de teste)

Define uma função fque aceita o código como argumento.

(Alguma) explicação

Essa monstruosidade é essencialmente um enorme E bit a bit recursivo, que de alguma forma funciona como um analisador para este subconjunto C. As pontuações são armazenados como 0137para 0123, respectivamente, e convertido no final, como log2(score+1); se alguma fase detectar um problema no código, ela retornará uma pontuação menor que 7, o que desabilita os bits da saída final e resulta em uma pontuação menor. Todas as funções, exceto TeB retornam uma pontuação.

Os identificadores usados ​​são rastreados Le o argumento da função conta U. A contagem de argumentos da função atual é Ne os nomes estão A. Atribuições, operadores binários e as chamadas são rastreados em x, yez respectivamente.

Se o código ficar sem entrada, ele continuará exibindo alegremente undefinedo toque deque. Isso é bom, pois a única função que corresponde undefinedé Je, eventualmente, qualquer coisa terminará de se repetir e retornará 0 devido à não correspondência de um fechamento }. (Exceto por Se Qque têm verificações explícitas para o final da entrada.) Mesmo empurrar undefinedo deque de volta é inofensivo, pois exibir undefinedé o mesmo que exibir uma matriz vazia.

PurkkaKoodari
fonte