Analiza składni dwuwymiarowej

25

tło

Alice i Bob tworzą język golfowy, aby wygrać każde wyzwanie PPCG. Alicja chce stworzyć dwuwymiarowy język, taki jak> <>, ale Bob woli składnię przedrostka-przedrostka jak w J. Jako kompromis decyduje się stworzyć dwuwymiarowy język przedrostka-przedrostka. Parser jest trudny do napisania i potrzebuje twojej pomocy!

Specyfikacja składni

W języku Alicji i Boba istnieją zmienne , które są reprezentowane małymi literami ASCII a-z, oraz funkcje , które są reprezentowane wielkimi literami ASCII A-Z. Funkcję można wywołać z jednym lub dwoma argumentami. Program jest prostokątna siatka liter a-zA-Zi spacji, a lewym górnym rogu nie może zawierać spacji. To jest przykład poprawnego programu:

F Gy
H   
R x 

Po przeanalizowaniu program przekształca się w wyrażenie języka w stylu C (C, Java, Python ...) zawierające zmienne jednoliterowe i wywołania funkcji w formacie <func>(<arg>)lub <func>(<arg1>,<arg2>). Na przykład powyższy program powoduje wyrażenie:

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

Szczegóły procesu analizowania są następujące:

  • Spacje są tylko wypełnianiem, więc nie są analizowane.
  • Każda zmienna a-zjest zawsze analizowana jako sama.
  • Każda funkcja A-Zjest analizowana jako wywołanie funkcji. Jego argumenty są najbliższymi wyrażeniami pod nim i po prawej stronie siatki, w tej kolejności. Jeśli obecny jest tylko jeden z nich, podaje się go jako jedyny argument. Możesz założyć, że wszystkie funkcje mają co najmniej jeden argument w siatce.

W powyższym przykładzie zmienne xi ysą analizowane jako one same. Funkcja Rnie ma nic poniżej i xpo prawej stronie, więc jest analizowana jako wywołanie jednoparametrowe R(x). Podobnie Hjest analizowany jako H(R(x)), ponieważ ma Rgo poniżej. Funkcja Gma xponiżej i ypo prawej stronie, więc jest analizowana jako G(x,y)i podobnie dla F. Wyrażenie przeanalizowane w lewym górnym rogu jest wynikiem analizy.

Wejście i wyjście

Twoje dane wejściowe to niepusty prostokątny układ znaków. Zawsze będzie to poprawny program w języku Alicji i Boba, ale może zawierać wyrażenia, które nie są używane w danych wyjściowych. Twój wynik będzie parsowanym wyrażeniem wynikającym z powyższego procesu.

Zasady i punktacja

Możesz napisać pełny program funkcji. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

Są one podane w formacie grid <newline> expressionz łącznikami ---między przypadkami. Format SE pozostawia niektóre wiersze puste, ale powinny być wypełnione spacjami.

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
źródło
Czy wyjście (A (B (D x)) (C (D x)))byłoby odpowiednie, czy format jest ustalony?
coredump
1
@coredump W tym wyzwaniu format wyjściowy jest ścisły; Alice i Bob chcą mieć możliwość bezpośredniego przeanalizowania wyrażenia.
Zgarb,
Gdzie jest część „infix” języka? Widzę tylko prefiks.
Paŭlo Ebermann,
6
Czy możesz rzeczywiście stworzyć język z tą składnią? :)
Martin Ender,
4
Kolejne wyzwanie: napisz meta-golfisty dla tej składni (biorąc pod uwagę drzewo wyrażeń, znajdź najmniejszą odpowiadającą mu siatkę). Dla dodatkowych trudności rozróżnij funkcje przemienne i nieprzemienne.
Martin Ender,

Odpowiedzi:

8

CJam, 67 62 60 58 57 54 bajtów

Dzięki Dennis za oszczędność 4 bajtów.

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

Definiuje nazwany blok (funkcję) Ji pozostawia go na stosie. Sama funkcja oczekuje tablicy ciągów na stosie, która reprezentuje siatkę wejściową, i pozostawia żądany ciąg zamiast niego.

Sprawdź to tutaj.

Chciałem rozwiązać ten problem, odkąd został opublikowany, ale najwyraźniej potrzebowałem nagrody i zbyt długiego rozwiązania w języku Pyth, aby zmotywować się wystarczająco.

Wyjaśnienie

Rozwiązanie jest oczywiście rekurencyjne i stopniowo buduje ciąg.

{
  :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
źródło
5

Python 2, 227 223 192 182 179 177 bajtów

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()

(Cztery spacje to tak naprawdę tabulatory)

Bierze listę 2d znaków jako pierwszy argument r.

niebieski
źródło
5

Pyth, 97 bajtów

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

Mój bóg, którego zrobienie zajęło dużo czasu (około 5/6 godzin?). Pyth tak naprawdę nie został zaprojektowany do tego ...

Wypróbuj tutaj .

Próba wyjaśnienia, a także odpowiednik w języku 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)

Gdzie funkcje Pprinti assignzwracają to, co podano.

niebieski
źródło
Dużo zwięzłości. Taki łał.
Addison Crump
5

Haskell, 124 122 120 119 bajtów

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)

Przykład użycia: (#id) ["RT Hq ","I xR k"]-> "R(I(x),T(H(R(k),q)))".

Jak to działa: oprócz siatki wejściowej rfunkcja #przyjmuje inną funkcję gjako argument, który jest stosowany, rgdy lewy górny znak jest spacją. Jeśli zamiast tego jest to mały znak, zwróć go. W przeciwnym razie musi to być duża litera i #jest wywoływana rekurencyjnie, raz, tailaby zejść na dół, a raz, map tailaby przejść w prawo. !łączy wyniki z połączeń rekurencyjnych z ,, jeśli to konieczne. Wszystko zaczyna się od siatki wejściowej i funkcji tożsamości.

nimi
źródło
0

Python 3, 187 bajtów

Wciąż szukam sposobów na grę w golfa, ale cieszę się, że udało mi się przekształcić go w jedno-liniowy.

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
źródło