lexers vs analizadores

308

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

Parece estar de moda odiar las expresiones regulares: codificar el horror , otra publicación de blog .

Sin embargo, las herramientas populares basadas en lexing: pygments , geshi o prettify , todas usan expresiones regulares. Parecen dejarlo todo ...

¿Cuándo es bastante lexing, cuándo necesita EBNF?

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

Naveen
fuente
2
si. Estoy tratando de analizar autohotkey. Pude construir un resaltador de sintaxis usando pigmentos realmente rápido. Pero Antlr está tardando mucho más ... No he visto mucha polinización cruzada entre las dos herramientas.
Naveen
67
Está de moda odiar las expresiones regulares cuando se usan incorrectamente. Muchas personas intentan usar expresiones regulares cuando se necesita un análisis sin contexto. Ellos siempre fallan. Y culpan a la tecnología de expresión regular. Es muy parecido a quejarse de que su martillo es una sierra horrible. Es cierto, pero no tendrás mucha simpatía.
Ira Baxter
2
Estoy empezando a acelerar un poco con antlr, afortunadamente. Por cierto, muchos lexing no tienen contexto y, a veces, incluso dependen del contexto.
Naveen
1
Un aspecto fundamental de la cuestión del lexer vs analizador es que los lexers se basan en autómatas finitos (FSA) o, más precisamente, en transductores finitos (FST). La mayoría de los formalismos de análisis (no solo sin contexto) se cierran bajo la intersección con FSA o la aplicación de FST. Por lo tanto, usar el formnalismo basado en expresiones regulares más simple para lexer no aumenta la complejidad de las estructuras sintácticas de los formalismos analizadores más complejos. Este es un problema de modularidad absolutamente importante al definir la estructura y la semántica de los idiomas, felizmente ignorado por las respuestas altamente votadas.
babou
Cabe señalar que los lexers y los analizadores no tienen que ser diferentes, por ejemplo, LLLPG y las versiones anteriores de ANTLR usan el mismo sistema de análisis LL (k) tanto para lexers como para analizadores. La principal diferencia es que las expresiones regulares suelen ser suficientes para lexers pero no para analizadores.
Qwertie

Respuestas:

475

Qué analizadores y lexers 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 sean 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 generalmente radica la verdadera diferencia. Ver 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 la semántica (significado) a las piezas de lenguaje que encuentran.

    • Los Lexers atribuyen significado clasificando lexemas (cadenas de símbolos de la entrada) como tokens particulares . Por ejemplo, todos estos lexemas: *, ==, <=, ^serán clasificados como "operador" Token por lexer la C / C ++.
    • Los analizadores asignan 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 tokens: [number][operator][number], [id][operator][id], [id][operator][number][operator][number]serán clasificados como "expresión" no terminal por el analizador de 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 convertirla a su valor binario y almacenarla con el token "número".
    • Del mismo modo, cuando un analizador reconoce una expresión, puede calcular su valor y almacenarlo con el nodo "expresión" del árbol de sintaxis.
  5. Todos 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 sin contexto que reconocen. Por lo general, es solo un gran árbol 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 sintáctico 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 sin formato. Por lo que va tokenize el documento SGML en una serie de fichas: [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 otro nivel superior. idioma. Por ejemplo, si *y -son los símbolos del alfabeto M(como "símbolos del código Morse"), puede crear un analizador sintáctico 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 tokensson símbolos atómicos de su idioma (p. ej., lenguaje de "palabras en inglés"). 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 idiomas difieren solo en la complejidad de la gramática . Nada mas.

Entonces, ¿qué hay 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

    Utilizan expresiones regulares, es decir, que sólo puede consistir de los símbolos del alfabeto ( a, b), sus concatenaciones ( ab, aba, bbbETD.), 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 pueden manejar con sintaxis anidada , por ejemplo, paréntesis anidados / emparejados correctamente (()()(()())), etiquetas HTML / BBcode anidadas, bloques anidados, etc.
  • Nivel 2: gramáticas sin contexto

    Pueden tener ramas anidadas, recursivas y similares en sus árboles de sintaxis, por lo que pueden manejarse bien con estructuras anidadas.
    Se pueden implementar como autómata de estado con pila. Esta pila se usa para representar el nivel de anidamiento de la sintaxis. En la práctica, generalmente se implementan como un analizador descendente recursivo descendente que usa la pila de llamadas de procedimiento de la máquina para rastrear el nivel de anidación y usa 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+3y en un contexto, este xpodrí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 no restringidas
    También llamadas gramáticas enumerables recursivamente.

SasQ
fuente
70
¿Oh si? Entonces, ¿qué son esas "palabras o fichas"? Son solo oraciones en el idioma normal, que consisten en letras del alfabeto. ¿Y cuáles son esas "construcciones" o "árboles" en el analizador? También son oraciones , pero en un lenguaje diferente de nivel superior, para el cual las fichas particulares son símbolos alfabéticos. La diferencia no es lo que ha dicho, sino en la COMPLEJIDAD DEL LENGUAJE UTILIZADO . Confronte su -1 con cualquier manual sobre la teoría de análisis.
SasQ
3
@SasQ ¿Sería justo decir que tanto Lexers como Parsers toman algo de gramática y una serie de tokens como entrada?
Parag
44
Muy asi. Ambos toman una serie de símbolos del alfabeto que reconocen. Para lexer, este alfabeto consiste solo en caracteres simples. Para el analizador sintáctico, el alfabeto consiste en símbolos terminales, cualquiera que sea su definición. También podrían ser caracteres, si no usa lexer y usa identificadores de un carácter y números de un dígito, etc. (bastante útil en las primeras etapas de desarrollo). Pero generalmente son tokens (clases léxicas) porque los tokens son una buena abstracción: puedes cambiar los lexemas (cadenas) reales que representan y el analizador no ve el cambio.
SasQ
66
Por ejemplo, puede usar un símbolo de terminal STMT_ENDen su sintaxis (para el analizador) para indicar el final de las instrucciones. Ahora puede tener un token con el mismo nombre asociado, generado por el lexer. Pero puede cambiar el lexema real que representa. P.ej. se puede definir STMT_ENDcomo ;tener C / C ++ - como el código fuente. O puede definirlo endpara que sea de alguna manera similar al estilo Pascal. O puede definirlo solo '\n'para finalizar la instrucción con el final de línea, como en Python. Pero la sintaxis de la instrucción (y el analizador sintáctico) se mantiene sin cambios :-) Solo es necesario cambiar el lexer.
SasQ
24
Horas en wikipedia y google no ayudaron, pero usted explicó las gramáticas de Chomsky en 3 minutos. Gracias.
enrey
107

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

