Retrait Recursion gauche de hors-contexte Grammars - Commande de nonterminals

Question

J'ai récemment mis en œuvre l'algorithme du Paull pour enlever récursivité à gauche de grammaires contexte:

  

Attribuer un ordre $ \ A_1, points, A_n $ aux non-terminaux de la grammaire.

     

pour $ i: = 1 $ pour faire $ n $ commencer
  $ \ Quad $ pour $ j: = 1 $ à i-1 $ ne commence
  $ \ Quad \ quad $ pour chaque production de la forme $ A_i \ à A_j \ alpha $ ne commencent
  $ \ Quad \ quad \ quad $ supprimer A_i $ \ pour A_j \ alpha $ de la grammaire
  $ \ Quad \ quad \ quad $ pour chaque production de la forme $ A_j \ à \ beta $ ne commencent
  $ \ Quad \ quad \ quad \ quad $ ajouter $ A_i \ to \ beta \ alpha $ à la grammaire
  $ \ Quad \ quad \ quad fin $
  $ \ Quad \ quad $ end
  $ \ Quad $ end
  $ \ Quad $ transformer le A_i $ $ -Productions pour éliminer
récursive gauche directe   fin

Selon ce document , l'efficacité de l'algorithme dépend essentiellement de l'ordre des nonterminals choisis au début; le document examine cette question en détail et de suggérer OPTIMISATIONS.

Quelques notations:

  

Nous dirons qu'un symbole $ X $ est un coin gauche directement de   un non-terminal $ A $, en cas d'un -production $ $ avec $ X $ comme le symbole le plus à gauche sur la droite. Nous définissons relation coin gauche pour être réflexif fermeture transitive de la relation coin directe à gauche, et on définit la relation coin correcte gauche pour être transitif fermeture de   la relation directe coin gauche. Un non-terminal est récursif gauche si elle est un coin approprié gauche de lui-même; un non-terminal est directement gauchement récursive si elle est un coin gauche direct de lui-même; et un non-terminal est indirectement à gauche récursive si elle est récursive gauche, mais pas récursive directement à gauche.

Voici ce que les auteurs proposent:

  

Dans la boucle interne de l'algorithme de Paull, pour nonterminals $ A_i $ et $ A_j $, de sorte que $ i> j $ et $ A_j $ est un coin gauche direct de $ A_i $, nous remplaçons toutes les occurrences de $ A_j $ comme un coin gauche direct de $ A_i $ avec toutes les extensions possibles de $ A_j $.

     

Cela ne contribue à l'élimination de la récursivité gauche de la grammaire si $ A_i $ est un non-terminal récursif gauche, et $ A_j $ se trouve sur un chemin qui fait A_i $ $ récursif gauche; qui est, si $ A_i $ est un coin gauche de $ A_j $ (en plus d'être un coin gauche de $ A_i $ $ A_j $).

     

Nous pourrions éliminer les remplacements qui sont inutiles pour enlever récursivité gauche si nous pouvions commander les nonterminals de la grammaire de sorte que, si $ i> j $ et $ A_j $ est un coin gauche direct de $ A_i $, puis $ A_i $ est également un coin gauche de $ A_j $.

     

Nous pouvons atteindre cet objectif en commandant les nonterminals dans l'ordre décroissant du nombre de coins différents de gauche qu'ils ont.

     

Depuis la relation coin gauche est transitive, si C est un coin gauche direct de B, chaque coin gauche de C est également un coin gauche de B.

     

En outre, étant donné que nous avons défini la relation coin gauche à être réfléchi, B est un coin gauche de lui-même.

     

Par conséquent, si C est un coin gauche direct de B, il doit suivre B dans l'ordre décroissant du nombre de coins distincts gauche, à moins que B est un coin gauche de C.

Tout ce que je veux, c'est de savoir comment commander les nonterminals au début, mais je ne comprends pas du papier. Quelqu'un peut-il expliquer d'une manière plus simple? Pseudocode me aider à mieux le comprendre.

Answer 1

Ceci est en fait pas très compliqué. Je suppose que les productions epsilon ont déjà été éliminés de la langue, parce que cela n'obscurcir le concept clé de « coin gauche ».

Formez un graphe G où les sommets sont tous les non-terminaux de la grammaire. Maintenant tirer un bord dirigé de A à B, s'il y a une règle de production qui ressemble à « A -> B [...] ». Les appels papier B un « coin gauche direct » de A. De manière plus générale, d'autres non-terminal C est appelé un « coin gauche » de A s'il y a un chemin de A à C le long des arêtes de ce graphe. Cela peut se faire en calculant la transitive fermeture de G, appeler H.

Le document suggère de commander les sommets en comptant le nombre de virages à gauche de chaque sommet A a (combien d'autres non-terminaux, vous pouvez atteindre de A, ou en degrés de A dans le graphique H), puis de tri dans l'ordre décroissant par ce nombre.

Une motivation handwavy de cette politique est que s'il y a un important non-terminal (dire le symbole de départ S) avec des connexions à beaucoup d'autres symboles), alors il est logique de purge tôt gauche récursion de S, parce que si vous le laissez à plus tard il y aura plus de copies de S que vous devez développer sur. Je pense que l'explication dans le document est plus convaincant, mais peut-être moins évident.