Subiendo con tokens para un lexer

Estoy escribiendo un analizador para un lenguaje de marcado que he creado (escrito en python, pero eso no es realmente relevante para esta pregunta; de hecho, si esto parece una mala idea, me encantaría una sugerencia para un mejor camino) .

Estoy leyendo sobre analizadores aquí: http://www.ferg.org/parsing/index.html , y estoy trabajando en escribir el lexer que debería, si lo entiendo correctamente, dividir el contenido en tokens. Lo que tengo problemas para entender es qué tipos de tokens debo usar o cómo crearlos. Por ejemplo, los tipos de tokens en el ejemplo al que me vinculé son:

• CUERDA
• IDENTIFICADOR
• NÚMERO
• Espacio en blanco
• COMENTARIO
• EOF
• Muchos símbolos como {y (cuentan como su propio tipo de token

El problema que tengo es que los tipos de tokens más generales me parecen un poco arbitrarios. Por ejemplo, por qué STRING es su propio tipo de token separado frente a IDENTIFICADOR. Una cadena se puede representar como STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

Esto también puede tener que ver con las dificultades de mi idioma. Por ejemplo, las declaraciones de variables se escriben {var-name var value}y se implementan con {var-name}. Parece '{'y '}'debe ser sus propios tokens, pero son NOMBRE_VAR y VAR_VALUE tipos de tokens elegibles, o lo haría éstos ambos caen bajo IDENTIFICADOR? Además, VAR_VALUE puede contener espacios en blanco. El espacio en blanco después var-namese usa para indicar el inicio del valor en la declaración ... cualquier otro espacio en blanco es parte del valor. ¿Este espacio en blanco se convierte en su propio token? El espacio en blanco solo tiene ese significado en este contexto. Además, {puede no ser el comienzo de una declaración de variable ... depende del contexto (¡esa palabra está de nuevo!). {:comienza una declaración de nombre y{ incluso se puede usar como parte de algún valor.

Mi lenguaje es similar a Python en que los bloques se crean con sangría. Estaba leyendo sobre cómo Python usa el lexer para crear tokens INDENT y DEDENT (que sirven más o menos como qué {y }harían en muchos otros idiomas). Python afirma estar libre de contexto, lo que significa para mí que al menos al lexer no debería importarle dónde está en la secuencia mientras crea tokens. ¿Cómo sabe el lexer de Python que está construyendo una ficha INDENT de una longitud específica sin conocer los caracteres anteriores (por ejemplo, que la línea anterior era una nueva línea, así que comience a crear los espacios para INDENT)? Pregunto porque necesito saber esto también.

Mi última pregunta es la más estúpida: ¿por qué es necesario un lexer? Me parece que el analizador podría ir personaje por personaje y descubrir dónde está y qué espera. ¿El lexer agrega el beneficio de la simplicidad?

Su pregunta (como sugiere su párrafo final) no se trata realmente del lexer, se trata del diseño correcto de la interfaz entre el lexer y el analizador. Como puede imaginar, hay muchos libros sobre el diseño de lexers y analizadores. Me gusta el libro analizador de Dick Grune , pero puede que no sea un buen libro introductorio. Resulta que me desagrada intensamente el libro basado en C de Appel , porque el código no es útilmente extensible 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 una buena introducción general (aunque bastante buena para los intérpretes específicamente). Pero volviendo a su pregunta.

La respuesta es, haga todo lo que pueda en el léxer sin necesidad de usar restricciones hacia adelante o hacia atrás.

Esto significa que (dependiendo, por supuesto, de los detalles del idioma) debe reconocer una cadena como un "carácter seguido de una secuencia de no-" y luego otro "carácter. Devuélvalo al analizador como una sola unidad. Hay varios 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 tomar medidas 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 se conoce. Si su analizador también analiza las constantes de cadena como CITA (ESPACIOS IDENTIFICADORES) * CITA, realizará muchas búsquedas irrelevantes en la tabla de símbolos, o terminará elevando las búsquedas de la tabla de símbolos más arriba en el árbol de elementos sintácticos del analizador, porque 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 debería preocuparse por la ortografía de las cosas y el analizador con la estructura de las cosas.

Puede notar que mi descripción de cómo se ve una cadena se parece mucho a una expresión regular. Esto no es casualidad. Los analizadores léxicos se implementan con frecuencia en pequeños lenguajes (en el sentido del excelente libro de Jon Bentley Programming Pearls ) que utilizan expresiones regulares. Estoy acostumbrado a pensar en términos de expresiones regulares al reconocer texto.

Con respecto a su pregunta sobre los espacios en blanco, reconózcala en el lexer. Si su idioma está destinado a ser de formato bastante libre, no devuelva los tokens WHITESPACE al analizador, ya que solo tendrá que tirarlos, por lo que las reglas de producción de su analizador se enviarán con ruido esencialmente, cosas que debe reconocer solo para lanzar ellos lejos.

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 hacer un juicio por usted que realmente funcione bien sin saber más sobre su idioma. Mi opinión rápida es evitar los casos en los que el espacio en blanco a veces es importante y a veces no, y usar algún tipo de delimitador (como comillas). Pero, si no puede diseñar el idioma de la manera que prefiera, es posible que esta opción no esté disponible para usted.

Existen otras formas de diseñar 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.

Por último una 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 dejó más memoria disponible para hacer que el analizador sea inteligente. Solía ​​usar el compilador de Whitesmiths C durante varios años, y si lo entiendo correctamente, funcionaría en solo 64 KB de RAM (era un programa MS-DOS de modelo pequeño) y aun así tradujo una variante de C que estaba muy muy cerca de ANSI C.

Asumiré tu pregunta final, que de hecho no es estúpida. Los analizadores pueden y construyen construcciones complejas 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 a partir de los caracteres individuales.

Desde el punto de vista de los idiomas formales, cualquier cosa que un lexer basado en expresiones regulares pueda reconocer y categorizar como "literal de cadena", "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 sintáctico 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, probablemente sea más fácil para un programador romper el trabajo entre un lexer de expresión regular y un analizador escrito de generador de analizadores.

Diría que las consideraciones prácticas hacen que las personas tomen la decisión de tener lexers y analizadores separados.

Parece que estás intentando escribir un lexer / parser sin comprender realmente las gramáticas. Por lo general, cuando las personas escriben un lexer y un analizador sintáctico, los escriben para ajustarse a cierta gramática. El lexer debe devolver los tokens en la gramática, mientras que el analizador utiliza esos tokens para que coincidan con las reglas / no terminales . Si pudiera analizar fácilmente su entrada yendo 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 cómo debería verse 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 está compuesto de
A) WORD seguido de DIGIT seguido de AND_SYMBOL (estos son "tokens" que yo defino)
B) Una " suma_expresión " (esta 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 yo 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 un token, verifico si encaja en simple_command. Si el primer token en la entrada es una WORD y el siguiente token es un DIGIT y el siguiente token es un AND_SYMBOL, entonces he encontrado algún simple_command y puedo tomar alguna acción. De lo contrario, intentaré hacerla coincidir con la otra regla de simple_command que es suma_expresión. Por lo tanto, si el primer token era un NUM seguido de un '+' seguido de un NUM, entonces emparejé un simple_command y tomé algunas medidas. Si no es ninguna de esas cosas, entonces tengo un error de sintaxis.

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

Usando una disposición lexer / parser, aquí hay un ejemplo de cómo se vería 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 declaraciones anidadas triples. Pero el punto es, imagínese tratando de hacer eso arriba de carácter por carácter en lugar de usar sus agradables funciones modulares "get_next_token" y "peek_next_token" . En serio, inténtalo. 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. ¿Ves el beneficio de usar un lexer?

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

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

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

Pero la viabilidad de alguna manera depende un poco de sus 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 explícitamente enumere todos los caracteres válidos. Mientras que, en un lexer, podrías preguntarle a 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 lenguaje y el nivel de caracteres. Tenga en cuenta que el nivel de caracteres, hoy en día, es otra abstracción por encima del nivel de bytes, que es una abstracción por encima del nivel de bits.

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

STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

No, no puede Qué pasa"(" ? Según usted, esa no es una cadena válida. ¿Y escapa?

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