Nombre para este tipo de analizador, O por qué no existe

Los analizadores convencionales consumen toda su información y producen un solo árbol de análisis. Estoy buscando uno que consuma una secuencia continua y produzca un bosque de análisis [ editar: vea la discusión en los comentarios sobre por qué este uso de ese término puede ser poco convencional ]. Mi instinto dice que no puedo ser la primera persona en necesitar (o pensar que necesito) un analizador de este tipo, pero lo he buscado durante meses sin resultado.

Reconozco que puedo quedar atrapado por el problema XY. Mi propósito final es analizar una secuencia de texto, ignorando la mayor parte, y producir una secuencia de árboles de análisis de las secciones que se reconocen.

Entonces mi pregunta es condicional: si existe una clase de analizadores con estas características, ¿cómo se llama? Y si no, ¿por qué no? Cual es la alternativa? Tal vez me estoy perdiendo alguna forma de hacer que los analizadores convencionales hagan lo que quiero.

Un analizador sintáctico que devuelve un resultado (parcial) antes de que se haya consumido toda la entrada se denomina analizador incremental . El análisis incremental puede ser difícil si hay ambigüedades locales en una gramática que solo se deciden más adelante en la entrada. Otra dificultad es fingir aquellas partes del árbol de análisis que aún no se han alcanzado.

Un analizador sintáctico que devuelve un bosque de todos los posibles árboles de análisis, es decir, devuelve un árbol de análisis por cada posible derivación de una gramática ambigua, se llama ... No estoy seguro de si estas cosas tienen un nombre todavía. Sé que el generador de analizadores Marpa es capaz de esto, pero cualquier analizador basado en Earley o GLR debería ser capaz de lograrlo.

Sin embargo, no parece querer nada de eso. Tiene una secuencia con varios documentos incrustados, con basura en el medio:

 garbagegarbage{key:42}garbagegarbage[1,2,3]{id:0}garbage...

Parece que quiere un analizador que salte la basura y (perezosamente) produzca una secuencia de AST para cada documento. Esto podría considerarse como un analizador incremental en su sentido más general. Pero en realidad implementaría un bucle como este:

while stream is not empty:
  try:
    yield parse_document(stream at current position)
  except:
    advance position in stream by 1 character or token

La parse_docmentfunción sería entonces un analizador no incremental convencional. Hay una dificultad menor para garantizar que ha leído lo suficiente del flujo de entrada para un análisis exitoso. Cómo se puede manejar esto depende del tipo de analizador que esté utilizando. Las posibilidades incluyen el crecimiento de un búfer en ciertos errores de análisis o el uso de tokenización diferida

La tokenización diferida es probablemente la solución más elegante debido a su flujo de entrada. En lugar de que una fase lexer produzca una lista fija de tokens, el analizador solicitaría perezosamente el siguiente token de una devolución de llamada lexer ^[1] . El lexer consumiría la mayor cantidad de flujo que fuera necesario. De esta forma, el analizador solo puede fallar cuando se alcanza el final real de la secuencia o cuando se produce un error de análisis real (es decir, comenzamos a analizar mientras todavía está en la basura).

^{[1] un lexer controlado por devolución de llamada también es una buena idea en otros contextos, ya que esto puede evitar algunos problemas con la coincidencia de token más larga .}

