Crear tokens para un lexer

Su pregunta (como lo sugiere su párrafo final) no es realmente sobre el lexer, sino sobre el diseño correcto de la interfaz entre el lexer y el analizador. Como puedes imaginar, hay muchos libros sobre el diseño de los lexers y los analizadores. Me gusta el libro de análisis de Dick Grune , pero puede que no sea un buen libro introductorio. Resulta que me disgusta mucho el libro basado en C de Appel , porque el código no es extensiblemente útil en su propio compilador (debido a los problemas de administración de memoria inherentes a la decisión de pretender que C es como ML). Mi propia introducción fue el libro de PJ Brown , pero no es un Buena introducción general (aunque bastante buena para intérpretes específicamente). Pero volvamos a tu pregunta.

La respuesta es, haz todo lo que puedas en el lexer sin necesidad de usar restricciones de avance o retroceso.

Esto significa que (dependiendo, por supuesto, de los detalles del idioma), debe reconocer una cadena como un "carácter seguido de una secuencia de caracteres no" y luego otro ". Devuélvalo al analizador como una sola unidad. Hay varias razones para esto, pero las más importantes son

1. Esto reduce la cantidad de estado que el analizador necesita mantener, limitando su consumo de memoria.
2. Esto permite que la implementación del lexer se concentre en reconocer los bloques de construcción fundamentales y libera al analizador para describir cómo se utilizan los elementos sintácticos individuales para construir un programa.

Muy a menudo, los analizadores pueden realizar acciones inmediatas al recibir un token del lexer. Por ejemplo, tan pronto como se recibe IDENTIFICADOR, el analizador puede realizar una búsqueda en la tabla de símbolos para averiguar si el símbolo ya es conocido. Si su analizador también analiza las constantes de cadena como CITA (ESPACIOS DE IDENTIFICADOR) * CITA, realizará una gran cantidad de búsquedas irrelevantes en la tabla de símbolos, o terminará elevando las búsquedas en la tabla de símbolos más arriba en el árbol de elementos de sintaxis del analizador, ya que solo puede hacerlo en el punto en el que ahora estás seguro de que no estás mirando una cadena.

Para reafirmar lo que estoy tratando de decir, pero de manera diferente, el lexer debe preocuparse por la ortografía de las cosas, y el analizador con la estructura de las cosas.

Podrías notar que mi descripción de cómo se ve una cadena parece mucho más que una expresión regular. Esto no es una coincidencia. Los analizadores léxicos se implementan con frecuencia en lenguajes pequeños (en el sentido de excelente Programming Pearls de Jon Bentley ) que utilizan expresiones regulares. Simplemente estoy acostumbrado a pensar en términos de expresiones regulares cuando reconozco un texto.

Con respecto a su pregunta sobre espacios en blanco, reconozca en el lexer. Si su idioma está destinado a ser de formato bastante libre, no devuelva tokens de WHITESPACE al analizador, ya que solo tendrá que deshacerse de ellas, por lo que las reglas de producción de su analizador serán básicamente spam con ruido, cosas que reconocer solo para lanzar lejos de ellos.

En cuanto a lo que eso significa acerca de cómo debe manejar los espacios en blanco cuando es sintácticamente significativo, no estoy seguro de poder emitir un juicio que realmente funcione bien sin saber más sobre su idioma. Mi criterio es evitar los casos en que los espacios en blanco a veces son importantes y otras no, y usar algún tipo de delimitador (como comillas). Pero, si no puede diseñar el idioma de la forma que prefiera, es posible que esta opción no esté disponible para usted.

Hay otras formas de hacer sistemas de análisis de lenguaje de diseño. Ciertamente, hay sistemas de construcción de compiladores que le permiten especificar un sistema combinado de lexer y analizador (creo que la versión Java de ANTLR hace esto) pero Nunca he usado uno.

Última nota histórica. Hace décadas, era importante que el lexer hiciera todo lo posible antes de entregarlo al analizador, porque los dos programas no cabían en la memoria al mismo tiempo. Hacer más en el lexer deja más memoria disponible para que el analizador sea inteligente. Solía usar el Whitesmiths C Compiler durante varios años, y si comprendo correctamente , operaría en solo 64KB de RAM (era un programa de MS-DOS de modelo pequeño) y aun así, tradujo una variante de C que estaba muy cerca de ANSI C.

Me ocuparé de tu pregunta final, que de hecho no es estúpida. Los analizadores pueden y construyen construcciones complejas en una base de carácter por carácter. Si recuerdo, la gramática en Harbison y Steele ("C - Un manual de referencia") tiene producciones que usan caracteres individuales como terminales, y construyen identificadores, cadenas, números, etc. como no terminales de los caracteres individuales.

Desde el punto de vista de los lenguajes formales, cualquier cosa que un lexer basado en expresiones regulares pueda reconocer y clasificar como "cadena literal", "identificador", "número", "palabra clave", etc., incluso un analizador LL (1) puede reconocer. Por lo tanto, no hay ningún problema teórico con el uso de un generador de analizador para reconocer todo.

