Les analyseurs sont des programmes qui aident à traiter le texte. Les compilateurs et les interpréteurs utilisent des analyseurs pour analyser les programmes avant de les traiter davantage, et des analyseurs pour des formats tels que JSON et YAML traitent le texte dans les structures de données natives du langage de programmation.
Dans cet article, nous allons voir comment construire des « analyseurs de descente récursive ». Les analyseurs de descente récursive sont un moyen simple mais puissant de créer des analyseurs - pour chaque "entité" du texte que vous souhaitez traiter, vous définissez une fonction.
Tout d'abord, nous allons examiner une partie de la théorie sous-jacente à l'analyse syntaxique. Ensuite, en utilisant Python, nous allons construire une calculatrice et un analyseur JSON qui prend en charge les commentaires, les virgules de fin et les chaînes sans guillemets. Enfin, nous allons discuter de la manière dont vous pouvez créer des analyseurs pour d'autres types de langages qui se comportent différemment des exemples susmentionnés.
Si vous connaissez déjà la théorie, vous pouvez passer directement aux parties où nous construisons l'analyseur.
Contenu
- 1 Comment fonctionne l'analyse ?
- 2 Rédiger des règles de production
- 3 points à prendre en compte lors de la création d'analyseurs
- 3.1 Gestion de la priorité dans les grammaires
- 3.2 Éviter la récursivité à gauche
- 3.3 Éviter les retours en arrière
- 4 Construire une base pour l'analyseur de descente récursive en Python
- 4.1 La classe d'exception
- 4.2 La classe Parser de base
- 4.3 Traitement des plages de caractères
- 4.4 Extraction de caractères du texte
- 4.5 Extraction de mots-clés et de symboles
- 4.6 Une aide pour faire correspondre plusieurs productions
- 4.7 Prévision de la suite :fonctions d'assistance
- 5 Premier exemple d'analyseur :une calculatrice
- 5.1 Règles de production de la grammaire de la calculatrice
- 5.2 Implémentation de l'analyseur
- 5.3 Reconnaître les nombres
- 5.4 Une interface pour notre analyseur
- 6 Deuxième exemple d'analyseur :un analyseur JSON "étendu"
- 6.1 Règles de production de la grammaire JSON
- 6.2 Implémenter l'analyseur et traiter les commentaires
- 6.3 Analyser des listes et des cartes
- 6.4 Reconnaître les valeurs nulles et booléennes
- 6.5 Reconnaître les chaînes et les nombres sans guillemets
- 6.6 Reconnaître les chaînes entre guillemets
- 6.7 Une interface pour notre analyseur JSON
- 7 Création d'autres types d'analyseurs
- 7.1 Langages sensibles aux espaces
- 7.2 Indentation basée sur les espaces
Comment fonctionne l'analyse ?
Afin de traiter un morceau de texte, un programme effectue trois tâches. Dans un processus appelé "lexing" ou "tokenization", le programme parcourt les caractères du texte et extrait des groupes logiques appelés "tokens". Par exemple, dans une expression telle que "3 + 5 - 10", un programme de traitement d'expressions arithmétiques pourrait extraire les jetons suivants :
[{ "Type": "Number" , "Text": "3" },
{ "Type": "Operator", "Text": "+" },
{ "Type": "Number" , "Text": "5" },
{ "Type": "Operator", "Text": "-" },
{ "Type": "Number" , "Text": "10" }] Le programme utilise ensuite des règles pour identifier des séquences significatives de jetons, et cela s'appelle "l'analyse". Les règles utilisées pour y parvenir sont appelées "grammaires" - de la même manière que les mots d'une langue naturelle comme l'anglais sont enchaînés en séquences significatives à l'aide de la grammaire anglaise. Les règles individuelles d'une grammaire sont appelées "productions".
Imaginez que nous construisions un programme pour traiter des expressions mathématiques et que nous ne nous intéressions qu'à l'addition et à la soustraction. Une expression doit comporter un nombre (tel que "3"), suivi d'un nombre quelconque d'opérateurs et de nombres (tel que "+ 5" ). La règle d'analyse peut être visualisée comme suit :
Le indique que le groupe peut répéter n'importe quel nombre de fois (y compris zéro).
Enfin, le programme prend un ensemble d'actions pour une règle de grammaire. Par exemple, après l'analyse, notre programme mathématique aurait besoin de calculer la valeur de l'expression.
Bien que nous ayons décrit ces étapes comme des étapes distinctes, un programme peut effectuer tout cela en même temps. Faire toutes les étapes en même temps comporte quelques avantages, et c'est l'approche que nous allons adopter dans cet article.
Rédaction des règles de production
Dans la suite de cet article, nous allons utiliser des règles de production pour visualiser les grammaires. Par conséquent, nous avons expliqué comment nous écrivons les règles de production tout au long de cet article. Si vous avez déjà parcouru un manuel sur l'analyse syntaxique, la notation que nous avons utilisée ici est un peu différente.
Plus tôt, nous avons vu un exemple de production simple. Lorsque la règle de grammaire contient le nom d'un jeton et que le jeton est assez simple, il est courant d'écrire le texte du jeton dans la grammaire. Si l'on considère l'exemple précédent, donne un + ou un - , afin que nous puissions réécrire la règle comme suit :
Nous avons également vu comment nous pouvons utiliser pour indiquer que quelque chose se répète un certain nombre de fois. De même, a indique que quelque chose se répète, mais cela devrait se produire au moins une fois. A indique quelque chose qui est facultatif.
Par exemple, supposons que nous construisions un analyseur pour traiter une liste de conditions, comme "x> 10 et y> 30". Supposons que le and est facultatif, nous pourrions donc réécrire cette condition sous la forme « x> 10 y> 30 ». Vous pourriez concevoir une grammaire pour ce qui précède comme suit :
Lorsqu'il y a plusieurs alternatives, l'ordre des alternatives est important. Pour une règle comme , nous devrions d'abord essayer de faire correspondre un "+", puis un "-". Bien que dans cet exemple trivial, il puisse sembler que l'ordre n'a pas d'importance, nous verrons plus tard des exemples où l'ordre devient important.
Enfin, une règle de production se concentre uniquement sur les jetons et autres symboles de grammaire :elle ignore les espaces et les commentaires.
Considérations lors de la création d'analyseurs
Auparavant, nous avons vu quelques grammaires simples. Cependant, lorsque vous essayez d'analyser quelque chose de plus complexe, un certain nombre de problèmes peuvent survenir. Nous allons en discuter ici.
Gérer la priorité dans les grammaires
Auparavant, nous avons vu une grammaire capable de gérer une expression mathématique composée d'additions et de soustractions. Malheureusement, vous ne pouvez pas étendre la même grammaire pour les multiplications (et les divisions), car ces opérations ont une priorité plus élevée que les additions (et les soustractions).
Afin de gérer ce scénario, nous devons concevoir notre grammaire de sorte que l'analyseur différe tout ajout, mais effectue des multiplications dès qu'il est rencontré. Pour ce faire, nous avons divisé la grammaire en deux règles distinctes, comme indiqué ci-dessous :
Prenons une expression (telle que "3 + 2 * 5") pour nous assurer que cela fonctionne vraiment. Nous supposerons qu'une fois que notre analyseur a fini de correspondre à une règle de grammaire, il calcule automatiquement l'expression. Nous utiliserons également du texte souligné pour indiquer ce que l'analyseur recherche. De plus, nous avons également omis les guillemets pour plus de clarté.
Quand 2 * 5 est analysé, l'analyseur renvoie immédiatement le résultat de 10. Ce résultat est reçu à l'étape et l'addition est effectuée à la fin, donnant 13 comme résultat.
En résumé, vous devez organiser vos règles de sorte que les opérateurs avec la priorité la plus faible soient en haut, tandis que ceux avec la priorité la plus élevée soient en bas.
Éviter la récursivité à gauche
Plus tôt, nous avons mentionné qu'un analyseur de descente récursive se compose de fonctions qui traitent les « entités » dans le texte. Maintenant que nous connaissons les jetons et les règles de production, redéfinissons cela un peu plus formellement :chaque fonction de l'analyseur extrait un jeton ou implémente la logique d'une règle de production.
Prenons une grammaire simple, de manière à voir ce que cela signifie réellement. Si vous écriviez le pseudocode de cette grammaire, il ressemblerait à ceci :
def expression():
first_number = number()
read('+')
second_number = number()
# process these two numbers, e.g. adding them
Ensuite, considérons une grammaire qui analyse une liste de nombres séparés par des virgules. Vous l'écririez généralement comme suit :
Maintenant, imaginez que pour une raison quelconque, vous souhaitiez éviter le caractère générique et le réécrire comme suit :
Cette grammaire est théoriquement correcte - soit elle sélectionne un seul numéro dans le texte, soit elle se développe en une liste avec un numéro à la fin. La deuxième liste, à son tour, peut s'étendre à un autre nombre ou à une liste, jusqu'à ce que l'analyseur finisse par parcourir le texte.
Cependant, il y a un problème avec cette approche - vous entreriez dans une récursivité infinie ! Si vous essayez d'appeler le list() fonction une fois, vous finissez par l'appeler à nouveau, et ainsi de suite. Vous pourriez penser que réécrire la grammaire pourrait aider. Cependant, si vous essayez d'écrire une fonction, vous lirez un seul nombre et quitterez l'analyse. Le nombre que vous lisez peut faire partie d'une liste comme "2, 4, 6" et vous ne pourrez pas lire les autres nombres.
Lorsqu'il s'agit d'analyse syntaxique, cela s'appelle la récursivité à gauche. Le cas que nous avons vu ci-dessus implique la "récursion gauche directe", mais il y a aussi la "récursion gauche indirecte", où A appelle B, B appelle A et ainsi de suite. Dans les deux cas, vous devez réécrire la grammaire d'une autre manière pour éviter ce problème.
Éviter les retours en arrière
Supposons que vous essayez de construire un analyseur qui analyse une opération de deux nombres, comme "2 + 4", et que vous écriviez une grammaire de cette manière :
Cette grammaire est correcte, et elle se comportera également de la manière attendue et produira des résultats corrects. Cependant, cette grammaire n'est pas ce que vous voudriez utiliser.
Pour voir pourquoi c'est le cas, considérons la chaîne d'entrée "5 - 2". Nous allons d'abord utiliser la règle d'addition et analyser un nombre. Ensuite, nous nous attendrions à un "+" mais lors de la lecture de la chaîne, nous obtiendrons un "-", ce qui signifie que nous devons revenir en arrière et appliquer la règle de soustraction. Ce faisant, nous avons perdu du temps et des cycles CPU à analyser un nombre, pour le supprimer et l'analyser à nouveau dans le cadre de la règle de soustraction.
De plus, lors de la création d'analyseurs qui fonctionnent directement à partir de flux de données, comme un socket réseau, le rembobinage du flux n'est souvent pas une option. Dans cet article, nous ne traiterons que des parseurs qui ont tout le texte en mémoire. Néanmoins, c'est une bonne pratique pour éviter de revenir en arrière et pour ce faire, vous devez factoriser les parties communes à partir de la gauche. Voici à quoi ressemblerait notre règle après l'affacturage :
L'étape de factorisation est terminée et évitera les retours en arrière. Cependant, pour des raisons esthétiques, nous l'écrirons simplement comme :
Construire une base pour l'analyseur de descente récursive en Python
Maintenant que nous avons discuté des diverses considérations pour l'analyse, nous allons construire la calculatrice et l'analyseur JSON. Cependant, avant de faire cela, nous allons écrire une classe "Parser" de base qui a quelques méthodes pour les fonctions courantes, telles que la reconnaissance des caractères et la gestion des erreurs.
Cette section peut sembler un peu trop longue, mais elle vaut bien la patience. Une fois cette section terminée, vous disposerez de tous les outils nécessaires pour créer des analyseurs complexes avec très peu de code requis pour reconnaître les jetons et mettre en œuvre des règles de production.
La classe d'exception
Comme il s'agit de loin de la tâche la plus facile, nous allons donc nous y attaquer en premier. Nous allons définir notre propre classe d'exception nommée ParseError comme ça :
class ParseError(Exception):
def __init__(self, pos, msg, *args):
self.pos = pos
self.msg = msg
self.args = args
def __str__(self):
return '%s at position %s' % (self.msg % self.args, self.pos)
La classe accepte la position du texte où l'erreur s'est produite, un message d'erreur (sous forme de chaîne de format) et les arguments de la chaîne de format. Voyons comment vous pourriez utiliser ce type d'exception :
e = ParseError(13, 'Expected "{" but found "%s"', "[") Lorsque vous essayez d'imprimer l'exception, vous obtenez un message formaté comme celui-ci :
Expected "{" but found "[" at position 13
Notez que nous n'avons pas utilisé de % symbole dans la chaîne de format et ses arguments (tels que '"Expected "{" but found "%s"' % "[" ). Ceci est géré dans le __str__ méthode de la classe, où nous avons formaté self.msg avec des éléments en self.pos .
Maintenant, vous pourriez demander, pourquoi voulons-nous le formater dans le __str__ méthode, au lieu de l'écrire avec un % ? Il s'avère qu'en utilisant le % l'opérateur pour formater une chaîne prend un peu de temps. Lors de l'analyse d'une chaîne, de nombreuses exceptions seront générées lorsque l'analyseur tentera d'appliquer diverses règles. Par conséquent, nous avons reporté la mise en forme de la chaîne au moment où elle est vraiment nécessaire.
La classe Parser de base
Maintenant que nous avons une classe d'erreur en place, l'étape suivante consiste à écrire la classe d'analyseur. Nous allons le définir comme suit :
class Parser:
def __init__(self):
self.cache = {}
def parse(self, text):
self.text = text
self.pos = -1
self.len = len(text) - 1
rv = self.start()
self.assert_end()
return rv
Ici, vous remarquerez un cache membre dans le __init__ méthode - nous reviendrons sur la raison pour laquelle cela est nécessaire lorsque nous discuterons de la reconnaissance des caractères.
Le parse La méthode est assez simple - d'abord, elle stocke la chaîne. Comme nous n'avons encore scanné aucune partie de la chaîne, nous allons définir la position sur -1. De plus, nous stockerons l'index maximum de la chaîne dans self.len . (L'index maximum est toujours un de moins que la longueur de la chaîne.)
Ensuite, nous allons commencer à analyser la chaîne et vérifier si nous avons atteint la fin de la chaîne. Cela permet de s'assurer que notre analyseur a pu traiter l'intégralité du texte sans rien laisser à la fin. Après cela, nous renvoyons le résultat.
Le assert_end méthode est simple :nous allons vérifier si la position actuelle est inférieure à l'index maximum. Gardez à l'esprit que ces méthodes sont à l'intérieur de la classe, bien que nous ayons omis l'indentation pour plus de simplicité.
def assert_end(self):
if self.pos < self.len:
raise ParseError(
self.pos + 1,
'Expected end of string but got %s',
self.text[self.pos + 1]
)
Tout au long de notre analyseur, nous examinerons le caractère qui est un de plus que l'index actuel (self.pos ). Pour voir pourquoi c'est le cas, considérons que nous commençons avec self.pos = -1 , donc nous regarderions l'index 0. Une fois que nous aurons reconnu un caractère avec succès, self.pos passe à 0 et nous regardons le caractère à l'index 1, et ainsi de suite. C'est pourquoi l'erreur utilise self.pos + 1 .
Avec la plupart des langages, les espaces entre les jetons peuvent être supprimés en toute sécurité. Par conséquent, il semble logique d'inclure une méthode qui vérifie si le caractère suivant est un caractère d'espacement, et si c'est le cas, le "supprime" en avançant à la position suivante.
def eat_whitespace(self):
while self.pos < self.len and self.text[self.pos + 1] in " fvrtn":
self.pos += 1
Traitement des plages de caractères
Maintenant, nous allons écrire une fonction pour nous aider à reconnaître les caractères dans le texte. Avant de faire cela, nous allons considérer notre fonction du point de vue de l'utilisateur - nous lui donnerons un ensemble de caractères à faire correspondre à partir du texte. Par exemple, si vous vouliez reconnaître un alphabet ou un trait de soulignement, vous pourriez écrire quelque chose comme :
self.char('A-Za-z_')
Nous donnerons le char méthode contenant une liste de caractères ou de plages (comme A-Z dans l'exemple ci-dessus). Les plages sont indiquées par deux caractères séparés par un - . Le premier caractère a une valeur numériquement inférieure à celle de droite.
Maintenant, si le caractère à self.text[self.pos + 1] correspond à quelque chose dans l'argument de self.char , nous le rendrons. Sinon, nous déclencherons une exception.
En interne, nous traiterons la chaîne en quelque chose de plus facile à gérer :une liste avec des caractères ou des plages séparés tels que ['A-Z', 'a-z', '_'] . Nous allons donc écrire une fonction pour diviser les plages :
def split_char_ranges(self, chars):
try:
return self.cache[chars]
except KeyError:
pass
rv = []
index = 0
length = len(chars)
while index < length:
if index + 2 < length and chars[index + 1] == '-':
if chars[index] >= chars[index + 2]:
raise ValueError('Bad character range')
rv.append(chars[index:index + 3])
index += 3
else:
rv.append(chars[index])
index += 1
self.cache[chars] = rv
return rv
Ici, nous parcourons le chars chaîne, recherche d'un - suivi d'un autre caractère. Si cette condition correspond et que le premier caractère est plus petit que le dernier, nous ajoutons toute la plage (comme A-Z ) à la liste rv . Sinon, on ajoute le caractère à chars[index] à rv .
Ensuite, on ajoute la liste en rv dans le cache. Si nous voyons cette chaîne une deuxième fois, nous la renverrons du cache en utilisant le try ... except KeyError: ... bloc en haut.
Certes, nous aurions pu fournir une liste du type ['A-Z', 'a-z', '_'] au char méthode. Cependant, à notre avis, le faire de cette manière appelle le char() regarde un peu plus propre.
Extraire des caractères du texte
Maintenant que nous avons une méthode qui donne une liste contenant des plages et des caractères, nous pouvons écrire notre fonction pour extraire un caractère du texte. Voici le code pour le char méthode :
def char(self, chars=None):
if self.pos >= self.len:
raise ParseError(
self.pos + 1,
'Expected %s but got end of string',
'character' if chars is None else '[%s]' % chars
)
next_char = self.text[self.pos + 1]
if chars == None:
self.pos += 1
return next_char
for char_range in self.split_char_ranges(chars):
if len(char_range) == 1:
if next_char == char_range:
self.pos += 1
return next_char
elif char_range[0] <= next_char <= char_range[2]:
self.pos += 1
return next_char
raise ParseError(
self.pos + 1,
'Expected %s but got %s',
'character' if chars is None else '[%s]' % chars,
next_char
)
Concentrons-nous d'abord sur l'argument chars=None . Cela vous permet d'appeler le self.char() sans lui donner un jeu de caractères. Ceci est utile lorsque vous souhaitez simplement extraire un caractère sans le restreindre à un ensemble spécifique. Sinon, vous pouvez l'appeler avec une plage de caractères, comme nous l'avons vu dans la section précédente.
Cette fonction est assez simple - d'abord, nous vérifions si nous n'avons plus de texte. Ensuite, nous choisissons le caractère suivant et vérifions si chars est None , auquel cas nous pouvons incrémenter la position et renvoyer le caractère immédiatement.
Cependant, s'il y a un ensemble de caractères dans chars , nous le divisons en une liste de caractères et de plages individuels, tels que ['A-Z', 'a-z', '_'] . Dans cette liste, une chaîne de longueur 1 est un caractère et tout le reste est une plage. Il vérifie si le caractère suivant correspond au caractère ou à la plage, et si c'est le cas, nous le renvoyons. Si nous ne parvenons pas à le faire correspondre à quoi que ce soit, il quitte la boucle qui lève ParseError , indiquant que nous n'avons pas pu obtenir le caractère attendu.
Le 'character' if chars is None else '[%s]' % chars est juste un moyen de fournir une exception plus lisible. Si chars est None , le message de l'exception indiquerait Expected character but got ... , mais si char a été défini sur quelque chose comme A-Za-z_ , nous obtiendrions Expected [A-Za-z_] but got ... .
Plus tard, nous verrons comment utiliser cette fonction pour reconnaître les tokens.
Extraire des mots-clés et des symboles
Outre l'extraction de caractères individuels, la reconnaissance des mots-clés est une tâche courante lors de la construction d'un analyseur. Nous utilisons des "mots-clés" pour faire référence à toute chaîne contiguë qui est sa "propre entité", et peut avoir des espaces blancs avant et après. Par exemple, en JSON { peut être un mot-clé, et dans un langage de programmation if , else peut être un mot-clé, etc.
Voici le code de reconnaissance des mots-clés :
def keyword(self, *keywords):
self.eat_whitespace()
if self.pos >= self.len:
raise ParseError(
self.pos + 1,
'Expected %s but got end of string',
','.join(keywords)
)
for keyword in keywords:
low = self.pos + 1
high = low + len(keyword)
if self.text[low:high] == keyword:
self.pos += len(keyword)
self.eat_whitespace()
return keyword
raise ParseError(
self.pos + 1,
'Expected %s but got %s',
','.join(keywords),
self.text[self.pos + 1],
)
Cette méthode prend des mots-clés, tels que self.keyword('if', 'and', 'or') . La méthode supprime les espaces blancs, puis vérifie si nous n'avons plus de texte à analyser. Il parcourt ensuite chaque mot-clé, vérifiant si le mot-clé existe dans le texte. S'il trouve quelque chose, nous supprimerons l'espace blanc après le mot-clé, puis renverrons le mot-clé.
Cependant, s'il ne trouve rien, il sort de la boucle qui lève ParseError , indiquant que les mots clés sont introuvables.
Une aide pour faire correspondre plusieurs productions
Dans les sections précédentes, vous avez remarqué que nous utilisons des exceptions pour signaler les erreurs. Nous savons également que pour écrire un analyseur de descente récursive, vous écrivez des fonctions qui reconnaissent un jeton ou une règle de production. Maintenant, imaginez que vous vouliez analyser un texte simple, où vous attendez un nombre ou un mot. La règle de production pourrait ressembler à :
Nous supposerons également que le texte contient un mot. Lorsque l'analyseur essaie de rechercher un chiffre (peut-être en utilisant char() ), il ne le trouvera pas, ce qui l'amène à lever une exception. De plus, vous devez supprimer les espaces blancs avant et après la mise en correspondance d'une règle de production. Donc, le code pour item() pourrait ressembler à ceci :
def item(self): self.eat_whitespace() try: rv = self.number() except ParseError: rv = self.word() self.eat_whitespace() return rv
Cela ressemble déjà beaucoup à mettre en place une règle simple ! Imaginez ce que ce serait d'implémenter une règle complexe - vous devriez utiliser try...except des blocs partout.
Donc, nous allons écrire un match() fonction qui supprimera les espaces et essaiera de faire correspondre plusieurs règles. La fonction est la suivante :
def match(self, *rules):
self.eat_whitespace()
last_error_pos = -1
last_exception = None
last_error_rules = []
for rule in rules:
initial_pos = self.pos
try:
rv = getattr(self, rule)()
self.eat_whitespace()
return rv
except ParseError as e:
self.pos = initial_pos
if e.pos > last_error_pos:
last_exception = e
last_error_pos = e.pos
last_error_rules.clear()
last_error_rules.append(rule)
elif e.pos == last_error_pos:
last_error_rules.append(rule)
if len(last_error_rules) == 1:
raise last_exception
else:
raise ParseError(
last_error_pos,
'Expected %s but got %s',
','.join(last_error_rules),
self.text[last_error_pos]
)
Avant de discuter de son fonctionnement, voyons à quel point il est simple de réécrire notre exemple précédent en utilisant match() :
def item(self):
return self.match('number', 'word')
Alors, comment ça marche ? match() prend un nom de méthode à exécuter (comme number ou word dans l'exemple ci-dessus). Tout d'abord, il se débarrasse de l'espace au début. Ensuite, il itère sur tous les noms de méthodes et récupère chaque méthode en utilisant son nom via getattr() . Il essaie ensuite d'invoquer la méthode, et si tout se passe bien, il supprimera également les espaces après le texte. Enfin, il renvoie la valeur qu'il a reçue en appelant la méthode
Cependant, s'il y a une erreur, il réinitialise self.pos à la valeur qui était là avant d'essayer de faire correspondre une règle. Ensuite, il essaie de sélectionner un bon message d'erreur en utilisant les règles suivantes :
- Lorsque plusieurs règles correspondent, beaucoup d'entre elles peuvent générer une erreur. L'erreur qui a été générée après l'analyse de la majeure partie du texte est probablement le message d'erreur que nous souhaitons.
Pour voir pourquoi c'est le cas, considérez la chaîne "abc1". Essayer d'appeler le number() échouerait à la position 0, alors que word() échouerait à la position 2. En regardant la chaîne, il est fort probable que l'utilisateur ait voulu saisir un mot, mais qu'il ait fait une faute de frappe.
- Si deux règles erronées ou plus aboutissent à une "égalité", nous préférons informer l'utilisateur de toutes les règles qui ont échoué.
Le last_error_pos et last_exception conserve la trace de la position et de l'exception de la dernière erreur respectivement. De plus, nous maintenons une liste last_error_rules afin qu'en cas d'égalité, nous puissions informer l'utilisateur de toutes les règles que nous avons essayé de respecter.
Dans le except ParseError bloc, nous comparons la position de la dernière erreur et l'erreur actuelle. Si l'erreur actuelle est égale, nous la considérons comme une égalité et l'ajoutons à la liste. Sinon, nous mettons à jour la position de l'erreur, l'exception et la liste des règles erronées.
À la fin, nous vérifions combien de règles ont échoué. S'il n'y en a qu'un, last_exception aurait le meilleur message d'erreur. Sinon, c'est une égalité, et nous le ferons savoir à l'utilisateur avec un message comme Expected number,word but found ... .
Prévision de la suite :fonctions d'assistance
À ce stade, nous avons toutes les choses nécessaires dans notre analyseur, et tous les échecs génèrent des exceptions. Cependant, nous souhaitons parfois ne faire correspondre un caractère, un mot-clé ou une règle que s'il existe, sans l'inconvénient de gérer les exceptions.
Nous allons présenter trois petites aides pour faire exactement cela. Dans le cas d'une exception lors de la recherche d'éléments, ceux-ci renverront None :
def maybe_char(self, chars=None):
try:
return self.char(chars)
except ParseError:
return None
def maybe_match(self, *rules):
try:
return self.match(*rules)
except ParseError:
return None
def maybe_keyword(self, *keywords):
try:
return self.keyword(*keywords)
except ParseError:
return None
L'utilisation de ces fonctions est facile. Voici comment vous pouvez les utiliser :
operator = self.maybe_keyword('+', '-'):
if operator == '+':
# add two numbers
elif operator == '-':
# subtract two numbers
else: # operator is None
# do something else
Premier exemple d'analyseur :une calculatrice
Maintenant que nous avons construit les bases pour écrire un analyseur, nous allons construire notre premier analyseur. Il sera capable d'analyser des expressions mathématiques avec des additions, des soustractions, des multiplications, des divisions, et également de gérer des expressions entre parenthèses comme "(2 + 3) * 5".
Nous allons commencer par visualiser la grammaire sous forme de règles de production.
Règles de production pour la grammaire de la calculatrice
Nous avons vu précédemment une grammaire pour tout gérer sauf les expressions entre parenthèses :
Maintenant, réfléchissons à la façon dont les expressions entre parenthèses s'intègrent dans cette grammaire. Lors de l'évaluation de "(2 + 3) * 5", nous devrions calculer "(2 + 3)" et le réduire à un nombre. Ce qui signifie que dans la grammaire ci-dessus, le terme "Nombre" peut faire référence soit à une expression entre parenthèses, soit à quelque chose qui est en réalité un nombre, comme "5".
Nous allons donc modifier nos règles pour tenir compte des deux. Dans la règle pour "Terme", nous remplacerons "Nombre" par un terme plus approprié comme "Facteur". « Facteur » peut alors faire référence soit à une expression entre parenthèses, soit à un « nombre ». La grammaire modifiée ressemble à ceci :
Cela dit, appliquons les règles de production !
Mise en œuvre de l'analyseur
Nous allons implémenter notre analyseur Calculator en étendant la classe Parser de base. Nous commençons à définir la classe comme suit :
class CalcParser(Parser):
def start(self):
return self.expression()
Auparavant, lors de l'implémentation de la classe d'analyseur de base, nous avions un start() méthode pour démarrer l'analyse. Nous appellerons simplement le expression() méthode ici, que nous définirons comme ci-dessous :
def expression(self):
rv = self.match('term')
while True:
op = self.maybe_keyword('+', '-')
if op is None:
break
term = self.match('term')
if op == '+':
rv += term
else:
rv -= term
return rv
La règle de grammaire pour . Donc, nous commençons par lire un terme du texte. On met alors en place une boucle infinie, et on cherche un « + » ou un « - ». Si nous ne trouvons ni l'un ni l'autre, cela signifie que nous avons fini de lire la liste des termes supplémentaires donnée par , afin que nous puissions sortir de la boucle.
Sinon, nous lisons un autre terme du texte. Ensuite, selon l'opérateur, nous l'ajoutons ou le soustrayons de la valeur initiale. Nous continuons ce processus jusqu'à ce que nous ne parvenions pas à obtenir un "+" ou un "-", et renvoyons la valeur à la fin.
Nous allons implémenter term() de la même manière :
def term(self):
rv = self.match('factor')
while True:
op = self.maybe_keyword('*', '/')
if op is None:
break
term = self.match('factor')
if op == '*':
rv *= term
else:
rv /= term
return rv Ensuite, nous allons implémenter "Facteur". Nous allons d'abord essayer de lire une parenthèse gauche, ce qui signifie qu'il y a une expression entre parenthèses. Si nous trouvons une parenthèse, nous lisons une expression et la parenthèse fermante, et renvoyons la valeur de l'expression. Sinon, nous lisons simplement et renvoyons un nombre.
def factor(self):
if self.maybe_keyword('('):
rv = self.match('expression')
self.keyword(')')
return rv
return self.match('number')
Dans la section suivante, nous allons faire en sorte que notre analyseur reconnaisse un nombre.
Reconnaître les nombres
Afin de reconnaître un nombre, nous devons examiner les caractères individuels de notre texte. Les nombres se composent d'un ou plusieurs chiffres, éventuellement suivis d'une partie décimale. La partie décimale comporte un point (.) suivi d'au moins un chiffre. De plus, les nombres peuvent être précédés d'un signe tel que "+" ou "-", tel que "-124,33".
Nous allons implémenter le number() méthode comme ceci :
def number(self):
chars = []
sign = self.maybe_keyword('+', '-')
if sign is not None:
chars.append(sign)
chars.append(self.char('0-9'))
while True:
char = self.maybe_char('0-9')
if char is None:
break
chars.append(char)
if self.maybe_char('.'):
chars.append('.')
chars.append(self.char('0-9'))
while True:
char = self.maybe_char('0-9')
if char is None:
break
chars.append(char)
rv = float(''.join(chars))
return rv
Bien que la fonction soit longue, elle est assez simple. Nous avons un chars liste dans laquelle on met les caractères du nombre. Tout d'abord, nous regardons tous les symboles "+" ou "-" qui peuvent être présents avant le nombre. S'il est présent, nous l'ajoutons à la liste. Ensuite, nous recherchons le premier chiffre obligatoire du numéro et continuons à chercher d'autres chiffres en utilisant le maybe_char() méthode. Une fois que nous obtenons None via maybe_char , nous savons que nous avons dépassé l'ensemble de chiffres et terminons la boucle.
De même, nous recherchons la partie décimale et ses chiffres. Enfin, nous convertissons tous les caractères en une chaîne, qui à son tour, nous convertissons en un nombre à virgule flottante.
Une interface pour notre analyseur
Nous avons fini de construire notre analyseur. Dans une dernière étape, nous ajouterons un peu de code dans la portée globale qui nous permettra d'entrer des expressions et de voir les résultats :
if __name__ == '__main__':
parser = CalcParser()
while True:
try:
print(parser.parse(input('> ')))
except KeyboardInterrupt:
print()
except (EOFError, SystemExit):
print()
break
except (ParseError, ZeroDivisionError) as e:
print('Error: %s' % e)
Si vous avez suivi jusqu'ici, félicitations ! Vous avez construit votre premier analyseur de descente récursive !
Si vous suivez dans un IDE local, vous pouvez exécuter votre code à ce stade. Alternativement, vous pouvez utiliser le terrain de jeu ci-dessous pour exécuter l'analyseur. Vous pouvez saisir des expressions via l'onglet "Entrée" ci-dessous :
Vous pouvez également trouver le code complet ici.
Deuxième exemple d'analyseur :un analyseur JSON "étendu"
JSON est un format d'échange de données qui prend en charge les structures de données de base telles que les nombres, les chaînes et les listes. C'est un format très largement utilisé, bien que sa simplicité signifie qu'il manque des choses comme des commentaires et qu'il est strict sur les choses qu'il accepte. Par exemple, vous ne pouvez pas avoir une virgule à la fin d'une liste ou avoir un "+" explicite devant un nombre pour indiquer son signe.
Puisque Python a déjà un module JSON, nous allons viser un peu plus haut et construire un analyseur JSON qui prend en charge les commentaires, les virgules de fin et les chaînes sans guillemets.
L'implémentation de cet analyseur vous apprendra à gérer les commentaires. Il illustrera également comment la création d'un langage facile à utiliser peut compliquer l'analyse, et comment vous pouvez gérer de telles situations.
Avant d'implémenter notre grammaire, essayons de comprendre notre format JSON étendu :
{
# Comments begin with a '#' and continue till the end of line.
# You can skip quotes on strings if they don't have hashes,
# brackets or commas.
Size: 1.5x,
# Trailing commas are allowed on lists and maps.
Things to buy: {
Eggs : 6,
Bread: 4,
Meat : 2,
},
# And of course, plain JSON stuff is supported too!
"Names": ["John", "Mary"],
"Is the sky blue?": true
} Règles de production pour la grammaire JSON
Notre JSON étendu s'en tient aux mêmes types de données que JSON prend en charge. JSON a quatre types de données primitifs - null, booléens, nombres et chaînes, et deux types de données complexes - listes (ou tableaux) et cartes (également appelées hachages ou dictionnaires). Les listes et les hachages ressemblent à ce qu'ils sont en Python.
Étant donné que les données JSON seraient constituées de l'un de ces types, vous pourriez écrire les règles de production comme suit :
Ensuite, vous pouvez décomposer ces deux types en types JSON :
Cette grammaire convient à l'analyse de JSON normal, mais nécessite quelques ajustements pour notre cas. Puisque nous allons prendre en charge les chaînes sans guillemets, ce qui signifie que "1,5" (sans les guillemets) est un nombre, mais "1,5x" (encore une fois, sans les guillemets), est une chaîne. Notre grammaire actuelle lirait le "1.5" de "1.5x", puis provoquerait une erreur car "x" n'était pas attendu après un nombre.
Cela signifie que nous devrons d'abord obtenir l'ensemble complet de caractères sans guillemets. Ensuite, nous analyserons les caractères et déterminerons s'il s'agit d'un nombre ou d'une chaîne. Nous allons donc combiner les nombres et les chaînes sans guillemets dans une seule catégorie, "Sans guillemets". Les chaînes entre guillemets conviennent, nous allons donc les séparer dans une autre catégorie, "QuotedString". Notre règle de production modifiée pour "PrimitiveType" ressemble maintenant à ceci :
De plus, l'ordre des règles est important. Puisque nous avons des clés sans guillemets, nous devons d'abord essayer d'analyser le texte comme un null ou un booléen. Sinon, nous pourrions finir par reconnaître "null" ou "true" comme une chaîne sans guillemets.
Mise en œuvre de l'analyseur et traitement des commentaires
Pour implémenter l'analyseur JSON, nous allons commencer par étendre la classe d'analyseur de base comme suit :
class JSONParser(Parser): # ...
Nous aborderons d'abord le problème du traitement des commentaires. Si vous y réfléchissez, les commentaires sont vraiment similaires aux espaces blancs - ils se produisent aux mêmes endroits où les espaces blancs peuvent se produire, et ils peuvent être supprimés tout comme les espaces blancs. Nous allons donc réimplémenter eat_whitespace() pour gérer les commentaires, comme ceci :
def eat_whitespace(self):
is_processing_comment = False
while self.pos < self.len:
char = self.text[self.pos + 1]
if is_processing_comment:
if char == 'n':
is_processing_comment = False
else:
if char == '#':
is_processing_comment = True
elif char not in ' fvrtn':
break
self.pos += 1
Ici, nous devons savoir si nous traitons des espaces ou un commentaire. Nous parcourons le texte caractère par caractère, en vérifiant si nous avons des espaces blancs ou un # . Quand il y a un # , nous mettons à jour is_processing_comment à True et dans les prochaines itérations du while boucle, nous pouvons supprimer tous les caractères en toute sécurité jusqu'à ce que nous atteignions la fin de la ligne. Cependant, lors du traitement des caractères d'espacement, nous devons nous arrêter une fois qu'un caractère non-espacement apparaît.
Ensuite, nous allons implémenter les règles de production et le start() méthode. Le texte d'entrée contiendra un type JSON, nous appellerons donc simplement any_type() dans le start() méthode :
def start(self):
return self.match('any_type')
def any_type(self):
return self.match('complex_type', 'primitive_type')
def primitive_type(self):
return self.match('null', 'boolean', 'quoted_string', 'unquoted')
def complex_type(self):
return self.match('list', 'map')
Listes et cartes d'analyse
Auparavant, nous avons vu comment analyser des listes séparées par des virgules. Les listes de JSON ne sont qu'une liste séparée par des virgules avec des crochets collés dessus, et la liste peut avoir zéro ou plusieurs éléments. Voyons comment vous implémenteriez l'analyse d'une liste :
def list(self):
rv = []
self.keyword('[')
while True:
item = self.maybe_match('any_type')
if item is None:
break
rv.append(item)
if not self.maybe_keyword(','):
break
self.keyword(']')
return rv
Nous commençons par lire le crochet initial suivi d'un élément de la liste en utilisant self.maybe_match('any_type') . Si nous n'avons pas réussi à obtenir un élément, cela indique que nous avons probablement fini de parcourir tous les éléments, nous sortons donc de la boucle. Sinon, nous ajoutons l'élément à la liste. Nous essayons ensuite de lire une virgule dans la liste, et l'absence de virgule indique également que nous en avons terminé avec la liste.
De même, les cartes ne sont que des listes de "paires" séparées par des virgules avec des accolades, où une paire est une clé de chaîne suivie de deux-points (:) et d'une valeur. Contrairement au dict de Python s qui peut avoir n'importe quel type "hashable" comme clé (qui inclut int s et tuple s), JSON ne prend en charge que les clés de chaîne.
Voici comment implémenter les règles pour les cartes et les paires :
def map(self):
rv = {}
self.keyword('{')
while True:
item = self.maybe_match('pair')
if item is None:
break
rv[item[0]] = item[1]
if not self.maybe_keyword(','):
break
self.keyword('}')
return rv
def pair(self):
key = self.match('quoted_string', 'unquoted')
if type(key) is not str:
raise ParseError(
self.pos + 1,
'Expected string but got number',
self.text[self.pos + 1]
)
self.keyword(':')
value = self.match('any_type')
return key, value
En pair() , nous essayons de lire un "QuotedString" ou "Unquoted" pour la clé. Comme nous l'avons mentionné précédemment, "Unquoted" peut renvoyer un nombre ou une chaîne, nous vérifions donc explicitement si la clé que nous avons lue est une chaîne. pair() renvoie ensuite un tuple avec une clé et une valeur, et map() appelle le pair() et les ajoute à un dict Python.
Reconnaître les valeurs nulles et booléennes
Maintenant que les principales parties de notre analyseur sont implémentées, commençons par reconnaître des jetons simples tels que null et booléens :
def null(self):
self.keyword('null')
return None
def boolean(self):
boolean = self.keyword('true', 'false')
return boolean[0] == 't'
None de Python est l'analogue le plus proche du null de JSON . In the case of booleans, the first characters is sufficient to tell whether it’s true or false , and we return the result of the comparison.
Recognizing unquoted strings and numbers
Before moving on to recognize unquoted strings, let us first define the set of acceptable characters. We’ll leave out anything that’s considered special in such as braces, quotes, colons, hashes (since they are used in comments) and backslashes (because they’re used for escape sequences). We’ll also include spaces and tabs in the acceptable set of characters so that you can write strings like “Things to buy” without using quotes.
So, what are the characters that we want to accept? We can use Python to figure this out:
>>> import string
>>> ''.join(sorted(set(string.printable) - set('{}[]:#"'fvrn')))
't !$%&()*+,-./0123456789;<=>[email protected]^_`abcdefghijklmnopqrstuvwxyz|~'
The next question is, how do you figure out if the text you read is a number or a string? The answer is — we cheat! Since Python’s int() and float() can take a string and return a number, we’ll use them and if those result in a ValueError , we’ll return a string. As for when to use int() or float() , we’ll use a simple rule. If the text contains “E”, “e” or “.”, (for example, “12.3” or “2e10”), we’ll call float(); otherwise, we’ll use int() .
Here’s the code:
def unquoted(self):
acceptable_chars = '0-9A-Za-z t!$%&()*+./;<=>?^_`|~-'
number_type = int
chars = [self.char(acceptable_chars)]
while True:
char = self.maybe_char(acceptable_chars)
if char is None:
break
if char in 'Ee.':
number_type = float
chars.append(char)
rv = ''.join(chars).rstrip(' t')
try:
return number_type(rv)
except ValueError:
return rv
Since matching rules are handled by match() , this takes care of stripping any initial whitespace before unquoted() can run. In this way, we can be sure that unquoted() won’t return a string consisting of only whitespaces. Any whitespace at the end is stripped off before we parse it as a number or return the string itself.
Recognizing quoted strings
Quoted strings are fairly simple to implement. Most programming languages (including Python) have single and double quotes that behave in the same way, and we’ll implement both of them.
We’ll support the following escape sequences — b (backspace), f (line feed), n (newline), r (carriage return), t (tab) and u(four hexadecimal digits) where those digits are used to represent an Unicode “code point”. For anything else that has a backslash followed by a character, we’ll ignore the backslash. This handles cases like using the backslash to escape itself ( ) or escaping quotes (" ).
Here’s the code for it:
def quoted_string(self):
quote = self.char('"'')
chars = []
escape_sequences = {
'b': 'b',
'f': 'f',
'n': 'n',
'r': 'r',
't': 't'
}
while True:
char = self.char()
if char == quote:
break
elif char == '':
escape = self.char()
if escape == 'u':
code_point = []
for i in range(4):
code_point.append(self.char('0-9a-fA-F'))
chars.append(chr(int(''.join(code_point), 16)))
else:
chars.append(escape_sequences.get(char, char))
else:
chars.append(char)
return ''.join(chars)
We first read a quote and then read additional characters in a loop. If this character is the same type of quote as the first character we read, we can stop reading further and return a string by joining the elements of chars .
Otherwise, we check if it’s an escape sequence and handle it in the aforementioned way, and add it to chars . Finally, if it matches neither of them, we treat it as a regular character and add it to our list of characters.
An interface for our JSON parser
To make sure we can interact with our parser, we’ll add a few lines of code that accepts input and parses it as JSON. Again, this code will be in global scope:
if __name__ == '__main__':
import sys
from pprint import pprint
parser = JSONParser()
try:
pprint(parser.parse(sys.stdin.read()))
except ParseError as e:
print('Error: '+ str(e))
To ensure we can read multiple lines, we have used sys.stdin.read() . If you’re going to run this locally, you can enter text and use Ctrl+D to stop the program from asking for more input. Otherwise, you can use this runnable snippet:
You can find the complete code here.
Building other kinds of parsers
Now that we’ve gone through building two parsers, you might have a fairly good idea of how to roll your own for the task at hand. While every language is unique (and therefore, their parsers), there are some common situations that we haven’t covered. For the sake of brevity, we won’t cover any code in these sections.
Whitespace sensitive languages
Before we begin, let us clarify that we’re not referring to languages that use whitespace-based indentation — we’ll cover them in the next section. Here, we’ll discuss languages where the meaning of things change based on the whitespace you put between elements.
An example of such a language would be where “a=10” is different than “a =10”. With bash and some other shells, “a=10” sets an environment variable, whereas “a =10” runs the program “a” with “=” and “10” as command-line arguments. You can even combine the two! Consider this:
a=10 b=20 c = 30
This sets the environment variables “a” and “b” only for the program “c”. The only way to parse such a language is to handle the whitespaces manually, and you’d have to remove all the eat_whitespace() calls in keyword() and match() . This is how you might write the production rules:
Whitespace based indentation
Languages like C and Javascript use curly braces to indicate the body of loops and if-statements. However, Python uses indentation for the same purpose, which makes parsing tricky.
One of the methods to handle this is to introduce a term such as “INDENT” to keep track of indented statements. To see how this would work, consider the following production rule:
After matching a condition, our parser would look for INDENT. Since this is the first time it’s trying to match INDENT, it takes whatever whitespace (except for newlines) that appears along with a non-whitespace character (since that would be part of a statement).
In subsequent iterations, it looks for the same whitespace in the text. If it encounters a different whitespace, it can raise an error. However, if there’s no whitespace at all, it indicates that the “while” loop is finished.
For nested indentations, you’d need to maintain a list of all indentations that you’re currently handling. When the parser handles a new indented block, it should add the new indentation string on the list. You can tell if you’re done parsing the block, by checking that you were able to retrieve less whitespace than you did previously. At this point, you should pop off the last indentation off the list.