Los Lexers se usan para reconocer "palabras" que componen 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 que se utilizan para implementar lexers.

Los analizadores se utilizan para reconocer la "estructura" de las frases de un idioma. Dicha estructura generalmente está mucho más allá de lo que las "expresiones regulares" pueden reconocer, por lo que uno necesita 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 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 ni la tecnología lexing ni la parsing desaparezcan pronto.

Ellos pueden ser unificados con la decisión de utilizar "analizar" la tecnología para reconocer las "palabras", como se hace actualmente explorada por los llamados analizadores GLR scannerless. Eso tiene un costo de 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 eso en gastos generales. Donde tenga muchos ciclos libres, esa sobrecarga puede no importar. Si procesa una gran cantidad de texto, la sobrecarga sí importa y se seguirán utilizando los analizadores de expresiones regulares clásicas.

Ira Baxter
fuente
40
Buena explicación, Ira. Agregando a su analogía: Si bien los lexers tratan de entender bien las palabras, los analizadores analizan cómo interpretar bien las oraciones. "See spot run" y "spot run See" son válidos en lo que respecta a un lexer. Se necesita un analizador para determinar que la estructura de la frase es incorrecta (en gramática inglesa).
Alan
Supongo que un analizador es para un lexer como un andador de árboles es para un analizador. No estoy convencido de que la teoría sea tan diferente: antlr.org/wiki/display/~admin/ANTLR+v4+lexers, pero estoy empezando a comprender las diferencias de convención entre ellos ...
Naveen
44
La teoría es muy diferente. La mayoría de las tecnologías de analizador están tratando de manejar lenguajes libres de contexto hasta cierto punto (algunos solo forman parte, por ejemplo, LALR, algunos lo hacen todo, por ejemplo, GLR). La mayoría de las tecnologías lexer solo intentan hacer expresiones regulares.
Ira Baxter
3
La teoría es diferente, porque ha sido propuesta por muchas personas diferentes y utiliza diferentes terminologías y algoritmos. Pero si los miras de cerca, puedes detectar las similitudes. Por ejemplo, el problema de la recursividad izquierda es muy similar al problema del no determinismo en los NFA, y eliminar la recursividad izquierda es similar a eliminar el no determinismo y convertir el NFA en DFA. Los tokens son oraciones para el tokenizer (salida), pero símbolos alfabéticos para el analizador (input). No niego las diferencias (niveles de Chomsky), pero las similitudes ayudan mucho en el diseño.
SasQ
1
Mi compañero de oficina estaba en la teoría de categorías. Mostró cómo la noción de la teoría categórica de las poleas cubría todo tipo de coincidencia de patrones y fue capaz de derivar el análisis LR a partir de una especificación categórica abstracta. De hecho, si te vuelves lo suficientemente abstracto, puedes encontrar tales puntos en común. El punto de la teoría de categorías es que a menudo puedes abstraer "hasta arriba"; Estoy seguro de que podría crear un analizador de teoría de categorías que borrara las diferencias. Pero cualquier uso práctico del mismo tiene que instanciarse al dominio del problema específico, y luego las diferencias se muestran como reales.
Ira Baxter
32

