Voici un extrait de mes notes sur le sujet. L’original est en anglais, je traduis sans vérifier la terminologie exacte en français. Je laisse quelques concepts en anglais en tant que différentes pistes à explorer avec un moteur de recherche.
Parsing, token, alphabet, terminaux
Parsing, première approximation : c’est de l’analyse syntaxique. Comment y procéder ? À l’aide d’une grammaire, structurer une succession linéaire de symboles — linéaire : le prochain symbole dépend d’une façon ou d’une autre des symboles qui l’ont précédés.
Token : on nomme tokens ce que les linguistes appellent phrases. En combinant la structure obtenue après le parsing avec les tokens, on peut définir une sémantique. Exemple : 3 + 4 ×ばつ 5 est un token dont on pourrait structurer comme 3 + (4 ×ばつ 5) pour lui attribuer la sémantique 23.
Un alphabet est un fonds où l’on peut puiser des symboles qui engendreront un langage. Celui-ci comportera deux catégories de symboles : ceux qui sont ‘visibles’ ou ‘palpables‘ participent à la construction de phrases (e.g. ‘freem’, ‘;’), ceux qui constituent des ‘méta-données’ ne peuvent pas apparaître dans une phrase (e.g. les notions de ‘phrase’ ou de ‘nom commun’).
Les symboles palpables sont appelés symboles terminaux. Les méta-données sont appelés symboles non-terminaux.
Grammaires, productions
Generative grammar : est ainsi appelée une grammaire qui définit comment faire des substitutions de symboles. Ainsi, écrire Y → X signifie « X pourrait remplacer Y » . Une procédure systématique d’applications de règles du genre Y → X est dite "generative process".
Les règles sont appelées "production rules", les différentes étapes "production steps".
On peut construire différents types de grammaires et les regrouper selon les types de productions qu’elles permettent. Un regroupement de ce genre qui est très connu est la "Chomsky hierarchy" où on trouve une catégorie de grammaires dite "context-free" (CF).
Pour écrire les règles de production d’une grammaire CF, il existe une palanquée de notations. Exemples: Backus-Naur Form (BNF), notation de van Wijngaarden, Extended BNF (EBNF), ...
Parsing, redux
L’objectif du parsing d’une chaîne de caractères est de détailler les étapes qui mènent à la chaîne en partant d’une grammaire. On ne peut pas se baser seulement sur la grammaire : au moment où celle-ci a été écrite, une sémantique lui a été attachée ; les règles de production dont elle comporte possèdent elles aussi une sémantique. Ce dont on a besoin alors, c’est de trouver quelles règles ont participé à la construction de la chaîne et comment elles ont été impliquées.
La succession des règles de production forme un arbre (ou des arbres) qui est appelé "parse tree". Parser revient à appliquer ces règles, parfois en prenant des décisions intermédiaires quand il y a plusieurs symboles candidats à la prochaine substitution.
Parser generators
On peut automatiser le processus qui, à partir d’un symbole donné, passe au prochain et, le cas échéant, lève les ambiguïtés. Un programme capable d’accomplir pareil processus est nommé "parser generator". Ses entrées : la grammaire (toujours), les symboles terminaux (parfois) ; ses sorties : un parseur.
Ce processus de passage de symbole en symbole peut se faire de haut-en-bas ou de bas-en-haut.
Notion de direction
La génération de parseurs peut être "non-directional" : on consulte la chaîne cible symbole après symbole afin de construire l’arbre (parse tree) au fur et à mesure. La méthode d’Unger y va de haut-en-ba tandis que la méthode CYK (ou CYK) y va de bas-en-haut — appellation faite d’après Cocke, Younger, et Kasami.
La génération peut aussi être "directional" : on procède de symbole en symbole, de gauche à droite (c’est ça la direction). Deux techniques prévalent pour cette méthode : "predictions/matches" quand on va de haut-en-bas, "shifts/reductions" de bas-en-haut.
Notion de déterminisme
Un automate qui génère des parseurs directionnels possède les caractéristiques suivantes.
Il est d’abord muni des symboles qui restent à parser.
Il est également muni d’instructions qui lui permettront de se débloquer dans tous les cas possibles.
Au cas où il est confronté à une ambiguïté, il a besoin de « tricher » et consulter un nombre k de symboles à venir sans les consommer. Cette technique de triche est appelée look-ahead. La méthode est appelée X(k).
Il n’existe qu’une seule méthode déterministe allant de haut-en-bas : LL. Première lettre L : "Left-to-right". deuxième L : la méthode identifie "the Leftmost production". L’appellation générale de X(k) devient alors LL(k). Parfois, on inverse la chaîne à parser avant d’appliquer LL. Dans ce cas, on fait spécifiquement du RR(k).
Les méthodes déterministes allant de bas-en-haut font légion. La plus connue est LR(k) avec L : "Left-to-right" ; R : identifier "the Rightmost production".
Quand on fait l’inversion comme au point précédent, on obtient RL(k).
Bibliothèques de génération de parseurs
Dans les langages de programmation dotés de types algébriques de données, la définition d’une grammaire est juste une définition de type. Cette simplicité mène à une prolifération de bibliothèques du genre parser generator, chaque se démarquant sur un point particulier.
TatTempo, le retour !
Regarde de ce côté pour un exemple d’utilisation d’une de ces bibliothèques ; chaque option
comporte une valeur par défaut ;
peut être parsée en version longue (--foo) ou courte (-f) ;
sera documentée après que le programme aura été invoqué via programme --help.
# Condensé de glossaire
Posté par gipoisson . En réponse au journal quick start pour coco/R. Évalué à 8.
Sommaire
Voici un extrait de mes notes sur le sujet. L’original est en anglais, je traduis sans vérifier la terminologie exacte en français. Je laisse quelques concepts en anglais en tant que différentes pistes à explorer avec un moteur de recherche.
Parsing, token, alphabet, terminaux
Parsing, première approximation : c’est de l’analyse syntaxique. Comment y procéder ? À l’aide d’une grammaire, structurer une succession linéaire de symboles — linéaire : le prochain symbole dépend d’une façon ou d’une autre des symboles qui l’ont précédés.
Token : on nomme tokens ce que les linguistes appellent phrases. En combinant la structure obtenue après le parsing avec les tokens, on peut définir une sémantique. Exemple :
3 + 4 ×ばつ 5est un token dont on pourrait structurer comme3 + (4 ×ばつ 5)pour lui attribuer la sémantique23.Un alphabet est un fonds où l’on peut puiser des symboles qui engendreront un langage. Celui-ci comportera deux catégories de symboles : ceux qui sont ‘visibles’ ou ‘palpables‘ participent à la construction de phrases (e.g. ‘freem’, ‘;’), ceux qui constituent des ‘méta-données’ ne peuvent pas apparaître dans une phrase (e.g. les notions de ‘phrase’ ou de ‘nom commun’).
Les symboles palpables sont appelés symboles terminaux. Les méta-données sont appelés symboles non-terminaux.
Grammaires, productions
Generative grammar : est ainsi appelée une grammaire qui définit comment faire des substitutions de symboles. Ainsi, écrire
Y → Xsignifie « X pourrait remplacer Y » . Une procédure systématique d’applications de règles du genreY → Xest dite "generative process".Les règles sont appelées "production rules", les différentes étapes "production steps".
On peut construire différents types de grammaires et les regrouper selon les types de productions qu’elles permettent. Un regroupement de ce genre qui est très connu est la "Chomsky hierarchy" où on trouve une catégorie de grammaires dite "context-free" (CF).
Pour écrire les règles de production d’une grammaire CF, il existe une palanquée de notations. Exemples: Backus-Naur Form (BNF), notation de van Wijngaarden, Extended BNF (EBNF), ...
Parsing, redux
L’objectif du parsing d’une chaîne de caractères est de détailler les étapes qui mènent à la chaîne en partant d’une grammaire. On ne peut pas se baser seulement sur la grammaire : au moment où celle-ci a été écrite, une sémantique lui a été attachée ; les règles de production dont elle comporte possèdent elles aussi une sémantique. Ce dont on a besoin alors, c’est de trouver quelles règles ont participé à la construction de la chaîne et comment elles ont été impliquées.
La succession des règles de production forme un arbre (ou des arbres) qui est appelé "parse tree". Parser revient à appliquer ces règles, parfois en prenant des décisions intermédiaires quand il y a plusieurs symboles candidats à la prochaine substitution.
Parser generators
On peut automatiser le processus qui, à partir d’un symbole donné, passe au prochain et, le cas échéant, lève les ambiguïtés. Un programme capable d’accomplir pareil processus est nommé "parser generator". Ses entrées : la grammaire (toujours), les symboles terminaux (parfois) ; ses sorties : un parseur.
Ce processus de passage de symbole en symbole peut se faire de haut-en-bas ou de bas-en-haut.
Notion de direction
La génération de parseurs peut être "non-directional" : on consulte la chaîne cible symbole après symbole afin de construire l’arbre (parse tree) au fur et à mesure. La méthode d’Unger y va de haut-en-ba tandis que la méthode CYK (ou CYK) y va de bas-en-haut — appellation faite d’après Cocke, Younger, et Kasami.
La génération peut aussi être "directional" : on procède de symbole en symbole, de gauche à droite (c’est ça la direction). Deux techniques prévalent pour cette méthode : "predictions/matches" quand on va de haut-en-bas, "shifts/reductions" de bas-en-haut.
Notion de déterminisme
Un automate qui génère des parseurs directionnels possède les caractéristiques suivantes.
kde symboles à venir sans les consommer. Cette technique de triche est appelée look-ahead. La méthode est appeléeX(k).Il n’existe qu’une seule méthode déterministe allant de haut-en-bas : LL. Première lettre L : "Left-to-right". deuxième L : la méthode identifie "the Leftmost production". L’appellation générale de
X(k)devient alorsLL(k). Parfois, on inverse la chaîne à parser avant d’appliquer LL. Dans ce cas, on fait spécifiquement duRR(k).Les méthodes déterministes allant de bas-en-haut font légion. La plus connue est
LR(k)avec L : "Left-to-right" ; R : identifier "the Rightmost production".Quand on fait l’inversion comme au point précédent, on obtient
RL(k).Bibliothèques de génération de parseurs
Dans les langages de programmation dotés de types algébriques de données, la définition d’une grammaire est juste une définition de type. Cette simplicité mène à une prolifération de bibliothèques du genre parser generator, chaque se démarquant sur un point particulier.
TatTempo, le retour !
Regarde de ce côté pour un exemple d’utilisation d’une de ces bibliothèques ; chaque option
--foo) ou courte (-f) ;programme --help.Et c’est compilé :)