Cómo escribir felizmente un pequeño analizador
Cómo escribir felizmente un pequeño analizador
En el artículo "Caprichos de software" de hace unos días, escribí casualmente: "Ahora parece que ya no es lex/yacc o En la era de bison/flex, personalmente vi a un colega que luchaba por analizar el archivo de datos de un determinado sistema línea por línea, pero nunca pensó que escribir BNF no era una opción para él” >
Muchos estudiantes estaban desconcertados y. me preguntó: ¿Lex/yacc no escribió el compilador [1]? Yo no invento nuevos lenguajes, entonces, ¿de qué me sirven?
A partir de este problema, podemos ver la profundidad del veneno en la educación universitaria nacional. Los profesores que enseñan sobre los principios de compilación en la torre de marfil probablemente escribieron un lenguaje de juguete inútil usando lex/yacc, y luego transmitieron sus pocos conocimientos a sus alumnos. Los estudiantes estaban medio informados y no tenían ningún interés en ello, después de terminar el. En el examen, devolvió todo el contenido memorizado de memoria al profesor.
No te rías, así es como llegué aquí. Lo único que uso lex/yacc es diseñar un lenguaje.
Hay tantos lenguajes en este mundo que realmente no hay lugar para que personas mediocres como yo diseñen otro lenguaje cutre, apresurado, sin apariencia ni rendimiento. Además, alrededor del año 2000, no existía ningún artefacto como LLVM, ni un pensadero como Github para "robar" las ideas de otras personas. El lenguaje de mierda diseñado solo podía detenerse en el paso del análisis de sintaxis y no tenía ninguna utilidad práctica.
Más tarde, lex/yacc evolucionó a flex/bison. En el trabajo, leí accidentalmente un libro llamado "Flex & Bison" de Orelley. El subtítulo de este libro decía claramente: herramientas de procesamiento de texto.
El contenido del libro es bastante dogmático y ligeramente desconectado del contenido real del trabajo, pero el término herramientas de procesamiento de texto me llamó la atención: sí, análisis léxico - análisis léxico (lex/flex), análisis gramatical - El análisis gramatical (yacc/bison) es simplemente una mejor herramienta de procesamiento de texto (analizador), un DSL (lenguaje específico de dominio) que procesa eficientemente texto con gramática. No tienen nada que ver con el compilador, pero uno de sus escenarios de aplicación está relacionado con el compilador. ¡No tenemos que pensar demasiado en esto!
Pensemos en ¿qué herramientas hay disponibles para el procesamiento de textos?
¡Expresión regular!
¿Qué lenguaje de programación hoy en día no soporta expresiones regulares? De manera similar, entre los programadores actuales, ¿cuál no usa expresiones regulares (no las usa en el código)?
La expresión regular también es una herramienta de procesamiento de texto y un DSL, pero no puede manejar una sintaxis compleja.
Sabemos que en la teoría de la automatización existen FSA (Finite State Automata) y PDA (PushDown Automata). El primero se puede expresar con expresiones regulares, mientras que el segundo puede manejar CFG (Gramática libre de contexto). ¡Y CFG es el objeto que será procesado por flex/bison!
Desafortunadamente, la mayoría de los lenguajes no tienen procesamiento CFG incorporado una vez que la complejidad del procesamiento de texto excede la complejidad que se puede expresar mediante expresiones regulares, no hay nada que podamos hacer.
Por ejemplo, si te pidieran que analizaras un texto como este, ¿qué harías?
Por supuesto, no hay nada que pueda hacer con las expresiones regulares. Puede leerlas carácter por carácter, dividir tokens por palabras y luego procesar sintaxis como llaves y punto y coma. Es equivalente a escribir su propio analizador. , Lo cual es muy difícil de garantizar la eficiencia y la escalabilidad. Entonces, en este momento debemos recurrir a flex/bison de terceros o herramientas similares.
Flex es una evolución de lex y realiza análisis léxico. El llamado análisis léxico, para decirlo sin rodeos, consiste en cortar el texto en unidades gramaticales que conoce. Por ejemplo, en la imagen de arriba, el servidor es una unidad gramatical. A esta unidad la llamamos token.
En flex, podemos describir los tokens que aparecen en el texto anterior de esta manera:
El siguiente paso es el análisis de sintaxis. El análisis de sintaxis realiza una coincidencia de patrones, que es diferente de la coincidencia de patrones de expresiones regulares. Le permite definir una serie de reglas recursivas. En Unix estándar, la herramienta de análisis de sintaxis es bison. Veamos cómo se analiza el texto anterior usando bison:
El código principal aún es muy claro para un servidor {...}, use SERVER OP(. {) exp_list CP(}) coincide con dicha regla. Cuando el analizador encuentra un contenido de exp_list que no puede reconocer, buscará una regla llamada exp_list para continuar coincidiendo. Si utiliza con frecuencia lenguajes de programación funcionales, encontrará que este tipo de escritura de reglas le resultará familiar.
La sintaxis utilizada por bison para describir reglas es una variante de BNF.
El siguiente es el resultado de la compilación y ejecución. Como demostración, solo imprimí el contenido del árbol de sintaxis que me interesa:
Del proceso de compilación anterior, puedes ver Sí, flex/bison es un DSL en lenguaje C. Por lo tanto, puede incrustar código C en el proceso de procesamiento léxico y sintaxis, y procesar (transformar) los resultados que necesita. Debe haber algunas interfaces bien establecidas entre el DSL y el idioma anfitrión, razón por la cual existen variables y métodos como yytext, yyparser, yyterminate, yylex, etc. Parecen extraños, pero si los miras con la misma mentalidad que DSL, se vuelven menos incómodos.
(2)
Desafortunadamente, la mayoría de los jóvenes literarios y artísticos ya no usan C, aunque muchos lenguajes proporcionan FFI (Foreign Function Interface) para C, como Python. Puede usar flex/bison para generar un analizador y luego envolverlo con FFI. Sin embargo, esto es problemático después de todo. ¿Qué tan conveniente sería si pudiera usar mi idioma favorito como analizador?
Bueno, hay productos dondequiera que haya demanda. Echa un vistazo a esta página wiki: /bramp/js-sequence-diagrams. Si desea definir un lenguaje que genere JavaScript (no le recomiendo que lo haga), puede consultar coffeescript, que también usa jison.
A continuación, hablemos de otro artefacto antlr4. Entré en contacto con antlr4 cuando estaba escribiendo este artículo y todavía estaba en el proceso de mi primer contacto íntimo. Aparte de las diferencias en el diseño del analizador - LL (*) - para mí, antlr4 tiene tres características poderosas:
Varias definiciones gramaticales listas para usar (básicamente licencia MIT/BSD, inclinarse) ¡Vamos, muchacho! ). Abre este repositorio:/antlr/grammars-v4. ¿Quieres llorar?
Generar analizador para lenguajes de programación convencionales.
Bueno, puedes generar fácilmente código fuente de Python, JavaScript, etc. a partir del archivo de sintaxis g4 y luego integrarlo en tu propio proyecto. Sólo sigue llorando.
Controlado por eventos tipo SAX. antlr4 genera directamente árboles de sintaxis complejos para usted: en términos generales, los árboles de sintaxis generados por antlr4 no son tan refrescantes como los generados por instaparse/bison, etc., por lo que es un poco difícil de procesar directamente. La innovación de antlr4 es: I. Primero te ayudará. Se genera el árbol y luego puedes atravesarlo a voluntad. Al igual que SAX procesa XML, puede configurar el escucha de entrada y salida para cada regla (se puede comparar con cada nodo de XML. Usted registra la devolución de llamada en el nodo que le interesa y antlr4 le entregará el contexto). tratamiento.
Por ejemplo, genere un analizador/lexer de JavaScript para la sintaxis de SQlite y luego escriba una llamada simple a index.js:
El resultado de la llamada (árbol de análisis):
Dado que antlr4 tiene definiciones de sintaxis para la mayoría de los idiomas, puede gastar su energía en transformar en lugar de definiciones de sintaxis. Por ejemplo, el jefe dijo: Xiao Ming, búsqueme todas las funciones en el código base de nuestra empresa que tienen más de 100 líneas y no tienen una línea de comentarios. Quiero revisar a estos nietos que no escriben comentarios.
Esta desagradable necesidad que antes parecía irresoluble ahora puede resolverse en solo un día:
Si el código es python3, busque el archivo g4 de python3 y use antlr4 para generar lexer /parser
Escuche cada regla def y cuente la cantidad de códigos válidos (excluyendo las líneas en blanco) y la cantidad de comentarios. Si el comentario es 0 y la cantidad de códigos excede 100, agregue el nombre de la función y el nombre del archivo. al principio/Escriba el número de línea final, luego use git culpable para encontrar al autor y generar un archivo csv.
Abra este csv con Excel, ajuste el formato y notifique a todos los amigos que conoce y a la persona cuyo nombre parece un nombre chino en él, y pídales que agreguen rápidamente comentarios a sus respectivos códigos y comience. de la lista Elimine (jeje) y luego agregue los 10 principales tipos malos, gráficos circulares, gráficos de barras, etc. Como "primo/primo", puede
Enviar el archivo de Excel al jefe
Bueno, acepta las bendiciones de tus amigos si quieren invitarte a cenar, no te niegues, especialmente de las chicas (hombres). :)
Vale, el último, parsec. parsec es un artefacto. Un artefacto de Haskell que nunca he usado pero quiero probarlo. Haskell es un idioma con el que te obsesionarás una vez que lo aprendas. Verás, Murong Fu, que practicaba Dou Chuan Xing Shi Shi, lamentablemente se volvió loco en el camino hacia su recuperación. El Maestro Zhang, que practicó el Gran Cambio del Cielo y. Tierra, no supo qué belleza elegir en el camino hacia la revolución y desapareció vergonzosamente. Se puede ver que si tu mente está llena de mónadas y composiciones, inevitablemente parecerás una persona psicótica.
Los analizadores mencionados anteriormente son en realidad generadores de analizadores y el código generado no se puede componer. Cuando escribe un analizador SQL, no puede escribir un analizador de selección primero y luego escribir una tabla de creación. los dos componen, es el analizador que admite seleccionar y crear. No puedes hacer eso. Pero el parsec sí puede. En parsec, puede comenzar desde un analizador muy detallado y componerlo en un analizador muy complejo. Por supuesto, parsec ya ha completado muchos analizadores para usted. Solo necesita definir algunos nuevos y luego componerlos con los existentes.
Esto es lo que parsec quiere decir con "un combinador de analizadores monádicos". ¿Shen Ma es una mónada? Ésta es una buena pregunta. Dejémosla de lado por ahora y hablemos de ella en un artículo posterior.
(3)
Este artículo no explica conceptos como LALR(1), LL(1), LL(*), etc., y no explica específicamente los analizador léxico y analizador gramatical Los pasos detallados, aunque brindan algunos ejemplos de BNF (y sus variantes), no abordan cómo escribir BNF. Estos contenidos son importantes, pero no lo son antes de escribir un analizador. Lo que necesitas saber es que además de las expresiones regulares, tienes otras herramientas para manejar texto con formato más complejo. Debe comprender algunos posibles escenarios de aplicación del analizador y también ha visto cómo se utilizan algunas herramientas importantes y cuáles son sus ventajas y desventajas.
No es necesario que abandones lo que estás haciendo de inmediato para aprender estas herramientas; una de las mejores maneras de aprender es practicando en lugar de aprender leyendo un libro (manual). La próxima vez que tu jefe te pida que realices algunas tareas relacionadas con el procesamiento de texto, debes recordar que además de las expresiones regulares, ¡también tienes algunas herramientas que pueden manejar problemas más complejos! No tenga miedo, asuma esta tarea. Creo que el poder de la fecha límite es suficiente para convertirlo de un analizador novato en un experto.
Además, la próxima vez, si cree que la sintaxis de Markdown tiene deficiencias y desea agregar contenido más rico, probablemente sepa cómo hacerlo y qué herramientas puede utilizar para hacerlo.