parsing antlr lexer pygments

parsing - lexers vs parsers



antlr pygments (5)

¿Son los lexers y los analizadores realmente tan diferentes en teoría?

Parece de moda odiar las expresiones regulares: codificar el horror , otra entrada de blog .

Sin embargo, las herramientas populares basadas en lexing: pygments , geshi o prettify , usan expresiones regulares. Parecen lex cualquier cosa ...

¿Cuándo es suficiente lexing, cuando necesita EBNF?

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

¿Cuándo es suficiente lexing, cuando necesita EBNF?

EBNF realmente no agrega mucho al poder de las gramáticas. Es solo una conveniencia / notación de atajo / "azúcar sintáctica" sobre las reglas gramaticales de la Forma Normal (CNF) estándar de Chomsky. Por ejemplo, la alternativa EBNF:

S --> A | B

Usted puede lograr en CNF simplemente listando 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?

se puede lograr en CNF utilizando una producción anulable , es decir, la que se puede reemplazar por una cadena vacía (indicada aquí como producción vacía; otros usan epsilon 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 (producir una cadena vacía en lugar de otra cosa).

Repetición cero o más de EBNF:

S --> A*

se puede obtener utilizando producción recursiva , es decir, una que se incrusta en algún lugar de ella. Se puede hacer de dos maneras. La primera es la recursión a la izquierda (que generalmente se debe evitar, porque los analizadores de Descenso Recursivo de arriba a abajo no pueden analizarla):

S --> S A // `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 (finalmente) seguida de cero o más A s, la misma cadena (¡ pero no el mismo idioma! ) Se puede expresar usando la recursión del derecho :

S --> A S // `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 + para una o más repeticiones de EBNF:

S --> A+

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

S --> A A*

que puede expresarse en CNF como tal (uso la recursión correcta aquí; intente descifrar el otro como un ejercicio):

S --> A S // `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, probablemente ahora puede reconocer una gramática para una expresión regular (es decir, una gramática regular ) como una que se puede expresar en una sola producción de EBNF que consiste solo de símbolos terminales. Más generalmente, puedes reconocer las 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, simples no terminales para sustituciones y cambios de estado, y usar la recursión solo para lograr la repetición (iteración, que es solo una recursión lineal , la que no se ramifica como un árbol). Nada más avanzado por encima de estos, entonces está seguro de que es una sintaxis regular y puede usar solo el lexer para eso.

Pero cuando tu sintaxis usa la recursión de una manera no trivial, para producir estructuras anidadas, similares a árboles, 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.

luego puede ver fácilmente que esto no se puede hacer con una expresión regular, porque no puede resolverlo en una sola producción EBNF de ninguna manera; terminarás con la sustitución de S por tiempo indefinido, que siempre agregará otras a s y b s en ambos lados. Los Lexers (más específicamente: los Autómatas de Estado Finito utilizados por los lexers) no pueden contar con un número arbitrario (son finitos, ¿recuerdas?), Por lo que no saben cuántos a eran para igualarlos con tantos b s. Las gramáticas de este tipo se denominan gramáticas sin contexto (como mínimo) y requieren un analizador.

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

A R B --> A S B

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

Hay varias razones por las que la parte de análisis de un compilador normalmente se separa en fases de análisis léxico y análisis (análisis de sintaxis).

  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 que tenía que lidiar con comentarios y espacios en blanco como unidades sintácticas sería. El analizador léxico ya ha eliminado los espacios en blanco considerablemente más complejos que los que pueden asumir comentarios. Si estamos diseñando un nuevo idioma, la separación de las inquietudes léxicas y sintácticas puede llevar a un diseño del lenguaje en general más limpio.
  2. Se mejora la eficiencia del compilador. Un analizador léxico separado nos permite aplicar técnicas especializadas que sirven solo para la tarea léxica, no para el trabajo de análisis. Además, las técnicas especializadas de almacenamiento en búfer para leer los caracteres de entrada pueden acelerar significativamente el compilador.
  3. Se mejora la portabilidad del compilador. Las peculiaridades específicas del dispositivo de entrada se pueden restringir al analizador léxico.

recurso___ Compiladores (2da edición) escrito por: Alfred V. Abo Universidad de Columbia Monica S. Lam Universidad de Stanford Ravi Sethi Avaya Jeffrey D. Ullman Universidad de Stanford

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

  1. Ellos leen los símbolos de algún alfabeto de su entrada.

    • Pista: El alfabeto no necesariamente tiene que ser de letras. Pero tiene que ser de símbolos atómicos para el lenguaje entendido por parser / 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 y tratan de relacionarlos con la gramática del lenguaje que entendieron.

    • Aquí es donde radica la verdadera diferencia. Ver más abajo para más.
    • Gramática entendida por lexers: gramática regular (nivel 3 de Chomsky).
    • Gramática entendida por analizadores: gramática libre de contexto (nivel 2 de Chomsky).

  3. Adjuntan semántica (significado) a las piezas de lenguaje que encuentran.

    • Los Lexers adjuntan significado al clasificar los lexemas (cadenas de símbolos de la entrada) como los tokens particulares. Por ejemplo, todos los lexemas: * , == , <= , ^ se clasificarán como token de "operador" por el lexer C / C ++.
    • Los analizadores adjuntan significado clasificando cadenas de tokens de la entrada (oraciones) como los no terminales particulares y construyendo el árbol de análisis . Por ejemplo, todas estas cadenas de token: [number][operator][number] , [id][operator][id] , [id][operator][number][operator][number] se clasificarán como "expresión" no terminal 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 adecuado, puede convertirla a su valor binario y almacenarla con el token "número".
    • De manera similar, cuando un analizador reconoce una expresión, puede calcular su valor y almacenarlo con el nodo "expresión" del árbol de sintaxis.

  5. Todos ellos producen en su salida una oración apropiada del lenguaje que reconocen.

    • Los Lexers producen tokens , que son oraciones del lenguaje regular que reconocen. Cada token puede tener una sintaxis 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 de sintaxis , que son representaciones de oraciones del lenguaje libre de contexto que reconocen. Por lo general, solo es 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 que el analizador no pueda producir una serie de árboles de sintaxis en su salida. Por ejemplo, podría ser un analizador que reconozca las etiquetas SGML pegadas en texto plano. Así que tokenizará el documento SGML en una serie de tokens: [TXT][TAG][TAG][TXT][TAG][TXT]...

Como puede ver, los analizadores 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 otros. idioma. Por ejemplo, si * y - son los símbolos del alfabeto M (como "símbolos del código Morse"), entonces puede crear un analizador que reconozca 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 algún otro analizador, para el cual estos tokens son símbolos atómicos de su lenguaje (por ejemplo, el lenguaje "Palabras en inglés"). Y estas "palabras en inglés" podrían ser tokens (símbolos del alfabeto) para un analizador de nivel superior que entiende el idioma de "oraciones en inglés". Y todos estos idiomas difieren solo en la complejidad de la gramática . Nada mas.

Entonces, ¿qué hay de estos "niveles gramaticales de Chomsky"? Bueno, Noam Chomsky clasificó las gramáticas en cuatro niveles dependiendo de su complejidad:

  • Nivel 3: gramáticas regulares

    Usan expresiones regulares, es decir, pueden consistir solo en 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 estado finito (FSA), como NFA (autómata finito no determinista) o mejor DFA (autómata finito determinista).
    Las gramáticas regulares no se pueden manejar con sintaxis anidada , por ejemplo, paréntesis anidados / emparejados (()()(()())) , etiquetas HTML / BBcode anidadas, bloques anidados, etc. Es porque los autómatas del estado deben lidiar con eso tienen infinitos estados para manejar infinitos niveles de anidamiento.

  • Nivel 2: gramáticas libres de contexto

    Pueden tener ramas anidadas, recursivas y similares a sí mismas en sus árboles de sintaxis, por lo que pueden manejar bien las estructuras anidadas.
    Se pueden implementar como autómatas de estado con stack. Esta pila se utiliza para representar el nivel de anidamiento de la sintaxis. En la práctica, por lo general se implementan como un analizador descendente recursivo descendente que utiliza la pila de llamadas de procedimientos de la máquina para rastrear el nivel de anidamiento y los procedimientos / funciones llamados recursivamente para cada símbolo no terminal en su sintaxis.
    Pero no pueden manejar con una sintaxis sensible al contexto . Por ejemplo, cuando tiene una expresión x+3 y en un contexto, esta x podría ser el nombre de una variable, y en otro contexto podría ser el 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 estructura de fase".

Para responder a la pregunta como se hace (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 de lenguaje simples: lenguajes regulares para lexers y, casi siempre, lenguajes sin contexto (CF) para analizadores. Ambos están asociados con modelos computacionales bastante simples, el autómata de estado finito y el autómata de pila de empuje hacia abajo. Los lenguajes regulares son un caso especial de lenguajes libres de contexto, por lo que los lexers podrían producirse con la tecnología de FQ algo más compleja. Pero no es una buena idea por al menos dos razones.

Un punto fundamental en la programación es que un componente del sistema debe estar construido con la tecnología más adecuada, de modo que sea fácil de producir, comprender y mantener. La tecnología no debe ser excesiva (utilizando técnicas mucho más complejas y costosas de lo necesario), ni debe estar en el límite de su poder, por lo que se requieren contorsiones técnicas para lograr el objetivo deseado.

Es por eso que "parece de moda odiar las expresiones regulares". Aunque pueden hacer mucho, a veces requieren una codificación 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 suelen ser una tecnología simple, eficiente y apropiada para analizar token. El uso de analizadores CF para el token sería excesivo, aunque es posible.

Otra razón para no usar el formalismo de la FQ para los lexers es que puede ser tentador utilizar la potencia total de la FQ. Pero eso podría plantear problemas estructurales relacionados con la lectura de los programas.

Fundamentalmente, la mayor parte de la estructura del texto del programa, del cual se extrae el significado, es una estructura de árbol. Expresa cómo la oración de análisis (programa) se genera a partir de reglas de sintaxis. La semántica se deriva de las técnicas de composición (homomorfismo para las orientadas matemáticamente) de la forma en que se componen las reglas de sintaxis para construir el árbol de análisis. Por eso 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, ya que el CF compuesto con regular todavía da el CF (estoy hablando de forma muy general acerca de los transductores regulares, que transforman un flujo de caracteres en un flujo de token).

Sin embargo, la FQ compuesta con FQ (a través de los transductores de FQ ... perdón por los cálculos), no necesariamente da FQ, y puede hacer que las cosas sean más generales, pero menos manejables en la práctica. Por lo tanto, la FQ no es la herramienta adecuada para los lexers, aunque se puede usar.

Una de las principales diferencias entre la regularidad y la CF es que los lenguajes regulares (y los transductores) se componen muy bien con casi cualquier formalismo de varias maneras, mientras que los lenguajes de la CF (y los transductores) no lo hacen, ni siquiera con ellos 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 sintaxis).

BNF es solo una sintaxis específica para presentar gramáticas de FQ.

EBNF es un azúcar sintáctico para BNF , que utiliza las facilidades de notación regular para dar una versión de prueba 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 sintaxis que corresponden a la estructura de los elementos léxicos, y debe reconocerse con el lexer, mientras que el resto debe presentarse en BNF directo. Pero no es una regla absoluta.

Para resumir, la estructura más simple de token se analiza mejor con la tecnología más simple de lenguajes regulares, mientras que la estructura orientada a árbol del lenguaje (de sintaxis de programa) se maneja mejor con las gramáticas de CF.

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

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

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

  • Le dan una estructura simple al texto.

  • son muy convenientes para asociar la semántica con el texto sobre la base de esa estructura, con una tecnología matemáticamente bien entendida (composición 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 las AST a menudo son diferentes del árbol de análisis 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 distorsiones gramaticales que luego se corrigen en AST. Esto se puede evitar con una tecnología de análisis más general (basada en programación dinámica) que acepte cualquier gramática de CF.

La declaración sobre el hecho de que los lenguajes de programación son sensibles al contexto (CS) en lugar de CF es arbitraria y discutible.

El problema es que la separación de sintaxis y semántica es arbitraria. Las declaraciones de verificación o el acuerdo de tipo pueden verse como parte de la sintaxis o parte de la semántica. Lo mismo podría decirse del acuerdo de género y número en las lenguas naturales. Pero hay lenguajes naturales en los que la concordancia plural depende del significado semántico real de las palabras, por lo que no encaja bien con la sintaxis.

Muchas definiciones de lenguajes de programación en semántica de denotación colocan declaraciones y verifican tipos en la semántica. Por lo tanto, como indica Ira Baxter, que los analizadores de CF se están pirateando para obtener una sensibilidad de contexto requerida por la sintaxis es, en el mejor de los casos, una visión arbitraria de la situación. Puede estar organizado como un hack en algunos compiladores, pero no tiene por qué serlo.

Además, no es solo que los analizadores CS (en el sentido utilizado en otras respuestas aquí) son difíciles de construir y menos eficientes. También son inadecuados para expresar perspicuamente el kinf de sensibilidad al contexto que podría ser necesario. Y, naturalmente, no producen una estructura sintáctica (como los árboles de análisis) que sea conveniente para derivar la semántica del programa, es decir, para generar el código compilado.

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

Los Lexers se utilizan 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 alto rendimiento que se utilizan 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 la ingeniería es utilizar gramáticas "sin contexto" y agregar hacks a los analizadores ("tablas de símbolos", etc.) para manejar la parte sensible al contexto.

Es probable que no desaparezca la tecnología de lectura ni de análisis.

Se pueden unificar al decidir utilizar la tecnología de "análisis" para reconocer "palabras", como lo exploran actualmente los llamados analizadores sin escáner GLR. Eso tiene un costo de tiempo de ejecución, ya que está aplicando una maquinaria más general a lo que suele ser un problema que no lo necesita, y por lo general se paga en gastos generales. Donde tienes muchos ciclos libres, esa sobrecarga puede no importar. Si procesa una gran cantidad de texto, entonces la sobrecarga es importante y los analizadores de expresiones regulares clásicas se seguirán utilizando.