scala - Combinadores de analizadores, gramática separadora y construcción AST.

grammar abstract-syntax-tree (4)

Sería realmente genial tener una gramática legible para humanos, directamente "construyendo" la fuente del analizador ...

Me pregunto qué es esa "gramática cercana a la lectura humana".

¿Cómo separo la definición de gramática de la transformación en nodos AST?

Lo que tienes es un Packrat Parser escrito a mano.

Podría estar equivocado, pero entiendo esta pregunta como una solicitud para usar una definición de gramática independiente para crear un analizador. Y luego use ese analizador para obtener el árbol de sintaxis de la fuente analizada.

Entonces, la gramática podría ser una EBNF o PEG o CFG o "tu propia" gramática, ¿verdad?

De todas formas...

Permite comenzar con una "definición gramatical separada", por ejemplo, EBNF.
Luego necesita un analizador para la gramática, por ejemplo, un EBNFParser .
Analizar la gramática con los resultados del analizador es una estructura interna de esa gramática: un árbol de sintaxis.
Dado un árbol de sintaxis para una gramática válida, puede devolver una lista de asociación con las claves (como los meta identificadores) y adjuntarles reglas gramaticales.
foreach grammar key add matching grammar rule
Eso significa que debe elegir una Regla de gramática identificada por RuleName y agregar su Regla a un "Analizador construido".
Al final: tiene un "Analizador construido" ensamblado a partir de "Reglas gramaticales" individuales capaces de analizar la Fuente definida por la Gramática dada.
Al analizar la fuente, le proporciona un árbol de sintaxis para la fuente.

Paso 1

Grammar -> GrammarParser -> GrammarTree -> GrammarRules -> ConstructedParserForGrammar

Paso 2

Source -> ConstructedParserForGrammar -> Syntax Tree -> Transformations...

En otras palabras: es bastante complicado pasar de BNF a un analizador Packrat construido automáticamente.

Estoy escribiendo un lenguaje de programación funcional simple en Scala usando la biblioteca de parser-combinators.

La sintaxis se especifica aquí: https://github.com/hejfelix/Frase/blob/master/src/main/scala/it/vigtig/lambda/ParserLike.scala

Hay una cosa que no he podido resolver con la implementación: ¿cómo separo la definición de gramática de la transformación en nodos AST?

Sería genial tener una gramática legible para el ser humano directamente en la fuente del analizador, especialmente teniendo en cuenta que soy el único programador en el proyecto ATM y podría servir como documentación.

¿Cómo separo la gramática y el código específico de AST?

Bueno, en principio, toda su transformación AST tiene un tipo específico. Podrías definirlos todos en otra parte y usarlos desde tu definición gramatical. Se aclararía un poco las cosas. Alternativamente, podría definir sus definiciones gramaticales como funciones de "pasar por nombre" que se evalúan en la llamada y luego usarlas desde su transformación.

Básicamente, cualquier lenguaje le permite romper la complejidad definiendo las cosas en algún lugar y refiriéndose a ellas en cualquier otro lugar. Ya que scala te permite tener funciones como valores, esto es aún más fácil.

Esta es una gran pregunta, y una con la que luché durante mucho tiempo antes de encontrar una solución que creo que funciona muy bien para mí.

Cuando construyo un analizador, uso dos árboles de sintaxis diferentes:

un árbol de sintaxis concreto o CST: es una forma de árbol del texto y tiene una correspondencia 1: 1 con el texto. Todo lo que aparece en el texto también aparecerá en el CST.
un árbol de sintaxis abstracta o AST: esto no necesariamente tiene una correspondencia 1: 1 con el texto, ya que los detalles de texto innecesarios (como llaves, puntuación, etc.) se han eliminado y no aparecen en el AST.

Por lo tanto, pasar del texto de entrada al AST tiene dos pasos: el primer paso es analizar la cadena de entrada en un CST; El segundo paso es convertir el CST en un AST, desechando detalles innecesarios.

String -> CST Aquí es donde uso los combinadores de analizador. No hago ninguna manipulación de la estructura del árbol en esta etapa. La estructura del CST está totalmente determinada por los combinadores utilizados. Cada combinador produce un subárbol de cierta forma, que nunca cambio en esta etapa. No hay acciones adjuntas a los combinadores, por lo que la definición de la gramática está limpia y libre de cualquier información AST.
CST -> AST Aquí es donde masajeo el árbol de análisis, extrayendo las cosas importantes, ignorando el resto. También es aquí donde a menudo realizo verificaciones sensibles al contexto (por ejemplo, verificando que una definición de función no tenga nombres de parámetros duplicados), manteniendo estos detalles fuera de la etapa de análisis real.

Ejemplo: aquí hay un analizador JSON que construí usando este método:

Ya que este se compromete

https://github.com/scala/scala-parser-combinators/commit/33792d3380791ddafb41760604857d2fc43e54e1

Los combinadores de analizador se vinculan a una publicación que resuelve mi problema con precisión. Esta es, imho, la respuesta más precisa a mi pregunta.

La publicación aquí https://enear.github.io/2016/03/31/parser-combinators/ lexes en un árbol de sintaxis concreto primero (lexing) y luego produce un AST después.

Lo dejo aquí porque agrega un ejemplo a la respuesta aceptada.