¿Por qué deberíamos aprender los principios de compilación?
Bibliografía recomendada
Aunque la teoría de la compilación se ha desarrollado hasta el día de hoy y se ha vuelto relativamente madura, como estudiante universitario, todavía es difícil escribir sus propios compiladores como TurbocC y Java. demasiado difícil. No sólo es difícil escribir un compilador, sino que también es difícil tomar un curso sobre principios de compilación.
El nombre original del primer libro es "CompilersPrinciples, Techniques, and Tools" (CompilersPrinciples, Techniques, andTools), y otro nombre famoso es "Dragon Book" (Libro del Dragón). La razón es que hay un dragón rojo en la portada del libro, y también porque Usiqiao Yishengqu? Para ser más natural, el libro se llama "Libro del Dragón". El área de la boca es de hecho "Xin", por lo que muchos eruditos extranjeros la llamaron directamente Long Shu. Recientemente, Machinery Industry Press publicó una versión china de este libro llamada "Principios de codificación". Este libro salió antes, probablemente escrito en 1985 o 1986, y uno de los autores fue un famoso científico de los Laboratorios Bell. Los principios básicos de compilación explicados en el libro no han cambiado hasta el día de hoy, por lo que todavía tienen un valor extraordinario en la actualidad. La característica más importante de este libro es que utiliza ejemplos prácticos desde el principio para enumerar el contenido general de los principios de compilación, de modo que muchos principiantes en los principios de compilación puedan obtener rápidamente una comprensión básica de por qué existen estas teorías y cómo usarlas. . Esto es algo que creo que falta en los libros de texto nacionales. Por lo tanto, los libros de texto nacionales no están escritos para lectores que estén dispuestos a estudiar por su cuenta. En resumen, la gente puede leerlos durante mucho tiempo sin conocer el uso de sus contenidos.
El nombre original del segundo libro es "Modern Compiler Design" (Modern Compiler Design), y el nombre chino es "Modern Compiler Design". Este libro es publicado por la Editorial de Correos y Telecomunicaciones del Pueblo. Este libro presta más atención a la práctica de los principios de compilación y proporciona muchos códigos de programas reales, muchas cuestiones técnicas prácticas de compilación, etc. Otra característica de este libro es que tiene un fuerte sentido de modernidad y cada palabra es exquisita. En los libros de texto tradicionales sobre principios de compilación, es poco probable que vea algoritmos como la recolección de basura en Java. Esto se debe a que los lenguajes interpretados como Java se han vuelto populares solo en los últimos años. Si desea obtener más información sobre los principios y teorías de la compilación, debe leer el libro anterior Descendientes del Dragón. Si desea crear un compilador avanzado usted mismo, debe leer este libro "Programación de compiladores modernos".
El tercer libro es "Principios y prácticas de compilación", recomendado por muchos estudiosos nacionales de los principios de compilación. Quizás este libro se introdujo en China relativamente temprano. Recuerdo que lo compré cuando estaba en la escuela secundaria, pero no lo leí completo hasta hace algún tiempo. De hecho, este libro es una buena opción como tutorial introductorio. Los principios de compilación dados en el libro también se explican con más detalle, aunque no con tanta profundidad como el libro largo anterior, en muchos lugares se da en el blanco y ya es muy profundo para la enseñanza de pregrado. La característica de este libro es que presta atención a la práctica, pero creo que no es tan pesado como el libro anterior "Diseño de programación de compiladores modernos" y tiene un sabor práctico más fuerte. El enfoque de este libro sigue estando en principios prácticos más que en las prácticas técnicas del libro anterior. Principios y práctica de compilación" explica cada parte del principio de compilación y también practica el compilador moderno TinyC paso a paso. Cuando termines de leer el libro, estarás casi listo para escribir TinyC tú mismo. El autor también presenta con gran detalle Lex y Yacc, dos herramientas relacionadas con la compilación de uso común, lo que también es difícil de ver en los libros de texto nacionales.
Los tres libros de texto recomendados están disponibles en chino e inglés. A muchos estudiantes que son buenos en inglés solo les gusta leer los libros originales, pero mi sensación es que las traducciones de estos tres libros son muy buenas, por lo que no es necesario comprar la versión en inglés. Es más importante comprender la esencia de la teoría que comprender las palabras superficiales.
La esencia de los principios de compilación
Casi todos los libros de texto sobre principios de compilación se dividen en análisis léxico, análisis de sintaxis (algoritmo LL, algoritmo de descenso recursivo, algoritmo LR), análisis semántico y entorno de ejecución. , código intermedio, generación de código, optimización de código. De hecho, muchos libros de texto de principios de compilación ahora organizan su contenido didáctico de acuerdo con las ediciones 85 y 86 publicadas por Longshu. Por lo tanto, el formato de contenido de Longshu casi se ha convertido en el formato fijo de los libros de texto de principios de compilación actuales, incluidos los libros de texto nacionales. En términos generales, la enseñanza de pregrado no puede cubrir seriamente todas las partes anteriores, sino que se centra más en las primeras partes. Cosas como la optimización del código son como un pozo sin fondo. Si quieres hablar de ello en serio, no puedes explicarlo claramente en un solo semestre. Por lo tanto, en general, para los estudiantes universitarios, los requisitos para dominar el análisis léxico y sintáctico son mayores.
El análisis léxico es relativamente sencillo. Puede deberse a que el programa de análisis léxico en sí es muy simple de implementar y muchas personas que no han aprendido los principios de compilación pueden escribir varios programas de análisis léxico. Sin embargo, al explicar el análisis léxico, el enfoque de los principios de compilación es agregar expresiones regulares y principios de autómatas, y luego explicar la generación de programas de análisis léxico de una manera muy estándar. La razón para adoptar este enfoque es obvia: elevar el análisis léxico de un programa a un nivel teórico.
La parte del análisis de sintaxis es más complicada. Actualmente existen dos algoritmos de análisis generales: el algoritmo de arriba hacia abajo LL y el algoritmo de abajo hacia arriba LR. El algoritmo LL está bien, pero cuando se trata del algoritmo LR, surge la dificultad. Muchas personas que estudian por su cuenta los principios de compilación abandonan el estudio por su cuenta después de encontrar problemas para comprender el algoritmo LR. De hecho, mientras entendamos estas cosas, no es como el análisis léxico, que debe escribirse para ser verdaderamente competente. Los analizadores de sintaxis como el algoritmo LR generalmente se generan utilizando la herramienta Yacc y en aplicaciones reales no hay comparabilidad con su propia implementación. Para el algoritmo de descenso recursivo especial en el algoritmo LL, debido a que su método es muy simple, se debe exigir que cada estudiante lo escriba por sí mismo. Por supuesto, existen muchas buenas herramientas de análisis de sintaxis para el algoritmo LL, pero si cambia a una plataforma de lenguaje que no sea C, como Java y Delphi, no podrá usar la herramienta YACC y tendrá que escribir su propia herramienta de análisis de sintaxis. .
Cuando aprendes sobre análisis léxico y análisis gramatical, es posible que te surja esta pregunta: ¿Qué son el análisis léxico y el análisis gramatical? Desde el punto de vista del compilador, el compilador necesita convertir el programa fuente escrito por el programador en una estructura de datos conveniente (árbol de sintaxis abstracta o árbol de sintaxis), luego este proceso de conversión se completa mediante análisis léxico y análisis de sintaxis. De hecho, el análisis léxico no se incluyó como parte necesaria del compilador al principio. Fue solo para simplificar el proceso de análisis gramatical que el tedioso trabajo del análisis léxico se eliminó por separado y se convirtió en la parte actual del análisis léxico. Además de la parte del compilador, el análisis léxico y el análisis de sintaxis también son útiles en otros lugares. Por ejemplo, cuando ingresamos comandos en DOS, Unix y Linux, la forma en que el programa analiza la forma del comando que ingresa también es una aplicación simple. En resumen, el trabajo de estas dos partes es convertir información de texto irregular en estructuras de datos para un mejor análisis y procesamiento. Entonces, ¿por qué los tutoriales sobre principios de compilación terminan convirtiendo el código fuente a analizar en una estructura de datos como un árbol? Hay muchas estructuras de datos, como Pila, Línea y Lista, y cada estructura tiene sus propias características. Pero la estructura del Árbol es muy recursiva, es decir, podemos extraer cualquier nodo del Árbol y sigue siendo un Árbol completo. Esto está en línea con los principios de compilación y análisis del lenguaje formal que utilizamos. Los árboles de letras, el uso de bucles dentro de bucles, el uso de condiciones dentro de condiciones, etc., se pueden expresar intuitivamente utilizando estructuras de datos como Tree. Asimismo, somos recursivos a la hora de ejecutar programas en lenguajes formales. En la parte de generación de código del principio de compilación, se introducirá un código intermedio de tipo pila. Basado en el árbol de sintaxis abstracta analizado, podemos generar conveniente y mecánicamente este código de instrucción atravesando recursivamente el árbol de sintaxis abstracta. Este código también se usa ampliamente en otros lenguajes interpretados.
En .NET, se puede decir que el código de bytes subyacente es un código de instrucción basado en pila.
En lo que respecta al análisis semántico, la traducción guiada por sintaxis, la verificación de tipos, etc. son en realidad un proceso de refinamiento del árbol de sintaxis abstracta obtenido previamente. Por ejemplo, cuando escribimos programas en C, todos sabemos que si asignamos un número de punto flotante directamente a un número entero, habrá una falta de coincidencia de tipos. Entonces, ¿cómo sabe esto el compilador de C? Este es el paso de la verificación de tipos. Para lenguajes como C++ que admiten funciones polimórficas, esta parte del problema es mucho más complicada. La mayoría de los libros de texto sobre principios de compilación solo explican algunas mejores estrategias de procesamiento en esta sección. Como constantemente surgen nuevos problemas, los viejos métodos nunca son suficientes.
Inicialmente, como compilador, la función de esta parte es desde la entrada del programa fuente por parte del usuario hasta la generación final del código. Pero al explicar la generación del código final, hay que explicar cosas como el entorno operativo de la máquina. Porque si no sabes cómo la máquina ejecuta el código final, por supuesto no sabes cómo generar el código final correcto. La importancia de esta parte en mi autocomprensión excede incluso el principio mismo de compilación. Debido a que organiza el proceso de ejecución de un programa de computadora frente a usted, es posible que no participe en el desarrollo del compilador en el futuro, pero siempre que esté en un campo relacionado con el desarrollo de software de computadora, estará involucrado en el proceso de ejecución. del programa. El entorno de ejecución le permitirá comprender mejor cómo se almacenan, cargan y ejecutan los programas informáticos. Con respecto a esta parte del contenido, el autor recomienda encarecidamente leer la explicación en el libro "Dragon". El autor comienza desde la organización de almacenamiento más básica, la estrategia de asignación de almacenamiento, el acceso a nombres no locales, el paso de parámetros y la tabla de símbolos a la dinámica. La asignación de almacenamiento (malloc, nueva) se ha introducido con gran detalle. Estas son cosas que hacemos a menudo cuando escribimos programas comunes, pero rara vez exploramos cómo se hace internamente.
El contenido sobre generación de código intermedio, generación de código y optimización de código realmente no es muy bueno. Muchos libros de texto nacionales simplemente repasan esta parte del contenido. Los estudiantes solo la entienden y no tienen idea de cómo usarla. Sin embargo, si se toma en serio esta parte del contenido, no se puede completar en un solo semestre. En el libro "Principios y práctica de compilación", esta parte del contenido se explica perfectamente. El autor explica principalmente el código de instrucción basado en pila, que es muy fácil de entender, fácil de entender de un vistazo, fácil de imitar y puede generar y escribir el código usted mismo. Por supuesto, la explicación de otras tecnologías de generación de código y tecnologías de optimización de código también es muy simple. Si desea estudiar detenidamente la tecnología de generación de código, en realidad hay otro libro llamado "Advance Compiler Design and Implement". Ese libro lo presenta ahora Machinery Industry Press. Es muy pesado y es la versión original en inglés. Sin embargo, no he incluido este libro como un libro recomendado para todos. Después de todo, el contenido del Libro del Dragón debe entenderse claramente. Para entonces, no leerá este libro "Advance". Diseño e implementación del compilador". Tarde. La parte de optimización del código todavía no es muy importante en la enseñanza de pregrado. Se considera un proceso práctico y creo que no es de mucha utilidad para todos. Después de todo, si su propio compilador puede generar correctamente el código de ejecución, ya es muy bueno, entonces, ¿qué más se puede decir sobre optimización?
Después de todo, el curso "Principios de compilación" es solo un curso que explica los principios, no un curso especializado en tecnología de compilación. Hay una gran diferencia entre estos dos cursos. Las técnicas de compilación se centran más en las técnicas reales utilizadas al escribir un compilador, mientras que el curso de principios
se centra más en las técnicas reales utilizadas al escribir un compilador.