El análisis de XML requiere una herramienta que sea capaz de reconocer algo llamado "lenguaje sin contexto". Las expresiones regulares reconocen los idiomas regulares, que son un subconjunto de lenguajes libres de contexto.
Reconociendo Regular Idiomas
lenguajes regulares son reconocidos por autómatas finitos determinista (DFA). Un DFA es un conjunto de estados con bordes de transición entre estados y un búfer de entrada (la cadena que está analizando). El DFA comienza en su estado de inicio. El DFA lee el carácter al principio del búfer de entrada, que le dice qué transición tomar. Esto mueve el DFA al siguiente estado, donde repite el proceso. Si el DFA alguna vez encuentra un carácter de entrada para el cual no tiene una transición, finaliza (la entrada no fue reconocida). Si el DFA alcanza un estado final designado, la entrada ha sido reconocida
Lo más importante que debe recordar es que los DFA no pueden recordar en qué estados han estado, justo donde están ahora y dónde para ir después. Esto hace que sea imposible que un DFA reconozca ciertos tipos de idiomas, como etiquetas XML coincidentes, por ejemplo.
Las implementaciones de expresiones regulares (como PCRE) tienen algunas extensiones por conveniencia ('+', '?' Y clases de caracteres, por ejemplo) y otras que cambian el poder de las expresiones regulares (como lookahead y back-references) . Estas expresiones regulares son más poderosas que los DFA, pero sería difícil o imposible construir un analizador XML solo con estas expresiones regulares extendidas.
Reconociendo libre de contexto Idiomas
lenguajes libres de contexto son reconocidos por autómatas de pila. Funcionan como los DFA, pero con la adición de una pila. Automatización de inserción Seleccione una transición utilizando el primer carácter de la entrada y el valor en la parte superior de la pila. En cada paso, la máquina consume un carácter de entrada y puede insertar un valor en la pila, hacer estallar uno o no hacer nada con la pila.
Pushdown autómata puede utilizar la pila para recordar dónde han estado, lo que los hace adecuados para analizar idiomas como XML (o la mayoría de los lenguajes de programación, con algunas excepciones especiales).
Análisis de XML
analizadores no se construyen mediante el diseño de un autómata de pila, de la misma manera que usted no reconoce lenguajes regulares mediante el diseño de un DFA. Las gramáticas libres de contexto son una forma más agradable de describir un lenguaje sin contexto. Generalmente están escritos en Backus-Naur Form (BNF). He aquí una sencilla gramática BNF para un subconjunto de XML:
Tags ::= Tag Tags | <nothing>
Tag ::= "<" /[a-zA-Z]+/ Attributes ">" Document "</" /[a-zA-Z]+/ ">"
Attributes ::= Attribute Attributes | <nothing>
Attribute ::= /[a-zA-Z]+/ "=" "\"" /[a-zA-Z0-9 ]+/ "\""
Esta gramática se compone de no terminales ("etiquetas", "Etiqueta", "Atributos" y "Atributo"). En cualquier lugar donde una terminal no terminal aparece en el lado derecho de una regla, puede ser reemplazada por cualquiera de las posibles definiciones (separadas por |). El texto entre comillas y las expresiones regulares son terminales, que deben coincidir exactamente con la entrada.
La etiqueta no terminal reconoce las etiquetas de inicio y fin, con una etiqueta no terminal entre ellas. Cada vez que el analizador reconoce una etiqueta de inicio, espera encontrar la etiqueta de cierre en el otro lado. Las etiquetas reconocerán una etiqueta, seguida de las etiquetas nuevamente. Esta definición recursiva permite que el analizador reconozca un número ilimitado de etiquetas.
Los generadores de analizadores son herramientas que convierten las gramáticas libres de contexto en autómatas pushdown para reconocer el idioma de entrada. Esto elimina la complejidad de construir un analizador sintáctico, aunque existen muchos desafíos para especificar con precisión una gramática.
Otros métodos para analizar
Se puede escribir un programa de análisis sin la construcción de la máquina de estados con la mano, o escribiendo una gramática libre de contexto. Por lo general, esto se hace con un analizador sintáctico de descenso recursivo o un analizador sintáctico hecho a mano que usa expresiones regulares con algún conocimiento especial sobre el lenguaje que se analiza. Los analizadores de descenso recursivos se parecen mucho a las gramáticas libres de contexto, pero tienen algunos problemas graves de rendimiento y limitaciones funcionales. También hay análisis gramaticales de expresión (PEG) que funcionan como un híbrido de expresiones regulares y gramáticas BNF. Hay excelentes artículos sobre todas estas técnicas en Wikipedia, y muchas herramientas disponibles para construir analizadores de todo tipo.
Lectura en [generadores de analizadores] (http://en.wikipedia.org/wiki/Parser_generator); en general, recorre los caracteres de la cuerda de a uno por vez, y hace un seguimiento del tipo de cosas que debe buscar, p. ej. "Si veo un' <- 'luego voy al modo en el que estoy analizando un comentario, si veo un' <'entonces entro en el modelo donde estoy analizando un elemento". Entonces, podría [usar un generador de analizador más una gramática] (http://stackoverflow.com/questions/570144/best-practices-for-writing-a-parser) para XML, o podría escribir su propio analizador con estado de la tierra arriba. – Phrogz
Por lo tanto, se trata de un análisis de texto similar al de los motores de expresiones regulares, solo especializado en una estructura de código esperada, que intercambia flexibilidad para el rendimiento. – Armatus
Similar, sí. De hecho, en algunos idiomas es fácil [compilar un analizador que usa expresiones regulares para sorber caracteres] (http://www.ruby-doc.org/stdlib-1.9.3/libdoc/strscan/rdoc/StringScanner.html). La diferencia es que una sola expresión regular no puede explicar el estado muy bien (por ejemplo, buscando '/] +> /' dentro de ' ->' mientras que un analizador realiza un seguimiento de dónde es. –
Phrogz