Analysieren Sie eine zweidimensionale Syntax

25

Hintergrund

Alice und Bob erschaffen eine Golfsprache, um jede einzelne PPCG-Herausforderung zu gewinnen. Alice möchte eine zweidimensionale Sprache wie> <> erstellen, aber Bob bevorzugt eine Präfix-Infix-Syntax wie in J. Als Kompromiss entscheiden sie sich, eine zweidimensionale Präfix-Infix-Sprache zu erstellen. Der Parser ist eine Qual zum Schreiben, und sie brauchen Ihre Hilfe!

Syntaxspezifikation

In der Sprache von Alice und Bob gibt es Variablen , die durch ASCII-Kleinbuchstaben dargestellt werden a-z, und Funktionen , die durch ASCII-Großbuchstaben dargestellt werden A-Z. Eine Funktion kann mit einem oder zwei Argumenten aufgerufen werden. Ein Programm ist ein rechteckiges Gitter aus Buchstaben a-zA-Zund Leerzeichen. Die linke obere Ecke darf kein Leerzeichen enthalten. Dies ist ein Beispiel für ein gültiges Programm:

F Gy
H   
R x 

Wenn das Programm analysiert wird, wird es in einen Ausdruck einer C-artigen Sprache (C, Java, Python ...) umgewandelt, die Variablen mit einem Buchstaben und Funktionsaufrufe im Format <func>(<arg>)oder enthält <func>(<arg1>,<arg2>). Das obige Programm führt zum Beispiel zu folgendem Ausdruck:

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

Die Details des Analyseprozesses lauten wie folgt:

  • Die Leerzeichen sind nur Füllzeichen, daher werden sie nicht analysiert.
  • Jede Variable a-zwird immer als sich selbst analysiert.
  • Jede Funktion A-Zwird als Funktionsaufruf analysiert. Seine Argumente sind die engsten Ausdrücke darunter und rechts davon im Raster, in dieser Reihenfolge. Wenn nur eines davon vorhanden ist, wird es als einziges Argument angegeben. Sie können davon ausgehen, dass alle Funktionen mindestens ein Argument im Raster haben.

Im obigen Beispiel werden die Variablen xund yals sich selbst analysiert. Die Funktion Rhat nichts unter sich und xrechts davon, daher wird sie als Aufruf mit einem Argument analysiert R(x). Ebenso Hwird analysiert, wie H(R(x)), da es Rdarunter hat. Die Funktion Gbefindet sich rechts xdarunter und wird yanalysiert als G(x,y)und in ähnlicher Weise für F. Der in der oberen linken Ecke analysierte Ausdruck ist das Ergebnis des Analyseprozesses.

Ein- und Ausgabe

Ihre Eingabe ist ein nicht leeres rechteckiges Zeichenfeld. Es ist immer ein gültiges Programm in der Sprache von Alice und Bob, es kann jedoch Ausdrücke enthalten, die in der Ausgabe nicht verwendet werden. Ihre Ausgabe soll der analysierte Ausdruck sein, der sich aus dem obigen Prozess ergibt.

Regeln und Wertung

Sie können ein vollständiges Programm einer Funktion schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.

Testfälle

Diese werden im Format grid <newline> expressionmit Bindestrichen ---zwischen den Fällen angegeben. Das SE-Format lässt einige Zeilen leer, sie sollten jedoch mit Leerzeichen gefüllt sein.

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
quelle
Wäre eine Ausgabe wie (A (B (D x)) (C (D x)))passend oder ist das Format festgelegt?
Coredump
1
@coredump Bei dieser Herausforderung ist das Ausgabeformat streng. Alice und Bob möchten den analysierten Ausdruck direkt verwenden können.
Zgarb
Wo ist das "Infix" Teil der Sprache? Ich sehe nur Präfix.
Paŭlo Ebermann
6
Können Sie bitte tatsächlich eine Sprache mit dieser Syntax erstellen? :)
Martin Ender
4
Folgeherausforderung: Schreibe einen Metagolfer für diese Syntax (finde bei gegebenem Ausdrucksbaum das kleinste Gitter, das diesem entspricht). Unterscheiden Sie für zusätzliche Schwierigkeiten zwischen kommutativen und nichtkommutativen Funktionen.
Martin Ender

Antworten:

8

CJam, 67 62 60 58 57 54 Bytes

Vielen Dank an Dennis für das Speichern von 4 Bytes.

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

Dies definiert einen benannten Block (Funktion) Jund belässt ihn auf dem Stapel. Die Funktion selbst erwartet ein Array von Zeichenfolgen auf dem Stapel, das das Eingaberaster darstellt, und lässt die gewünschte Zeichenfolge an ihrer Stelle.

Teste es hier.

Ich hatte vor, dieses Problem anzugehen, seit es veröffentlicht wurde, aber anscheinend brauchte ich ein Kopfgeld und eine zu lange Pyth-Lösung, um mich ausreichend zu motivieren.

Erläuterung

Die Lösung ist natürlich rekursiv und baut den String schrittweise auf.

{
  :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
quelle
5

Python 2, 227 223 192 182 179 177 Bytes

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

(Die vier Leerzeichen sind in der Tat Registerkarten)

Nimmt eine 2D-Liste von Zeichen als erstes Argument für r.

Blau
quelle
5

Pyth, 97 Bytes

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

Mein Gott, das hat lange gedauert (ca. 5/6 Stunden?). Pyth war wirklich nicht dafür gedacht ...

Probieren Sie es hier aus .

Erklärungsversuch sowie Python-Äquivalent

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)

Wo die Funktionen Pprintund assignzurückgeben, was sie gegeben sind.

Blau
quelle
Viel Prägnanz. So wow.
Addison Crump
5

Haskell, 124 122 120 119 Bytes

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)

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

rFunktionsweise : Neben dem Eingaberaster #übernimmt die Funktion eine weitere Funktion gals Argument, das angewendet wird, rwenn das Zeichen oben links ein Leerzeichen ist. Wenn es sich stattdessen um ein Kleinbuchstabenzeichen handelt, geben Sie es zurück. Andernfalls muss es ein Großbuchstabe sein und #wird rekursiv aufgerufen, einmal mit tailnach unten und einmal mit map tailnach rechts. !Verbindet die Ergebnisse der rekursiven Aufrufe bei ,Bedarf mit einem . Alles beginnt mit dem Eingaberaster und der Identitätsfunktion.

nimi
quelle
0

Python 3, 187 Bytes

Ich bin immer noch auf der Suche nach Möglichkeiten, dies herunterzuspielen, aber ich bin nur froh, dass ich es geschafft habe, daraus einen Einzeiler zu machen.

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
quelle