lenguaje con dos operadores binarios de la misma precedencia, asociativo a la izquierda y asociativo a la derecha

11

¿Existe algún lenguaje de programación (o scripting) (o algún lenguaje específico de dominio) que tenga dos operadores binarios oply oprde la misma precedencia que oplser asociativo a la izquierda y asociativo a la oprderecha?

(No puedo encontrar ese ejemplo, pero estoy tratando de codificar un analizador lo suficientemente general como para manejar ese caso extraño)

¿Cómo se analizarían las expresiones de la forma x opl y opr z o x opr y opl z ? ¿Y más generalmente con aún más operandos?

Basile Starynkevitch
fuente
44
Si te duele, no hagas eso.
CodesInChaos
1
En Haskell, puede definir sus propios operadores de infijo con sus propias precedentes y, en este caso, obtiene un error; si tiene x <@ y @> zcon <@que se asociativo por la izquierda y @>siendo asociativo por la derecha, GHC le da una "Precedencia error de análisis": "No se puede mezclar ' <@' [infixl 0] y ' @>' [infixr 0] en la misma expresión infija" (donde he definido estos operadores en el nivel 0 para el ejemplo).
Antal Spector-Zabusky
@ AntalSpector-Zabusky: ¡Esa sería una gran respuesta!
Basile Starynkevitch
@ AntalSpector-Zabusky: Lo mismo en Swift. Creo que realmente puede definir los operadores, pero en una expresión debe usar todos los operadores asociativos izquierdos o todos los asociativos derechos con la misma precedencia. Por lo tanto, puede usar x leftop y leftop z, o x rightop y rightop z, pero no x leftop y rightop z.
gnasher729
@BasileStarynkevitch: ¡Como quieras! Como mencionó "analizadores flexibles", incluí un par de lenguajes más oscuros que tienen analizadores muy flexibles (¿alguna vez quiso if_then_else_o [1;2;3]se definió en bibliotecas?).
Antal Spector-Zabusky

Respuestas:

10

¡Aquí hay tres idiomas que le permiten definir sus propios operadores, que hacen dos cosas y media diferentes ! Haskell y Coq no permiten este tipo de travesuras, pero de manera diferente, mientras que Agda permite este tipo de mezcla de asociatividades.


Primero, en Haskell , simplemente no tienes permitido hacer esto. Puede definir sus propios operadores y darles la precedencia (de 0 a 9) y la asociatividad que elija. Sin embargo, el Informe Haskell no le permite mezclar asociatividades :

Los operadores consecutivos sin paréntesis con la misma precedencia deben ser asociativos izquierda o derecha para evitar un error de sintaxis. [Informe Haskell 2010, cap. 3]

Entonces, en GHC , si definimos un infixloperador <@asociativo @>a la izquierda ( ) y un operador asociativo a la derecha en el mismo nivel de precedencia, digamos 0, entonces evaluar x <@ y @> zda el error

El error de análisis de precedencia
    no puede mezclar ' <@' [ infixl 0] y ' @>' [ infixr 0] en la misma expresión infija

(De hecho, también puede declarar que un operador es infijo pero no asociativo ==, por lo que x == y == zes un error de sintaxis).


Por otro lado, está el comprobador de lenguaje / teorema de tipo dependiente Agda (que, ciertamente, es considerablemente menos convencional). Agda tiene una de las sintaxis más maleables de cualquier lenguaje que conozco, y admite operadores mixfix : la biblioteca estándar contiene la función

if_then_else_ : ∀ {a} {A : Set a} → Bool → A → A → A

que, cuando se llama, está escrito

if b then t else f

con los argumentos llenando los guiones bajos! Menciono esto porque significa que debe admitir un análisis increíblemente flexible. Naturalmente, Agda también tiene declaraciones de fijeza (aunque sus niveles de precedencia oscilan sobre números naturales arbitrarios, y típicamente están en 0–100), y Agda le permite mezclar operadores de la misma precedencia pero con fijezas diferentes. Sin embargo, no puedo encontrar información sobre esto en la documentación, así que tuve que experimentar.

Reutilicemos nuestro <@y @>desde arriba. En los dos casos simples, tenemos

  • x <@ y @> zanalizando como x <@ (y @> z); y
  • x @> y <@ zanalizando como (x @> y) <@ z.