Si sabe qué tipo de documentos está buscando, puede optimizar la omisión para detenerse solo en ubicaciones prometedoras. Por ejemplo, un documento JSON siempre comienza con el carácter {o [. Por lo tanto, la basura es cualquier cadena que no contenga estos caracteres.

No hay un nombre específico para un analizador que haga esto. Pero destacaré un algoritmo que hace esto: análisis con derivados .

Consume entrada, una ficha a la vez. Producirá un bosque de análisis al final de la entrada. Alternativamente, también puede obtener todo el bosque de análisis mientras está en medio del análisis (un análisis parcial ).

El análisis con derivados maneja gramáticas libres de contexto y producirá un bosque de análisis para gramáticas ambiguas.

Es una teoría elegante, en realidad, pero solo está en su infancia y no está ampliamente implementada. Matt Might tiene una lista de enlaces a varias implementaciones en Scala / Racket / etc.

La teoría es más fácil de aprender si comienza con el reconocimiento con derivados (es decir, comienza con la toma de derivados de idiomas , con el objetivo de reconocer alguna entrada para determinar si es válida o no), y luego altera el programa para analizar con derivados ( es decir, cámbielo para que, en lugar de tomar derivados de idiomas , tome derivados de analizadores y calcule un bosque de análisis).

Lejos de ser ideal, pero lo he visto hacer más de una vez: en cada línea de entrada, intente analizar. si falla, mantenga la línea y agregue la siguiente. En pseudocódigo:

buffer = ''
for each line from input:
    buffer = buffer + line
    if can parse buffer:
        emit tree
        buffer = ''

El gran problema es que en algunos idiomas no se puede saber si una expresión está completa antes de leer la siguiente línea. En ese caso, parece que podría leer el siguiente y verificar si es un comienzo válido o una continuación válida ... Pero para eso necesita la sintaxis exacta del idioma

Peor aún, en esos idiomas no es difícil crear un caso patológico que no se pueda analizar hasta el final del archivo, incluso si no se trata de una sola declaración larga.

En una palabra

Parece que la solución rápida a su problema es definir un REGEX, o un FSA (autómata de estado finito), que reconoce todos los comienzos posibles de los documentos (se permiten falsos positivos, que en realidad no corresponderían a un documento). Luego puede ejecutarlo muy rápido en su entrada para identificar el próximo lugar donde un documento podría comenzar con pocos errores. Puede causar algunas posiciones erróneas para el inicio de un documento, pero el analizador los reconocerá y los abandonará.

Por lo tanto, Finite State Automaton puede ser el nombre del analizador que estaba buscando. :)

El problema

Siempre es difícil entender un problema práctico, especialmente cuando el vocabulario puede tener muchas interpretaciones. La palabra bosque de análisis fue acuñada (afaik) para el análisis sin contexto (CF) de oraciones ambiguas que tienen varios árboles de análisis. Se puede generalizar un poco para analizar una red de oraciones u otros tipos de gramática. De ahí todas las respuestas sobre Earley, GLR, Marpa y analizadores derivados (hay muchos otros) que no fueron relevantes en este caso.

Pero eso aparentemente no es lo que tienes en mente. Desea analizar una cadena única que es una secuencia de documentos inequívocos y obtener un árbol de análisis para cada uno , o algún tipo de representación estructurada, ya que realmente no dice cómo se define la sintaxis de sus documentos, desde dónde se encuentra. Un punto de vista del lenguaje formal. Lo que tiene es un algoritmo y tablas que harán el trabajo de análisis cuando se inicie al comienzo de un documento. Que así sea.

El problema real es que su flujo de documentos contiene basura considerable que separa los documentos. Y parece que su dificultad es escanear esta basura lo suficientemente rápido. Su técnica actual es comenzar desde el principio e intentar escanear desde el primer carácter, y saltar al reinicio en el siguiente carácter cada vez que falle, hasta que escanee un documento completo. Luego repite indicando desde el primer carácter después del documento recién escaneado.

Esa es también la solución sugerida por @amon en la segunda parte de su respuesta .

Puede que no sea una solución muy rápida (no tengo forma de probarlo), porque es poco probable que el código del analizador esté optimizado para iniciarse de manera muy eficiente al comienzo de un documento. En uso normal, hace esto solo una vez, por lo que no es un punto caliente desde el punto de vista de la optimización. Por lo tanto, su felicidad moderada con esta solución no es demasiado sorprendente.

Entonces, lo que realmente necesita es un algoritmo que pueda encontrar rápidamente el comienzo de un documento que comienza con una gran cantidad de basura. Y tienes suerte: tales algoritmos existen. Y estoy seguro de que lo sabes: se llama buscar un REGEX.

La solución simple

Lo que debe hacer es analizar la especificación de sus documentos para encontrar cómo comienzan estos documentos. No puedo decir exactamente cómo, ya que no estoy seguro de cómo se organiza formalmente su especificación de sintaxis. Posiblemente todos comienzan con alguna palabra de una lista finita, posiblemente mezclada con algunos signos de puntuación o números. Eso es para que lo compruebes.

Lo que debe hacer es definir un autómata de estado finito (FSA), o de manera equivalente para la mayoría de los programadores, una expresión regular (REGEX) que pueda reconocer los primeros caracteres de un documento: cuanto más, mejor, pero no tiene por qué ser muy grande (ya que puede llevar tiempo y espacio). Esto debería ser relativamente fácil de hacer desde la especificación de sus documentos, y probablemente se pueda hacer automáticamente con un programa que lea la especificación de sus documentos.

Una vez que haya producido su expresión regular, puede ejecutarla en su flujo de entrada para llegar muy rápidamente al comienzo de su primer (o siguiente) documento de la siguiente manera:

Asumo:
- docstartes una expresión regular que coincide con el comienzo de todos los documentos
- search(regex, stream)es una función que las búsquedas streampara una subcadena que los fósforos regex. Cuando regresa, el flujo se reduce a su flujo secundario de sufijo que comienza al comienzo de la primera subcadena coincidente, o al flujo vacío si no se encuentra ninguna coincidencia.
- parse(stream)intenta analizar un documento desde el principio de la secuencia (lo que queda de él) y devuelve el árbol de análisis en cualquier formato, o falla. Cuando regresa, el flujo se reduce a su flujo secundario de sufijo comenzando en la posición que sigue inmediatamente al final del documento analizado. Llama a una excepción si el análisis falla.

forest = empty_forest
search(docstart, stream)
while stream is not empty:
  try:
    forest = forest + parse(stream)
  except
    remove first character from stream
  search(docstart, stream)

Tenga en cuenta que la eliminación del primer carácter es necesaria para que la próxima búsqueda no vuelva a encontrar la misma coincidencia.

Por supuesto, el acortamiento de la corriente es una imagen. Puede ser solo un índice en la transmisión.

Una nota final es que su expresión regular no necesita ser demasiado precisa, siempre que reconozca todos los comienzos. Si reconoce ocasionalmente una cadena que no puede ser el comienzo de un documento (falso positivo), entonces la única penalización es el costo de una llamada inútil al analizador.

Por lo tanto, eso puede ayudar a simplificar la expresión regular, si es útil.

Sobre la posibilidad de una solución más rápida

La solución anterior debería funcionar bastante bien en la mayoría de los casos. Sin embargo, si realmente tiene una gran cantidad de basura y terabytes de archivo para procesar, puede haber otros algoritmos que se ejecuten más rápido.

La idea se deriva del algoritmo de búsqueda de cadenas de Boyer-Moore . Este algoritmo puede buscar una secuencia para una sola cadena extremadamente rápido porque utiliza un análisis estructural de la cadena para omitir la lectura de la mayor parte de la secuencia, saltando fragmentos sin siquiera mirarlos. Es el algoritmo de búsqueda más rápido para una sola cadena.

La dificultad es que su adaptación a la búsqueda de expresiones regulares, en lugar de una sola cadena, parece muy delicada y podría no funcionar tan bien, dependiendo de las características de la expresión regular que esté considerando. Eso a su vez podría depender de la sintaxis de los documentos que está analizando. Pero no confíe demasiado en mí en esto, ya que no tuve tiempo de hacer una lectura cuidadosa de los documentos que encontré.

Te dejo con uno o dos punteros que encontré en la web, incluido uno que aparentemente es un trabajo de investigación arbitrado , pero debes considerar esto como más especulativo, posiblemente investigativo, para ser considerado solo si tienes problemas de rendimiento. Y probablemente no haya ningún programa de plataforma que lo haga.

Lo que está describiendo se puede describir como SAX vs. SOM.

SAX: (API simple para XML) es una API de analizador de acceso secuencial de eventos desarrollada por la lista de correo XML-DEV para documentos XML.

SOM: acceso aleatorio (modelo de objetos de esquema XML) a la representación en memoria de un archivo XML

Hay implementaciones de ambos tipos en C # y Java, y probablemente muchas más. Por lo general, un XSD o DTD es opcional.

La alegría de SAX es que tiene poca sobrecarga de memoria, lo cual es ideal para archivos XML grandes. La desventaja es que el acceso aleatorio que usa SAX es inexistente o lento, y lo que es peor, el tiempo de desarrollo suele ser considerable más que con SOM. El problema obvio con SOM son los requisitos de RAM potencialmente grandes.

Esta respuesta no es aplicable para todas las plataformas y todos los idiomas.