haskell - sintactico - antlr tutorial español

¿Debo usar un Lexer cuando use una biblioteca combinadora de analizadores como Parsec?

Question

Al escribir un analizador sintáctico en una biblioteca de combinación de analizadores como Haskell''s Parsec, generalmente tiene 2 opciones:

• Escribe un lexer para dividir tu entrada String en tokens, luego realiza el análisis en [Token]
• Escribir directamente combinadores de analizadores en String

El primer método a menudo parece tener sentido dado que muchas entradas de análisis se pueden entender como fichas separadas por espacios en blanco.

En otros lugares, he visto a personas recomendar no tokenizar (o escanear o leer , cómo algunos lo llaman), con la sencillez que se cita como la razón principal.

¿Cuáles son las ventajas y desventajas generales entre lexing y no hacerlo?

Answer 1

La diferencia más importante es que el lexing traducirá su dominio de entrada .

Un buen resultado de esto es que

• Ya no tienes que pensar en el espacio en blanco. En un analizador directo (no-léxico), tienes que rociar analizadores space en todos los lugares donde se permite el espacio en blanco, lo cual es fácil de olvidar y desordena su código si el espacio en blanco debe separar todos sus tokens de todos modos.

• Puedes pensar en tus comentarios de una manera pieza por pieza, lo cual es fácil para los humanos.

Sin embargo, si realiza lexing, obtiene los problemas que

• Ya no puede usar analizadores comunes en String ; por ejemplo, para analizar un número con una biblioteca Función parseFloat :: Parsec String s Float (que opera en un flujo de entrada String), debe hacer algo como takeNextToken :: TokenParser String y execute el parseFloat analizador sintáctico, inspeccionando el resultado del análisis sintáctico (generalmente, Either ErrorMessage a ). Esto es complicado de escribir y limita la capacidad de compilación.

• Has ajustado todos los mensajes de error. Si su analizador en tokens falla en el vigésimo token, ¿dónde está en la cadena de entrada? Tendrá que asignar manualmente las ubicaciones de error a la cadena de entrada, lo cual es tedioso (en Parsec esto significa ajustar todos los valores de SourcePos ).

• El informe de errores generalmente es peor. Ejecutar una string "hello" *> space *> float en una entrada incorrecta como "hello4" le dirá con precisión que hay un espacio en blanco esperado después del hello , mientras que un lexer solo afirmará haber encontrado un "invalid token" .

• Muchas cosas que uno esperaría que fueran unidades atómicas y estar separadas por un lexer son en realidad bastante "demasiado difíciles" para que las identifique un lexer. Tomemos como ejemplo los literales String - de repente "hello world" ya no son dos tokens "hello y world" (pero solo , por supuesto, si las cotizaciones no se escapan, como /" ) - aunque esto es muy natural para un analizador sintáctico, significa reglas complicadas y casos especiales para un lexer.

• No puede volver a utilizar los analizadores en tokens como muy bien. Si define cómo analizar un doble de una String , expórtela y el resto del mundo puede usarla; no pueden ejecutar tu tokenizador (especializado) primero.

• Estás atrapado con eso. Cuando está desarrollando el lenguaje para analizar, usar un lector lex puede llevarlo a tomar decisiones tempranas, arreglando cosas que tal vez quiera cambiar después. Por ejemplo, imagine que definió un idioma que contiene algún token de Float . En algún momento, desea introducir literales negativos ( -3.4 y - 3.4 ) - esto podría no ser posible debido al espacio en blanco de interpretación lexer como separador de fichas. Con un enfoque de solo analizador, puede mantenerse más flexible, facilitando los cambios en su idioma. Esto no es realmente sorprendente, ya que un analizador es una herramienta más compleja que codifica reglas inherentes.

Para resumir, recomendaría escribir analizadores libres de lexer para la mayoría de los casos.

Al final, un lexer es solo un analizador "embotado" *; si necesita un analizador de todos modos, combínelo en uno.

_{* De la teoría de la informática, sabemos que todos los idiomas regulares también son idiomas sin contexto ; Los lexers suelen ser regulares, los analizadores sintácticamente libres de contexto o incluso sensibles al contexto (los analizadores monádicos como Parsec pueden expresar sensibilidad al contexto).}