En programación informática , el truco del analizador léxico 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 la información contextual hacia atrás desde el analizador al analizador léxico.
El hack del analizador léxico está mal visto en los compiladores modernos, ya que crea un acoplamiento estrecho 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 se desambiguan en el 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, dependiendo del contexto.
En más detalle, en un compilador , el analizador léxico realiza una de las primeras etapas de la conversión del código fuente a un programa. Escanea el texto para extraer tokens significativos , como palabras, números y cadenas. El analizador analiza secuencias de tokens intentando hacerlas coincidir con reglas de sintaxis que representan estructuras del lenguaje, como bucles y declaraciones de variables. Aquí se produce un problema si una sola secuencia de tokens puede coincidir de forma ambigua con más de una regla de sintaxis.
Esta ambigüedad puede ocurrir en C si el analizador léxico no distingue entre identificadores de variable y de tipo definido . [1] Por ejemplo, en la expresión de C:
A * B ; El analizador léxico puede encontrar estos tokens:
Dependiendo de si Aes un nombre de typedef o no, puede ser deseable convertirlo Aen un identificador o en un tipo para que el analizador no tenga que manejar un análisis ambiguo. Esta ambigüedad gramatical se conoce como el problema "nombre de typedef: identificador", debido al nombre de la regla de producción problemática . [2]
La solución generalmente consiste en introducir información de la tabla de símbolos semánticos en el analizador léxico. Es decir, en lugar de funcionar como un conducto unidireccional puro desde el analizador léxico al analizador sintáctico, existe un canal de retorno desde el análisis semántico hasta el analizador léxico. Esta combinación de análisis sintáctico y semántico generalmente se considera poco elegante, por lo que se la llama un " truco ".
Sin contexto adicional, el analizador léxico 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 analizador léxico encuentre el identificador A, debería poder clasificar el token como un identificador de tipo. Las reglas del lenguaje se aclararían al especificar que las conversiones de tipos requieren un identificador de tipo y la ambigüedad desaparecería.
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 es necesario ningún "truco" para resolverlo) cuando se utilizan técnicas de análisis sintáctico sin analizador léxico , ya que son intrínsecamente contextuales. Sin embargo, generalmente se consideran diseños menos elegantes porque carecen de la modularidad de tener un analizador léxico y un analizador sintáctico concurrentes en una secuencia de comandos. [ cita requerida ]
Algunos generadores de analizadores, como el BtYacc ("Backtracking Yacc") derivado de byacc , le dan al analizador generado la capacidad de intentar múltiples intentos para 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 sintáctico de Clang maneja la situación de una manera completamente diferente, es decir, utilizando una gramática léxica no referencial. El analizador sintáctico de Clang no intenta diferenciar entre nombres de tipos y nombres de variables: simplemente informa el token actual como un identificador. El analizador sintáctico luego utiliza la biblioteca de análisis semántico de Clang para determinar la naturaleza del identificador. Esto permite una arquitectura más simple y más fácil de mantener que The Lexer Hack. [4] Este es también el enfoque utilizado en la mayoría de los demás lenguajes modernos, que no distinguen diferentes clases de identificadores en la gramática léxica, sino que los difieren a la fase de análisis sintáctico o semántico, cuando hay suficiente información disponible. [ ejemplo necesario ]