c - for - wiki llvm

¿Los analizadores de GCC y Clang están realmente escritos a mano? (5)

Parece que GCC y LLVM-Clang están usando analizadores sintácticos de descenso recursivos escritos a mano , y no analizados en máquina, basados en Bison-Flex, de abajo hacia arriba.

¿Podría alguien aquí por favor confirmar que este es el caso? Y si es así, ¿por qué los marcos de compilación convencionales usan analizadores manuscritos?

Actualización : blog interesante sobre este tema aquí

¡Respuestas extrañas allí!

Las gramáticas C / C ++ no están libres de contexto. Son sensibles al contexto debido a la barra Foo *; ambigüedad. Tenemos que crear una lista de typedefs para saber si Foo es un tipo o no.

Ira Baxter: No veo el punto con su cosa GLR. ¿Por qué construir un árbol de análisis sintáctico que comprenda ambigüedades? El análisis significa resolver ambigüedades, construir el árbol de sintaxis. Usted resuelve estas ambigüedades en un segundo pase, por lo que esto no es menos feo. Para mí es mucho más feo ...

Yacc es un generador de analizador LR (1) (o LALR (1)), pero se puede modificar fácilmente para que sea sensible al contexto. Y no hay nada feo en eso. Yacc / Bison ha sido creado para ayudar a analizar el lenguaje C, por lo que probablemente no sea la herramienta más fea para generar un analizador C ...

Hasta GCC 3.x el analizador C es generado por yacc / bison, con la tabla typedefs construida durante el análisis. Con el desarrollo de tablas typedefs "en análisis", la gramática C se vuelve localmente libre de contexto y además "localmente LR (1)".

Ahora, en Gcc 4.x, es un analizador de descenso recursivo. Es exactamente el mismo analizador que en Gcc 3.x, sigue siendo LR (1) y tiene las mismas reglas gramaticales. La diferencia es que el analizador de yacc ha sido reescrito a mano, el desplazamiento / reducción ahora está oculto en la pila de llamadas, y no hay "estado454: si (nextsym == ''('') goto state398" como en gcc 3.x yacc analizador sintáctico, por lo que es más fácil parchar, manejar errores e imprimir mensajes más agradables, y realizar algunos de los próximos pasos de compilación durante el análisis. Al precio de mucho menos código "fácil de leer" para un novato gcc.

¿Por qué cambiaron de yacc a descenso recursivo? Porque es bastante necesario evitar que yacc analice C ++, y porque GCC sueña con ser un compilador multilingüe, es decir, compartiendo el máximo de código entre los diferentes lenguajes que puede compilar. Esta es la razón por la cual el analizador C ++ y el C se escriben de la misma manera.

C ++ es más difícil de analizar que C porque no es "localmente" LR (1) como C, ni siquiera es LR (k). Mire func<4 > 2> que es una función de plantilla instanciada con 4> 2, es decir, func<4 > 2> debe leerse como func<1> . Esto definitivamente no es LR (1). Ahora considere, func<4 > 2 > 1 > 3 > 3 > 8 > 9 > 8 > 7 > 8> . Aquí es donde un descenso recursivo puede resolver fácilmente la ambigüedad, al precio de unas pocas llamadas a la función (parse_template_parameter es la función ambigua del analizador. Si parse_template_parameter (17tokens) falló, intente de nuevo parse_template_parameter (15tokens), parse_template_parameter (13tokens) ... hasta funciona).

No sé por qué no sería posible agregar en las subgramáticas recursivas yacc / bison, tal vez este sea el siguiente paso en el desarrollo del analizador gcc / GNU?

El analizador de Clang es un analizador sintáctico de descenso recursivo escrito a mano, al igual que otros frontales C y C ++ de código abierto y comerciales.

Clang usa un analizador sintáctico de descenso recursivo por varias razones:

