¿Existe algún lenguaje de programación (o scripting) (o algún lenguaje específico de dominio) que tenga dos operadores binarios opl
y opr
de la misma precedencia que opl
ser asociativo a la izquierda y asociativo a la opr
derecha?
(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?
language-design
parsing
Basile Starynkevitch
fuente
fuente
x <@ y @> z
con<@
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).if_then_else_
o[1;2;3]
se definió en bibliotecas?).Respuestas:
¡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 :
Entonces, en GHC , si definimos un
infixl
operador<@
asociativo@>
a la izquierda ( ) y un operador asociativo a la derecha en el mismo nivel de precedencia, digamos 0, entonces evaluarx <@ y @> z
da el error(De hecho, también puede declarar que un operador es infijo pero no asociativo
==
, por lo quex == y == z
es 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
que, cuando se llama, está escrito
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, tenemosx <@ y @> z
analizando comox <@ (y @> z)
; yx @> y <@ z
analizando 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
analizando como
o
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, obtenemosLa 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).
fuente
graphviz
?)\ttfamily \Tree[.<@ [.<@ [.<@ a b ] [.@> c [.@> d [.@> e f ]]]] g ]
.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.
fuente