Aprender más acerca de Parsing

Question

He estado programando desde 1999 para el trabajo y la diversión. Quiero aprender cosas nuevas, y últimamente me he centrado en el análisis, ya que una gran parte de mi trabajo es leer, integrar y analizar datos. También tengo una gran cantidad de tareas repetitivas que creo que podría expresar en lenguajes específicos de dominio muy simples si la sobrecarga era lo suficientemente baja. Tengo algunas preguntas sobre el tema.

1. La mayor parte de mi código de análisis actual no define una gramática formal. Por lo general, hackeo algo en mi idioma de elección porque es fácil, sé cómo hacerlo y puedo escribir ese código muy rápido. También es fácil para otras personas con las que trabajo mantener. ¿Cuáles son las ventajas y desventajas de definir una gramática y generar un analizador real (como se haría con ANTLR o YACC) para analizar cosas en comparación con los hacks que la mayoría de los programadores utilizan para escribir analizadores?
2. ¿Cuáles son las mejores herramientas de generación de analizador para escribir analizadores gramaticales en C++, Perl y Ruby? He observado ANTLR y no he encontrado mucho sobre el uso de ANTLRv3 con un objetivo de C++, pero por lo demás eso parece interesante. ¿Cuáles son las otras herramientas que son similares a ANTLR sobre las que debería leer?
3. ¿Cuáles son los libros y artículos canónicos que alguien está interesado en aprender más sobre el análisis? Desafortunadamente, un curso de compiladores no formaba parte de mi educación, por lo que el material básico es muy bienvenido. He oído grandes cosas sobre el Dragon Book, pero ¿qué más hay por ahí?

Answer 1

En 1., yo diría que la principal ventaja es mantenimiento - haciendo un pequeño cambio en el lenguaje simplemente significa hacer un pequeño cambio correspondientemente a la gramática, en lugar de minuciosamente la piratería a través de los diversos lugares en el código eso puede tener algo que ver con lo que quiere cambiar ... órdenes de magnitud, mejor productividad y menor riesgo de errores.

En 2. y 3., no puedo sugerir mucho más de lo que ya encontraste (uso principalmente Python y pyparsing, y podría comentar por experiencia en muchos frameworks de análisis parseados en Python, pero para C++ utilizo principalmente bueno viejo yacc o bison de todos modos, y mi vieja copia nudosa del Libro del Dragón, no la última edición, en realidad, es todo lo que mantengo a mi lado para el propósito ...).

Answer 2

Let's Build A Compiler es un tutorial paso a paso sobre cómo escribir un compilador simple. El código está escrito en Delphi (Pascal), pero es lo suficientemente básico como para traducirlo fácilmente a la mayoría de los demás idiomas.

Answer 3

En perl, los módulos Parse :: RecDescent es el primer lugar para comenzar. Agregue un tutorial al nombre del módulo y Google debería poder encontrar muchos tutoriales para comenzar.

Answer 4

Esta es mi opinión sobre sus (muy bueno) preguntas:

1. creo un programa de análisis más se beneficia de situaciones no triviales cuando en realidad existe una gramática. Debes saber cómo los analizadores y las gramáticas trabajan para pensar en esa técnica, y no todos los desarrolladores lo hacen.
2. lex/yacc son herramientas antiguas de Unix que pueden ser útiles para usted como desarrollador de C++. Quizás Bison también.
3. ANTRL y su libro asistente son muy buenos. "Writing Compilers and Interpreters" tiene ejemplos de C++ que te pueden gustar.

El patrón de Interpretación GoF es otra técnica para escribir "pequeños idiomas". Mira eso.

Answer 5

Definir una gramática utilizando BNF, EBNF o algo similar, es más fácil y más adelante lo tendrá mejor para mantenerlo. Además, puedes encontrar muchos ejemplos de definiciones de gramática. Por último, pero no menos importante, si vas a hablar sobre tu gramática con alguien más en el campo, es mejor si ambos hablan el mismo idioma (BNF, EBNF, etc.).

Escribir su propio código de análisis es como reinventar la rueda y es propenso a errores. También es menos sostenible. Por supuesto, puede ser más flexible, y para proyectos pequeños también podría ser una buena opción, pero usar un generador de analizadores existente que tome una gramática y escuche el código debería cubrir la mayoría de nuestras necesidades.

Para C++ También sugeriría lex/yacc. Para Ruby esto parece una opción decente: Coco/R(uby)

Answer 6

Momento divertido: pasé muchas de esta mañana preguntándome sobre las máquinas de estado y los analizadores sintácticos, y tratando de descubrir cómo podría aprender más sobre ellas.

Para 2, puede echar un vistazo a Ragel (es bueno para C++ y Ruby).

Answer 7

Me gustaría echar un vistazo serio al análisis basado en un combinador monádico (que a menudo también se ocupa del análisis léxico) en Haskell. Me pareció bastante revelador; es increíble lo fácil que es construir un analizador desde cero utilizando este método. De hecho, es tan fácil que a menudo es más rápido escribir su propio analizador que tratar de usar las bibliotecas existentes.

El ejemplo más famoso es probablemente Parsec que tiene un buen user guide que explica cómo usarlo. Hay una lista de puertos de esta biblioteca a otros idiomas (incluidos C++ y Ruby) enumerados en el Parsec page of the Haskell wiki, aunque no los conozco, por lo que no puedo decir qué tan cerca están de usar Parsec en Haskell.

Si quiere aprender cómo funcionan internamente y cómo escribir uno propio, le recomiendo comenzar con el Capítulo 8 ("Analizadores Funcionales") de Graham Hutton's Programming in Haskell. Una vez que comprenda bien ese capítulo (que probablemente tomará varias lecturas), lo establecerá.

Answer 8

Aquí hay un tutorial sobre un auto-contenida, completamente portátil compilador de computador que puede ser utilizado para diseñar e implementar una SL de "bajo costo operativo" muy rápidamente (10 páginas!):

http://www.bayfronttechnologies.com/mc_tutorial.html

Este El sitio lo guía a través del documento de 1964 de Val Schorre sobre MetaII. Sí, 1964. Y es increíble. Así es como aprendí sobre los compiladores en 1970.