Vollmodular C: Bewertung

8

Sie sind Professor für Informatik und unterrichten die Programmiersprache C. Ein Prinzip, das Sie den Schülern vermitteln möchten, ist die Modularität . Leider haben frühere Klassen die Nachricht nicht erhalten und Aufgaben mit dem gesamten Programm eingereicht main(). Daher haben Sie für dieses Semester strenge Modularitätsrichtlinien herausgegeben, nach denen die Studierenden benotet werden.

Eine Teilmenge der C-Grammatik und Regeln für "wohlgeformte" Übersetzungseinheiten sind unten definiert. Code, der diesen Regeln folgt, sollte C89 gültig sein, WENN kein Bezeichner verwendet wird, der ein Schlüsselwort ist.

Aufgabe

Sie erhalten als Eingabe eine Zeichenfolge, die angeblich C-Code enthält. Sie können davon ausgehen, dass diese Zeichenfolge nur Leerzeichen, Zeilenumbrüche und Zeichen enthält abcdefghijklmnopqrstuvwxyz123456789(){},+-*/%;=.

Ihr Code muss die Anzahl der Punkte ausgeben, die die Aufgabe des Schülers gemäß der folgenden Rubrik erhalten soll:

  • Die Eingabe ist translation-unitlaut Grammatik nicht gültig : 0 Punkte
  • Die Eingabe folgt der Grammatik, ist jedoch gemäß den folgenden Regeln nicht "wohlgeformt": 1 Punkt
  • Die Eingabe ist eine wohlgeformte Übersetzungseinheit, jedoch nicht vollständig modular: 2 Punkte
  • Der Eingang ist eine vollständig modulare, wohlgeformte Übersetzungseinheit: 3 Punkte

Token-Definitionen

  • identifier: Beliebige Folge von 1 oder mehr englischen Kleinbuchstaben. Wenn ein Bezeichner ein reserviertes C89-Wort 1 ist , können Sie optional 0 zurückgeben, anstatt das Ergebnis, das reservierte Wörter ignoriert hätte. Sie müssen nicht konsequent sein, um die Verwendung reservierter Wörter als Bezeichner zu erkennen. Sie können sie in einigen Fällen markieren und in anderen passieren lassen.

  • integer-literal: Eine Folge von 1 oder mehr der Ziffern 1-9 (denken Sie daran, dass das Zeichen 0garantiert nicht in der Eingabe erscheint)

  • Andere gültige Token werden in der Grammatik wörtlich definiert.
  • Ein Zeichen muss genau dann zu einem Token gehören, wenn es kein Leerzeichen ist.
  • Zwei aufeinanderfolgende alphanumerische Zeichen müssen Teil desselben Tokens sein.

EBNF-Grammatik

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*

Gut geformte Programmanforderungen

  • Keine zwei Funktionsdefinitionen dürfen denselben Funktionsnamen haben.
  • Keine zwei Bezeichner in einem argument-listdürfen identisch sein.
  • Kein Bezeichner in a argument-listdarf mit einem Funktionsnamen identisch sein (ob von a function-definitionoder a call-expr).
  • Die Kennung in a var-exprmuss in den umschließenden Funktionen enthalten sein argument-list.
  • Für eine gegebene Funktion müssen alle call-exprs und function-definition(falls vorhanden) in der Anzahl der Argumente übereinstimmen.

Voll modular

  • Nicht mehr als 1 Binäroperator pro Funktion
  • Nicht mehr als 1 Zuweisungsanweisung pro Funktion
  • Nicht mehr als 1 Funktionsaufruf pro Funktion

Beispiele (eines pro Zeile)

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

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

Punktzahl 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) ; }

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

Punktzahl 0 oder 1

h(auto, auto) { return 1; }

Punktzahl 0 oder 3

if() { return 1; }

1 Reservierte Wortliste: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

code-golf parsing c Feersum
quelle
Darf die Eingabezeichenfolge leer sein? (Wenn ja, denke ich, sollte es 3 Punkte bringen.)
Arnauld
@Arnauld Ja, das ist richtig.
Feersum
Wie sollen wir die Anzahl der Argumente nicht deklarierter Funktionen überprüfen? Ist das 4. Beispiel in "Score 1" nicht wohlgeformt, weil writees einmal ohne Argument und einmal mit einem Argument aufgerufen wurde?
Arnauld
@Arnauld Ja, Sie überprüfen, ob jeder Aufruf einer nicht definierten Funktion dieselbe Anzahl von Argumenten enthält.
Feersum
Aha. Nun, dies ist derzeit nicht mit meinem Parser kompatibel, daher lösche ich meine Antwort vorerst. Ich kann es später noch einmal versuchen.
Arnauld

Antworten:

3

JavaScript (ES6), 599 Byte

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)

Probieren Sie es online aus! (kommt mit Testfällen)

Definiert eine Funktion f, die den Code als Argument verwendet.

(Einige) Erklärung

Diese Monstrosität ist im Wesentlichen ein riesiges rekursives bitweises UND, das irgendwie als Parser für diese C-Teilmenge fungiert. Scores werden jeweils als 0137für gespeichert 0123und am Ende als konvertiert log2(score+1); Wenn eine Phase ein Problem im Code feststellt, gibt sie eine Punktzahl unter 7 zurück, wodurch wiederum Bits von der endgültigen Ausgabe entfernt werden und eine niedrigere Punktzahl erzielt wird. Alle Funktionen außer Tund Bgeben eine Punktzahl zurück.

Verwendete Bezeichner werden nachverfolgt Lund Funktionsargumente zählen nach U. Die Anzahl der Argumente der aktuellen Funktion ist Nund die Namen sind in A. Zuordnungen, binäre Operatoren und Anrufe Verfolgt werden in x, yund zjeweils.

Wenn der Code keine Eingabe mehr hat, wird er einfach weiterhin glücklich undefinedvon der Token-Deque entfernt. Dies ist in Ordnung, da die einzige Funktion, die übereinstimmt, undefinedist Jund alles irgendwann rekursiv beendet wird und 0 zurückgibt , da ein Abschluss nicht übereinstimmt }. (Mit Ausnahme von Sund Qmit expliziten Überprüfungen für das Ende der Eingabe.) Selbst das undefinedZurückschieben der Deque ist harmlos, da das Poppen undefineddasselbe ist wie das Poppen eines leeren Arrays.

PurkkaKoodari
quelle