J'ai mentionné la récurrence gauche comme une pierre d'achoppement à plusieurs reprises, et il est temps de le comprendre. Le problème principal est qu'un analyseur avec une descente récursive gauche se bloque instantanément en raison d'un débordement de pile.
Contenu de la série Python PEG Parser Considérez cette règle de grammaire hypothétique:
expr: expr '+' term | term
Si nous implémentions ce morceau de grammaire dans la méthode de l'analyseur récursif gauche, nous obtiendrions quelque chose comme ceci:
def expr(): if expr() and expect('+') and term(): return True if term(): return True return False
Ainsi, expr() commence par un appel à expr() , qui commence par un appel à expr() , qui commence par un appel ... Cela ne peut se terminer qu'avec un débordement de pile, exprimé comme une exception RecursionError .
La solution traditionnelle consiste à réécrire la grammaire. Dans les parties précédentes, c'est exactement ce que j'ai fait. En fait, la règle de grammaire ci-dessus peut être réécrite comme suit:
expr: term '+' expr | term
Cependant, à l'étape de la construction de l'arbre d'analyse, sa forme serait différente. Cela pourrait ruiner la situation si nous ajoutions l'opérateur '-' à la grammaire (puisque a - (b - c) pas identique à (a - b) - c ). Cela est généralement résolu avec des fonctions PEG plus puissantes, telles que le regroupement et l'itération, et nous pourrions réécrire la règle ci-dessus comme suit:
expr: term ('+' term)*
En fait, c'est exactement comme cela que la grammaire Python actuelle est écrite pour l'analyseur pgen (qui a les mêmes problèmes avec les règles récursives gauches).
Cependant, il y a un petit problème: puisque les opérateurs comme '+' et '-' (en Python) sont principalement binaires, lorsque nous analysons quelque chose comme a + b + c , nous devons passer par le résultat de l'analyse (qui essentiellement une liste de ['a', '+', 'b', '+', 'c'] ) pour créer un arbre d'analyse récursive à gauche (qui ressemblerait à quelque chose comme ceci [['a', '+', 'b'] , '+', 'c'] ).
La grammaire récursive gauche d'origine fait déjà allusion à l'associativité souhaitée, il serait donc bien de générer un analyseur directement à partir de ce formulaire. Et nous le pouvons! Un lecteur a souligné une bonne astuce avec une preuve mathématique facile à mettre en œuvre. Maintenant, je vais essayer d'expliquer.
Regardons un exemple d'entrée foo + bar + baz . L'arbre d'analyse que nous aimerions obtenir correspond à (foo + bar) + baz . Cela nécessite trois appels récursifs à gauche à la fonction expr() : l'un correspond à l'opérateur de niveau supérieur '+' (c'est-à-dire le second); un de plus - à l'opérateur interne '+' (c'est-à-dire le premier); et la troisième est le choix de la deuxième alternative (c'est- term dire le term ).
Comme je ne suis pas bon pour dessiner de vrais diagrammes à l'aide d'outils spéciaux, je vais le montrer ici en utilisant l'art ASCII:
expr------------+------+ | \ \ expr--+------+ '+' term | \ \ | expr '+' term | | | | term | | | | | 'foo' 'bar' 'baz'
L'idée est que dans la fonction expr() , nous avons besoin d'un «oracle» qui nous indique s'il faut choisir la première alternative (c'est-à-dire l'appel récursif à expr() ) ou la seconde (c'est-à-dire l'appel term() ). Au premier appel à expr() oracle devrait nous dire de suivre la première alternative ( expr() ); dans le deuxième appel (récursif) - de même, mais dans le troisième, il devrait nous inciter à appeler term() . Dans le code, cela ressemblera à ceci:
def expr(): if oracle() and expr() and expect('+') and term(): return True if term(): return True return False
Comment écrire un tel oracle? Voyons voir ... Nous pourrions essayer de suivre le nombre d'appels expr() récursive à gauche expr() dans la pile d'appels et de le comparer avec le nombre d'opérateurs '+' dans l'expression suivante. Si la pile d'appels est plus profonde que le nombre d'instructions, l'oracle doit retourner false (nous obliger à sélectionner term() ). J'ai hâte de l'implémenter avec sys._getframe() , mais il y a une meilleure façon: retournons la pile des appels!
L'idée est que nous commençons par un appel où l'oracle retourne faux, et enregistrons le résultat. Cela nous donne la séquence expr() -> term() -> 'foo' . (Il devrait retourner un arbre d'analyse pour le term initial, c'est-à-dire 'foo' . Le code ci-dessus renvoie juste True , mais dans la deuxième partie de la série d'articles, j'ai déjà montré comment retourner l'arbre d'analyse à la place.) Un tel oracle est facile à implémenter, car il devrait renvoyez simplement False lors du premier appel - aucune vérification de pile ou scrutation dans le futur n'est requise.
Ensuite, nous appelons à nouveau expr() , et cette fois l'oracle retourne True , mais au lieu de l'appel récursif gauche à expr() nous substituons le résultat enregistré de l'appel précédent. Et puisque l'opérateur attendu '+' et le prochain jeton approprié sont également présents, cela nous donnera un arbre d'analyse pour foo + bar .
Encore une fois, nous répétons l'algorithme, et tout se passe à nouveau: cette fois, nous obtenons un arbre d'analyse pour l'expression complète, et il est vraiment récursif à gauche ( (foo + bar) + baz ).
Ensuite, nous répétons l'algorithme à nouveau. Mais cette fois, bien que Oracle renvoie True et que le résultat enregistré de l'appel précédent soit également disponible, il n'y a plus '+' opérateur '+' et la première alternative échoue. Ainsi, nous essayons la deuxième option, qui réussit, et ne trouve que le terme initial ( 'foo' ). Ce résultat est pire que celui obtenu à partir de la première alternative, donc à ce stade, nous arrêtons et enregistrons l'analyse la plus longue (c'est-à-dire (foo + bar) + baz ).
Pour transformer cela en code de travail, j'ai d'abord modifié un peu l'algorithme pour combiner l'appel oracle() avec l'appel récursif gauche à expr() . Appelons-le oracle_expr() . Code:
def expr(): if oracle_expr() and expect('+') and term(): return True if term(): return True return False
Ensuite, nous allons écrire un wrapper qui implémente la logique décrite ci-dessus. Il utilise une variable globale (ne vous inquiétez pas, je m'en débarrasserai plus tard). La fonction oracle_expr() lira la variable globale et le wrapper la contrôlera:
saved_result = None def oracle_expr(): if saved_result is None: return False return saved_result def expr_wrapper(): global saved_result saved_result = None parsed_length = 0 while True: new_result = expr() if not new_result: break new_parsed_length = <calculate size of new_result> if new_parsed_length <= parsed_length: break saved_result = new_result parsed_length = new_parsed_length return saved_result
Le code, bien sûr, est terrible, mais au moins il transmet l'essence de l'algorithme. Remodelons-le pour que nous puissions en être fiers.
La compréhension la plus importante (qui m'appartient, bien que je ne sois probablement pas le premier à le remarquer) est que nous pouvons utiliser le cache de mémorisation au lieu d'une variable globale. Nous y stockons le résultat d'un appel à l'autre. Nous nous débarrassons donc d'une fonction distincte oracle_expr() , car nous pouvons générer un appel standard à expr() qu'il soit en position récursive à gauche ou à droite.
Nous avons donc besoin d'un décorateur @memoize_left_rec distinct, qui n'est utilisé que pour les règles récursives de gauche. Il appelle la fonction oracle_expr() , tirant la valeur stockée du cache de mémorisation, et contient une boucle qui appelle la fonction expr() plusieurs fois, jusqu'à ce que chaque nouveau résultat soit comparable à une partie des données d'entrée plus longue que la précédente. Et, bien sûr, puisque chaque position d'entrée et chaque méthode d'analyse sont mises en cache séparément, il ne se soucie pas du retour en arrière ou de quelques règles récursives (par exemple, dans la grammaire du jouet que j'ai utilisée, expr et term restent récursifs).
Un autre avantage du prototype que j'ai créé dans la troisième partie est qu'il permet de vérifier facilement si le nouveau résultat est plus long que l'ancien: la méthode mark() renvoie l'index dans le tableau des jetons d'entrée, nous pouvons donc simplement l'utiliser au lieu de parsed_length .
J'omets la preuve de la raison pour laquelle cet algorithme fonctionne toujours, quelle que soit la folie de la grammaire. En fait, je ne l'ai même pas lu. Je vois que cela fonctionne pour les cas simples, tels que expr dans ma grammaire des jouets, ainsi que pour les cas un peu plus complexes (par exemple, en utilisant la récursion gauche cachée derrière des éléments facultatifs dans une alternative, ou en utilisant la récursion mutuelle entre plusieurs règles). La situation la plus difficile dont je me souvienne dans la grammaire Python est toujours résolue par cet algorithme, donc je fais confiance au théorème et aux personnes qui l'ont prouvé.
Écrivons le code de bataille.
Premièrement, le générateur d'analyseur doit déterminer quelles règles restent récursives. Il s'agit d'un problème résolu en théorie des graphes. Je ne vais pas montrer l'algorithme ici, et en fait je veux même le simplifier encore plus. Je suppose que les seules règles de grammaire récursive à gauche sont directement récursives à gauche, comme expr dans notre grammaire des jouets. Ensuite, pour vérifier la récursivité gauche, il vous suffit de rechercher une alternative qui commencera par le nom de la règle actuelle:
def is_left_recursive(rule): for alt in rule.alts: if alt[0] == rule.name: return True return False
Maintenant, nous allons changer le générateur d'analyseur pour que pour les règles récursives à gauche, il génère un autre décorateur. Rappelons que dans la troisième partie, nous avons @memoize toutes les méthodes de l'analyseur dans @memoize . Maintenant, nous allons faire un petit changement dans le générateur, de sorte que pour les règles récursives à gauche, nous utilisons @memoize_left_rec , puis implémentons la magie dans le décorateur memoize_left_rec . Le reste du générateur et d'autres codes n'ont pas besoin d'être modifiés! (Même si je devais bricoler avec le code de visualisation)
Pour référence, voici à @memoize décorateur @memoize original, copié à partir de la partie 3. Souvenez-vous que self est une instance de Parser qui a un attribut memo (initialisé avec un dictionnaire vide) et les méthodes mark() et reset() qui obtiennent et définissent la position actuelle tokenizer:
def memoize(func): def memoize_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else: res = func(self, *args) endpos = self.mark() memo[key] = res, endpos return res return memoize_wrapper
Le décorateur @memoize souvient des appels précédents pour chaque position dans le flux d'entrée - pour chaque position dans le tableau (paresseux) de jetons d'entrée, il existe un dictionnaire de memo séparé. Les quatre premières lignes de memoize_wrapper dédiées à l'obtention du dictionnaire de memoize_wrapper correct.
Et voici @memoize_left_rec . Seule la branche else est légèrement différente de l'implémentation dans @memoize ci-dessus:
def memoize_left_rec(func): def memoize_left_rec_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else:
Il est probablement intéressant de voir comment cela fonctionne pour la méthode expr() . Voyons comment le code suivant s'exécutera:
@memoize_left_rec def expr(self): pos = self.mark() if ((expr := self.expr()) and self.expect('+') and (term := self.term())): return Node('expr', [expr, term]) self.reset(pos) if term := self.term(): return Node('term', [term]) self.reset(pos) return None
Sur l'exemple de l'analyse de foo + bar + baz .
Chaque fois que vous appelez la fonction expr() , l'appel est «accroché» par le décorateur qui recherche l'appel précédent à la position actuelle. Au premier appel, nous arrivons à la branche else , où nous appelons à plusieurs reprises la fonction décorée expr() . Évidemment, nous reviendrons d'abord au décorateur, mais cette fois, il y a déjà une certaine valeur dans le cache, donc la récursivité est interrompue.
Que se passe-t-il ensuite? La valeur de cache initiale est calculée sur cette ligne:
Cela conduit au fait que décor expr() renvoie None , après quoi le premier if dans expr() tombe (lorsque expr: = self.expr() ). Autrement dit, nous passons au deuxième if , qui reconnaît avec succès le term (dans notre exemple, 'foo' ) et expr renvoie une instance de Node . D'où revenons-nous? À la while dans le décorateur. Nous mettons à jour le cache de mémorisation avec un nouveau résultat (cette instance de Node ), puis exécutons l'itération suivante.
expr() est à nouveau appelée, et cette fois, l'appel récursif intercepté renvoie l'instance mise en cache de Node (term), puis passe à l'appel pour expect('+') . Tout est en ordre, puisque nous sommes désormais le premier opérateur '+' . Après cela, nous recherchons un terme qui réussit également (trouvé 'bar' ).
Alors maintenant expr() , ayant déjà reconnu foo + bar , retourne à la while , qui effectue les mêmes actions: il met à jour le cache de mémorisation avec un nouveau résultat (plus long) et commence l'itération suivante.
Ce jeu se répète à nouveau. Encore une fois, l'appel récursif intercepté expr() récupère un nouveau résultat (cette fois foo + bar ) du cache, et nous nous attendons à voir un autre '+' (deuxième) et un autre term ( 'baz' ). Nous créons un Node représentant (foo + bar) + baz , et le renvoyons à la while , qui le place dans le cache et le répète à nouveau.
Mais maintenant, nous allons suivre une autre branche de l'algorithme. Nous nous attendons à rencontrer un autre '+' , mais ne le trouvons pas! Ainsi, cet appel à expr() retourne à sa deuxième alternative et retourne uniquement term . Lorsque cela apparaît avant la while , il s'avère que ce résultat est plus court que le dernier. Ainsi, il interrompt et renvoie un résultat plus long ( (foo + bar) + baz ) à celui qui a initié l'appel expr() (par exemple, l'appel de la statement() n'est pas affiché ici).
Donc, c'est là que l'histoire d'aujourd'hui se termine: nous avons réussi à implémenter la récursion gauche dans un analyseur PEG. La semaine prochaine, je prévois de discuter de l'ajout d '«actions» à la grammaire, ce qui nous permettra de personnaliser le résultat renvoyé par la méthode de l'analyseur pour cette alternative (au lieu de toujours renvoyer une instance de Node ).
Si vous souhaitez jouer avec le code, consultez le référentiel GitHub . (J'ai également ajouté un code de visualisation pour la récursion gauche, mais je ne suis pas tout à fait satisfait, donc je ne fournirai pas de lien ici.)
Licence pour cet article et code cité: CC BY-NC-SA 4.0