Especificación de una prioridad dinámica y precedencia para un operador en Menhir/Ocamlyacc

Question

Estoy tratando de analizar un lenguaje donde los operadores tienen atributos dinámicos (prioridad y precedencia) usando el analizador Menhir (similar a Ocamlyacc). Durante la fase de léxico, todos los operadores rellenan un token OP:string (por lo que "+" se convierte en (OP "+"), etc.).

Los atributos del operador se determinan en el tiempo de análisis y llenan una tabla que asocia operadores y sus atributos. Dada esta tabla, ¿cómo puedo instruir a Menhir para que cambie dinámicamente la prioridad de la regla que analiza los operadores según los datos de esta tabla?

Gracias, CharlieP.

Answer 1

Lamento responder con un tipo de comentario "lo estás haciendo mal". Tengo tres objeciones que espero son constructivas, en orden decreciente de pertinencia:

1. Menhir no es para actualizaciones dinámicas de gramática; Si insistes en cambiar tu gramática en el momento del análisis, deberías utilizar una herramienta que proporcione esta función, como el analizador GLR Dypgen. El manual de Dypgen menciona la posibilidad de actualizar dinámicamente las prioridades del operador, de forma limitada (parece que puede agregar nuevos operadores y las prioridades correspondientes, pero no cambiar la prioridad de los existentes) que pueden o no coincidir con sus necesidades. Ver la sección 6.6 del Dypgen manual (PDF), página ... 42.

2. La actualización dinámica de una gramática CFG no es, creo, la mejor manera de manejar las precedencias de operador definidas por el usuario. Agda tiene operadores de mixfix definidos por el usuario muy generales, y su solución es más o menos la siguiente: utilice su analizador CFG para analizar la estructura gramatical que se conoce estáticamente, pero para la expresión que posiblemente utilice precendencias sofisticadas y asociaciones, simplemente analícelas en una lista de tokens. Por ejemplo, let x = if foo then x + y * z else bar se analizaría en algo así como Let(x, If(foo, Expr(x, +, y, *, z), bar). Un pase especializado posterior puede recopilar la información necesaria para analizar posteriormente aquellos en los nodos Expr en su estructura especializada. Usa los generadores de analizadores para lo que son buenos (CFG rico estáticamente conocido) y utiliza un pase de postprocesamiento para las cosas complejas, mal definidas y dinámicas. Los chicos de Agda tienen algo de literatura sobre el tema, por ejemplo Parsing Mixfix Operators, Danielsson y Norell, 2009.

   Desde el punto de vista del diseño, le recomiendo encarecidamente que separe su lex y análisis en varios pases diferentes, cada uno de ellos bien -definido y utilizando solo la información recopilada en la estructura anterior, en lugar de tratar de cambiar dinámicamente su propio comportamiento. Tendrás algo mucho más simple y mucho más robusto.

3. La prioridad y las prioridades dinámicas o definidas por el usuario son, en mi opinión, un poco perniciosas. OCaml tiene un sistema diferente en el que las prioridades de precedencia del operador están determinadas por sus primeros caracteres (por ejemplo, @, @@ y @+ son asociaciones correctas). Es un poco restrictivo para las personas que eligen un operador infijo, pero hace código lector vive mucho más cómodo, ya que solo tienen un conjunto de reglas gramaticales para aprender, en lugar de tener que adaptar dinámicamente sus ojos a cualquier nueva pieza de código . Si desea permitir la inserción de fragmentos de código extraños con una sintaxis completamente diferente, los mecanismos de cotizaciones (por ej., Camlp4 <:foo<...>>) son mucho más sólidos que manipular las asociaciones y prioridades a nivel de operador, y también son mucho más simples de analizar.

   Dicho esto, los proyectos tienen diferentes necesidades y lo entendería completamente si insiste en cambiar dinámicamente la precedencia y asociatividad de los operadores para alguna aplicación que desconozco.Solo tenga en cuenta que no es la única forma de evitarlo, y que a veces la consistencia y la simplicidad son mejores que la flexibilidad absoluta.