¿Cuál debería ser el tipo de datos de los tokens que un lexer devuelve a su analizador?

21

Como se dice en el título, ¿qué tipo de datos debe devolver un lexer / darle al analizador? Al leer el artículo de análisis léxico que Wikipedia tiene, declaró que:

En informática, el análisis léxico es el proceso de convertir una secuencia de caracteres (como en un programa de computadora o página web) en una secuencia de tokens ( cadenas con un "significado" identificado).

Sin embargo, en completa contradicción con la declaración anterior, cuando se respondió otra pregunta que hice en un sitio diferente ( Revisión de Código si tiene curiosidad), la persona que respondió declaró que:

El lexer generalmente lee la cadena y la convierte en una secuencia ... de lexemas. Los lexemas solo necesitan ser una corriente de números .

y le dio este visual:

nl_output => 256
output    => 257
<string>  => 258

Más adelante en el artículo que mencionó Flex, un lexer ya existente, y dijo que escribir "reglas" con él sería más simple que escribir un lexer a mano. Él procedió a darme este ejemplo:

Space              [ \r\n\t]
QuotedString       "[^"]*"
%%
nl_output          {return 256;}
output             {return 257;}
{QuotedString}     {return 258;}
{Space}            {/* Ignore */}
.                  {error("Unmatched character");}
%%

Para ampliar mi visión y obtener más información, leí el artículo de Wikipedia sobre Flex . El artículo de Flex mostró que se podía definir un conjunto de reglas de sintaxis, con tokens, de la siguiente manera:

digit         [0-9]
letter        [a-zA-Z]

%%
"+"                  { return PLUS;       }
"-"                  { return MINUS;      }
"*"                  { return TIMES;      }
"/"                  { return SLASH;      }
"("                  { return LPAREN;     }
")"                  { return RPAREN;     }
";"                  { return SEMICOLON;  }
","                  { return COMMA;      }
"."                  { return PERIOD;     }
":="                 { return BECOMES;    }
"="                  { return EQL;        }
"<>"                 { return NEQ;        }
"<"                  { return LSS;        }
">"                  { return GTR;        }
"<="                 { return LEQ;        }
">="                 { return GEQ;        }
"begin"              { return BEGINSYM;   }
"call"               { return CALLSYM;    }
"const"              { return CONSTSYM;   }
"do"                 { return DOSYM;      }
"end"                { return ENDSYM;     }
"if"                 { return IFSYM;      }
"odd"                { return ODDSYM;     }
"procedure"          { return PROCSYM;    }
"then"               { return THENSYM;    }
"var"                { return VARSYM;     }
"while"              { return WHILESYM;   }

Me parece que Flex lexer está devolviendo cadenas de palabras clave \ tokens. Pero podría estar devolviendo constantes que son iguales a ciertos números.

Si el lexer iba a devolver números, ¿cómo leería los literales de cadena? devolver un número está bien para palabras clave individuales, pero ¿cómo lidiaría con una cadena? El lexer no tendría que convertir la cadena a números binarios y luego el analizador volvería a convertir los números a una cadena. Parece mucho más lógico (y más fácil) que el lexer devuelva cadenas y luego permita que el analizador convierta cualquier literal de cadena de números en números reales.

¿O podría el lexer posible devolver ambos? He estado tratando de escribir un simple lexer en c ++, que le permite tener solo un tipo de retorno para sus funciones. Así me lleva a hacer mi pregunta.

Para condensar mi pregunta en un párrafo: al escribir un lexer, y suponiendo que solo pudiera devolver un tipo de datos (cadenas o números), ¿cuál sería la opción más lógica?

