En programación de computadoras , el truco de lexer es una solución para analizar gramáticas sensibles al contexto como C , donde clasificar una secuencia de caracteres como un nombre de variable o un nombre de tipo requiere información contextual, al alimentar información contextual hacia atrás desde el analizador al lexer.
El truco de Lexer está mal visto en los compiladores modernos, ya que crea un estrecho acoplamiento entre pasos que de otro modo serían en gran medida independientes en el proceso de compilación. En cambio, los tokens similares a identificadores se tokenizan como identificadores y luego eliminan la ambigüedad del analizador, lo que permite una separación más clara de las preocupaciones .
El problema fundamental es diferenciar los tipos de otros identificadores. En el siguiente ejemplo, la clase léxica de Ano se puede determinar sin más información contextual:
A * B ; Este código podría ser una multiplicación o una declaración, según el contexto.
Más detalladamente, en un compilador , el lexer realiza una de las primeras etapas de conversión del código fuente en un programa. Escanea el texto para extraer tokens significativos , como palabras, números y cadenas. El analizador analiza secuencias de tokens intentando hacer coincidirlos con reglas de sintaxis que representan estructuras del lenguaje, como bucles y declaraciones de variables. Aquí se produce un problema si una única secuencia de tokens puede coincidir ambiguamente con más de una regla de sintaxis.
Esta ambigüedad puede ocurrir en C si el lexer no distingue entre identificadores de variable y typedef . [1] Por ejemplo, en la expresión C:
A * B ; el lexer puede encontrar estos tokens:
Dependiendo de si Aes un nombre typedef o no, puede ser conveniente tokenizarlo Acomo un identificador o un tipo para que el analizador no tenga que manejar un análisis ambiguo. Esta ambigüedad gramatical se conoce como el problema "typedef-name:identifier", debido al nombre de la regla de producción problemática . [2]
La solución generalmente consiste en devolver información de la tabla de símbolos semánticos al lexer. Es decir, en lugar de funcionar como un conducto unidireccional puro desde el lexer al analizador, existe un canal secundario desde el análisis semántico hasta el lexer. Esta combinación de análisis sintáctico y semántico se considera generalmente poco elegante, por lo que se denomina " truco ".
Sin contexto agregado, el lexer no puede distinguir los identificadores de tipo de otros identificadores porque todos los identificadores tienen el mismo formato. Con el truco del ejemplo anterior, cuando el lexer encuentra el identificador A, debería poder clasificar el token como un identificador de tipo. Las reglas del lenguaje se aclararían especificando que los encasillados requieren un identificador de tipo y la ambigüedad desaparece.
El problema también existe en C++ y los analizadores pueden utilizar el mismo truco. [1]
Este problema no surge (y por lo tanto no necesita ningún "truco" para resolverse) cuando se utilizan técnicas de análisis sin lexer , ya que son intrínsecamente contextuales. Sin embargo, estos generalmente se consideran diseños menos elegantes porque carecen de la modularidad necesaria para tener un lexer y un analizador simultáneos en una tubería. [ cita necesaria ]
Algunos generadores de analizadores, como el BtYacc ("Backtracking Yacc") derivado de byacc , le dan al analizador generado la capacidad de intentar múltiples intentos de analizar los tokens. En el problema descrito aquí, si un intento falla debido a la información semántica sobre el identificador, puede retroceder e intentar otras reglas. [3]
El analizador Clang maneja la situación de una manera completamente diferente, es decir, utilizando una gramática léxica sin referencia. El lexer de Clang no intenta diferenciar entre nombres de tipos y nombres de variables: simplemente informa el token actual como un identificador. Luego, el analizador utiliza la biblioteca de análisis semántico de Clang para determinar la naturaleza del identificador. Esto permite una arquitectura más simple y fácil de mantener que The Lexer Hack. [4] Este es también el enfoque utilizado en la mayoría de los otros lenguajes modernos, que no distinguen diferentes clases de identificadores en la gramática léxica, sino que los difieren hasta la fase de análisis sintáctico o semántico, cuando hay suficiente información disponible. [ ejemplo necesario ]