Hack de Lexer

En programación informática , el truco del analizador léxico es una solución para analizar una gramática sensible al contexto como C , donde clasificar una secuencia de caracteres como nombre de variable o nombre de tipo requiere información contextual, al alimentar la información contextual desde el analizador sintáctico al analizador léxico.

El truco del analizador léxico no es bien 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 su lugar, los tokens similares a identificadores se tokenizan como identificadores y posteriormente el analizador sintáctico los desambigua, lo que permite una separación de responsabilidades más clara .

El problema fundamental radica en diferenciar los tipos de otros identificadores. En el siguiente ejemplo, la clase léxica Ano se puede determinar sin información contextual adicional:

A * B ;

Este código podría ser una multiplicación o una declaración, dependiendo del contexto.

En 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 de caracteres. El analizador sintáctico analiza secuencias de tokens intentando hacerlas coincidir con las reglas de sintaxis que representan las estructuras del lenguaje, como bucles y declaraciones de variables. Surge un problema si una misma secuencia de tokens puede coincidir ambiguamente 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 variables y de tipo . ^{[ 1 ]} Por ejemplo, en la expresión C:

A * B ;

El analizador léxico puede encontrar estos tokens:

1. ?? 'A'
2. operador '*'
3. identificador 'B'
4. signo de puntuación ';'

Dependiendo de si Ase trata de un nombre de tipo definido 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 ] [ 3 ]}

La solución generalmente consiste en retroalimentar el analizador léxico con información de la tabla de símbolos semánticos. Es decir, en lugar de funcionar como una simple comunicación unidireccional del analizador léxico al analizador sintáctico, existe un canal de retorno del análisis semántico al analizador léxico. Esta combinación de análisis sintáctico y análisis semántico se considera generalmente poco elegante, por lo que se la denomina una « solución chapucera ».

Sin contexto adicional, el analizador léxico no puede distinguir los identificadores de tipo de otros identificadores, ya que todos tienen el mismo formato. Con la solución propuesta en el ejemplo anterior, cuando el analizador léxico encuentre el identificador A , debería poder clasificarlo como un identificador de tipo. Las reglas del lenguaje se aclararían al especificar que las conversiones de tipo requieren un identificador de tipo, y la ambigüedad desaparecería.

El problema también existe en C++ y los analizadores sintácticos pueden usar el mismo truco. ^{[ 1 ]}

Este problema no surge (y, por lo tanto, no requiere ninguna solución improvisada) al usar técnicas de análisis sintáctico sin analizador léxico , ya que estas son intrínsecamente contextuales. Sin embargo, generalmente se consideran diseños menos elegantes, debido a que carecen de la modularidad que ofrece un analizador léxico y un analizador sintáctico simultáneos en una misma secuencia.

Algunos generadores de analizadores sintácticos, como BtYacc ("Backtracking Yacc") derivado de byacc , otorgan al analizador generado la capacidad de realizar múltiples intentos para analizar los tokens. En el problema aquí descrito, si un intento falla debido a información semántica sobre el identificador, puede retroceder e intentar otras reglas. ^{[ 4 ]}

El analizador sintáctico de Clang maneja la situación de una manera completamente diferente, concretamente mediante el uso de una gramática léxica sin referencia. El analizador léxico de Clang no intenta diferenciar entre nombres de tipos y nombres de variables: simplemente informa del token actual como un identificador. A continuación, 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 mantenible que la de The Lexer Hack. ^{[ 5 ]} 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 posponen a la fase de análisis sintáctico o semántico, cuando se dispone de información suficiente.

• Colgando otra cosa
• El análisis más desconcertante

• http://www.cs.berkeley.edu/~smcpeak/elkhound/sources/elkhound/index.html
• http://cs.nyu.edu/rgrimm/papers/pldi06.pdf
• http://cens.ioc.ee/local/man/CompaqCompilers/ladebug/ladebug-manual-details.html Archivado el 6 de enero de 2005 en Wayback Machine
• DOI.org
• http://groups.google.com/group/comp.compilers/browse_frm/thread/db7f68e9d8b49002/fa20bf5de9c73472?lnk=st&q=%2B%22the+lexer+hack%22&rnum=1&hl=en#fa20bf5de9c73472