Analyse par résolution de problèmes - questions

10

J'ai récemment rencontré un article décrivant la technique d'analyse mentionnée dans le titre. Malheureusement, la terminologie utilisée dans cet article est quelque peu au-delà de ma compréhension, j'ai donc essayé de saisir l'algorithme de construction de manière plus intuitive. Je crois que j'ai réussi ( cette présentation a été la source du moment ah-ha), mais une vérification de l'exactitude de la part de quelqu'un qui est familier avec la technique ou la terminologie qu'elle contient serait grandement appréciée.

Je vais décrire mon point de vue sur la solution (si elle est correcte, je pense qu'elle pourrait être utile à d'autres personnes essayant de comprendre la technique) et poser des questions supplémentaires par la suite. Pour assurer qu'il n'y ait pas de malentendu, je vais utiliser la notation standard suivante: , , , et, comme dans l'article,a,b,c,...T. . . X , Y , Z N T α , β , γ , . . . { N T } A i ωA,B,C,...N...X,Y,ZNTα,β,γ,...{NT}Aiω pour désigner la règle numéro . Cependant, je vais probablement utiliser des noms différents pour les concepts que le papier original.i

De plus, tout au long de la description, la relation d'équivalence est utilisée.κ0

Construction

Il existe deux types d'éléments à l'intérieur de l'automate d'analyse: les éléments LR (0) simples de la forme que j'appelle les éléments shift et les éléments de la forme A i α β , m , n que j'appelle résoudre articles ; ceux-ci indiquent à l'analyseur de repousser symboles dans le flux d'entrée, puis de les réduire par le numéro de règle sur le premier symbole de .AiαβAiαβ,m,nm βnmβ

La grammaire est augmentée de la règle et la construction commence avec l'élément de décalage dans l'état initial.S 0S $S0S$S0S$

Maintenant, pour construire l'automate, choisissez entre ces alternatives pour chaque élément dans un état :q

  1. Si l'item est un item de décalage , il y aura une transition q X q dans l'automate, où X est le premier symbole de β .AiαβqXqXβ

  2. Si l'article est un article de quart de travail fini , ajoutez un élément de résolution B j α A β , i , 0 pour chaque règle B j α A β .AiωBjαAβ,i,0BjαAβ

  3. Si l'élément est un élément de résolution , soit X le premier symbole de β . Si X N , ajoutez un élément de décalage X jω pour chaque règle X j ω . Si d'autres éléments que A i α β , m , n ont X comme point de référence de point, ajoutez une transition q X q Aiαβ,m,nXβXNXjωXjωAiαβ,m,nXqXqà l'automate. Chaque élément de résolution dans q se traduira par un élément de résolution C i α X β , m , n + 1 dans q .CiαXβ,m,nqCiαXβ,m,n+1q

  4. Si l'élément est un élément de résolution il ne fournira aucune information de recherche et peut être supprimé, mais ajoutez d'abord un élément de résolution B j α A β , m , n pour chaque règle B j α A β .Aiω,m,nBjαAβ,m,nBjαAβ

Ce n'est bien sûr qu'un croquis; en fait, une fermeture de l'État doit être calculée en premier et ce n'est qu'ensuite que nous pourrons gérer les transitions / changements et résolutions.

Transformer l'automate en une table d'analyse de résolution de décalage est ensuite trivial; juste, comme une variation mineure, les auteurs de l'article interprètent une résolution comme l'action d'accepter. Compte tenu de l'automate résultant, j'ai trouvé plus pratique de simplement traiter un décalage de $ comme action d'acceptation.r0,0$

Des questions

Le premier est, évidemment, si le processus décrit ci-dessus est correct.

La seconde concerne les relations d'équivalence. Je peux seulement deviner que la relation d'équivalence est ce qui est responsable de décider quels éléments de résolution sont introduits lorsqu'un élément de quart de travail fini a été vu. κ 0 semble donner un lookahead étonnamment similaire aux ensembles d'analyseurs LSLR F O L L O W L M. L'article décrit une «relation d'équivalence plus fine» à la page 11; existe-t-il un moyen d'interpréter cette relation en termes intuitifs? Y a-t-il d'autres relations connues?κκ0FOLLOWLM

Et le dernier concerne la résolution des conflits. L'article décrit bien ce qui constitue une insuffisance dans un automate de résolution de changement; Existe-t-il un moyen de résoudre ces insuffisances, similaire aux moyens de résoudre les conflits dans un analyseur LR traditionnel? Quelque chose comme la résolution de conflits de style yacc via la priorité et l'associativité pourrait-il être implémenté dans un générateur d'analyseur ShRe?

Merci si vous lisez tout cela et toutes les réponses seront grandement appréciées :)

Jakub Lédl
la source
suggérer de migrer cette question vers cstheory. quant au papier, il semble que ce soit un algorithme très complexe qui "probablement" (?) n'a été implémenté par personne. l'idée principale semble être de combiner l'anticipation arbitraire mais aussi avec l'analyse temporelle linéaire ...? mais combien d'applications seraient acceptables avec un algorithme superlinéaire plus simple et plus standard? une idée, quelle application fonctionnerait mieux avec cette approche? en avez-vous un ou en connaissez-vous un?
vzn
1
Un très bel exercice théorique (même si je n'ai pas regardé les détails techniques). Étant donné que la pleine puissance de LR (k) n'est souvent même pas utilisée, on peut s'interroger sur l'impact pratique. Je vois 2 problèmes avec ce genre de travail: (1) étant donné que l'algorithme devient plus complexe, est-il toujours possible pour l'esprit humain de déformer la grammaire et de comprendre les conséquences, quand cela ne fonctionne pas. Il est fréquent que les techniques hautement sophistiquées soient très gratifiantes lorsqu'elles fonctionnent, mais aggravent les choses lorsqu'elles ne fonctionnent pas. (2) sera-t-il linéaire dans les cas où les algorithmes CF généraux ne sont pas linéaires.
babou

Réponses: