¿Los pases de análisis y lexing separados son una buena práctica con los combinadores de analizador?

18

Cuando comencé a usar los combinadores de analizador sintáctico, mi primera reacción fue una sensación de liberación de lo que parecía una distinción artificial entre analizador y lexing. De repente, ¡todo se estaba analizando!

Sin embargo, recientemente encontré esta publicación en codereview.stackexchange que ilustra a alguien que restablece esta distinción. Al principio pensé que esto era muy tonto de ellos, pero luego el hecho de que existan funciones en Parsec para apoyar este comportamiento me lleva a cuestionarme.

¿Cuáles son las ventajas / desventajas de analizar sobre una secuencia ya lexed en combinadores analizadores?

parsing lexer parser-combinator Eli Frey
fuente
¿Podría alguien agregar la etiqueta [parser-combinator]?
Eli Frey

Respuestas:

15

Bajo análisis, entendemos con mayor frecuencia el análisis de lenguajes libres de contexto. Un lenguaje libre de contexto es más poderoso que uno normal, por lo tanto, el analizador puede (muy a menudo) hacer el trabajo del analizador léxico de inmediato.

Pero, esto es a) bastante antinatural b) a menudo ineficiente.

Para a), si pienso en cómo se ifve una expresión, por ejemplo , creo que SI expr ENTONCES expr ELSE expr y no 'i' 'f', tal vez algunos espacios, entonces cualquier carácter con el que una expresión pueda comenzar, etc. idea.

Para b) hay herramientas poderosas que hacen un excelente trabajo al reconocer entidades léxicas, como identificadores, literales, corchetes de todo tipo, etc. Ellos harán su trabajo prácticamente en ningún momento y le brindarán una interfaz agradable: una lista de tokens. Ya no te preocupes por omitir espacios en el analizador, tu analizador será mucho más abstracto cuando se trata de fichas y no de personajes.

Después de todo, si crees que un analizador debería estar ocupado con cosas de bajo nivel, ¿por qué entonces procesar los personajes? ¡Se podría escribir también en el nivel de bits! Usted ve, un analizador que funciona en el nivel de bits sería casi incomprensible. Es lo mismo con los personajes y tokens.

Solo mis 2 centavos.

Ingo
fuente
3
Solo por razones de precisión: un analizador siempre puede hacer el trabajo de un analizador léxico.
Giorgio
Además, con respecto a la eficiencia: no estoy seguro de si un analizador sería menos eficiente (más lento). Esperaría que la gramática resultante contuviera una subgramática que describiera un lenguaje regular, y el código para esa subgramática sería tan rápido como un analizador léxico correspondiente. En mi opinión, el punto real es (a): cuán natural e intuitivo es trabajar con un analizador más simple y abstracto.
Giorgio el
@Giorgio - Con respecto a tu primer comentario: tienes razón. Lo que tenía en mente aquí son casos en los que el lexer hace un trabajo pragmático que facilita la gramática, de modo que uno puede usar LALR (1) en lugar de LALR (2).
Ingo
2
He eliminado mi aceptación de su respuesta después de más experimentación y reflexión. Parece que ustedes dos provienen de su mundo de Antlr et all. Teniendo en cuenta la naturaleza de primera clase de los combinadores de analizador, a menudo simplemente termino definiendo un analizador de envoltura para mis analizadores de tokens, dejando cada token como un solo nombre en la capa de analizadores. por ejemplo, su ejemplo if se vería así if = string "if" >> expr >> string "then" >> expr >> string "else" >> expr.
Eli Frey
1
El rendimiento sigue siendo una pregunta abierta, haré algunos puntos de referencia.
Eli Frey
8

Todo el mundo sugiere que separar el lexing y el parsing es una "buena práctica", tengo que estar en desacuerdo, en muchos casos realizar lexing y parsing en una sola pasada proporciona mucho más poder, y las implicaciones de rendimiento no son tan malas como se presentan en el otras respuestas (ver Packrat ).

Este enfoque brilla cuando uno tiene que mezclar varios idiomas diferentes en una sola secuencia de entrada. Esto no solo es necesario para los extraños lenguajes orientados a la metaprogramación como Katahdin y similares , sino también para aplicaciones mucho más convencionales, como la programación alfabetizada (mezcla de látex y, por ejemplo, C ++), el uso de HTML en los comentarios, el relleno de Javascript en HTML, y pronto.

SK-logic
fuente
En mi respuesta sugerí que es una "buena práctica en ciertos contextos" y no que es una "mejor práctica en todos los contextos".
Giorgio
5

Un analizador léxico reconoce un lenguaje regular y un analizador reconoce un lenguaje libre de contexto. Dado que cada lenguaje regular también está libre de contexto (puede definirse mediante una llamada gramática lineal derecha ), un analizador también puede reconocer un lenguaje regular y la distinción entre analizador léxico y analizador parece agregar una complejidad innecesaria: un contexto único libre de gramática (analizador) podría hacer el trabajo de un analizador y un analizador léxico.

Por otro lado, puede ser útil capturar algunos elementos de un lenguaje sin contexto a través de un lenguaje regular (y, por lo tanto, un analizador léxico) porque

  1. A menudo, estos elementos aparecen con tanta frecuencia que pueden tratarse de manera estándar: reconociendo literales de números y cadenas, palabras clave, identificadores, omitiendo espacios en blanco, etc.
  2. La definición de un lenguaje regular de tokens simplifica la gramática resultante libre de contexto, por ejemplo, uno puede razonar en términos de identificadores, no en términos de caracteres individuales, o puede ignorar el espacio en blanco por completo si no es relevante para ese idioma en particular.

