parsing - Analizadores de ejemplo para aprender a escribirlos

language-agnostic

Question

Estoy buscando códigos fuente de analizadores sintácticos y / o analizadores sintácticos que puedan estudiarse para desarrollar aún más mis habilidades que adquirí durante un curso escolar. ¿Conoces algún analizador recomendable de cualquier tipo?

Answer 1

Acabo de pasar por las mismas batallas y finalmente siento que tengo un buen control de tus opciones.

Muchos analizadores son compilados para gramáticas libres de contexto. Puede leer la definición formal de sin contexto, pero mi intuición es que básicamente significa que los tokens / reglas de sintaxis no pueden cambiar en función de algún contexto. Podría estar equivocado acerca de esto, pero creo que también significa que no tienes la mirada hacia adelante.

Por ejemplo, markdown no está libre de contexto, y creo que prácticamente cualquier lenguaje que esté basado en indentación no está libre de contexto sin tener que hacer un preprocesamiento para envolver bloques con tokens de inicio y finalización. C es un ejemplo perfecto de una gramática libre de contexto.

Si se trata de una gramática libre de contexto, BNF es una forma formal de especificar el compilador. Este fue un artículo inmensamente útil que explica cómo funcionan las gramáticas de BNF, cómo están funcionando y las extensiones comunes de las gramáticas de BNF.

Algunas de sus opciones en esta categoría son ANTLR, Bison, Yacc, Jison y Peg.js.

Sin embargo, después de luchar contra ANTLR por un tiempo, encontré lo que creo que es la mejor solución: "combinadores de analizadores sintácticos". Es básicamente regex en esteroides y muy popular en el mundo de la programación funcional.

Aún no tengo recursos de aprendizaje buenos para usted, pero busque en Google y los encontrará en casi cualquier idioma. Vengo del mundo de JavaScript y leer el código fuente de esta pequeña biblioteca realmente me ayudó a entender de qué se trata.

Answer 2

Debes saber cómo construir analizadores de descenso recursivos a mano. Aquí hay un enlace SO a una lección rápida sobre cómo hacer esto: https://.com/a/2336769/120163

Si desea comprender cómo los analizadores de descenso recursivos se pueden construir automáticamente, puede leer un documento (y ver un tutorial) en MetaII en este enlace: https://.com/a/1142034/120163

Answer 3

Los analizadores por sí mismos no suelen ser tan interesantes, son los generadores de analizadores los que son más un tema de estudio.

• ANTLR genera analizadores LL que son fáciles de leer una vez generados. (Java)
• Bison genera analizadores LALR (1) que son imposibles de leer. (DO)

Si LALR (1) te interesa, tengo una biblioteca en github que intenta hacer un nuevo número en el análisis LALR. Siéntete libre de echar un vistazo. Está en C # y he intentado todo lo posible para que el código sea comprensible. Ha sido un proyecto de aprendizaje para mí, pero es más pequeño que las herramientas grandes y un poco más fácil de penetrar. Y definitivamente no dude en contribuir, muchas características para agregar aún.

De lo contrario, eche un vistazo al código generado de estas herramientas para ver cómo construyen los analizadores reales que hacen el trabajo.

Answer 4

Sugeriría este libro: http://www.cs.nott.ac.uk/~gmh/book.html . es bastante bueno comenzar Haskell y tiene un capítulo completo sobre analizadores sintácticos.

Si puedes entender eso, crear un analizador usando Haskell es bastante directo. Tenga también en cuenta que Haskell es bastante rápido y bueno para la programación multi-core, por lo que puede ser el futuro.

Más.

Aquí hay un analizador sintáctico en Haskell: Happy - http://www.haskell.org/happy/ .

Answer 5

• Bison es un ejemplo clásico (C / C ++).
• Pyparsing es un gran módulo, y es muy fácil de usar (Python).
• Lemon es muy fácil de usar (C ++).

Verifica los ejemplos y buena suerte.

Editar:

Creo que debería comentar. Un parser es un programa que procesa una entrada y la "entiende". Un parser generator es una herramienta utilizada para escribir analizadores. Supongo que quiere decir que desea obtener más información sobre la generación de analizadores, en cuyo caso, debe consultar la documentación de los generadores de analizadores sintácticos (todos los anteriores).