Mengurai sintaks dua dimensi

25

Latar Belakang

Alice dan Bob menciptakan bahasa golf untuk memenangkan setiap tantangan PPCG. Alice ingin membuat bahasa dua dimensi, seperti> <>, tetapi Bob lebih memilih sintaks awalan-infiks seperti pada J. Sebagai kompromi, mereka memutuskan untuk membuat bahasa awalan-infiks dua dimensi. Pengurai adalah rasa sakit untuk menulis, dan mereka membutuhkan bantuan Anda!

Spesifikasi sintaks

Dalam bahasa Alice dan Bob, ada variabel , yang diwakili oleh huruf ASCII huruf kecil a-z, dan fungsi , yang diwakili oleh huruf ASCII huruf besar A-Z. Suatu fungsi dapat dipanggil dengan satu atau dua argumen. Suatu program adalah kotak persegi panjang dari huruf a-zA-Zdan spasi, dan sudut kiri atas tidak boleh mengandung spasi. Ini adalah contoh dari program yang valid:

F Gy
H   
R x 

Ketika program diurai, itu diubah menjadi ekspresi bahasa gaya-C (C, Java, Python ...) yang berisi variabel huruf tunggal dan panggilan fungsi dalam format <func>(<arg>)atau <func>(<arg1>,<arg2>). Misalnya, program di atas menghasilkan ekspresi ini:

F(H(R(x)),G(x,y))

Rincian proses penguraian adalah sebagai berikut:

  • Spasi hanyalah pengisi, sehingga tidak diurai.
  • Setiap variabel a-zselalu diurai seperti itu sendiri.
  • Setiap fungsi A-Zdiuraikan sebagai panggilan fungsi. Argumennya adalah ekspresi terdekat di bawahnya dan ke kanan di grid, dalam urutan ini. Jika hanya satu yang hadir, itu diberikan sebagai satu-satunya argumen. Anda dapat mengasumsikan bahwa semua fungsi memiliki setidaknya satu argumen di kisi.

Dalam contoh di atas, variabel xdan ydiuraikan sebagai diri mereka sendiri. Fungsi Rtidak memiliki apa pun di bawahnya dan di xsebelah kanannya, sehingga diuraikan sebagai doa satu argumen R(x). Demikian pula, Hdiuraikan sebagai H(R(x)), karena memiliki Rdi bawahnya. Fungsi Gmemiliki xdi bawahnya dan di ysebelah kanannya, sehingga diuraikan sebagai G(x,y), dan demikian pula untuk F. Ekspresi yang diuraikan di sudut kiri atas adalah hasil dari proses penguraian.

Masukan dan keluaran

Input Anda adalah array karakter persegi panjang yang tidak kosong. Ini akan selalu menjadi program yang valid dalam bahasa Alice dan Bob, tetapi mungkin berisi ekspresi yang tidak digunakan dalam output. Output Anda akan menjadi ekspresi parsing yang dihasilkan dari proses di atas.

Aturan dan penilaian

Anda dapat menulis program lengkap suatu fungsi. Hitungan byte terendah menang, dan celah standar tidak diizinkan.

Uji kasus

Ini diberikan dalam format grid <newline> expression, dengan tanda hubung ---antara kasus. Format SE membiarkan beberapa baris kosong, tetapi harus diisi dengan spasi.

x
x
---
x y
z  
x
---
Fx
F(x)
---
Fx
y 
F(y,x)
---
ABu
A(B(u))
---
G
H
k
G(H(k))
---
ABCA
x xs
 DFk
A(x,B(D(F(k)),C(x,A(s))))
---
A  B  

C  D x
A(C(D(x)),B(D(x)))
---
RT Hq 
I xR k
R(I(x),T(H(R(k),q)))
---
A A  A a 
 S A  b  
B  C   Dx
d X  u f 
A(B(d,C(D(f,x))),A(X(u),A(u,a)))
Zgarb
sumber
Apakah output suka (A (B (D x)) (C (D x)))cocok atau formatnya sudah diperbaiki?
coredump
1
@coredump Dalam tantangan ini, format outputnya ketat; Alice dan Bob ingin dapat menggunakan ekspresi yang diuraikan secara langsung.
Zgarb
Di mana bagian "infiks" dari bahasa itu? Saya hanya melihat awalan.
Paŭlo Ebermann
6
Bisakah Anda benar-benar membuat bahasa dengan sintaks ini? :)
Martin Ender
4
Tantangan tindak lanjut: menulis meta-pegolf untuk sintaks ini (diberi pohon ekspresi, temukan kisi terkecil yang sesuai dengannya). Untuk kesulitan ekstra, bedakan antara fungsi komutatif dan non-komutatif.
Martin Ender

Jawaban:

8

CJam, 67 62 60 58 57 54 byte

Terima kasih kepada Dennis karena telah menghemat 4 byte.

