La mise en œuvre « *? » (Paresseux « * ») de l'expression rationnelle dans parseurs GLR combinatoires

Question

Je l'ai mis en œuvre parseurs GLR combinatoires. Parmi eux il y a:

• analyseur char(·) qui consume caractère spécifié ou la plage de caractères.
• many(·) combinateur qui répète analyseur spécifiée de zéro à des temps infinis.

Exemple:. "char('a').many()" correspondra à une chaîne avec un nombre quelconque de "a"-s

Mais many(·) Combinator est gourmand, donc, par exemple, char('{') >> char('{') >> char('a'..'z').many() >> char('}') >> char('}') (où ">>" est séquentielle de chaînage parseurs) consommera avec succès toute la chaîne de "{{foo}}some{{bar}}".

Je veux mettre en œuvre la version paresseuse de many(·) qui, utilisé dans l'exemple précédent, consommera seulement "{{foo}}". Comment puis-je faire?

Modifier

Peut être je ya tout confus. Dans mon programme un analyseur est une fonction (ou « foncteur » en termes de C ++) qui accepte une « étape » et retourne la forêt des « étapes ». Une « étape » peut être de type OK (cela signifie que l'analyseur a consommé une partie de succès d'entrée) et le type FAIL (ce qui signifie que l'analyseur a rencontré une erreur). Il existe plusieurs types d'étapes, mais ils sont auxiliaires.

Parser = f(Step) -> Collection of TreeNodes of Steps.

Alors, quand je parse entrée, I:

• simple, Compose fonctions Parser prédéfinies pour fonction Parser complexe représentant la grammaire nécessaire.

• Étape initiale de l'entrée du formulaire.

• Donner la première étape à la fonction Parser complexe.

• Filtre TreeNodes avec les étapes, laissant SEULS OK (ou avec un minimum FAIL-s en cas d'erreurs dans l'entrée).

• Recueillir des informations, des étapes qui ont été laissées.

Answer 1

Considérons le <.*?> d'expression régulière et la <a>bc<d>ef d'entrée. Cela devrait trouver <a>, et pas les autres matches, non?

Considérons maintenant le <.*?>e d'expression régulière avec la même entrée. Cela devrait trouver <a>bc<d>e, droit?

Cela pose un dilemme. nous voulons que le comportement du >> combinateur à comprendre en termes de ses deux opérandes Pour l'amour de l'utilisateur,. Pourtant, il n'y a aucun moyen de produire le deuxième comportement de l'analyseur en termes de ce que le premier trouve.

Une réponse est pour chaque analyseur pour produire un séquence de tous les Parsis, classés par ordre de préférence, plutôt que l'ensemble de tous les parseurs non ordonné. correspondant Greedy renverrait à plus long éléments sont classés le plus court; non gourmand, le plus court au plus long.

Answer 2

J'ai mis en œuvre et ont été à l'aide parseurs GLR pendant 15 ans comme extrémités avant de la langue pour un système de transformation du programme.

Je ne sais pas ce qu'est un « analyseur GLR combinatoire » est, et je ne suis pas familier avec votre notation, donc je ne suis pas tout à fait sûr comment l'interpréter. Je suppose que cela est une sorte de notation fonction cari? Je me fais vos règles combinateur sont équivalentes à un definining Grammer en termes de caractères terminaux, où correspond à des règles de grammaire « char ( « a ») beaucoup. »:

 char = "a" ;
 char = char "a" ;

GLR parseurs, en effet, produire tous les Parsis possibles. L'idée clé de l'analyse syntaxique GLR est son traitement psuedo parallèle de tous les Parsis possibles. Si votre « combinateur » peuvent proposer plusieurs Parsis (qui est, ils produisent des règles de grammaire sorte d'équivalent à ce qui précède), et vous avez bien les connectés à un analyseur de GLR, ils auront tous essayé, et seules les séquences de productions que la tuile le texte survivra (ce qui signifie tout parsess valide, par exemple, Parsis ambigus) survivront.

Si vous avez en effet mis en place un analyseur GLR, cette collection de tous les Parsis possibles aurait été extrêmement clair pour vous. Le fait que ce n'est pas fait allusion ce que vous avez mis en œuvre n'est pas un analyseur GLR.

récupération d'erreur avec un analyseur de GLR est possible, tout comme avec toute autre technologie d'analyse syntaxique. Ce que nous faisons est de garder l'ensemble des Parsis en direct avant le point de l'erreur; lorsqu'une erreur est trouvée, nous essayons (en psuedo parallèle, l'appareil analyse syntaxique GLR facilite cette opération si elle plié correctement) tous les éléments suivants: a) la suppression du jeton offenser, b) l'insertion de tous les jetons qui essentiellement sont FOLLOW (x) où x est parse en direct. En substance, supprimer le jeton, ou insérer celui attendu par une analyse syntaxique en direct. Nous passons ensuite à l'analyseur de GLR lâche à nouveau. Seuls les Parsis valides (par exemple, les réparations) survivront. Si le jeton actuel ne peut pas être traité, l'analyseur à traiter le flux avec le jeton Deleted survive. Dans le pire des cas, les extrémités de récupération d'erreur d'analyseur GLR jusqu'à jeter tous les jetons à EOF. Un inconvénient sérieux à cette règle est le temps d'exécution de l'analyseur GLR se développe assez radicalement en erreurs d'analyse syntaxique; s'il y a beaucoup en un seul endroit, le temps de récupération d'erreur peut passer par le toit.

Answer 3

est un analyseur de GLR produire tous les Parsis possibles de l'entrée? Puis résoudre l'ambiguïté est une question de choisir l'analyse syntaxique que vous préférez. Pour ce faire, je suppose que les éléments de la nécessité de la forêt Parse à être étiquetés en fonction de ce genre de combinateur leur produit, avide ou paresseux. (Vous ne pouvez pas résoudre l'ambiguïté progressivement avant que vous avez vu toutes les entrées, en général.)

(Cette réponse basée sur ma mémoire faible et d'incompréhension possible vague de l'analyse syntaxique GLR. Espérons que quelqu'un expert viendra par.)

Answer 4

fonctionnalité non gourmand est rien de plus qu'un mécanisme d'homonymie. Si vous avez vraiment un analyseur généralisé (qui ne nécessite pas homonymie pour produire ses résultats), puis « non gourmand » n'a pas de sens; les mêmes résultats seront retournés ou non un opérateur est « non gourmand ».

comportement homonymie non gourmand pourrait être appliquée à l'ensemble des résultats fournis par un analyseur généralisé. Utilisation de gauche à droite, filtre les sous-groupes ambiguës correspondant à un opérateur non avide d'utiliser la plus courte rencontre toujours conduit à une analyse syntaxique réussie de l'entrée restante.