Desde un punto de vista algorítmico, un reconocedor de expresiones regulares puede ejecutarse mucho más rápido que cualquier analizador. Desde un punto de vista cognitivo, es probablemente más fácil para un programador dividir el trabajo entre un analizador de expresiones regulares y un analizador de parser-generador escrito.

Yo diría que las consideraciones prácticas hacen que las personas tomen la decisión de tener lexers y analizadores por separado.

Parece que estás intentando escribir un lexer / parser sin entender realmente las gramáticas. Normalmente, cuando las personas escriben un lexer y un analizador, las escriben para que se ajusten a la gramática. El lexer debe devolver los tokens en la gramática, mientras que el analizador usa esos tokens para coincidir con las reglas / no terminales . Si pudiera analizar fácilmente su entrada pasando byte a byte, entonces un lexer y un analizador podrían ser excesivos.

Los Lexers hacen las cosas más simples.

Descripción general de la gramática : una gramática es un conjunto de reglas sobre el aspecto de una sintaxis o entrada. Por ejemplo, aquí hay una gramática de juguete (simple_command es el símbolo de inicio):

simple_command:
 WORD DIGIT AND_SYMBOL
simple_command:
     addition_expression

addition_expression:
    NUM '+' NUM

Esta gramática significa que -
Un simple_command se compone de cualquiera de los dos A) WORD seguido de DIGIT seguido de AND_SYMBOL (estos son "tokens" que defino)
B) Una "suma_expresión" (esto es una regla o "no terminal")

Una suma_expresión se compone de:
NUM seguido de un '+' seguido de un NUM (NUM es un "token" que defino, '+' es un signo más literal).

Por lo tanto, dado que simple_command es el "símbolo de inicio" (el lugar donde comienzo), cuando recibo una ficha, verifico si encaja en simple_command. Si el primer token en la entrada es una PALABRA y el siguiente token es un DÍGITO y el siguiente token es un AND_SYMBOL, entonces he combinado algún simple_command y puedo tomar alguna acción. De lo contrario, intentaré hacerlo coincidir con la otra regla de simple_command, que es add_expression. Por lo tanto, si el primer token fue un NUM seguido de un '+' seguido de un NUM, entonces emparejé un simple_command y tomo alguna acción. Si no es ninguna de esas cosas, entonces tengo un error de sintaxis.

Es una introducción muy, muy básica a las gramáticas. Para una comprensión más completa, consulte este artículo de wiki y busque en la web tutoriales de gramática sin contexto.

Utilizando un arreglo lexer / parser, aquí hay un ejemplo de cómo podría verse su analizador:

bool simple_command(){
   if (peek_next_token() == WORD){
       get_next_token();
       if (get_next_token() == DIGIT){
           if (get_next_token() == AND_SYMBOL){
               return true;
           } 
       }
   }
   else if (addition_expression()){
       return true;
   }

   return false;
}

bool addition_expression(){
    if (get_next_token() == NUM){
        if (get_next_token() == '+'){
             if (get_next_token() == NUM){
                  return true;
             }
        }
    }
    return false;
}

Ok, entonces ese código es un poco feo y nunca recomendaría el triple anidado si las declaraciones. Pero el punto es, imagina que intentas hacer eso por encima de carácter por personaje en lugar de usar tus agradables funciones modulares "get_next_token" y "peek_next_token" . En serio, dale una oportunidad. No te gustará el resultado. Ahora tenga en cuenta que la gramática anterior es aproximadamente 30 veces menos compleja que casi cualquier gramática útil. ¿Ve la ventaja de usar un lexer?

Honestamente, los lexers y los analizadores no son los temas más básicos del mundo. Recomiendo leer primero y comprender las gramáticas, luego leer un poco sobre los lexers / parsers, y luego profundizar.

  

Mi última pregunta es la más estúpida: ¿por qué es incluso necesario un lexer? Me parece que el analizador podría ir carácter por personaje y averiguar dónde está y qué espera.

Esto no es estúpido, es solo la verdad.

Pero la practicabilidad de alguna manera depende un poco de tus herramientas y objetivos. Por ejemplo, si usa yacc sin un lexer, y desea permitir letras Unicode en los identificadores, tendrá que escribir una regla grande y fea que explique explícitamente todos los caracteres válidos. Mientras que, en un lexer, tal vez podría pedir una rutina de biblioteca si un personaje es miembro de la categoría de letras.

Usar o no usar un lexer es una cuestión de tener un nivel de abstracción entre su idioma y el nivel de carácter. Tenga en cuenta que el nivel de caracteres, en la actualidad, es otra abstracción por encima del nivel de bytes, que es una abstracción por encima del nivel de bits.

Entonces, finalmente, podrías incluso analizar en el nivel de bits.

STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

No, no puede. ¿Qué hay de "(" ? Según usted, eso no es una cadena válida. ¿Y se escapa?

En general, la mejor manera de tratar los espacios en blanco es ignorarlos, más allá de delimitar tokens. Mucha gente prefiere espacios en blanco muy diferentes y hacer cumplir las reglas de espacios en blanco es, en el mejor de los casos, controvertido.