Nom de ce type d'analyseur, ou pourquoi il n'existe pas

Les analyseurs conventionnels consomment l'intégralité de leur entrée et produisent un seul arbre d'analyse. J'en cherche un qui consomme un flux continu et produit une forêt d'analyse [ modifier: voir la discussion dans les commentaires concernant les raisons pour lesquelles cette utilisation de ce terme peut être non conventionnelle ]. Mon instinct dit que je ne peux pas être la première personne à avoir besoin (ou à penser que j'ai besoin) d'un tel analyseur, mais j'ai cherché pendant des mois en vain.

Je reconnais que je peux être pris au piège par le problème XY. Mon but ultime est d'analyser un flux de texte, en ignorant la majeure partie, et de produire un flux d'arbres d'analyse à partir des sections reconnues.

Ma question est donc conditionnelle: s'il existe une classe d'analyseurs possédant ces caractéristiques, comment s'appelle-t-elle? Et sinon, pourquoi pas? Quelle est l'alternative? Peut-être que je manque un moyen de faire en sorte que les analyseurs conventionnels fassent ce que je veux.

Un analyseur qui renvoie un résultat (partiel) avant que l'intégralité de l'entrée n'ait été consommée est appelé analyseur incrémentiel . L'analyse syntaxique incrémentielle peut être difficile s'il existe des ambiguïtés locales dans une grammaire qui ne sont décidées que plus tard dans l'entrée. Une autre difficulté consiste à simuler les parties de l'arbre d'analyse qui n'ont pas encore été atteintes.

Un analyseur qui renvoie une forêt de tous les arbres d'analyse possibles - c'est-à-dire, retourne un arbre d'analyse pour chaque dérivation possible d'une grammaire ambiguë - est appelé ... Je ne suis pas sûr si ces choses ont encore un nom. Je sais que le générateur d'analyseur Marpa est capable de cela, mais tout analyseur basé sur Earley ou GLR devrait être capable de le faire.

Cependant, vous ne semblez pas vouloir tout cela. Vous avez un flux avec plusieurs documents intégrés, avec des déchets entre les deux:

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

Vous semblez vouloir un analyseur qui saute la poubelle et (paresseusement) génère une séquence d'AST pour chaque document. Cela pourrait être considéré comme un analyseur incrémental dans son sens le plus général. Mais vous implémenteriez une boucle comme celle-ci:

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_docmentfonction serait alors un analyseur conventionnel, non incrémentiel. Il y a une difficulté mineure à vous assurer que vous avez lu suffisamment du flux d'entrée pour une analyse réussie. La manière dont cela peut être géré dépend du type d'analyseur que vous utilisez. Les possibilités incluent l'agrandissement d'un tampon sur certaines erreurs d'analyse ou l'utilisation d'une tokenisation paresseuse.

La tokenisation paresseuse est probablement la solution la plus élégante en raison de votre flux d'entrée. Au lieu d'avoir une phase de lexer produisant une liste fixe de jetons, l'analyseur demanderait paresseusement le prochain jeton à un rappel de lexer ^[1] . Le lexer consommerait alors autant de flux que nécessaire. De cette façon, l'analyseur ne peut échouer que lorsque la fin réelle du flux est atteinte, ou lorsqu'une véritable erreur d'analyse s'est produite (c'est-à-dire que nous avons commencé l'analyse tout en restant dans les ordures).

^{[1] un lexer piloté par le rappel est également une bonne idée dans d'autres contextes, car cela peut éviter certains problèmes avec la correspondance des jetons les plus longs .}

Si vous savez quel type de documents vous recherchez, vous pouvez optimiser le saut pour ne vous arrêter que dans des endroits prometteurs. Par exemple, un document JSON commence toujours par le caractère {ou [. Par conséquent, garbage est une chaîne qui ne contient pas ces caractères.

Il n'y a pas de nom spécifique pour un analyseur qui fait cela. Mais je vais mettre en évidence un algorithme qui fait cela: l' analyse avec des dérivés .

Il consomme des entrées, un jeton à la fois. Il produira une forêt d'analyse à la fin de l'entrée. Alternativement, vous pouvez également obtenir l'intégralité de la forêt d'analyse au milieu de l'analyse (une analyse partielle ).

L'analyse avec des dérivés gère les grammaires sans contexte et produira une forêt d'analyse pour les grammaires ambiguës.

C'est une théorie élégante, vraiment, mais qui n'en est qu'à ses balbutiements et n'est pas largement déployée. Matt Might a une liste de liens vers diverses implémentations dans Scala / Racket / etc.

La théorie est plus facile à apprendre si vous commencez par la reconnaissance avec des dérivés (c'est-à-dire, commencez par prendre des dérivés de langues , dans le but de reconnaître certaines entrées pour déterminer si elles sont valides ou non), puis modifiez le programme pour analyser les dérivés ( c'est-à-dire, changez-le donc au lieu de prendre des dérivés de langages , il prend des dérivés d' analyseurs et calcule une forêt d'analyse).

Loin d'être idéal, mais je l'ai vu faire plus d'une fois: à chaque ligne d'entrée, essayez d'analyser. en cas d'échec, conservez la ligne et ajoutez la suivante. En pseudocode:

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

Le gros problème est que dans certaines langues, vous ne pouvez pas savoir si une expression est complète avant de lire la ligne suivante. Dans ce cas, vous semblez pouvoir lire le suivant, et vérifier si c'est un début valide, ou une suite valide ... Mais pour cela il vous faut la syntaxe exacte du langage

Pire, dans ces langues, il n'est pas difficile de créer un cas pathologique qui ne peut pas être analysé jusqu'à la fin du fichier, même s'il ne s'agit pas d'une seule longue déclaration.

En un mot

Il semble que la solution rapide à votre problème soit de définir un REGEX, ou un FSA (automate à états finis), qui reconnaisse tous les débuts possibles de documents (les faux positifs sont autorisés, qui ne correspondraient pas réellement à un document). Vous pouvez ensuite l'exécuter très rapidement sur votre entrée pour identifier le prochain endroit où un document pourrait commencer avec quelques erreurs. Cela peut entraîner quelques positions erronées pour le démarrage d'un document, mais elles seront reconnues par l'analyseur et abandonnées.

Donc , Finite State Automaton peut être le nom de l' analyseur que vous recherchez. :)

Le problème

Il est toujours difficile de comprendre un problème pratique, surtout lorsque le vocabulaire peut avoir de nombreuses interprétations. Le mot forêt d'analyse a été inventé (afaik) pour une analyse sans contexte (CF) de phrases ambiguës qui ont plusieurs arbres d'analyse. Il peut être quelque peu généralisé à l'analyse d'un réseau de phrases ou à d'autres types de grammaire. D'où toutes les réponses concernant Earley, GLR, Marpa et les analyseurs dérivés (il y en a beaucoup d'autres) qui n'étaient pas pertinentes dans ce cas.

Mais ce n'est apparemment pas ce que vous avez en tête. Vous voulez analyser une chaîne unique qui est une séquence de documents non ambigus et obtenir un arbre d'analyse pour chacun , ou une sorte de représentation structurée, car vous ne dites pas vraiment comment la syntaxe de vos documents est définie, d'où elle se situe un point de vue linguistique formel. Ce que vous avez est un algorithme et des tableaux qui feront le travail d'analyse lors du démarrage au début d'un document. Ainsi soit-il.

Le problème réel est que votre flux de documents contient des déchets considérables qui séparent les documents. Et il semble que votre difficulté soit de scanner ces déchets assez rapidement. Votre technique actuelle consiste à commencer au début, à essayer de numériser à partir du premier caractère et à passer au redémarrage au caractère suivant chaque fois qu'il échoue, jusqu'à ce que vous obteniez un document entier numérisé. Ensuite, vous répétez énoncer à partir du premier caractère après la numérisation du document.

C'est également la solution suggérée par @amon dans la deuxième partie de sa réponse .

Ce n'est peut-être pas une solution très rapide (je n'ai aucun moyen de tester), car il est peu probable que le code de l'analyseur soit optimisé pour être démarré très efficacement au début d'un document. En utilisation normale, il ne le fait qu'une seule fois, de sorte qu'il ne s'agit pas d'un point chaud du point de vue de l'optimisation. Par conséquent, votre bonheur modéré avec cette solution n'est pas trop surprenant.

Donc, ce dont vous avez vraiment besoin, c'est d'un algorithme qui puisse trouver rapidement le début d'un document qui commence par une masse de déchets. Et vous avez de la chance: de tels algorithmes existent. Et je suis sûr que vous le savez: cela s'appelle la recherche d'un REGEX.

La solution simple

Ce que vous devez faire est d'analyser les spécifications de vos documents pour trouver comment ces documents commencent. Je ne peux pas vous dire exactement comment, car je ne sais pas comment leur spécification de syntaxe est organisée officiellement. Peut-être qu'ils commencent tous par un mot d'une liste finie, éventuellement mélangé avec de la ponctuation ou des nombres. C'est à vous de vérifier.

Ce que vous devez faire est de définir un automate à états finis (FSA), ou de manière équivalente pour la plupart des programmeurs une expression régulière (REGEX) qui peut reconnaître les premiers caractères d'un document: plus, mieux c'est, mais il n'est pas nécessaire que ce soit très grand (car cela peut prendre du temps et de l'espace). Cela devrait être relativement facile à faire à partir des spécifications de vos documents, et peut probablement être fait automatiquement avec un programme qui lit les spécifications de vos documents.

Une fois que vous avez produit votre expression rationnelle, vous pouvez l'exécuter sur votre flux d'entrée pour accéder très rapidement au début de votre premier (ou suivant) document comme suit:

Je suppose:
- docstartest une expression régulière qui correspond au début de tous les documents
- search(regex, stream)est une fonction qui recherche streamune sous-chaîne qui correspond regex. Quand il revient, le flux est réduit à son sous-flux de suffixe commençant au début de la première sous-chaîne correspondante, ou au flux vide si aucune correspondance n'est trouvée.
- parse(stream)tente d'analyser un document depuis le début du flux (ce qui en reste) et retourne l'arborescence d'analyse dans n'importe quel format, ou échoue. À son retour, le flux est réduit à son sous-flux de suffixes à partir de la position qui suit immédiatement la fin du document analysé. Il appelle une exception si l'analyse échoue.

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)

Notez que la suppression du premier caractère est nécessaire pour que la prochaine recherche ne retrouve pas la même correspondance.

Bien sûr, le raccourcissement du flux est une image. Il peut simplement s'agir d'un index sur le flux.

Une dernière note est que votre expression régulière n'a pas besoin d'être trop précise, tant qu'elle reconnaît tous les débuts. S'il reconnaît parfois une chaîne qui ne peut pas être le début d'un document (faux positif), alors la seule pénalité est le coût d'un appel inutile à l'analyseur.

Cela peut donc aider à simplifier l'expression régulière, si cela est utile.

À propos de la possibilité d'une solution plus rapide

La solution ci-dessus devrait fonctionner assez bien dans la plupart des cas. Cependant, si vous avez vraiment beaucoup de déchets et de téraoctets de fichier à traiter, il peut y avoir d'autres algorithmes qui s'exécutent plus rapidement.

L'idée est dérivée de l' algorithme de recherche de chaînes de Boyer-Moore . Cet algorithme peut rechercher dans un flux une chaîne unique extrêmement rapidement car il utilise une analyse structurelle de la chaîne pour ignorer la lecture de la plupart du flux, en sautant par-dessus les fragments sans même les regarder. Il s'agit de l'algorithme de recherche le plus rapide pour une seule chaîne.

La difficulté est que son adaptation à la recherche d'expressions régulières, plutôt qu'à une seule chaîne, semble très délicate et pourrait ne pas fonctionner aussi bien, selon les caractéristiques de l'expression régulière que vous envisagez. Cela peut à son tour dépendre de la syntaxe des documents que vous analysez. Mais ne me faites pas trop confiance à ce sujet car je n'ai pas eu le temps de lire attentivement les documents que j'ai trouvés.

Je vous laisse avec un ou deux pointeurs que j'ai trouvés sur le Web, dont un qui est apparemment un document de recherche arbitré , mais vous devriez considérer cela comme plus spéculatif, éventuellement de la recherche, à considérer uniquement si vous avez de graves problèmes de performance. Et il n'y a probablement aucun programme d'étagère qui le fera.

Ce que vous décrivez peut être décrit comme SAX vs SOM.

SAX - (Simple API for XML) est une API d'analyseur d'accès séquentiel d'événements développée par la liste de diffusion XML-DEV pour les documents XML.

SOM - (XML Schema Object Model) accès aléatoire à la représentation en mémoire d'un fichier XML

Il existe des implémentations des deux types en C # et Java, et probablement beaucoup plus. Habituellement, un XSD ou DTD est facultatif.

La joie de SAX est qu'il s'agit d'une surcharge de mémoire, ce qui est idéal pour les gros fichiers XML. Le compromis est que l'accès aléatoire à l'aide de SAX est soit inexistant soit lent, et pire, le temps de développement est généralement beaucoup plus important qu'avec SOM. Le problème évident avec SOM est potentiellement de grandes exigences de RAM.

Cette réponse n'est pas applicable pour toutes les plateformes et toutes les langues.