Rendimiento : un analizador escrito a mano nos permite escribir un analizador rápido, optimizando las rutas calientes según sea necesario, y siempre estamos en control de ese rendimiento. Tener un analizador rápido ha permitido que Clang se utilice en otras herramientas de desarrollo donde los analizadores "reales" no se utilizan habitualmente, por ejemplo, resaltado de sintaxis y finalización de código en un IDE.
Diagnóstico y recuperación de errores : debido a que tiene el control total con un analizador de descenso recursivo escrito a mano, es fácil agregar casos especiales que detectan problemas comunes y proporcionan diagnósticos excelentes y recuperación de errores (por ejemplo, consulte http://clang.llvm.org/features.html#expressivediags ) Con los analizadores generados automáticamente, está limitado a las capacidades del generador.
Simplicidad : los analizadores sintácticos de descenso recursivo son fáciles de escribir, comprender y depurar. No es necesario que sea un experto en análisis sintáctico ni aprenda una nueva herramienta para ampliar / mejorar el analizador sintáctico (que es especialmente importante para un proyecto de código abierto), pero aún puede obtener excelentes resultados.

En general, para un compilador de C ++, simplemente no importa mucho: la parte de C ++ de análisis no es trivial, pero sigue siendo una de las partes más fáciles, por lo que vale la pena mantenerlo simple. El análisis semántico, en particular la búsqueda de nombres, la inicialización, la resolución de sobrecarga y la creación de instancias de plantillas, son órdenes de magnitud más complicadas que el análisis sintáctico. Si quieres pruebas, ve a ver la distribución del código y las confirmaciones en el componente "Sema" de Clang (para el análisis semántico) frente a su componente "Parse" (para el análisis sintáctico).

Hay un folk-teorema que dice que C es difícil de analizar, y C ++ esencialmente imposible.

No es verdad

Lo que es cierto es que C y C ++ son bastante difíciles de analizar utilizando analizadores LALR (1) sin hackear la maquinaria de análisis sintáctico y sin enredarse en los datos de la tabla de símbolos. GCC de hecho solía analizarlos, usando YACC y hackers adicionales como este, y sí, era feo. Ahora GCC usa analizadores sintácticos escritos a mano, pero aún con la piratería de tablas de símbolos. La gente de Clang nunca intentó usar generadores de analizadores automáticos; El analizador AFAIK the Clang siempre ha sido codificado a mano por recursivo.

Lo que sí es cierto es que C y C ++ son relativamente fáciles de analizar con analizadores generados automáticamente más potentes, por ejemplo, analizadores GLR , y no es necesario ningún hackeo. El analizador Elsa C ++ es un ejemplo de esto. Nuestro Front End de C ++ es otro (al igual que todos nuestros front end "compiladores", GLR es una tecnología de análisis bastante maravillosa).

Nuestra interfaz C ++ no es tan rápida como la de GCC, y ciertamente más lenta que Elsa; hemos puesto poca energía en ajustarlo con cuidado porque tenemos otros problemas más apremiantes (sin embargo, se ha utilizado en millones de líneas de código C ++). Elsa es probablemente más lento que GCC simplemente porque es más general. Dadas las velocidades de los procesadores en estos días, estas diferencias pueden no importar mucho en la práctica.

Pero los "compiladores reales" que se distribuyen ampliamente hoy tienen sus raíces en compiladores de hace 10 o 20 años o más. Las ineficiencias entonces importaban mucho más, y nadie había oído hablar de los analizadores de GLR, por lo que la gente hacía lo que sabía hacer. Clang es ciertamente más reciente, pero luego los teoremas folk retienen su "persuasión" durante mucho tiempo.

Ya no tienes que hacerlo de esa manera. Es muy razonable utilizar GLR y otros analizadores de este tipo como interfaces, con una mejora en el mantenimiento del compilador.

Lo que es verdad, es que obtener una gramática que coincida con el comportamiento del compilador de tu vecindario amigable es difícil. Aunque prácticamente todos los compiladores de C ++ implementan (la mayoría) del estándar original, también tienden a tener muchas extensiones de esquina oscuras, por ejemplo, especificaciones de DLL en compiladores de MS, etc. Si tiene un motor de análisis sólido, puede pasar el tiempo tratando de obtener la gramática final para que coincida con la realidad, en lugar de tratar de doblar la gramática para que coincida con las limitaciones de su generador de analizador.

EDITAR Noviembre de 2012: desde que escribimos esta respuesta, hemos mejorado nuestra interfaz de C ++ para manejar C ++ 11 completo, incluidos los dialectos de variantes ANSI, GNU y MS. Si bien hubo muchas cosas adicionales, no tenemos que cambiar nuestro motor de análisis sintáctico; acabamos de revisar las reglas de la gramática. Tuvimos que cambiar el análisis semántico; C ++ 11 es semánticamente muy complicado, y este trabajo inunda el esfuerzo para que el analizador funcione.

EDITAR Febrero de 2015: ... ahora maneja C ++ 14 completo. (Ver obtener AST legible para humanos desde código c ++ para análisis GLR de un código simple, y el infame "análisis más irritante" de C ++).

EDITAR Abril de 2017: Ahora maneja (borrador) C ++ 17.

Sí:

GCC usó un analizador de yacc (bison) una vez, pero fue reemplazado por un analizador de descenso recursivo escrito a mano en algún momento de la serie 3.x: ver http://gcc.gnu.org/wiki/New_C_Parser para enlaces a presentaciones de parches relevantes.
Clang también usa un analizador sintáctico de descenso recursivo escrito a mano: consulte la sección "Un único analizador unificado para C, Objetivo C, C ++ y Objetivo C ++" cerca del final de http://clang.llvm.org/features.html .

El analizador de gcc está escrito a mano. . Sospecho lo mismo de clang. Esto es probablemente por algunas razones:

Rendimiento : algo que haya optimizado a mano para su tarea en particular casi siempre funcionará mejor que una solución general. La abstracción generalmente tiene un golpe de rendimiento
Sincronización : al menos en el caso de GCC, GCC es anterior a muchas herramientas de desarrollo gratuitas (apareció en 1987). No había una versión gratuita de yacc, etc. en ese momento, lo que supongo que habría sido una prioridad para la gente de la FSF.

Probablemente este no sea un caso del síndrome "no inventado aquí", sino más bien en la línea de "no había nada optimizado específicamente para lo que necesitábamos, así que escribimos el nuestro".