Forma de libro de texto de informática para hacer texto / xml / cualquier análisis
-
02-07-2019 - |
Pregunta
Ha estado en mi cerebro por un tiempo.
He investigado un poco sobre Compiladores / Flex / Byson y otras cosas, pero nunca encontré una buena referencia que hablara en detalle acerca de la "pila de análisis" o cómo implementar una.
¿Alguien sabe de buenas referencias donde pueda ponerme al día?
Editar : aprecio todas las referencias del compilador, y voy a obtener algunos de los libros enumerados, pero mi enfoque principal estaba en el análisis en sí y no en lo que haces con él después .
Solución
Esto es en respuesta a la respuesta de Dima que usted aceptó como la respuesta correcta. Aunque no es una mala respuesta afirmar que el análisis está relacionado con la teoría de autómatas, creo que hay algunos malentendidos aquí.
-
En primer lugar, los autómatas de estado finito solo pueden reconocer idiomas regulares (por ejemplo, expresiones regulares). Para reconocer lenguajes libres de contexto necesita pushdown automata , que es más potente. Consulte http://en.wikipedia.org/wiki/Automata_theory#Classes_of_automata para obtener más autómatas y su relación con diferentes clases de idiomas.
-
En segundo lugar, el análisis es diferente de reconocer . Reconocer una cadena solo te dice si esa cadena está en el lenguaje generado por tu gramática. El propósito de un analizador sintáctico es producir un árbol de sintaxis concreto que sea más difícil y generalmente más útil.
Existe una gran variedad de métodos de análisis, por lo que es difícil darle una referencia específica que le diga lo que necesita saber ... En general, debe comprender la diferencia entre análisis de arriba hacia abajo y análisis de abajo hacia arriba . Pero aquí hay una descripción general de algunas técnicas comunes empleadas por los generadores de analizadores sintéticos en caso de que esté interesado:
- Los artículos de Wikipedia para LR Parsing , Análisis LL , Análisis SLR , Análisis LALR , Análisis de GLR
- ANTLR's LL (*) análisis
- Análisis monádico en Haskell (para construir analizadores en programación funcional idiomas)
- Y los más exóticos Analizando las gramáticas de expresión
EDITAR: Perdón por responder esta pregunta nuevamente, acabo de pasar por dos excelentes publicaciones que describen la relación entre lenguajes regulares y autómatas finitos , idiomas sin contexto y autómatas push-down . Puede ser interesante para las personas que encuentran esta pregunta.
Otros consejos
¡El Dragon book ! Lo utilicé recientemente para escribir un compilador (¡en PHP!) Para un lenguaje de procesamiento para archivos de plantilla escritos en RTF ...
Un analizador es básicamente una máquina de estados finitos, también conocido como un autómata finito. Debería encontrar un libro sobre teoría de la computación, que discute autómatas finitos y cosas como lenguajes regulares, lenguajes libres de contexto, etc.
pruebe amazon
Construcción del compilador es solo un buen ejemplo
Echa un vistazo a "Brinch Hansen en los compiladores de Pascal". Fue escrito en 1985, pero lo utilicé el año pasado para un curso sobre compiladores (por supuesto por Per Brinch Hansen) y lo encontré muy conciso y útil para el diseño del compilador. .