lexers vs analizadores

¿Los lexers y analizadores son realmente tan diferentes en teoría?

Parece de moda odiar las expresiones regulares: encoding de terror , otra publicación de blog .

Sin embargo, las herramientas populares basadas en lexings: pygments , geshi o embellecer , todas usan expresiones regulares. Parecen leer cualquier cosa …

Cuando lexing es suficiente, ¿cuándo necesita EBNF?

¿Alguien ha usado los tokens producidos por estos lexers con generadores de analizadores de bisontes o antlr?

Lo que los analizadores y los lectores tienen en común:

  1. Leen símbolos de algún alfabeto de su entrada.

    • Sugerencia: el alfabeto no necesariamente tiene que ser de letras. Pero tiene que ser de símbolos que son atómicos para el lenguaje que entiende el analizador / lexer.
    • Símbolos para el lexer: caracteres ASCII.
    • Símbolos para el analizador: los tokens particulares, que son símbolos terminales de su gramática.
  2. Analizan estos símbolos e intentan combinarlos con la gramática del idioma que entendieron.

    • Aquí es donde generalmente radica la diferencia real. Vea abajo para más.
    • Gramática entendida por los lexers: gramática regular (nivel 3 de Chomsky).
    • Gramática entendida por los analizadores sintácticos: gramática libre de contexto (nivel 2 de Chomsky).
  3. Aportan semántica (significado) a las piezas de idioma que encuentran.

    • Lexers adjunta significado clasificando lexemas (cadenas de símbolos de la entrada) como los tokens particulares. Por ejemplo, todos estos lexemas: * , == , <= , ^ se clasificarán como token de "operador" por el lector de C / C ++.
    • Los analizadores adjuntos asignan significado al clasificar las cadenas de tokens de la entrada (oraciones) como las no terminales particulares y construyendo el árbol de análisis sintáctico . Por ejemplo, todas estas cadenas de tokens: [number][operator][number] , [id][operator][id] , [id][operator][number][operator][number] se clasificarán como "expression" nonterminal por el analizador C / C ++.
  4. Pueden adjuntar algún significado adicional (datos) a los elementos reconocidos.

    • Cuando un lexer reconoce una secuencia de caracteres que constituye un número apropiado, puede convertirlo a su valor binario y almacenarlo con el token de "número".
    • De forma similar, cuando un analizador reconoce una expresión, puede calcular su valor y almacenarla con el nodo "expresión" del árbol de syntax.
  5. Todos ellos producen en su salida oraciones adecuadas del lenguaje que reconocen.

    • Los Lexers producen tokens , que son oraciones del lenguaje habitual que reconocen. Cada token puede tener una syntax interna (aunque nivel 3, no nivel 2), pero eso no importa para los datos de salida y para el que los lee.
    • Los analizadores producen árboles sintácticos , que son representaciones de oraciones del lenguaje sin contexto que reconocen. Por lo general, es solo un árbol grande para todo el documento / archivo fuente, porque todo el documento / archivo fuente es una oración adecuada para ellos. Pero no hay ninguna razón por la cual el analizador no pudo producir una serie de árboles de syntax en su salida. Por ejemplo, podría ser un analizador sintáctico que reconozca tags SGML pegadas en texto plano. Por lo tanto, convertirá el documento SGML en una serie de tokens: [TXT][TAG][TAG][TXT][TAG][TXT]...

Como puede ver, los analizadores sintácticos y los tokenizadores tienen mucho en común. Un analizador puede ser un tokenizador para otro analizador, que lee sus tokens de entrada como símbolos de su propio alfabeto (los tokens son simplemente símbolos de algún alfabeto) de la misma manera que las oraciones de un idioma pueden ser símbolos alfabéticos de otro nivel superior. idioma. Por ejemplo, si * y - son los símbolos del alfabeto M (como "símbolos del código Morse"), entonces puede construir un analizador sintáctico que reconoce las cadenas de estos puntos y líneas como letras codificadas en el código Morse. Las oraciones en el lenguaje "Código Morse" podrían ser tokens para otro analizador sintáctico, para el cual estos tokens son símbolos atómicos de su lenguaje (por ejemplo, el lenguaje "Palabras inglesas"). Y estas "palabras en inglés" podrían ser tokens (símbolos del alfabeto) para algún analizador de nivel superior que entienda el lenguaje de "oraciones en inglés". Y todos estos lenguajes difieren solo en la complejidad de la gramática . Nada mas.