Christian Dean
fuente
El lexer devuelve lo que le dices que devuelva. Si su diseño requiere números, entonces devolverá números. Obviamente, representar literales de cadena requerirá un poco más que eso. Consulte también ¿Es el trabajo de un Lexer analizar números y cadenas? Tenga en cuenta que los literales de cadena generalmente no se consideran "Elementos del lenguaje".
Robert Harvey
@RobertHarvey Entonces, ¿convertirías el literal de cadena en números binarios?
Christian Dean
Según tengo entendido, el propósito del lexer es tomar los elementos del lenguaje (como palabras clave, operadores, etc.) y convertirlos en tokens. Como tal, las cadenas citadas no son de interés para el lexer, porque no son elementos del lenguaje. Aunque nunca he escrito un lexer, me imagino que la cadena entre comillas simplemente se pasa sin cambios (incluidas las comillas).
Robert Harvey
Entonces, lo que dice es que el lexer no lee ni se preocupa por los literales de cadena. ¿Y entonces el analizador debe buscar estos literales de cadena? Esto es muy confuso.
Christian Dean
Es posible que desee pasar unos minutos leyendo esto: en.wikipedia.org/wiki/Lexical_analysis
Robert Harvey

Respuestas:

10

En general, si está procesando un lenguaje a través de lexing y parsing, tiene una definición de sus tokens léxicos, por ejemplo:

NUMBER ::= [0-9]+
ID     ::= [a-Z]+, except for keywords
IF     ::= 'if'
LPAREN ::= '('
RPAREN ::= ')'
COMMA  ::= ','
LBRACE ::= '{'
RBRACE ::= '}'
SEMICOLON ::= ';'
...

y tienes una gramática para el analizador:

STATEMENT ::= IF LPAREN EXPR RPAREN STATEMENT
            | LBRACE STATEMENT BRACE
            | EXPR SEMICOLON
EXPR      ::= ID
            | NUMBER
            | ID LPAREN EXPRS RPAREN
...

Su lexer toma la secuencia de entrada y produce una secuencia de tokens. El analizador consume el flujo de tokens para producir un árbol de análisis. En algunos casos, solo conocer el tipo de token es suficiente (por ejemplo, LPAREN, RBRACE, FOR), pero en algunos casos, necesitará el valor real asociado con el token. Por ejemplo, cuando encuentre un token de ID, querrá los caracteres reales que componen la ID más adelante cuando intente averiguar a qué identificador está tratando de hacer referencia.

Entonces, normalmente tienes algo más o menos así:

enum TokenType {
  NUMBER, ID, IF, LPAREN, RPAREN, ...;
}

class Token {
  TokenType type;
  String value;
}

Entonces, cuando el lexer devuelve un token, sabe de qué tipo es (que necesita para el análisis) y la secuencia de caracteres a partir de la cual se generó (que necesitará más adelante para interpretar cadenas, literales, identificadores, etc.) Puede parecer que está devolviendo dos valores, ya que está devolviendo un tipo agregado muy simple, pero realmente necesita ambas partes. Después de todo, querrás tratar los siguientes programas de manera diferente:

if (2 > 0) {
  print("2 > 0");
}
if (0 > 2) {
  print("0 > 2");
}

Estos producen la misma secuencia de tipos de tokens : IF, LPAREN, NUMBER, GREATER_THAN, NUMBER, RPAREN, LBRACE, ID, LPAREN, STRING, RPAREN, SEMICOLON, RBRACE. Eso significa que también analizan lo mismo. Pero cuando realmente está haciendo algo con el árbol de análisis, le importará que el valor del primer número sea '2' (o '0') y que el valor del segundo número sea '0' (o '2 '), y que el valor de la cadena es' 2> 0 '(o' 0> 2 ').

