Analyse par résolution de problèmes - questions

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, ... \in T$. . . X , Y , Z ∈ N ∪ T α , β , γ , . . . ∈ { N ∪ T } ∗ A i →$A, B, C, ... \in N$$... X, Y, Z \in N \cup T$$\alpha, \beta, \gamma, ... \in \{N \cup T\}^*$$A \xrightarrow{i} \omega$ 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.$\kappa_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 .$A \xrightarrow{i} \alpha \bullet \beta$$A \xrightarrow{i} \alpha \bullet \beta, m, n$m $n$$m$$\beta$

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 ′ 0 → ∙ S $S' \xrightarrow{0} S \$$$S' \xrightarrow{0} \bullet S \$$

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 β .$A \xrightarrow{i} \alpha \bullet \beta$$q \xrightarrow{X} q'$$X$$\beta$

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 β .$A \xrightarrow{i} \omega \bullet$$B \xrightarrow{j} \alpha A \bullet \beta, i, 0$$B \xrightarrow{j} \alpha A \beta$

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 $A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$\beta$$X \in N$$X \xrightarrow{j} \bullet \omega$$X \xrightarrow{j} \omega$$A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$q \xrightarrow{X} q'$à 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 ′ .$C \xrightarrow{i} \alpha \bullet X \beta, m, n$$q$$C \xrightarrow{i} \alpha X \bullet \beta, m, n + 1$$q'$

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 β .$A \xrightarrow{i} \omega \bullet, m, n$$B \xrightarrow{j} \alpha A \bullet \beta, m, n$$B \xrightarrow{j} \alpha A \beta$

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.$r_{0,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?$\kappa$$\kappa_0$$FOLLOW_{LM}$

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 :)

Vérifiez si cela est discuté dans l'encyclopédie D. Grune, CJH Jacobs, "Techniques d'analyse: un guide pratique" (Spinger, 2008). Sinon, c'est peut-être assez similaire à une technique discutée.