Entonces, ¿qué es todo acerca de estos "niveles de gramática de Chomsky"? Bueno, Noam Chomsky clasificó las gramáticas en cuatro niveles según su complejidad:

  • Nivel 3: gramáticas regulares

    Usan expresiones regulares, es decir, pueden consistir solo de los símbolos del alfabeto ( a , b ), sus concatenaciones ( ab , aba , bbb etd.), O alternativas (por ejemplo, a|b ).
    Se pueden implementar como autómatas de estados finitos (FSA), como NFA (autómata finito no determinista) o mejor DFA (autómata finito determinista).
    Las gramáticas regulares no pueden manejar con syntax anidada , por ejemplo, paréntesis nesteds / coincidentes (()()(()())) , tags HTML / BBcode anidadas, bloques nesteds, etc. Se debe a que el autómata estatal debe lidiar con esto. tiene infinitos estados para manejar infinitamente muchos niveles de anidamiento.

  • Nivel 2: gramáticas libres de contexto

    Pueden tener twigs anidadas, recursivas y auto-similares en sus árboles de syntax, por lo que pueden manejar bien las estructuras anidadas.
    Se pueden implementar como autómatas de estado con stack. Esta stack se usa para representar el nivel de anidamiento de la syntax. En la práctica, generalmente se implementan como un analizador sintáctico de descendente recursivo descendente que utiliza la stack de llamadas de procedimiento de la máquina para seguir el nivel de anidación y utiliza procedimientos / funciones recursivamente llamados para cada símbolo no terminal en su syntax.
    Pero no pueden manejar con una syntax sensible al contexto . Por ejemplo, cuando tienes una expresión x+3 y en un contexto, esta x podría ser un nombre de una variable, y en otro contexto podría ser un nombre de una función, etc.

  • Nivel 1: gramáticas sensibles al contexto

  • Nivel 0: gramáticas sin restricciones
    También se llama "gramáticas de fase estructural".

Sí, son muy diferentes en teoría y en implementación.

Los Lexers se usan para reconocer las “palabras” que componen los elementos del lenguaje, porque la estructura de tales palabras es generalmente simple. Las expresiones regulares son extremadamente buenas para manejar esta estructura más simple, y existen motores de coincidencia de expresiones regulares de muy alto rendimiento utilizados para implementar lexers.

Los analizadores se utilizan para reconocer la “estructura” de las frases de un idioma. Dicha estructura generalmente está más allá de lo que las “expresiones regulares” pueden reconocer, por lo que se necesitan analizadores “sensibles al contexto” para extraer dicha estructura. Los analizadores sensibles al contexto son difíciles de construir, por lo que el compromiso de ingeniería es usar gramáticas “sin contexto” y agregar ataques a los analizadores sintácticos (“tablas de símbolos”, etc.) para manejar la parte sensible al contexto.

Ni la tecnología lexing ni la analítica probablemente desaparecerán pronto.

Pueden unificarse al decidir utilizar la tecnología de “análisis sintáctico” para reconocer “palabras”, tal como lo exploran actualmente los analizadores de GLR sin escáner. Eso tiene un costo en tiempo de ejecución, ya que está aplicando maquinaria más general a lo que a menudo es un problema que no lo necesita, y generalmente paga por eso en gastos generales. Donde tienes muchos ciclos libres, esa sobrecarga puede no importar. Si procesa una gran cantidad de texto, la sobrecarga sí importa y los analizadores clásicos de expresiones regulares continuarán siendo utilizados.

Cuando lexing es suficiente, ¿cuándo necesita EBNF?

EBNF realmente no agrega mucho al poder de las gramáticas. Es solo una notación de conveniencia / atajo / “azúcar sintáctico” sobre las reglas gtwigticales estándar de Chomsky’s Normal Form (CNF). Por ejemplo, la alternativa EBNF:

 S --> A | B 