Joshua Taylor
fuente
Entiendo la mayor parte de lo que dices, pero ¿cómo se String valueva a llenar eso ? ¿se llenará con una cadena o un número? Y también, ¿cómo definiría el Stringtipo?
Christian Dean
1
@ Mr.Python En el caso más simple, es solo la cadena de caracteres que coincide con la producción léxica. Entonces, si ve foo (23, "bar") , obtendrá los tokens [ID, "foo"], [LPAREN, "("], [NUMBER, "23"], [COMMA "," ], [STRING, "" 23 ""], [RPAREN, ")"] . Preservar esa información podría ser importante. O podría adoptar otro enfoque y hacer que el valor tenga un tipo de unión que puede ser una cadena, o un número, etc., y elegir el tipo de valor correcto en función del tipo de token que tenga (por ejemplo, cuando el tipo de token es NUMBER , use value.num, y cuando sea STRING, use value.str).
Joshua Taylor
@MrPython "Y también, ¿cómo definiría el tipo de cadena?" Estaba escribiendo desde una mentalidad Java-ish. Si está trabajando en C ++, podría usar el tipo de cadena de C ++, o si está trabajando en C, podría usar un char *. El punto es que, asociado con un token, tiene el valor correspondiente o el texto que puede interpretar para producir el valor.
Joshua Taylor
1
@ ollydbg23 es una opción, y no es irrazonable, pero hace que el sistema sea menos consistente internamente. Por ejemplo, si desea el valor de cadena de la última ciudad que analizó, ahora tendría que verificar explícitamente un valor nulo y luego utilizar una búsqueda inversa de token a cadena para averiguar cuál hubiera sido la cadena. Además, es un acoplamiento más estricto entre el lexer y el analizador sintáctico; habrá más código para actualizar si LPAREN podría coincidir con cadenas diferentes o múltiples.
Joshua Taylor el
2
@ ollydbg23 Un caso sería un pseudominificador simple. Es bastante fácil de hacer parse(inputStream).forEach(token -> print(token.string); print(' '))(es decir, simplemente imprima los valores de cadena de los tokens, separados por espacio). Eso es bastante rápido E incluso si LPAREN solo puede venir de "(", eso podría ser una cadena constante en la memoria, por lo que incluir una referencia en el token podría no ser más costoso que incluir la referencia nula. En general, prefiero escribir código que no me hace caso especial ningún código.
Joshua Taylor
6

Como se dijo en el título, ¿qué tipo de datos debe devolver un lexer / darle al analizador?

"Token", obviamente. Un lexer produce un flujo de tokens, por lo que debería devolver un flujo de tokens .

Mencionó Flex, un lexer ya existente, y dijo que escribir "reglas" con él sería más simple que escribir un lexer a mano.

Los lexers generados por máquina tienen la ventaja de que puede generarlos rápidamente, lo que es particularmente útil si cree que su gramática léxica va a cambiar mucho. Tienen la desventaja de que a menudo no obtienes mucha flexibilidad en tus elecciones de implementación.

Dicho esto, ¿a quién le importa si es "más simple"? ¡Escribir el lexer generalmente no es la parte difícil!

Al escribir un lexer, y suponiendo que solo pueda devolver un tipo de datos (cadenas o números), ¿cuál sería la opción más lógica?

Ninguno. Un lexer generalmente tiene una operación "siguiente" que devuelve un token, por lo que debería devolver un token . Un token no es una cadena o un número. Es una ficha.

El último lexer que escribí fue un lexer de "fidelidad total", lo que significa que devolvió un token que rastreaba la ubicación de todos los espacios en blanco y comentarios, que llamamos "trivia", en el programa, así como el token. En mi lexer, un token se definió como:

  • Una serie de curiosidades principales
  • Un tipo de ficha
  • Un ancho de token en caracteres
  • Una serie de trivia final

Trivia se definió como:

  • Un tipo de trivia: espacios en blanco, nueva línea, comentarios, etc.
  • Un ancho de trivia en caracteres

Entonces si tuviéramos algo como

    foo + /* comment */
/* another comment */ bar;

que lex como cuatro fichas con tipos de tokens Identifier, Plus, Identifier, Semicolon, y anchos de 3, 1, 3, 1. El primer identificador tiene trivia que consiste en que conduce Whitespacecon una anchura de 4 y posterior trivia Whitespacecon anchura de 1. El Plusno tiene trivia líder y trivia final que consta de un espacio en blanco, un comentario y una nueva línea. El identificador final tiene una trivia principal de un comentario y un espacio, y así sucesivamente.