Por lo tanto, separar el análisis del análisis léxico tiene la ventaja de que puede trabajar con una gramática más simple y libre de contexto y encapsular algunas tareas básicas (a menudo rutinarias) en el analizador léxico (divide et impera).

EDITAR

No estoy familiarizado con los combinadores de analizador sintáctico, por lo que no estoy seguro de cómo se aplican las consideraciones anteriores en ese contexto. Mi impresión es que, incluso con los combinadores de analizador sintáctico, uno solo tiene una gramática libre de contexto, distinguir entre dos niveles (análisis léxico / análisis) podría ayudar a hacer que esta gramática sea más modular. Como se dijo, la capa inferior de análisis léxico podría contener analizadores básicos reutilizables para identificadores, literales, etc.

Giorgio
fuente
2
Lexemes cae en gramáticas regulares, no de forma natural, sino por convención, ya que todos los lexers se basan en motores de expresión regular. Está limitando el poder expresivo de los idiomas que puede diseñar.
SK-logic
1
¿Puede dar un ejemplo de un idioma para el que sería apropiado definir lexemas que no pueden describirse como un lenguaje normal?
Giorgio
1
por ejemplo, en un par de los lenguajes específicos de dominio que he construido, los identificadores podrían haber sido expresiones TeX, lo que simplificó la impresión bonita del código, por ejemplo, una expresión como \alpha'_1 (K_0, \vec{T}), donde \ alpha'_1, K_0 y \ vec {T} son identificadores
SK-logic
1
Dada una gramática libre de contexto, siempre puede tomar un N no terminal y tratar las palabras que puede derivar como unidades que tienen un significado útil en sí mismas (por ejemplo, una expresión, un término, un número, una declaración). Esto se puede hacer independientemente de cómo analice esa unidad (analizador, analizador + lexer, etc.). En mi opinión, la elección de un analizador + lexer es más técnica (cómo implementar el análisis) que semántica (cuál es el significado de los bloques de código fuente que analiza). Tal vez estoy pasando por alto algo, pero los dos aspectos me parecen ortogonales.
Giorgio
3
Entonces, estoy de acuerdo con usted: si define algunos bloques de construcción básicos arbitrarios ( lexemas ) y desea utilizar un analizador léxico para reconocerlos, esto no siempre es posible. Me pregunto si este es el objetivo de un lexer. Según tengo entendido, el objetivo de un analizador léxico es más técnico: eliminar algunos detalles de implementación tediosos de bajo nivel del analizador.
Giorgio
3

Simplemente, el lexing y el análisis deberían separarse porque son diferentes complejidades. Lexing es un DFA (autómata finito determinista) y un analizador es un PDA (autómata push-down). Esto significa que el análisis consume inherentemente más recursos que el lexing, y existen técnicas de optimización específicas disponibles solo para DFA. Además, escribir una máquina de estados finitos es mucho menos complejo y es más fácil de automatizar.

Está siendo un desperdicio al usar un algoritmo de análisis para lex.

DeadMG
fuente
Si usa un analizador sintáctico para hacer un análisis léxico, el PDA nunca usaría la pila, básicamente funcionaría como un DFA: simplemente consumir información y saltar entre estados. No estoy 100% seguro, pero creo que las técnicas de optimización (que reducen el número de estados) que se pueden aplicar a un DFA también se pueden aplicar a un PDA. Pero sí: es más fácil escribir el analizador léxico como tal sin usar una herramienta más poderosa, y luego escribir un analizador más simple encima.
Giorgio
Además, hace que todo sea más flexible y sostenible. Por ejemplo, supongamos que tenemos un analizador para el lenguaje Haskell sin la regla de diseño (es decir, con punto y coma y llaves). Si tenemos un lexer separado, ahora podríamos agregar las reglas de diseño simplemente haciendo otro pase sobre los tokens, agregando llaves y punto y coma según sea necesario. O, para un ejemplo más fácil: supongamos que comenzamos con un lenguaje que admite caracteres ASCII solo en identificadores y ahora queremos admitir letras unicode en los identificadores.
Ingo
1
@Ingo, y ¿por qué necesitarías hacerlo en un lexer separado? Solo factoriza esos terminales.
SK-logic
1
@ SK-logic: no estoy seguro de entender tu pregunta. Por qué un lexer separado puede ser una buena opción, he tratado de corroborarlo en mi publicación.
Ingo
Giorgio, no. La pila es un componente crucial de un analizador de estilo LALR normal. Hacer lexing con un analizador es un desperdicio de memoria horrible (tanto el almacenamiento estático como el asignado dinámicamente) y será mucho más lento. El modelo Lexer / Parser es eficiente
úsalo
1

Una de las principales ventajas de parse / lex por separado es la representación intermedia: el flujo de tokens. Esto se puede procesar de varias maneras que de otra manera no serían posibles con un lex / parse combinado.

Dicho esto, descubrí que un buen método recursivo decente puede ser menos complicado y más fácil de trabajar que aprender un generador de analizador, y tener que descubrir cómo expresar la debilidad de la gramática dentro de las reglas del generador de analizador sintáctico.

sylvanaar
fuente
¿Podría explicar más sobre las gramáticas que se expresan más fácilmente en una secuencia prefabricada que luego se realiza en tiempo de análisis? Solo tengo experiencia en la implementación de lenguajes de juguete y pocos formatos de datos, por lo que tal vez me haya perdido algo. ¿Ha notado alguna característica de rendimiento entre sus analizadores RD parser / lex combinados a mano y los generadores alimentados por BNF (supongo)?
Eli Frey