puede lograr en CNF simplemente enumerando cada producción alternativa por separado:

 S --> A // `S` can be `A`, S --> B // or it can be `B`. 

El elemento opcional de EBNF:

 S --> X? 

puede lograr en CNF usando una producción que admite valores NULL , es decir, la que puede ser reemplazada por una cadena vacía (denotada por producción vacía aquí, otros usan épsilon o lambda o círculo cruzado):

 S --> B // `S` can be `B`, B --> X // and `B` can be just `X`, B --> // or it can be empty. 

Una producción en una forma como la última B anterior se llama “borrado”, porque puede borrar lo que representa en otras producciones (producto una cadena vacía en lugar de otra cosa).

Cero o más repetición de EBNF:

 S --> A* 

puedes obtan usando producción recursiva , es decir, una que se inserta en algún lugar de ella. Se puede hacer de dos maneras. El primero es la recursividad (lo que generalmente debería evitarse, porque los analizadores de Descenso Recursivo descendente no pueden analizarlo):

 S --> SA // `S` is just itself ended with `A` (which can be done many times), S --> // or it can begin with empty-string, which stops the recursion. 

Sabiendo que genera solo una cadena vacía (en última instancia) seguida de cero o más A s, la misma cadena (¡ pero no el mismo idioma! ) Se puede express usando recursión a la derecha :

 S --> AS // `S` can be `A` followed by itself (which can be done many times), S --> // or it can be just empty-string end, which stops the recursion. 

Y cuando se trata de + por una repetición de EBNF:

 S --> A+ 

se puede hacer descompensando una A y usando * como antes:

 S --> AA* 

que puedes express en CNF como tal (uso la recursión correcta aquí, trata de descubrir la otra como ejercicio):

 S --> AS // `S` can be one `A` followed by `S` (which stands for more `A`s), S --> A // or it could be just one single `A`. 

Sabiendo eso, ahora probablemente puedas reconocer una gramática para una expresión regular (es decir, gramática regular ) como una que se puede express en una única producción EBNF que consiste únicamente en símbolos de terminal. De manera más general, puedes reconocer gramáticas regulares cuando ves producciones similares a estas:

 A --> // Empty (nullable) production (AKA erasure). B --> x // Single terminal symbol. C --> y D // Simple state change from `C` to `D` when seeing input `y`. E --> F z // Simple state change from `E` to `F` when seeing input `z`. G --> G u // Left recursion. H --> v H // Right recursion. 

Es decir, usar solo cadenas vacías, símbolos de terminal, no terminales simples para sustituciones y cambios de estado, y usar recursión solo para lograr la repetición (iteración, que es solo recursividad lineal , la que no se ramifica como un árbol). Nada más avanzado por encima de estos, entonces está seguro de que es una syntax regular y puede ir con más lexer para eso.

Pero cuando su syntax utiliza la recursión de una manera no trivial, para producir estructuras anidadas, parecidas a un árbol, como la siguiente:

 S --> a S b // `S` can be itself "parenthesized" by `a` and `b` on both sides. S --> // or it could be (ultimately) empty, which ends recursion. 

entonces puede ver fácilmente que esto no se puede hacer con expresiones regulares, ya que no puede resolverlo en una sola producción EBNF de ninguna manera; terminarás sustituyendo indefinidamente a S , que siempre agregará otras a s y b s en ambos lados. Los Lexers (más específicamente: autómatas de estados finitos utilizados por los lexers) no pueden contar hasta un número arbitrario (son finitos, ¿recuerdas?), Por lo que no saben cuántas estaban allí para unirlos de manera pareja con tantas b s. Las gramáticas como esta se llaman gramáticas libres de contexto (por lo menos) y requieren un analizador sintáctico.

Las gramáticas libres de contexto son bien conocidas para analizar, por lo que son ampliamente utilizadas para describir la syntax de los lenguajes de progtwigción. Pero hay más. A veces se necesita una gramática más general, cuando tienes más cosas para contar al mismo tiempo, de forma independiente. Por ejemplo, cuando desea describir un idioma en el que se pueden usar paréntesis redondos y llaves cuadradas intercaladas, pero deben emparejarse correctamente entre sí (frenillos con llaves, redondo con redondo). Este tipo de gramática se llama contexto sensible . Puedes reconocerlo porque tiene más de un símbolo a la izquierda (antes de la flecha). Por ejemplo:

 ARB --> ASB 

