¿Cómo hago tokens de sangría/dedentificación de estilo de pitón con alex/haskell?

Question

Escribo un lexer para un lenguaje pequeño en Alex con Haskell.

El idioma se especifica para tener una indentación pitonesca significativa, con un token INDENT o un token DEDENT emitido cada vez que cambia el nivel de sangría.

En un lenguaje imperativo tradicional como C, mantendría un global en el lexer y lo actualizaría con el nivel de sangría en cada línea.

Esto no funciona en Alex/Haskell porque no puedo almacenar datos globales en ninguna parte con Haskell, y no puedo poner todas mis reglas de lexing dentro de ninguna mónada ni nada.

Entonces, ¿cómo puedo hacer esto? ¿Es posible? ¿O tendré que escribir mi propio Lexer y evitar el uso de alex?

Answer 1

Tenga en cuenta que en otros lenguajes sensibles al espacio en blanco, como Haskell, el manejo de la disposición se realiza realmente en el lexer. GHC de hecho implementa el manejo del diseño en Alex. Aquí está la fuente:

https://github.com/ghc/ghc/blob/master/compiler/parser/Lexer.x

Hay algunos errores graves en su pregunta que te llevan por mal camino, como jrockway señala. "No puedo almacenar datos globales en ninguna parte con Haskell" está en la pista incorrecta. En primer lugar, usted puede tener estado global, en segundo lugar, no debe utilizar el estado global aquí, cuando Alex es totalmente compatible con las transiciones de estado en las reglas de una manera segura.

Mire la estructura de AlexState que proporciona Alex, lo que le permite pasar el estado a través de su lexer. Luego, observe cómo se usa el estado en la implementación del diseño de GHC para implementar la sangría/indefinición de las reglas de diseño. (Busque "Procesamiento de diseño" en el lexer de GHC para ver cómo se empuja y se levanta el estado).

Answer 2

no puedo almacenar los datos globales en cualquier lugar con Haskell

esto no es cierto; en la mayoría de los casos es suficiente algo como el State monad, pero también está el ST monad.

Sin embargo, no necesita un estado global para esta tarea. Escribir un analizador consiste en dos partes; análisis léxico y análisis de sintaxis. El análisis léxico solo convierte una secuencia de caracteres en una secuencia de tokens significativos. El análisis de sintaxis convierte tokens en un AST; aquí es donde debes lidiar con la sangría.

Mientras está interpretando la sangría, llamará a una función del manejador cuando cambie el nivel de sangría: cuando aumenta (anidamiento), llama a la función del manejador (quizás con un arg incrementado, si desea rastrear la sangría nivel); cuando el nivel disminuye, simplemente devuelve la parte relevante de AST de la función.

(Como un lado, el uso de una variable global para esto es algo que tampoco se me ocurriría en un lenguaje imperativo - en todo caso, es una variable de instancia. La mónada de Estado es muy similar conceptualmente a esto.)

Finalmente, creo que la frase "No puedo poner todas mis reglas de lexing dentro de una mónada" indica algún tipo de malentendido de las mónadas. Si necesitaba para analizar y mantener el estado global, el código se vería así:

data AST = ... 
type Step = State Int AST 

parseFunction :: Stream -> Step 
parseFunction s = do 
    level <- get 
    ... 
    if anotherFunction then put (level + 1) >> parseFunction ... 
    else parseWhatever 
    ... 
    return node 

parse :: Stream -> Step 
parse s = do 
    if looksLikeFunction then parseFunction ... 

main = runState parse 0 -- initial nesting of 0 

En lugar de la combinación de aplicaciones de funciones con (.) o ($), se combinan con (>>=) o (>>). Aparte de eso, el algoritmo es el mismo. (No hay una "mónada" para estar "dentro".)

Por último, que le gustaría funtores aplicativos:

eval :: Environment -> Node -> Evaluated 
eval e (Constant x) = Evaluated x 
eval e (Variable x) = Evaluated (lookup e x) 
eval e (Function f x y) = (f <$> (`eval` x) <*> (`eval` y)) e 

(o

eval e (Function f x y) = ((`eval` f) <*> (`eval` x) <*> (`eval` y)) e 

si tiene algo así como "funcall" ... pero estoy divagando.)

Hay mucha literatura sobre el análisis con funcionadores aplicativos, mónadas y flechas; todos los cuales tienen el potencial de resolver su problema. Lea sobre eso y vea lo que obtiene.