c++ - flex c
¿Cuánto tiempo tomaría escribir un compilador de C++ usando flex/yacc? (13)
Mucho tiempo, y lex y yacc no ayudarán.
Si tiene las habilidades para escribir un compilador para un lenguaje tan grande, no necesitará la poca ayuda que le dan lex y yacc. De hecho, si bien lex está bien, puede llevar más tiempo usar yacc, ya que no es lo suficientemente potente como para C o C ++, y puede pasar más tiempo haciendo que funcione correctamente de lo que se necesitaría solo para escribir un recursivo. analizador de descenso.
Creo que lex y yacc se utilizan mejor para las gramáticas simples, o cuando vale la pena el esfuerzo adicional de tener un archivo de gramática que sea fácil de leer, tal vez porque la gramática es experimental y está sujeta a cambios.
De hecho, el analizador completo posiblemente no sea la mayor parte de su trabajo, dependiendo de los objetivos que tenga para el generador de código.
¿Cuánto tiempo tomaría escribir un compilador de C ++ usando lex / yacc?
¿Dónde puedo empezar con él?
A menos que ya hayas escrito otros compiladores; C ++ no es un lenguaje para el que incluso desee comenzar a escribir un compilador desde cero, el lenguaje tiene muchos lugares donde el significado requiere mucho contexto antes de que la situación pueda ser desambiguada.
Incluso si tiene mucha experiencia en la creación de compiladores, está buscando varios años para un equipo de desarrolladores. Esto es solo para analizar el código correctamente en un formato intermedio. Escribir el backend para generar código es otra tarea especializada (aunque podría robar el backc gcc).
Si haces un google para "gramáticas de C ++" hay un par de sitios para comenzar.
C++ LEX Tokens: http://www.computing.surrey.ac.uk/research/dsrg/fog/CxxLexer.l
C++ YACC Grammer: http://www.computing.surrey.ac.uk/research/dsrg/fog/CxxGrammar.y
http://www.computing.surrey.ac.uk/research/dsrg/fog/CxxTester.y
Bueno, ¿qué quieres decir con escribir un compilador?
Dudo que alguien haya hecho un verdadero compilador de C ++ que lo haya llevado hasta el código de ensamblaje, pero he usado lex y yacc para hacer un compilador de C y lo he hecho sin él.
Usando ambos puedes hacer un compilador que deja de lado la semántica en un par de días, pero descubrir cómo usarlos puede llevar semanas o meses fácilmente. Descubrir cómo hacer un compilador en absoluto llevará semanas o meses sin importar qué, pero la cifra que recuerdo es que una vez que sabes cómo funciona, tomó algunos días con lex y yacc y algunas semanas sin el segundo, pero el segundo tuvo mejores resultados y menos errores, así que realmente es cuestionable si vale la pena usarlos.
La ''semántica'' es la producción de código real. Ese puede ser un código muy simple que es suficiente para funcionar y puede que no tarde mucho, o podrías pasar toda tu vida optimizando.
Con C ++, el gran problema son las plantillas, pero hay tantos pequeños problemas y reglas que no puedo imaginar que alguien quiera hacer esto. Incluso si terminas, el problema es que no necesariamente tendrás compatibilidad binaria, es decir, ser capaz de ser reconocido como un programa ejecutable por un enlazador o el sistema operativo porque hay más que solo C ++ y es difícil de definir, pero hay También hay aún más normas de las que preocuparse que están aún menos disponibles.
Como ya han dicho otros, yacc es una mala elección para implementar un analizador de C ++. Uno puede hacerlo; El GCC original lo hizo, antes de que el equipo de GCC se disgustara con lo difícil que era mantener y extender. (Flex podría estar bien como un lexer).
Algunos dicen que los analizadores de descenso recursivo son mejores, porque Bjarne Stroustrop lo dijo. Nuestra experiencia es que el análisis de GLR es la respuesta correcta para esto, y nuestra interfaz de C ++ basada en GLR es una buena prueba, al igual que la interfaz de Elsa. Nuestro front-end se ha utilizado en la ira en millones de líneas de C ++ (incluidos los dialectos de Microsoft y GCC) para llevar a cabo análisis de programas y una transformación masiva de código fuente.
Pero lo que no se enfatiza lo suficiente es que el análisis es solo una pequeña parte de lo que se necesita para construir un compilador, especialmente para C ++. También necesita crear tablas de símbolos ("¿qué significa este identificador en este contexto?") Y para hacer eso necesita codificar esencialmente la mayoría de varios cientos de páginas del estándar C ++. Creemos que la base sobre la que construimos herramientas similares a un compilador, DMS , es extremadamente buena para hacer esto, y nos llevó un año-hombre para entender bien esta parte.
Pero entonces tienes el resto del compilador a considerar:
- Preprocesador
- Construcción AST
- Análisis semántico y comprobación de tipos.
- Control, flujo de datos y análisis de punteros.
- Generación de código básico
- Optimizaciones
- Asignación de registro
- Generación de código final
- Soporte de depuración
Sigo diciendo esto: construir un analizador (la parte BNF) para un lenguaje es como escalar las estribaciones de los Himalayas. Construir un compilador completo es como escalar el Everest. Casi todos los terrones pueden hacer lo primero (aunque C ++ está justo en el borde). Solo los realmente serios hacen lo último, y solo cuando están extremadamente bien preparados.
Espera que la construcción de un compilador de C ++ te lleve años.
(El extremo frontal de SD C ++ maneja el lexing, el análisis, la generación de AST, las tablas de símbolos, algunas comprobaciones de tipos y la regeneración de texto fuente compilable desde AST, incluidos los comentarios originales, para los principales dialectos de C ++. Se ha desarrollado durante un período de unos 6 años).
EDITAR: mayo de 2015. La respuesta original fue escrita en 2010; Ahora tenemos 11 años invertidos, llevándonos hasta C ++ 14. El punto es que es un gran esfuerzo infinito para construir uno de estos.
El decente recursivo es una buena opción para analizar C ++. GCC y clang lo utilizan.
El analizador Elsa (y mi compilador ellcc) utilizan el generador del compilador GLR de Elkhound.
En cualquier caso, escribir un compilador de C ++ es un trabajo GRANDE.
En primer lugar, la etiqueta "flex" en SO se refiere al producto de Adobe, no al generador lexer. En segundo lugar, Bjarne Stroustrup está en el registro diciendo que deseaba haber implementado Cfront (el primer compilador de C ++) usando un descenso recursivo en lugar de una herramienta de tabla. Y en tercer lugar, para responder a su pregunta directamente - muchos. Si crees que necesitas escribir uno, echa un vistazo a ANTLR , no es mi herramienta favorita, pero ya existen parsers de C ++.
Es probable que le lleve años y probablemente cambie a otro generador de analizador en el proceso.
El análisis de C ++ es notoriamente propenso a errores. La gramática no es totalmente analizable por LR, ya que muchas partes son sensibles al contexto. No podrá hacerlo funcionar correctamente en flex / yacc, o al menos será muy difícil de implementar. Solo hay dos front-ends que conozco que lo hacen bien. Lo mejor que puedes hacer es usar uno de estos y enfocarte en escribir el back-end. Ahí es donde las cosas interesantes es de todos modos :-).
Frontales C ++ existentes:
La interfaz de EDG es utilizada por la mayoría de los proveedores comerciales ( Intel , Portland Group , etc.) en sus compiladores. Cuesta dinero , pero es muy minucioso. La gente paga mucho dinero por ello porque no quiere lidiar con el dolor de escribir su propio analizador de C ++.
La interfaz de C ++ de GCC es lo suficientemente exhaustiva para el código de producción, pero tendría que encontrar la forma de integrar esto en su proyecto. Creo que es bastante complicado separarlo de GCC. Esto también sería GPL, pero no estoy seguro de que sea un problema para ti. Puede usar el front-end de GCC en su proyecto a través de gcc_xml , pero esto solo le dará XML para las clases, funciones, espacios de nombres y definiciones de tipo. No le dará un árbol de sintaxis para el código.
Otra posibilidad es usar clang , pero su soporte de C ++ es irregular actualmente. Será agradable verlos eliminar todos los errores, pero si miras su página de estado de C ++ , notarás que hay más de unos pocos casos de prueba que aún se rompen. Fíjate, clang es un gran proyecto. Si a estos muchachos les lleva años implementar un front-end de C ++, te llevará más tiempo.
Otros han mencionado ANTLR , y hay una gramática de C ++ disponible para ello, pero soy escéptico. No he oído hablar de un extremo delantero de ANTLR que se use en los compiladores principales, aunque creo que se usa en el IDE de NetBeans. Puede ser adecuado para un IDE, pero soy escéptico de que puedas usarlo en el código de producción.
Este es un problema no trivial, y tomaría bastante tiempo para hacerlo correctamente. Por un lado, la gramática para C ++ no es completamente analizable por un LALR(1) como yacc. Puedes hacer subconjuntos del idioma, pero hacer que la especificación del idioma sea correcta es complicado.
No eres la primera persona en pensar que esto es divertido. Aquí hay un buen artículo de estilo de blog sobre el tema: Análisis de C ++
Aquí hay una cita importante del artículo:
"Después de mucha investigación, decidí que escribir un analizador / herramienta de análisis para C ++ es lo suficientemente difícil como para que esté más allá de lo que quiero hacer como pasatiempo".
El problema con ese artículo es que es un poco viejo, y varios de los enlaces están rotos. Aquí hay algunos enlaces a otros recursos sobre el tema de la escritura de analizadores de C ++:
Hay muchas reglas de análisis que no pueden ser analizadas por un analizador bison / yacc (por ejemplo, distinguir entre una declaración y una llamada de función en algunas circunstancias). Además, a veces la interpretación de tokens requiere la entrada del analizador, particularmente en C ++ 0x. El manejo de la secuencia de caracteres >> por ejemplo, es crucialmente dependiente del contexto de análisis.
Esas dos herramientas son muy malas opciones para analizar C ++ y tendría que incluir muchos casos especiales que escaparon del marco básico en el que se basan esas herramientas para analizar correctamente C ++. Te llevaría mucho tiempo, e incluso entonces, tu analizador podría tener errores extraños.
yacc y bison son generadores de analizadores LALR(1) , que no son lo suficientemente sofisticados para manejar C ++ de manera efectiva. Como han señalado otras personas, la mayoría de los compiladores de C ++ ahora usan un analizador de descenso recursivo, y varias otras respuestas han señalado buenas soluciones para escribir las suyas.
Las plantillas de C ++ no son buenas para manejar cadenas, incluso las constantes (aunque esto puede solucionarse en C ++ 0x, no he investigado con cuidado), pero si lo fueran, podría escribir un analizador de descenso recursivo en la plantilla de C ++. idioma. Encuentro eso bastante divertido.
Lex, yacc no será suficiente. Necesitas un enlazador, ensamblador también .., c preprocesador. Depende de cómo lo hagas. ¿Cuántos componentes prefabricados planeas usar? Necesitas obtener la descripción de la sintaxis y su token desde algún lugar.
Por ejemplo, si usa LLVM, puede proceder más rápido. Ya proporciona una gran cantidad de herramientas, ensamblador, enlazador, optimizador ... Puede obtener un preprocesador de CA desde el proyecto boost. Necesita crear un conjunto de pruebas para probar su compilador automáticamente.
Puede tardar un año si lo trabajas todos los días o, mucho menos, tienes más talento y motivación.
Parece que eres bastante nuevo en el análisis / creación del compilador. Si ese es el caso, recomiendo no comenzar con C ++. Es un monstruo de una lengua.
Invente un lenguaje de juguete trivial propio o haga algo basado en algo mucho más pequeño y sencillo. Vi un analizador de lua donde la definición de la gramática era de una página. Eso sería mucho más razonable como punto de partida.
Un compilador de C ++ es muy complicado. Implementar lo suficiente de C ++ para ser compatible con la mayoría de los códigos de C ++ podría llevar a varios desarrolladores un par de años a tiempo completo. clang es un proyecto de compilación financiado por Apple para desarrollar un nuevo compilador para C, C ++ y Objective-C, con varios desarrolladores a tiempo completo, y el soporte de C ++ está muy lejos de estar completo después de un par de años de desarrollo.
Unos cuantos años, si puede obtener una beca de investigación para volver a escribir lex / yacc :-)
La gente sigue persiguiéndose mucho con esto, empezando por Stroustrup, que siempre fue un "diseñador" de lenguaje en lugar de un compilador real (recuerde que su C ++ fue un simple código para las edades y aún estaría allí si no fuera por gcc y otras personas).
El problema central es que la investigación real sobre los generadores de analizadores dejó de existir prácticamente desde que las CPU-s se convirtieron en lo suficientemente rápidas para manejar lenguajes funcionales y descensos recurrentes de fuerza bruta. El descenso recursivo es el último recurso cuando no sabes qué hacer: realiza una búsqueda exhaustiva hasta que encuentra una "regla" que dispara. Una vez que estés satisfecho con eso, pierdes el interés en investigar cómo hacerlo de manera eficiente.
Lo que esencialmente necesitarías es un punto medio razonable, como LALR (2) con retroceso fijo y limitado (más un verificador estático para gritar si "desiogner" se derrumba en un árbol no determinista) y también comentarios limitados y particionados de la tabla de símbolos (parser moderno necesita ser compatible con la concurrencia).
Suena como una propuesta de beca de investigación, ¿no es así? :-) Ahora, si encontramos a alguien que realmente la financie, eso sería algo :-))