Puede pensar en estos símbolos adicionales a la izquierda como un “contexto” para aplicar la regla. Podría haber algunas condiciones previas, postcondiciones, etc. Por ejemplo, la regla anterior sustituirá R en S , pero solo cuando esté entre A y B , dejando esos A y B sin cambios. Este tipo de syntax es realmente difícil de analizar, porque necesita una máquina de Turing completa. Es toda una historia diferente, así que terminaré aquí.

Para responder la pregunta como se le pide (sin repetir indebidamente lo que aparece en otras respuestas)

Lexers y analizadores no son muy diferentes, como lo sugiere la respuesta aceptada. Ambos se basan en formalismos sencillos de lenguaje: lenguajes regulares para lexers y, casi siempre, lenguajes sin contexto (CF) para analizadores sintácticos. Ambos están asociados con modelos computacionales bastante simples, el autómata de estado finito y el autómata de stack de empuje descendente. Los idiomas regulares son un caso especial de idiomas sin contexto, por lo que los lexers podrían producirse con la tecnología CF algo más compleja. Pero no es una buena idea por al menos dos razones.

Un punto fundamental en la progtwigción es que un componente del sistema debe tener la tecnología más apropiada, de modo que sea fácil de producir, comprender y mantener. La tecnología no debe ser exagerada (utilizando técnicas mucho más complejas y costosas de lo necesario), ni debe estar al límite de su poder, lo que requiere contorsiones técnicas para lograr el objective deseado.

Es por eso que “Parece estar de moda odiar las expresiones regulares”. Aunque pueden hacer mucho, a veces requieren una encoding muy ilegible para lograrlo, sin mencionar el hecho de que varias extensiones y restricciones en la implementación reducen algo su simplicidad teórica. Los Lexers no suelen hacer eso, y generalmente son una tecnología simple, eficiente y apropiada para analizar el token. Usar analizadores CF para token sería exagerado, aunque es posible.

Otra razón para no usar el formalismo CF para los lexers es que podría ser tentador utilizar toda la potencia CF. Pero eso podría plantear problemas sociales con respecto a la lectura de progtwigs.

Fundamentalmente, la mayor parte de la estructura del texto del progtwig, del cual se extrae el significado, es una estructura de árbol. Expresa cómo se genera la oración de parseo (progtwig) a partir de las reglas de syntax. La semántica se deriva de las técnicas de composición (homomorfismo para las matemáticas) a partir de la forma en que se componen las reglas de syntax para construir el árbol de análisis sintáctico. Por lo tanto, la estructura del árbol es esencial. El hecho de que los tokens se identifiquen con un lexer basado en un conjunto regular no cambia la situación, porque el CF compuesto con regular todavía da CF (estoy hablando muy libremente sobre transductores regulares, que transforman un flujo de caracteres en un flujo de token).

Sin embargo, CF se compuso con CF (a través de transductores de CF … lo siento por las matemáticas), no necesariamente da CF, y podría hacer que las cosas sean más generales, pero menos manejables en la práctica. Entonces, CF no es la herramienta adecuada para los lexers, aunque puede usarse.

Una de las principales diferencias entre regular y CF es que los lenguajes regulares (y transductores) componen muy bien con casi cualquier formalismo de varias maneras, mientras que los lenguajes CF (y transductores) no lo hacen, ni siquiera consigo mismos (con algunas excepciones).

(Tenga en cuenta que los transductores regulares pueden tener otros usos, como la formalización de algunas técnicas de manejo de errores de syntax).

BNF es solo una syntax específica para presentar las gramáticas de CF.

EBNF es un azúcar sintáctico para BNF , que utiliza las funciones de notación regular para dar una versión más completa de las gramáticas BNF. Siempre se puede transformar en un BNF puro equivalente.

Sin embargo, la notación regular se usa a menudo en EBNF solo para enfatizar estas partes de la syntax que corresponden a la estructura de los elementos léxicos, y debe reconocerse con el lexer, mientras que el rest debe presentarse en un BNF directo. Pero no es una regla absoluta.