¿Cuándo es bastante lexing, cuándo necesita EBNF?

EBNF realmente no agrega mucho al poder de las gramáticas. Es solo una conveniencia / notación de acceso directo / "azúcar sintáctico" sobre las reglas gramaticales de forma normal de Chomsky (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 utilizando una producción anulable , es decir, la que se puede reemplazar por una cadena vacía (indicada aquí solo por producción vacía; otras 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 Banterior se llama "borrado", porque puede borrar lo que representa en otras producciones (producto una cadena vacía en lugar de otra cosa).

Repetición cero o más de EBNF:

S --> A*

puede obtan mediante el uso de producción recursiva , es decir, una que se incrusta en algún lugar. Se puede hacer de dos maneras. El primero es la recursión izquierda (que generalmente debe evitarse, porque los analizadores descendentes recursivos descendentes 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 (en última instancia) seguida de cero o más As, la misma cadena (¡ pero no el mismo idioma! ) Se puede expresar utilizando la recursión correcta :

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 una o más repeticiones de EBNF:

S --> A+

puede hacerse factorizando uno Ay usando *como antes:

S --> A A*

que puede expresar en CNF como tal (uso la recursividad correcta aquí; trate de descubrir el otro usted mismo como 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, ahora probablemente pueda reconocer una gramática para una expresión regular (es decir, gramática regular ) como una que se puede expresar en una sola producción EBNF que consiste solo en símbolos terminales. En términos más generales, puede reconocer las gramáticas regulares cuando ve 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 la recursión solo para lograr la repetición (iteración, que es solo recursión lineal , la que no se ramifica en forma de árbol). Nada más avanzado por encima de estos, entonces estás seguro de que es una sintaxis regular y puedes usar solo lexer para eso.

Pero cuando su sintaxis usa la recursión de una manera no trivial, para producir estructuras anidadas similares a árboles, similares a las siguientes, 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 puede hacerse con expresión regular, porque no puede resolverlo en una sola producción EBNF de ninguna manera; que va a terminar con la sustitución de Sforma indefinida, que siempre será añadir otros as y bs en ambos lados. Los Lexers (más específicamente: Autómatas de estado finito utilizados por lexers) no pueden contar hasta un número arbitrario (son finitos, ¿recuerdan?), Por lo que no saben cuántos as estaban allí para combinarlos de manera uniforme con tantos bs. Las gramáticas como esta se denominan gramáticas libres de contexto (como mínimo) y requieren un analizador sintáctico.

Las gramáticas libres de contexto son bien conocidas por 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 desea describir un lenguaje en el que uno puede usar paréntesis redondos y llaves cuadradas intercaladas, pero deben estar correctamente emparejadas 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 precondiciones, postcondiciones, etc. Por ejemplo, la regla anterior sustituirá Ra S, pero solo cuando esté en el medio Ay B, dejando a ellos Ay a Bellos mismos sin cambios. Este tipo de sintaxis es realmente difícil de analizar, ya que necesita una máquina Turing completa. Es otra historia, así que terminaré aquí.

SasQ
fuente
1
Usted declara que EBNF es "solo una conveniencia / notación de acceso directo /" azúcar sintáctico "sobre las reglas gramaticales estándar de la forma normal de Chomsky (CNF)". Pero CNF casi no tiene nada que ver con el tema en cuestión. EBNF se puede transformar fácilmente en BNF estándar. Período. Es azúcar sintáctico para BNF estándar.
babou
11

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

Los 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 sintácticos. Ambos están asociados con modelos computacionales bastante simples, el autómata de estado finito y el autómata de pila push-down. Los lenguajes regulares son un caso especial de lenguajes libres de 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 programación es que un componente del sistema debe construirse 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 al límite de su poder, por lo que requiere contorsiones técnicas para lograr el objetivo deseado.

Es por eso que "parece estar 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 su simplicidad teórica. Los Lexers no suelen hacer eso, y suelen ser una tecnología simple, eficiente y apropiada para analizar el token. Usar analizadores CF para el token sería excesivo, aunque es posible.

Otra razón para no utilizar el formalismo CF para los lexers es que podría ser tentador usar toda la potencia de CF. Pero eso podría plantear problemas de estructura con respecto a la lectura de 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 se genera la oración de análisis (programa) a partir de las reglas de sintaxis. La semántica se deriva de las técnicas de composición (homomorfismo para los orientados matemáticamente) de la forma en que se componen las reglas de sintaxis para construir el árbol de análisis. 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 la CF compuesta 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, la FQ compuesta con FQ (a través de transductores de FQ ... perdón por las matemáticas), 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 CF no es la herramienta adecuada para los lexers, aunque puede usarse.

Una de las principales diferencias entre el lenguaje regular y el CF es que los lenguajes regulares (y transductores) se componen muy bien con casi cualquier formalismo de varias maneras, mientras que los lenguajes CF (y 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 las gramáticas de la FQ.

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

Sin embargo, la notación regular a menudo se usa en EBNF solo para enfatizar estas partes de la sintaxis que corresponden a la estructura de los elementos léxicos, y deben 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 del token se analiza mejor con la tecnología más simple de los lenguajes regulares, mientras que la estructura de árbol del lenguaje (de la sintaxis del programa) se maneja mejor con 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 sintaxis porque

  • 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 (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 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 FQ, 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 CF.

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

El problema es que la separación de la sintaxis y la 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 sería cierto para el acuerdo de género y número en los idiomas naturales. Pero hay lenguajes naturales donde 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 denotacional colocan declaraciones y verificaciones de tipo en la semántica. Por lo tanto, afirmar como lo hizo Ira Baxter que los analizadores de FQ están siendo pirateados para obtener una sensibilidad al 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 truco en algunos compiladores, pero no tiene que ser así.

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

babou
fuente
Sí, los árboles de análisis y los AST son diferentes, pero prácticamente no de una manera realmente útil. Vea mi discusión sobre esto: stackoverflow.com/a/1916687/120163
Ira Baxter
@IraBaxter No estoy de acuerdo con usted, pero realmente no tengo tiempo ahora para redactar una respuesta limpia a su publicación. Básicamente, estás tomando un punto de vista pragmático (y también defendiendo tu propio sistema, creo). Esto es aún más fácil porque está utilizando analizadores CF generales (sin embargo, GLR puede no ser el más eficiente), en lugar de los deterministas como en algunos sistemas. Considero AST como la representación de referencia, que se presta a un tratamiento formalmente definido, transformaciones probadamente correctas, pruebas matemáticas, análisis de múltiples representaciones concretas, etc.
babou
La vista "pragmática" es la razón por la que afirmo que no son muy diferentes de una manera útil. Y simplemente no creo que el uso de un (AST ad hoc) le proporcione "transformaciones demostrablemente correctas"; su AST ad hoc no tiene una relación obvia con la gramática real del lenguaje que se está procesando (y aquí, sí, mi sistema es defendible en el sentido de que nuestro "AST" es probablemente un equivalente isomorfo al BNF). Los AST ad hoc no le brindan ninguna capacidad adicional para analizar "representaciones concretas múltiples". Su objeción a GLR (no la más eficiente) parece bastante inútil. Tampoco son no deterministas.
Ira Baxter
De hecho, no entiendo ninguna parte de su objeción a mi comentario. Tendrás que escribir esa "respuesta limpia".
Ira Baxter
@IraBaxter Los comentarios están demasiado restringidos para una respuesta adecuada (¿sugerencia?). "Ad hoc" no es un calificador adecuado para AST que defiendo, que debería ser (a veces es) la sintaxis de referencia. Esto es históricamente cierto, considerando tanto la historia del concepto de AST en informática como la historia de los sistemas formales como términos (árboles) en un álgebra ordenada, junto con la interpretación. AST es la forma de referencia, no derivada. Vea también sistemas de prueba modernos y generación automática de programas. Puede estar sesgado por el hecho de que tiene que trabajar desde una sintaxis concreta diseñada por otros.
babou
7

Existen varias razones por las cuales 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 sintáctico que tuviera que lidiar con comentarios y espacios en blanco como unidades sintácticas. Considerablemente más complejo que uno que puede asumir comentarios y espacios en blanco ya han sido eliminados 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 de lenguaje 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 el trabajo de análisis. Además, las técnicas de almacenamiento en búfer especializadas para leer caracteres de entrada pueden acelerar significativamente el compilador.
  3. Se mejora la portabilidad del compilador. Las peculiaridades específicas del dispositivo de entrada pueden restringirse al analizador léxico.

recurso___ Compiladores (2ª 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

AHR
fuente