{:Gsc_32&{"()"[GGz2{1m<_{S#}#>W<\}*z]{},{J}%',**+}|}:J

Ini mendefinisikan blok bernama (fungsi) Jdan meninggalkannya di tumpukan. Fungsi itu sendiri mengharapkan array string pada stack, yang mewakili grid input, dan meninggalkan string yang diinginkan sebagai gantinya.

Uji di sini.

Saya sudah bermaksud untuk mengatasi yang ini sejak diposting, tetapi ternyata saya membutuhkan solusi Pyth karunia dan terlalu lama untuk memotivasi diri saya sendiri secara memadai.

Penjelasan

Solusinya tentu saja bersifat rekursif dan secara bertahap membangun string.

{
  :G       e#  Store the current grid in G.
  sc       e#  Convert the grid to a string, flattening it, then to a character, which
           e#  discards everything but the first character. This is a golfed 0=0=.
           e#  This character will either be an upper-case letter (function) or a lower-
           e#  case letter (variable).
  _32&     e#  Make a copy of the character and take bitwise AND with 32. This gives a
           e#  NULL character for functions and a space for variables.
  {        e#  If the result is falsy... (i.e. NULL, i.e. we have a function)
    "()"   e#   Push parentheses for later use.
    [      e#   Remember the current stack depth.
    GGz    e#   Push an array which contains the grid and its transpose.
    2{     e#   Run this block twice... (it will be applied once to each grid)
      1m<  e#    Rotate the rows. This has two effects: a) It removes the first row
           e#    from the front such that we can go looking for the next non-space
           e#    character down the first column from the start. b) It places a row
           e#    at the end which we know doesn't start with a space, which acts as
           e#    a guard in case there are no further letters below the current one.
      _    e#    Duplicate this grid.
      {    e#    Find the first index where this block yields something truthy...
        S# e#     Find the index of the first space in the current row. If the row
           e#     starts with a space, this is 0, i.e. falsy and the search continues.
           e#     If there is a space in any later position, that will be positive and
           e#     truthy, so this index gets returned. If there is no space at all,
           e#     the result is -1 which is also truthy and ends the search.
      }#        
      >    e#     Discard all lines up to (but not including) the found index.
      W<   e#     Discard the guard row at the end.
      \    e#     Swap the grids so that the next pass processes the other grid.
    }*       
    z      e#    Transpose the second grid back to its original orientation.
    ]      e#    Wrap both processed grids in an array.
    {},    e#    Remove a grid if it's empty.
    {J}/   e#    For each remaining grid, call J recursively.
    ',*    e#    Join the grids with commas if there are still two of them.
    *      e#    Wrap this string in the parentheses below on the stack.
    +      e#    Prepend the function name.
  }|
}:J
Martin Ender
sumber
5

Python 2, 227 223 192 182 179 177 byte

def r(i,y=0,x=0):
 c=i[y][x];z=[]
 for t in"pq":
    p=q=0
    try:
     while" "==i[y+p][x+q]or 1>p+q:exec t+"+=1"
     z+=[r(i,y+p,x+q)]
    except:1
 return c+"(%s)"%",".join(z)*c.isupper()

(Keempat spasi sebenarnya tab)

Mengambil daftar karakter 2d sebagai argumen pertama ke r.

Biru
sumber
5

Pyth, 97 byte

D:TkdI}p@@QTkGR)=Z0p\(V2JK0W|q\ @@Q=b+TJ=H+kK!+JK=J+NJ=K+!NK)I!|gblQgHl@Q0p*Z\,:bH+=Z1d))p\);:000

Ya Tuhan, butuh waktu lama (sekitar 5/6 jam?). Pyth benar-benar tidak dirancang untuk ini ...

Coba di sini .

Coba di penjelasan serta setara python

Q = literal_eval(input())

def at_slice(T,k,d):
  if Pprint(Q[T][k]) in "abcdefghijklmnopqrstuvwxyz": return 
  Z = 0
  Pprint("(")
  for N in range(2):
    J=K=0
    while " "==Q[assign('b',T+J)][assign('H',k+K)] or not J+K:
      J+=N
      K+=not N
    if not (b>=len(Q) or H>=len(Q[0])):
      Pprint(Z*",")
      at_slice(b,H,assign('Z',1)+d)
   Pprint(")")
at_slice(0,0,0)

Di mana fungsi Pprintdan assignmengembalikan apa yang diberikan.

Biru
sumber
Banyak keputusan. Wow begitu.
Addison Crump
5

Haskell, 124 122 120 119 byte

r@((c:_):_)#g|c>'_'=[c]|c<'!'=g%r|1<2=c:'(':(tail%r)!(map tail%r)++")"
_#_=""
g%r=g r#g
a!b=a++[','|a>"",b>""]++b
(#id)

Contoh penggunaan: (#id) ["RT Hq ","I xR k"]-> "R(I(x),T(H(R(k),q)))".

Cara kerjanya: selain kisi masukan r, fungsi tersebut #mengambil fungsi lain gsebagai argumen yang diterapkan rkapan pun karakter kiri atas adalah spasi. Jika itu adalah huruf kecil, kembalikan. Kalau tidak, itu harus karakter huruf besar dan #disebut secara rekursif, sekali dengan tailturun dan sekali dengan map tailke kanan. !bergabung dengan hasil dari panggilan rekursif dengan ,,, jika perlu. Semua dimulai dengan kisi masukan dan fungsi identitas.

nimi
sumber
0

Python 3, 187 byte

Masih mencari cara untuk bermain golf ini, tapi saya senang saya berhasil mengubahnya menjadi satu-liner.

lambda g,r=0,c=0:g[r][c]+'(%s)'%','.join([p(g,R,c)for R in range(r+1,len(g))if c<len(g[R])and' '!=g[R][c]][:1]+[p(g,r,C)for C in range(c+1,len(g[r]))if' '!=g[r][C]][:1])*g[r][c].isupper()
Tim Pederick
sumber