Lines Matching full:strong
6 <p>Les <strong>compilateurs</strong> permettent d'<strong>analyser</strong> et
7 <strong>manipuler</strong> des données <strong>textuelles</strong>. Leurs
20 <p>Un <strong>langage</strong> est une façon d'exprimer ou de
21 <strong>formuler</strong> une <strong>solution</strong> à un
22 <strong>problème</strong>. Et des problèmes, il en existe beaucoup. Nous
24 langages sont <strong>compris</strong> par des <strong>machines</strong>.
25 Cette opération est possible grâce aux <strong>compilateurs</strong>.</p>
27 langages</a> étudie entre autres l'<strong>analyse automatique</strong> de ces
28 langages à travers des outils comme des <strong>automates</strong> ou des
29 <strong>grammaires</strong>. Il est nécessaire d'avoir un cours détaillé pour
36 <p>Un <strong>langage</strong> est un ensemble de <strong>mots</strong>.
37 Chaque mot est une <strong>séquence</strong> de <strong>symboles</strong>
38 appartenant à un <strong>alphabet</strong>. Un symbole représente la plus
39 petite <strong>unité lexicale</strong> d'un langage, il est atomique et nous
40 l'appellons <strong>lexème</strong> (ou <em lang="en">token</em> en anglais).
42 <strong>règles</strong>. À partir d'un mot et d'une règle racine, nous allons
43 essayer de <strong>dériver</strong> ses sous-règles. Si une dérivation existe,
44 alors le mot est considéré comme <strong>valide</strong>, sinon il est
45 considéré comme <strong>invalide</strong>. Nous parlons aussi de
46 <strong>reconnaissance</strong> de mots. Par exemple, si nous considérons les
58 <strong>disjonction</strong>, <em>i.e.</em> le « ou », est représentée par le
65 <p>Nous continuons à dériver jusqu'à <strong>éliminer</strong> toutes les
66 règles et n'avoir que des <strong>lexèmes</strong> :</p>
84 <p>Un ensemble de règles est appelé une <strong>grammaire</strong>. Et donc,
85 une grammaire représente un <strong>langage</strong> !</p>
90 <strong>niveaux</strong> :</p>
92 <li>grammaires <strong>générales</strong>, ou <em lang="en">unrestricted
95 <li>grammaires <strong>contextuelles</strong>, ou
98 <li>grammaires <strong>algébriques</strong>, ou <em lang="en">context-free
101 <li>grammaires <strong>régulières</strong>, ou <em lang="en">regular
110 de reconnaître des <strong>couples de symboles</strong> (comme des
134 <strong>analyses</strong> : <strong>lexicale</strong> et
135 <strong>syntaxique</strong>. Une analyse lexicale consiste à
136 <strong>découper</strong> un mot en une <strong>séquence de lexèmes</strong>.
138 vérifier que le mot <strong>appartient</strong> au langage.</p>
142 d'<strong>avancer</strong> dans la <strong>dérivation</strong> des règles de
145 <strong>catégories</strong> : LL, LR, LALR etc. <code>Hoa\Compiler</code> ne
153 <strong>revenir</strong> jusqu'à <em>k</em> étapes en arrière ; nous parlons
155 <strong>ambiguës</strong> : à chaque fois que nous dérivons une règle de la
158 <em>k</em> permet de définir le <strong>niveau</strong> d'ambiguïté. Si une
160 <strong>non-ambiguë</strong> : à chaque lexème utilisé pour dériver nos
163 <strong>indéfinie</strong>. L'exemple suivant illustre une grammaire
189 <p>Écrire des compilateurs est une tâche <strong>laborieuse</strong>. Ce n'est
191 pourquoi il existe des <strong>compilateurs de compilateurs</strong>, ou
194 <strong>intermédiaire</strong> pour écrire une grammaire. La bibliothèque
197 <strong>dédié</strong>.</p>
202 <strong>grammaires algébriques</strong>. Il s'écrit dans des fichiers portant
205 <p>Une grammaire est constituée de <strong>lexèmes</strong> et de
206 <strong>règles</strong>. La déclaration d'un lexème se fait de la manière
209 <strong>nom</strong> du lexème, <code><em>value</em></code> représente sa
210 <strong>valeur</strong>, au format <a href="http://pcre.org/">PCRE</a>
213 <code><em>namespace_out</em></code> représentent les noms des <strong>espaces
214 de noms</strong> et sont optionels (vaut <code>default</code> par défaut). Par
218 <p>Les espaces de noms représentent des <strong>sous-ensembles</strong>
219 disjoints de lexèmes, utilisés pour <strong>faciliter</strong> les analyses.
221 excepté qu'elle représente un lexème à <strong>sauter</strong>, c'est à dire
226 <code>Json.pp</code>, grammaire légèrement <strong>simplifiée</strong> du
229 <strong>complète</strong> se situe dans le fichier
271 <strong>confondre</strong> les lexèmes <code>quote_</code> et
273 ensuite la règle <code>value</code> qui est une <strong>disjonction</strong>
274 de plusieurs lexèmes et règles. Les <strong>constructions</strong> du langage
277 <li><code><em>rule</em>()</code> pour <strong>appeler</strong> une
280 pour <strong>déclarer</strong> un lexème (les espaces de noms n'apparaissent
282 <li><code>|</code> pour une <strong>disjonction</strong> (un choix) ;</li>
285 <strong>optionel</strong> ;</li>
287 apparaître <strong>1 ou plusieurs</strong> fois ;</li>
289 apparaître <strong>0 ou plusieurs</strong> fois ;</li>
293 <li><code>#<em>node</em></code> pour créer un <strong>nœud</strong>
295 <li><code><em>token</em>[<em>i</em>]</code> pour <strong>unifier</strong>
324 est classique. Il commence par analyser <strong>lexicalement</strong> la
326 séquence de lexèmes. L'<strong>ordre</strong> de déclaration des lexèmes est
328 Ensuite, c'est l'analyseur <strong>syntaxique</strong> qui entre en jeu afin
329 de <strong>reconnaître</strong> notre donnée.</p>
331 <strong>trace</strong>. Cette trace peut être transformée en AST, pour
335 <strong>contraintes</strong> qui ne peuvent pas être exprimées dans la
338 <strong>assistant</strong> pour lire une grammaire au format PP facilement.
369 tâches très <strong>régulièrement</strong>. C'est pourquoi, le script
385 <p>C'est un moyen pratique pour tester <strong>rapidement</strong> des données
388 <p>Les analyses s'effectuent sur la règle <strong>racine</strong> mais nous
389 pouvons préciser une <strong>autre règle</strong> à l'aide du deuxième
417 <li>durant l'analyse <strong>lexicale</strong>,
424 <li>durant l'analyse <strong>syntaxique</strong>,
434 <strong>production</strong> d'un AST. Il est important de contrôler sa
435 <strong>forme</strong>, sa <strong>taille</strong>, les données qu'il
436 <strong>contient</strong> etc. C'est pourquoi il est nécessaire de comprendre
438 <strong>nœuds</strong> dans l'AST. Une précision tout d'abord, les lexèmes
445 <strong>surchargent</strong> les unes par rapport aux autres au sein d'une
446 <strong>même règle</strong>. Enfin, un nom de règle peut être précédé par
448 un nœud par <strong>défaut</strong>, mais il peut être surchargé. Par exemple,
463 <strong>empruntée</strong> dans la règle. Le mécanisme est normalement assez
464 <strong>intuitif</strong>.</p>
469 <strong>espaces de noms</strong>.</p>
470 <p>Les <strong>lexèmes</strong> sont placés dans des espaces de noms,
472 <strong>courant</strong> seront utilisés par l'analyseur lexical. L'espace de
475 consommé, il peut <strong>changer</strong> l'espace courant pour la suite de
481 espaces de noms <strong>différent</strong> :</p>
538 donnée a pu être <strong>découpée</strong>, et nous sommes passés d'un espace
545 l'opérateur <code>-></code>. Aucun <strong>historique</strong> sur les espaces
547 qu'un espace de lexèmes soit accessible via <strong>plusieurs</strong> autres
549 <strong>précédent</strong>. Autrement dit, nous aimerions un historique des
558 espaces sont gérés comme une <strong>pile</strong>, d'où le vocabulaire
624 <strong>unification</strong> de lexèmes. Imaginons la grammaire
634 <code>'foo'</code> sont valides, mais <strong>également</strong>
636 <p>L'unification des lexèmes permet d'ajouter une <strong>contrainte</strong>
637 supplémentaire sur la <strong>valeur</strong> des lexèmes à l'exécution. La
640 valeur. Et enfin, l'unification est <strong>locale</strong> à une instance
642 plusieurs règles et que cela s'applique sur la règle <strong>appelée</strong>
672 <p>Un arbre <strong>syntaxique abstrait</strong> représente une donnée
673 textuelle sous forme <strong>structurelle</strong>. Chaque
674 <strong>nœud</strong> de cet arbre est représenté par la classe
692 <strong>parcourir</strong> un AST. En guise d'exemple, nous allons écrire le
800 <strong>stocker</strong> des données susceptibles d'être
801 <strong>réutilisées</strong>, par exemple d'un visiteur à l'autre. Cette
802 méthode retourne une <strong>référence</strong> sur un tableau ; ainsi :</p>
810 <p>Il est courant d'utiliser un visiteur par <strong>contrainte</strong> :
816 <strong>trivial</strong> et nous l'utiliserons la plupart du temps avec un
840 plusieurs <strong>couches</strong>. Chaque couche est exploitable pour
843 il en résulte une <strong>trace</strong>. Cette trace est un tableau composé
924 nous avons son <strong>nom</strong> (avec la méthode <code>getRule</code>), et
925 si nous sommes sur un lexème, nous avons son <strong>nom</strong> (avec la
926 méthode <code>getTokenName</code>), sa <strong>représentation</strong> (sous
928 <strong>valeur</strong> (avec la méthode <code>getValue</code>), si c'est un
929 nœud à <strong>conserver</strong> dans l'AST (avec la méthode
930 <code>isKept</code>) et son index d'<strong>unification</strong> s'il existe
937 <strong>numérique</strong>, comme <code>13</code>, <code>12</code>,
940 <strong>linéarisée</strong> selon les opérateurs du langage PP :</p>
951 Nous allons afficher toutes les règles <strong>accessibles</strong> depuis la
1019 pour être sous sa forme la plus <strong>réduite</strong> possible. Ceci permet
1020 de <strong>raisonner</strong> beaucoup plus <strong>facilement</strong> et
1021 <strong>rapidement</strong> sur les règles. En effet, les traitements sur la
1028 <strong>valider</strong> une donnée (si nous la voyons comme un automate) ou
1029 <strong>générer</strong> des données. Jusqu'à présent, nous avons vu comment
1031 <strong>préparation</strong> de notre compilateur, exécution des
1032 <strong>analyseurs</strong> lexical et syntaxique résultant sur une
1033 <strong>trace</strong>, transformation de la trace vers un
1034 <strong>AST</strong> pour enfin <strong>visiter</strong> cet arbre. Mais nous
1039 <strong>générations</strong> de données :</p>
1046 qu'un seul algorithme peut suffir aux <strong>nombreux</strong> contextes
1049 <p>Générer une donnée à partir d'une grammaire se fait en <strong>deux
1050 étapes</strong> :</p>
1052 <li>générer des valeurs pour les <strong>lexèmes</strong> afin d'avoir des données
1054 <li>générer un <strong>chemin</strong> dans les règles de la grammaire.</li>
1063 doit être <strong>rapide</strong>. Nous allons utiliser un parcours dit
1064 <strong>isotrope</strong>. Nous partons d'une règle et nous avançons
1065 uniquement à partir de choix <strong>aléatoires</strong> et <strong>uniformes
1066 localement</strong> (uniquement pour ce choix). Par exemple si nous avons une
1081 <p>Cette génération est <strong>naïve</strong> mais ce n'est pas important. Ce
1083 autrement dit, la génération des <strong>séquences de lexèmes</strong>.</p>
1088 <p>Le premier algorithme est celui de la génération <strong>aléatoire</strong>
1089 et <strong>uniforme</strong>. Cet algorithme est utile si nous voulons générer
1090 des séquences de lexèmes de <strong>taille <em>n</em> fixe</strong> et avec
1091 une <strong>uniformité</strong> non pas locale (comme avec un parcours
1092 isotrope) mais sur l'<strong>ensemble</strong> de toutes les séquences
1094 <strong>pré-calcul</strong> (une seule fois par taille) puis
1095 <strong>génération</strong>. Le pré-calcul est une étape
1096 <strong>automatique</strong> et calcule le <strong>nombre</strong> de
1098 au calcul de <strong>fonctions de répartions</strong> pour
1099 <strong>guider</strong> la génération des séquences de lexèmes finales.</p>
1140 <p>Le deuxième algorithme est celui de la génération <strong>exhaustive
1141 bornée</strong>. Cet algorithme génère <strong>toutes</strong> les séquences
1142 (c'est le côté exhaustif) de lexèmes de taille 1 <strong>jusqu'à</strong>
1144 algorithme est que l'exhaustivité est une forme de <strong>preuve</strong> !
1195 <p>Le dernier algorithme est celui de la génération <strong>basée sur la
1196 couverture</strong>. Cet algorithme réduit l'<strong>explosion
1197 combinatoire</strong> rencontrée avec l'algorithme précédent mais l'objectif
1199 « <strong>activer</strong> » toutes les <strong>branches</strong> des règles
1202 utilisé dans une séquence. Pour assurer une <strong>diversité</strong> dans
1204 couvertes sont résolus par tirages <strong>aléatoires</strong>. L'algorithme
1225 <strong>termination</strong> de l'algorithme, nous utilisons
1226 l'<strong>heuristique</strong> suivante sur les opérateurs de
1227 <strong>répétition</strong> : <code>*</code> répétera <code>0</code>,
1232 trouve ses origines dans le test aux <strong>limites</strong>.</p>
1234 à <strong>couvrir</strong> l'ensemble de notre grammaire !</p>
1239 <p>Voici quelques <strong>indices</strong> pour savoir quand utiliser tel ou
1271 est <strong>monolithique</strong>.</p>
1275 <p><code>Hoa\Compiler</code> propose deux <strong>compilateurs de
1276 compilateurs</strong> : <code>Hoa\Compiler\Llk</code> et
1277 <code>Hoa\Compiler\Ll1</code>, afin de <strong>valider</strong> des données.
1278 Le <strong>langage PP</strong> permet d'écrire des <strong>grammaires
1279 algébriques</strong> de manière <strong>simple</strong> et
1280 <strong>naturelle</strong>. Le compilateur de compilateurs LL(<em>k</em>) est
1281 découpé en <strong>processus distincts</strong> ce qui le rend très
1283 <strong>générer</strong> des données à partir d'une grammaire selon le