Con este esquema, todos los caracteres del archivo se contabilizan en la salida del lexer, que es una propiedad útil para cosas como la coloración sintáctica.

Por supuesto, si no necesita la trivia, simplemente puede hacer una ficha de dos cosas: el tipo y el ancho.

Puede notar que el token y las curiosidades contienen solo sus anchos, no su posición absoluta en el código fuente. Eso es deliberado. Tal esquema tiene ventajas:

  • Es compacto en memoria y formato de cable
  • Permite re-lexing sobre ediciones; Esto es útil si el lexer se está ejecutando dentro de un IDE. Es decir, si detecta una edición en un token, simplemente haga una copia de seguridad de su lexer en un par de tokens antes de la edición y comience a lexing nuevamente hasta que esté sincronizado con la secuencia de tokens anterior. Cuando escribe un personaje, la posición de cada ficha después de que ese personaje cambia, pero generalmente solo una o dos fichas cambian de ancho, por lo que puede reutilizar todo ese estado.
  • Los desplazamientos de caracteres exactos de cada token se pueden derivar fácilmente iterando sobre la secuencia de tokens y haciendo un seguimiento del desplazamiento actual. Una vez que tenga los desplazamientos de caracteres exactos, es fácil extraer el texto cuando sea necesario.

Si no le importa ninguno de esos escenarios, entonces un token podría representarse como un tipo y un desplazamiento, en lugar de un tipo y un ancho.

Pero la conclusión clave aquí es: la programación es el arte de hacer abstracciones útiles . Estás manipulando tokens, así que haz una abstracción útil sobre los tokens, y luego puedes elegir por ti mismo qué detalles de implementación subyacen.

Eric Lippert
fuente
3

En general, devuelve una estructura pequeña que tiene un número que significa el token (o el valor de enumeración para facilitar su uso) y un valor opcional (cadena, o posiblemente un valor genérico / con plantilla). Otro enfoque sería devolver un tipo derivado para elementos que necesitan transportar datos adicionales. Ambas son soluciones ligeramente desagradables, pero lo suficientemente finas para un problema práctico.

Telastyn
fuente
¿Qué quieres decir con algo desagradable ? ¿Son formas ineficientes de obtener valores de cadena?
Christian Dean el
@ Mr.Python: conducirán a muchas comprobaciones antes de su uso en el código, lo cual es ineficiente, pero además hace que el código sea un poco más complejo / frágil.
Telastyn
Tengo una pregunta similar al diseñar un lexer en C ++, podría devolver a Token *o a simplemente a Token, o a, TokenPtrque es un puntero compartido de Tokenclase. Pero también veo que algunos lexers devuelven solo un TokenType y almacenan la cadena o el valor numérico en otras variables globales o estáticas. Otra pregunta es cómo podemos almacenar la información de ubicación, ¿necesito tener una estructura de token que tenga los campos TokenType, String y Location? Gracias.
ollydbg23
@ ollydbg23: cualquiera de estas cosas puede funcionar. Yo usaría una estructura. Y para los idiomas que no aprenden, de todos modos usará un generador de analizador sintáctico.
Telastyn el
@Telastyn gracias por la respuesta. ¿Quieres decir que una estructura Token podría ser algo así struct Token {TokenType id; std::string lexeme; int line; int column;}, verdad? Para una función pública de Lexer, como PeekToken(), la función podría devolver un Token *o TokenPtr. Creo que por un tiempo, si la función solo devuelve el TokenType, ¿cómo intenta el Analizador obtener la otra información sobre el Token? Por lo tanto, se prefiere un puntero como datatype para el retorno de dicha función. ¿Algún comentario sobre mi idea? Gracias
ollydbg23