En resumen, la estructura más simple de token se analiza mejor con la tecnología más simple de los lenguajes regulares, mientras que la estructura del lenguaje orientada a los árboles (de la syntax del progtwig) es mejor manejada por las gramáticas de CF.

Sugeriría también mirar la respuesta de AHR .

Pero esto deja una pregunta abierta: ¿Por qué los árboles?

Los árboles son una buena base para especificar la syntax porque

  • dan una estructura simple al texto

  • es muy conveniente asociar la semántica con el texto sobre la base de esa estructura, con una tecnología matemáticamente bien comprendida (composicionalidad a través de homomorfismos), como se indicó anteriormente. Es una herramienta algebraica fundamental para definir la semántica de los formalismos matemáticos.

Por lo tanto, es una buena representación intermedia, como lo demuestra el éxito de Abstract Syntax Trees (AST). Tenga en cuenta que AST a menudo son diferentes del árbol de análisis sintáctico porque la tecnología de análisis utilizada por muchos profesionales (como LL o LR) se aplica solo a un subconjunto de gramáticas de CF, lo que obliga a las distorsiones gtwigticales que luego se corrigen en AST. Esto se puede evitar con una tecnología de análisis más general (basada en progtwigción dinámica) que acepte cualquier gramática CF.

La statement sobre el hecho de que los lenguajes de progtwigción son contextuales (CS) en lugar de CF son arbitrarios y discutibles.

El problema es que la separación de la syntax y la semántica es arbitraria. Comprobar las declaraciones o el acuerdo de tipo puede verse como parte de la syntax o como parte de la semántica. Lo mismo podría decirse del acuerdo de género y número en los idiomas naturales. Pero hay lenguajes naturales donde el acuerdo plural depende del significado semántico real de las palabras, de modo que no encaja bien con la syntax.

Muchas definiciones de lenguajes de progtwigción en semántica denotacional colocan declaraciones y comprobación de tipos en la semántica. Así que, como dice Ira Baxter, que los analizadores de CF están siendo pirateados para obtener una sensibilidad de contexto requerida por la syntax es, en el mejor de los casos, una visión arbitraria de la situación. Puede estar organizado como un hack en algunos comstackdores, pero no tiene que ser así.

Además, no es solo que los analizadores de CS (en el sentido utilizado en otras respuestas aquí) son difíciles de construir y menos eficientes. Ellos también son inadecuados para express de manera perspicaz el grado de sensibilidad al contexto que podría ser necesario. Y no producen de forma natural una estructura sintáctica (como los árboles de análisis sintáctico) que es conveniente para derivar la semántica del progtwig, es decir, para generar el código comstackdo.

Hay una serie de razones por las cuales la porción de análisis de un comstackdor normalmente se separa en fases de análisis léxico y análisis (análisis de syntax).

  1. La simplicidad del diseño es la consideración más importante. La separación del análisis léxico y sintáctico a menudo nos permite simplificar al menos una de estas tareas. Por ejemplo, un analizador sintáctico que tuviera que tratar los comentarios y el espacio en blanco como unidades sintácticas. Considerablemente más complejo que uno que puede asumir comentarios y el espacio en blanco ya ha sido eliminado por el analizador léxico. Si estamos diseñando un nuevo lenguaje, separar las preocupaciones léxicas y sintácticas puede conducir a un diseño general del lenguaje más limpio.
  2. La eficiencia del comstackdor es mejorada. Un analizador léxico separado nos permite aplicar técnicas especializadas que solo sirven para la tarea léxica, no para el análisis. Además, las técnicas de almacenamiento en búfer especializadas para leer los caracteres de entrada pueden acelerar el comstackdor de manera significativa.
  3. La portabilidad del comstackdor está mejorada. Las peculiaridades específicas del dispositivo de entrada pueden restringirse al analizador léxico.

resource___ Compilers (2nd Edition) escrito por Alfred V. Abo Universidad de Columbia Monica S. Lam Universidad de Stanford Ravi Sethi Avaya Jeffrey D. Ullman Universidad de Stanford