Sepenuhnya Modular C: Grading

8

Anda adalah seorang profesor Ilmu Komputer yang mengajarkan bahasa pemrograman C. Satu prinsip yang Anda coba berikan kepada siswa adalah modularitas . Sayangnya, kelas-kelas sebelumnya cenderung tidak mendapatkan pesan, mengirimkan tugas dengan seluruh program di dalamnya main(). Oleh karena itu, untuk semester ini Anda telah mengeluarkan panduan modularitas yang ketat di mana siswa akan dinilai.

Subset tata bahasa C dan aturan untuk unit terjemahan "well-formed" didefinisikan di bawah ini. Kode yang mengikuti aturan ini harus valid C89, KECUALI pengenal yang merupakan kata kunci yang digunakan.

Tugas

Anda akan menerima sebagai input string yang konon mengandung kode C. Anda dapat mengasumsikan bahwa string ini hanya berisi spasi, baris baru, dan karakter abcdefghijklmnopqrstuvwxyz123456789(){},+-*/%;=.

Kode Anda harus menampilkan jumlah poin yang harus diterima oleh tugas siswa sesuai dengan rubrik berikut:

  • Input tidak valid translation-unitsesuai dengan tata bahasa: 0 poin
  • Input mengikuti tata bahasa tetapi tidak "terbentuk dengan baik" sesuai dengan aturan di bawah ini: 1 poin
  • Input adalah unit terjemahan yang dibentuk dengan baik tetapi tidak sepenuhnya modular: 2 poin
  • Input adalah unit terjemahan sepenuhnya modular yang terbentuk dengan baik: 3 poin

Definisi token

  • identifier: Urutan 1 atau lebih huruf bahasa Inggris huruf kecil. Jika pengidentifikasi adalah kata yang dilindungi undang-undang C89 1 , Anda dapat secara opsional mengembalikan 0 daripada apa pun hasilnya akan mengabaikan kata-kata yang dipesan. Anda tidak harus konsisten dalam mendeteksi penggunaan kata-kata yang dipesan sebagai pengidentifikasi; Anda dapat menandai mereka dalam beberapa kasus dan membiarkannya lewat yang lain.

  • integer-literal: Urutan 1 atau lebih dari angka 1-9 (ingat bahwa karakter 0dijamin tidak muncul di input)

  • Token yang valid lainnya didefinisikan secara harfiah dalam tata bahasa.
  • Karakter harus menjadi token jika dan hanya jika itu bukan spasi putih.
  • Dua karakter alfanumerik berturut-turut harus menjadi bagian dari token yang sama.

Tata bahasa 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*

Persyaratan program yang dibentuk dengan baik

  • Tidak ada dua definisi fungsi yang memiliki nama fungsi yang sama.
  • Tidak ada dua pengidentifikasi dalam suatu yang argument-listmungkin identik.
  • Tidak ada pengidentifikasi dalam yang argument-listmungkin identik dengan nama fungsi (apakah dari a function-definitionatau a call-expr).
  • Pengidentifikasi dalam a var-exprharus dimasukkan dalam fungsi terlampir argument-list.
  • Untuk fungsi yang diberikan, semua call-exprs dan function-definition(jika ada) harus setuju dalam sejumlah argumen.

Sepenuhnya modular

  • Tidak lebih dari 1 operator biner per fungsi
  • Tidak lebih dari 1 pernyataan tugas per fungsi
  • Tidak lebih dari 1 panggilan fungsi per fungsi

Contoh (satu per baris)

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

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

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

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

Skor 0 atau 1

h(auto, auto) { return 1; }

Skor 0 atau 3

if() { return 1; }

1 daftar kata yang dicadangkan: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
sumber
Bisakah string input kosong? (Jika demikian, saya pikir seharusnya skor 3.)
Arnauld
@Arnauld Ya, itu benar.
feersum
Bagaimana kita memeriksa jumlah argumen dari fungsi yang tidak dideklarasikan? Apakah contoh ke-4 dalam "Skor 1" tidak terbentuk dengan baik karena writedipanggil sekali tanpa argumen dan sekali dengan satu argumen?
Arnauld
@Arnauld Ya, Anda memeriksa bahwa setiap panggilan ke suatu fungsi yang tidak didefinisikan memiliki jumlah argumen yang sama.
feersum
Saya melihat. Nah, ini saat ini tidak kompatibel dengan parser saya, jadi saya menghapus jawaban saya untuk saat ini. Saya mungkin mencoba lagi nanti.
Arnauld

Jawaban:

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)

Cobalah online! (dilengkapi dengan kasus uji)

Menentukan fungsi fyang menggunakan kode sebagai argumen.

(Beberapa) penjelasan

Monstrositas ini pada dasarnya adalah bitwise rekursif AND besar, yang entah bagaimana bekerja sebagai parser untuk subset C ini. Skor disimpan 0137untuk 0123masing - masing dan dikonversi pada akhirnya sebagai log2(score+1); jika ada fase yang mendeteksi masalah dalam kode, ia mengembalikan skor lebih rendah dari 7, yang pada gilirannya akan menghapus bit dari hasil akhir dan menghasilkan skor yang lebih rendah. Semua fungsi kecuali untuk Tdan Bmengembalikan skor.

Pengidentifikasi yang digunakan dilacak Ldan argumen fungsi diperhitungkan U. Jumlah argumen fungsi saat ini adalah Ndan namanya ada di A. Tugas, operator biner, dan panggilan dilacak x, ydan zmasing - masing.

Jika kode kehabisan input, itu hanya akan terus dengan senang hati undefinedkeluar dari token deque. Ini bagus, karena satu-satunya fungsi yang cocok undefinedadalah J, dan apa pun akhirnya akan selesai berulang dan kembali 0 karena tidak cocok dengan penutupan }. (Kecuali untuk Sdan Qyang memiliki pemeriksaan eksplisit untuk akhir input.) Bahkan mendorong undefinedkembali pada deque tidak berbahaya, karena popping undefinedsama dengan popping array kosong.

PurkkaKoodari
sumber