Creo que lo que Agda hace es agrupar la línea en fragmentos "asociativos izquierdos" y "asociativos derechos", y, a menos que esté pensando en cosas incorrectas, el fragmento asociativo correcto obtiene "prioridad" al captar los argumentos adyacentes. Entonces eso nos da

a <@ b <@ c @> d @> e @> f <@ g

analizando como

(((a <@ b) <@ (c @> (d @> (e @> f)))) <@ g

o

Analizar el árbol de <code> (((a <@ b) <@ (c @> (d </code> @> (e @> f)))) <@ g

Sin embargo, a pesar de mis experimentos, adiviné mal la primera vez que escribí eso, lo que podría ser instructivo :-)

(Y Agda, como Haskell, tiene operadores no asociativos, que dan errores de análisis correctamente, por lo que sería posible que las asociatividades mixtas también generen un error de análisis).


Finalmente, está el lenguaje Coq , que prueba el teorema / dependientemente , que tiene una sintaxis aún más flexible que Agda porque sus extensiones de sintaxis se implementan realmente al proporcionar especificaciones para las nuevas construcciones sintácticas y luego reescribirlas en el lenguaje central (vagamente como macro , Supongo). En Coq, la sintaxis de la lista [1; 2; 3]es una importación opcional de la biblioteca estándar. ¡Las nuevas sintaxis incluso pueden unir variables!

Una vez más, en Coq, podemos definir nuestros propios operadores de infijo y darles niveles de precedencia (de 0 a 99, principalmente) y asociatividades. Sin embargo, en Coq, cada nivel de precedencia solo puede tener una asociatividad . Entonces, si definimos <@como asociativo a la izquierda y luego intentamos definirlo @>como asociativo a la derecha en el mismo nivel, digamos 50, obtenemos

Error: el nivel 50 ya se ha declarado asociativo a la izquierda, mientras que ahora se espera que sea asociativo a la derecha

La mayoría de los operadores en Coq están en niveles que son divisibles por 10; Si he tenido problemas de asociatividad (estas asociatividades de nivel son globales), generalmente he superado el nivel en uno en cualquier dirección (generalmente hacia arriba).

Antal Spector-Zabusky
fuente
2
(Vaya, qué selección más extraña de idiomas. ¿Puedes decir que estudio teoría del lenguaje de programación? :-P)
Antal Spector-Zabusky
Muchas gracias por su respuesta detallada. Por cierto, ¿cómo dibujó la imagen (con qué herramienta graphviz?)
Basile Starynkevitch
Por cierto, ¿por qué "fijeza" en lugar de "precedencia"?
Basile Starynkevitch
@BasileStarynkevitch: Eso depende de dónde te refieres. Si te refieres a la sección Coq, eso fue solo un error :-) (¡Y uno que ya está solucionado!)
Antal Spector-Zabusky
1
@BasileStarynkevitch: ¡También me perdí tu pregunta sobre la foto! Dibujé eso con el paquete qtree de LaTeX , y lo rendericé en LaTeXit , un procesador de fragmentos de LaTeX para Mac. El código fuente relevante era \ttfamily \Tree[.<@ [.<@ [.<@ a b ] [.@> c [.@> d [.@> e f ]]]] g ].
Antal Spector-Zabusky
2

Desde que Douglas Crockford los popularizó, los analizadores Pratt (o analizadores de precedencia de operador de arriba hacia abajo) se han vuelto más comunes. Estos analizadores funcionan desde una tabla de precedencia de operadores y asociatividad, en lugar de tener las reglas integradas en una gramática fija, por lo que son útiles para los idiomas que permiten a los usuarios definir sus propios operadores.

Tienen una función de análisis que funciona analizando primero el término más a la izquierda de una expresión, luego vinculando recursivamente nuevos operadores y términos de la mano derecha siempre que se unan adecuadamente. Los operadores asociativos a la izquierda vincularán los términos de la derecha que tienen prioridad hasta e incluyen la misma precedencia, mientras que los operadores asociativos a la derecha solo se unen a su nivel de precedencia, pero no lo incluyen. Creo que esto da como resultado el mismo árbol de análisis que para Agda, citado anteriormente.

Jules
fuente