¿Cómo implemento hacia adelante referencias en un compilador?

Question

Estoy creando un compilador con Lex y YACC (en realidad Flex y Bison). El lenguaje permite un número ilimitado de referencias hacia adelante a cualquier símbolo (como C #). El problema es que es imposible analizar el lenguaje sin saber lo que es un identificador.

La única solución que conozco es a la lex toda la fuente, y luego hacer un "primero en amplitud" analizar, las cosas nivel tan altas como las declaraciones de clase y declaraciones de funciones se analizan antes de que las funciones que los utilizan. Sin embargo, esto podría tomar una gran cantidad de memoria para archivos de gran tamaño, y que sería difícil de manejar con YACC (que tendría que crear gramáticas independientes para cada tipo de declaración / cuerpo). También tendría que escribir a mano el analizador léxico (que no es mucho de un problema).

No me importa mucho acerca de la eficiencia (aunque todavía es importante), porque voy a volver a escribir el compilador en sí mismo una vez que termine, pero yo quiero que la versión para ser rápido (lo que si hay cualquier técnica rápida generales que no se pueden hacer en Lex / YACC, pero se pueden hacer a mano, por favor, sugieren ellos también). Así que ahora mismo, la facilidad de desarrollo es el factor más importante.

¿Hay buenas soluciones a este problema? ¿Cómo es esto generalmente se hace en los compiladores de lenguajes como C # o Java?

Answer 1

Es totalmente posible analizarlo. A pesar de que hay una ambigüedad entre los identificadores y palabras clave, lex estará feliz de hacer frente a la que al dar la prioridad palabras clave.

No veo qué otros problemas existen. No es necesario para determinar si los identificadores son válidos durante la etapa de análisis. Usted está construyendo ya sea un árbol de análisis o un árbol de sintaxis abstracta (la diferencia es sutil, pero irrelevante para los propósitos de esta discusión) a medida que analizar. Después de que construir sus estructuras de la tabla de símbolos anidados realizando un pase al centro del AST se generó durante el análisis. Entonces haces otra pase al AST para comprobar que los identificadores utilizados son válidos. Siga esto con uno o más análisis sintácticos sobre el AST para generar el código de salida, o alguna otra estructura de datos intermedios y ya está!

EDIT: Si quieres ver cómo se hace, compruebe el código fuente para el compilador de C # Mono. Esto es en realidad escrito en C # en lugar de C o C ++, pero utiliza el puerto NET de Jay, que es muy similar a yacc.

Answer 2

Una opción es tratar las referencias adelantarse aunque solo escaneo y almacenamiento en caché de fichas hasta que golpeó algo que sabes cómo real con (algo así como la recuperación de errores "en modo pánico"). Una vez que haya ejecutado pensaba que el archivo completo, volver atrás y tratar de volver a analizar los bits que no se analizan antes.

En cuanto a tener que dar escribe el léxico; No, el uso de la lex para generar un analizador normal y acaba de leer de ella a través de una cuña escrito a mano que le permite volver atrás y alimenta el analizador desde una memoria caché, así como lo hace la lex.

En cuanto a la toma de varias gramáticas, un poco de diversión con un preprocesador en el archivo yacc y usted debería ser capaz de hacer que todo fuera de la misma fuente original