Comment modifier les actions sémantiques lors de la suppression récursivité à gauche d'une grammaire

Question

Y at-il algorithme qui nous indique comment modifier les actions sémantiques associées à une grammaire récursive gauche? Par exemple, nous avons la grammaire suivante, et ses actions sémantiques associées:

$ S \ rightarrow id = expr $ {S.s = expr.size}

S $ \ rightarrow $ si expr alors S_1 $ $ $ $ autre S_2 {$ S_1.t = S.T + 2; $ $ S_2.t = S.T + 2; $ $ S.s = expr.size + S_1.size + S_2.size + 2; $}

S $ \ rightarrow $, tandis que expr do $ S_1 $ {$ S_1.t = S.T + 4; $ $ S.s = expr.size + S_1.s + 1; $}

S $ \ rightarrow $ $ S_1 $; $ S_2 $ {$ S_1.t = S_2.t = S.T; $ $ S.s = S_1.s + S_2.s; $}

Il est clair que la version non récurrente du Grammer est:

S $ \ rightarrow $ id = expr T

S $ \ rightarrow $ si expr alors S_1 $ $ $ else S_2 $ T

S $ \ rightarrow $, tandis que expr do $ S_1 $ T

T $ \ rightarrow $; $ S_2 $ T

T $ \ rightarrow $ $ \ epsilon $

Mais il faut aussi changer les actions sémantiques en conséquence. Toute idée comment cela peut être fait?

Answer 1

D'après ce que j'ai découvert, il n'y a pas de technique générale de modifier les actions sémantiques tout en retirant gauche récursivité. Au lieu de cela, la meilleure méthode est de prendre un exemple représentatif, dessiner son arbre d'analyse syntaxique, puis de vérifier quelles actions sémantiques nous donnent le même résultat que la grammaire précédente.

Answer 2

J'ai une solution partielle (je suis à la recherche d'ordre général). Si votre grammaire a aucune production epsilon, aucune nonterminals sont annulable. Cela signifie que l'algorithme pour éliminer la récursivité gauche passe par (si elle présente des productions epsilon).

Si vous ajoutez des actions sémantiques de la forme d'action (étiquette, nombre) qui reconnaissent la chaîne vide, et utiliser un changement / réduire l'analyseur, et d'examiner toutes les solutions de rechange **, il n'y a pas besoin du tout de réorganiser l'arbre d'analyse syntaxique. Lors de l'analyse, si un terminal est reconnu qu'il pousse un attribut dans la pile de l'analyseur, ceci est une action de transfert. Lorsqu'une action est rencontré, il apparaît N valeurs de la pile et pousse un noeud avec l'étiquette spécifiée et les valeurs extraites de la pile, à l'envers, comme des enfants. Ceci est la réduire action.

L'analyseur doit propager la position actuelle et la pile de l'analyseur, et les opérations de changement et réduire doit être fait avec des mises à jour fonctionnelles et non des mutations. Il est alors clair que de réarranger la grammaire ne change pas la séquence de changement et de réduire les actions, de sorte que l'arbre d'analyse syntaxique résultante est invariante par refactoring.

Cela signifie que si vous générez un AST plutôt qu'un arbre d'analyse syntaxique, vous devez vous référer aux attributs par numéro. La machine fonctionne parce que la pile de l'analyseur et la pile de contrôle sont découplés et refactoring ne change la pile de contrôle. La difficulté est que la grammaire doit être epsilon libre d'abord parce que les termes d'action Réduire sont eux-mêmes annulable.

** L'hypothèse toutes les alternatives sont examinées est fait pour que l'ordre d'examen est sans importance. Bien que refactorisations produisent l'équivalent grammaires, rien ne garantit automatiquement les arbres d'analyse qui en résultent seront les mêmes à moins que toutes les possibilités sont examinées. Dans ce cas, les restes de commande indéterminée, mais l'ensemble des résultats seront égaux.