aboutsummaryrefslogtreecommitdiffstats
path: root/Documentation
diff options
context:
space:
mode:
authorIvan Enderlin <ivan.enderlin@hoa-project.net>2013-04-11 21:22:38 +0200
committerIvan Enderlin <ivan.enderlin@hoa-project.net>2013-04-11 21:22:38 +0200
commit590195800afbbaa11cf226d2c814391b4ea05a4d (patch)
tree87cbac86945aa1e9a6e78e215c56f32d61ebd83a /Documentation
parent86447ded23fe4f87340ebc295a8f06d2513eefa2 (diff)
downloadCompiler-590195800afbbaa11cf226d2c814391b4ea05a4d.zip
Compiler-590195800afbbaa11cf226d2c814391b4ea05a4d.tar.gz
Compiler-590195800afbbaa11cf226d2c814391b4ea05a4d.tar.bz2
Add french documentation.
Diffstat (limited to 'Documentation')
-rw-r--r--Documentation/Fr/Index.xyl1131
1 files changed, 1131 insertions, 0 deletions
diff --git a/Documentation/Fr/Index.xyl b/Documentation/Fr/Index.xyl
new file mode 100644
index 0000000..0ec1358
--- /dev/null
+++ b/Documentation/Fr/Index.xyl
@@ -0,0 +1,1131 @@
+<?xml version="1.0" encoding="utf-8"?>
+
+<overlay xmlns="http://hoa-project.net/xyl/xylophone">
+<yield id="chapter">
+
+ <p>Les <strong>compilateurs</strong> permettent d'<strong>analyser</strong> et
+ <strong>manipuler</strong> des données <strong>textuelles</strong>. Leurs
+ applications sont très nombreuses. <code>Hoa\Compiler</code> propose de
+ manipuler plusieurs compilateurs selon les besoins.</p>
+
+ <h2 id="Table_des_matieres">Table des matières</h2>
+
+ <tableofcontents id="main-toc" />
+
+ <h2 id="Introduction" for="main-toc">Introduction</h2>
+
+ <blockquote cite="https://secure.wikimedia.org/wikipedia/fr/wiki/Nicolas_Boileau">Ce
+ qui se conçoit bien s'énonce clairement, et les mots pour le dire viennent
+ aisément.</blockquote>
+ <p>Un <strong>langage</strong> est une façon d'exprimer ou de
+ <strong>formuler</strong> une <strong>solution</strong> à un
+ <strong>problème</strong>. Et des problèmes, il en existe beaucoup. Nous
+ lisons et écrivons dans plusieurs langages au quotidien, et certains de ces
+ langages sont <strong>compris</strong> par des <strong>machines</strong>.
+ Cette opération est possible grâce aux <strong>compilateurs</strong>.</p>
+ <p>La
+ <a href="https://secure.wikimedia.org/wikipedia/fr/wiki/Théorie_des_langages">théorie
+ des langages</a> étudie entre autres l'<strong>analyse automatique</strong> de
+ ces langages à travers des outils comme des <strong>automates</strong> ou des
+ <strong>grammaires</strong>. Il est nécessaire d'avoir un cours détaillé pour
+ bien comprendre tous ces concepts. Toutefois, nous allons essayer de
+ vulgariser un minimum pour permettre une utilisation correcte de
+ <code>Hoa\Compiler</code>.</p>
+
+ <h3 id="Langage_et_grammaire" for="main-toc">Langage et grammaire</h3>
+
+ <p>Un <strong>langage</strong> est un ensemble de <strong>mots</strong>.
+ Chaque mot est une <strong>séquence</strong> de <strong>symboles</strong>
+ appartenant à un <strong>alphabet</strong>. Un symbole représente la plus
+ petite <strong>unité lexicale</strong> d'un langage, il est atomique et nous
+ l'appellons <strong>lexème</strong> (ou <em lang="en">token</em> en anglais).
+ Les séquences de lexèmes représentant les mots sont construites avec des
+ <strong>règles</strong>. À partir d'un mot et d'une règle racine, nous allons
+ essayer de <strong>dériver</strong> ses sous-règles. Si une dérivation existe,
+ alors le mot est considéré comme <strong>valide</strong>, sinon il est
+ considéré comme <strong>invalide</strong>. Nous parlons aussi de
+ <strong>reconnaissance</strong> de mots. Par exemple, si nous considérons les
+ règles suivantes :</p>
+ <pre><code>  exp ::= exp + exp
+  | nombre
+ nombre ::= chiffre nombre
+  | chiffre
+chiffre ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9</code></pre>
+ <p>Le mot que nous voulons reconnaître est <code>7 + 35</code>. La règle
+ racine est <code><em>exp</em></code>. Si nous la dérivons (de gauche à droite
+ et de haut en bas, ou <em lang="en">left-to-right</em> et <em
+ lang="en">top-to-bottom</em> en anglais), nous pouvons avoir
+ <code><em>exp</em> + <em>exp</em></code> ou <code><em>nombre</em></code> (la
+ <strong>disjonction</strong>, <ie /> le « ou », est représentée par le symbole
+ « <code>|</code> ») :</p>
+ <pre><code>exp + exp | nombre
+→ exp + exp
+→ ( exp + exp | nombre ) + exp
+→ nombre + exp
+→ ( chiffre nombre | chiffre ) + exp</code></pre>
+ <p>Nous continuons à dériver jusqu'à <strong>éliminer</strong> toutes les
+ règles et n'avoir que des <strong>lexèmes</strong> :</p>
+ <pre><code>…
+→ ( chiffre nombre | chiffre ) + exp
+→ chiffre + exp
+→ ( 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ) + exp
+→ 7 + exp
+→ 7 + ( exp + exp | nombre )
+→ 7 + nombre
+→ 7 + ( chiffre nombre | chiffre )
+→ 7 + chiffre nombre
+→ 7 + ( 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ) nombre
+→ 7 + 3 nombre
+→ 7 + 3 ( chiffre nombre | chiffre )
+→ 7 + 3 chiffre
+→ 7 + 3 ( 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 )
+→ 7 + 3 5</code></pre>
+ <p>Une dériviation existe bel et bien pour reconnaître le mot <code>7 +
+ 35</code>, c'est donc un mot valide pour ces règles.</p>
+ <p>Un ensemble de règles est appelé une <strong>grammaire</strong>. Et donc,
+ une grammaire représente un <strong>langage</strong> !</p>
+ <p>Toutefois, il existe plusieurs catégories de grammaires. C'est en 1956 qu'a
+ été formulée la
+ <a href="https://secure.wikimedia.org/wikipedia/fr/wiki/Hiérarchie_de_Chomsky">hiérarchie
+ de Chomsky</a>, classant les grammaires en quatre
+ <strong>niveaux</strong> :</p>
+ <ol>
+ <li>grammaires <strong>générales</strong>, ou <em lang="en">unrestricted
+ grammars</em>, reconnaissant les langages dits de Turing, aucune
+ restriction n'est imposée aux règles ;</li>
+ <li>grammaires <strong>contextuelles</strong>, ou
+ <em lang="en">context-sensitive grammars</em>, reconnaissant les langages
+ contextuels ;</li>
+ <li>grammaires <strong>algébriques</strong>, ou <em lang="en">context-free
+ grammars</em>, reconnaissant les langages algébriques, basés sur les
+ automates à pile ;</li>
+ <li>grammaires <strong>régulières</strong>, ou <em lang="en">regular
+ grammars</em>, reconnaissant les langages réguliers.</li>
+ </ol>
+ <p>Chaque niveau reconnait le niveau suivant. <code>Hoa\Compiler</code> ne
+ traite que les langages définis par les grammaires de niveau 3 et 4. Pour
+ donner rapidement une idée, les grammaires régulières peuvent s'apparenter aux
+ <a href="https://secure.wikimedia.org/wikipedia/fr/wiki/Expression_régulière">expressions
+ régulières</a> (comme les <a href="http://pcre.org/">PCRE</a>), bien connues
+ des développeurs. Mais les grammaires régulières ne permettent pas par exemple
+ de reconnaître des <strong>couples de symboles</strong> (comme des
+ parenthèses, des accolades ou des guillemets), alors que les grammaires
+ algébriques le permettent (grâce à la notion de piles de lexèmes).</p>
+
+ <h3 id="Reconnaissance_de_mots" for="main-toc">Reconnaissance de mots</h3>
+
+ <div id="parsers" class="verbatim schema"></div>
+ <script>
+ Hoa.Document.onReady(function ( ) {
+
+ var paper = Hoa.Graph(Hoa.$('#parsers'), 800, 180);
+ var grid = paper.grid(0, 0, 800, 180, 5, 2);
+ var word = grid.push(paper.rect(0, 0, 140, 80, 3, 'mot'), 0, 0);
+ var sequence = grid.push(paper.rect(0, 0, 140, 80, 3, 'séquence'), 2, 0);
+ var trace = grid.push(paper.rect(0, 0, 140, 80, 3, 'résultat'), 4, 0);
+ grid.push(paper.rect(0, 0, 140, 50, 3, 'abcdef'), 0, 1);
+ grid.push(paper.rect(0, 0, 380, 50, 3, '[[a ⟼ …], [bc ⟼ …], [d ⟼ …], [ef ⟼ …]]'), 2, 1);
+ grid.push(paper.rect(0, 0, 140, 50, 3, 'valide/invalide'), 4, 1);
+
+ paper.link.between(word, sequence, 'analyseur lexical');
+ paper.link.between(sequence, trace, 'analyseur syntaxique');
+ });
+ </script>
+ <p>En général, le processus de compilation débute par deux
+ <strong>analyses</strong> : <strong>lexicale</strong> et
+ <strong>syntaxique</strong>. Une analyse lexicale consiste à
+ <strong>découper</strong> un mot en une <strong>séquence de lexèmes</strong>.
+ Cette séquence sera ensuite utilisée par l'analyseur syntaxique afin de
+ vérifier que le mot <strong>appartient</strong> au langage.</p>
+ <p>Selon la grammaire, la reconnaissance ne sera fera pas de la même manière,
+ mais le principe reste identique : prendre les lexèmes les uns après les
+ autres dans la séquence et vérifier qu'ils permettent
+ d'<strong>avancer</strong> dans la <strong>dérivation</strong> des règles de
+ notre grammaire.</p>
+ <p>Les analyses syntaxiques sont aussi classées en
+ <strong>catégories</strong> : LL, LR, LALR etc. <code>Hoa\Compiler</code> ne
+ propose que des analyseurs syntaxiques LL, pour <em lang="en">Left-to-right
+ Leftmost derivation</em>, <ie /> de la plus haute règle vers la plus profonde,
+ et les règles sont dérivées de la gauche vers la droite. Là encore, il existe
+ des sous-catégories, dont deux que traite <code>Hoa\Compiler</code> : LL(1) et
+ LL(*). D'une manière générale, on parle d'analyseurs syntaxiques
+ LL(<em>k</em>) : si un lexème ne permet pas de dériver une règle comme il
+ faut, alors l'analyseur peut <strong>revenir</strong> jusqu'à <em>k</em>
+ étapes en arrière ; nous parlons aussi de <em lang="en">backtrack</em>.
+ Autrement dit, les règles peuvent être <strong>ambiguës</strong> : à chaque
+ fois que nous dérivons une règle de la grammaire, nous avons plusieurs choix
+ possibles et l'analyseur peut se tromper, c'est pourquoi il doit parfois
+ revenir en arrière. La variable <em>k</em> permet de définir le
+ <strong>niveau</strong> d'ambiguïté. Si une grammaire peut être analysée par
+ un analyseur syntaxique LL(1), elle est dite <strong>non-ambiguë</strong> : à
+ chaque lexème utilisé pour dériver nos règles, il n'y a qu'un seul choix
+ possible. Et si nous avons un analyseur syntaxique LL(*), cela signifie que la
+ variable <em>k</em> est <strong>indéfinie</strong>. L'exemple suivant illustre
+ une grammaire non-ambiguë :</p>
+ <pre><code>rule ::= a b c | d e f</code></pre>
+ <p>Et cet exemple illustre une grammaire ambiguë :</p>
+ <pre><code>rule1 ::= a rule2
+rule2 ::= b rule3 | b rule4
+rule3 ::= c d
+rule4 ::= e f</code></pre>
+ <p>Voyons quand nous essayons de trouver une dérivation pour le mot
+ <code>abef</code> à partir de la règle racine <code>rule1</code> :</p>
+ <pre><code>rule1
+→ a rule2 <em> a bef ✔</em>
+ → a (b rule3 | b rule4) <em> a bef</em>
+ → a b rule3 <em> ab ef ✔</em>
+ → a b c d <em> abe f ✖</em>
+ ← a b rule3 <em> ab ef ✖</em>
+ ← a (b rule3 | b rule4) <em> a bef</em>
+ → a b rule4 <em> ab ef ✔</em>
+ → a b e f <em>abef ✔</em></code></pre>
+ <p>La règle <code>rule2</code> est ambiguë, ce qui peut entraîner une mauvaise
+ dérivation et donc un retour en arrière, un
+ <em lang="en">backtracking</em>.</p>
+
+ <h2 id="Compilateur_de_compilateurs_LLk" for="main-toc">Compilateur de
+ compilateurs LL(<em>k</em>)</h2>
+
+ <p>Écrire des compilateurs est une tâche <strong>laborieuse</strong>. Ce n'est
+ pas forcément toujours difficile mais souvent répétitif et long. C'est
+ pourquoi il existe des <strong>compilateurs de compilateurs</strong>, ou
+ autrement dit, des générateurs de compilateurs. La plupart du temps, ces
+ compilateurs de compilateurs utilisent un langage
+ <strong>intermédiaire</strong> pour écrire une grammaire. La bibliothèque
+ <code>Hoa\Compiler</code> propose la classe <code>Hoa\Compiler\Llk</code> qui
+ permet l'écriture de compilateurs de compilateurs à travers un langage
+ <strong>dédié</strong>.</p>
+
+ <h3 id="Langage_PP" for="main-toc">Langage PP</h3>
+
+ <p>Le langage PP, pour <em lang="en">PHP Parser</em>, permet d'exprimer des
+ <strong>grammaires algébriques</strong>. Il s'écrit dans des fichiers portant
+ l'extension <code>.pp</code> (voir le fichier
+ <code>hoa://Library/Compiler/.Mime</code>).</p>
+ <p>Une grammaire est constituée de <strong>lexèmes</strong> et de
+ <strong>règles</strong>. La déclaration d'un lexème se fait de la manière
+ suivante : <code>%token <em>namespace_in</em>:<em>name</em> <em>value</em> ->
+ <em>namespace_out</em></code>, où <code><em>name</em></code> représente le
+ <strong>nom</strong> du lexème, <code><em>value</em></code> représente sa
+ <strong>valeur</strong>, au format <a href="http://pcre.org/">PCRE</a>, et
+ <code><em>namespace_in</em></code> et <code><em>namespace_out</em></code>
+ représentent les noms des <strong>espaces de noms</strong> et sont optionels
+ (vaut <code>default</code> par défaut). Par exemple <code>number</code> qui
+ représente un nombre composé de chiffres de <code>0</code> à
+ <code>9</code> :</p>
+ <pre><code class="language-pp">%token number \d+</code></pre>
+ <p>Les espaces de noms représentent des <strong>sous-ensembles</strong>
+ disjoints de lexèmes, utilisés pour <strong>faciliter</strong> les analyses.
+ Une déclaration <code>%skip</code> est similaire à <code>%token</code>
+ excepté qu'elle représente un lexème à <strong>sauter</strong>, c'est à dire
+ à ne pas considérer. Un exemple courant de lexèmes <code>%skip</code> est les
+ espaces :</p>
+ <pre><code class="language-pp">%skip space \s</code></pre>
+ <p>Pour expliquer les règles, nous allons utiliser comme exemple la grammaire
+ <code>Json.pp</code>, grammaire légèrement <strong>simplifiée</strong> du
+ <a href="http://json.org/">langage JSON</a> (voir la
+ <a href="https://tools.ietf.org/html/rfc4627">RFC4627</a>). La grammaire
+ <strong>complète</strong> se situe dans le fichier
+ <code>hoa://Library/Json/Grammar.pp</code>. Ainsi :</p>
+ <pre><code class="language-pp">%skip space \s
+// Scalars.
+%token true true
+%token false false
+%token null null
+// Strings.
+%token quote_ " -> string
+%token string:string [^"]+
+%token string:_quote " -> default
+// Objects.
+%token brace_ {
+%token _brace }
+// Arrays.
+%token bracket_ \[
+%token _bracket \]
+// Rest.
+%token colon :
+%token comma ,
+%token number \d+
+
+value:
+ &amp;lt;true> | &amp;lt;false> | &amp;lt;null> | string() | object() | array() | number()
+
+string:
+ ::quote_:: &amp;lt;string> ::_quote::
+
+number:
+ &amp;lt;number>
+
+#object:
+ ::brace_:: pair() ( ::comma:: pair() )* ::_brace::
+
+#pair:
+ string() ::colon:: value()
+
+#array:
+ ::bracket_:: value() ( ::comma:: value() )* ::_bracket::</code></pre>
+ <p>Nous remarquons que nous avons deux espaces de noms pour les lexèmes :
+ <code>default</code> et <code>string</code> (cela permet de ne pas
+ <strong>confondre</strong> les lexèmes <code>quote_</code> et
+ <code>string:_quote</code> qui ont la même représentation). Nous remarquons
+ ensuite la règle <code>value</code> qui est une <strong>disjonction</strong>
+ de plusieurs lexèmes et règles. Les <strong>constructions</strong> du langage
+ PP sont les suivantes :</p>
+ <ul>
+ <li><code><em>rule</em>()</code> pour <strong>appeler</strong> une
+ règle ;</li>
+ <li><code>&amp;lt;<em>token</em>></code> et <code>::<em>token</em>::</code>
+ pour <strong>déclarer</strong> un lexème (les espaces de noms n'apparaissent
+ pas ici) ;</li>
+ <li><code>|</code> pour une <strong>disjonction</strong> (un choix) ;</li>
+ <li><code>(<em>…</em>)</code> pour grouper ;</li>
+ <li><code><em>e</em>?</code> pour dire que <code><em>e</em></code> est
+ <strong>optionel</strong> ;</li>
+ <li><code><em>e</em>+</code> pour dire que <code><em>e</em></code> peut
+ apparaître <strong>1 ou plusieurs</strong> fois ;</li>
+ <li><code><em>e</em>*</code> pour dire que <code><em>e</em></code> peut
+ apparaître <strong>0 ou plusieurs</strong> fois ;</li>
+ <li><code><em>e</em>{<em>x</em>,<em>y</em>}</code> pour dire que <em>e</em>
+ peut apparaître entre <code><em>x</em></code> et <code><em>y</em></code>
+ fois ;</li>
+ <li><code>#<em>node</em></code> pour créer un <strong>nœud</strong>
+ <code><em>node</em></code> dans l'arbre ;</li>
+ <li><code><em>token</em>[<em>i</em>]</code> pour <strong>unifier</strong>
+ des lexèmes entre eux.</li>
+ </ul>
+ <p>Peu de constructions mais amplement suffisantes.</p>
+ <p>Enfin, la grammaire du langage PP est écrite … dans le langage PP ! Vous
+ pourrez la trouver dans le fichier
+ <code>hoa://Library/Compiler/Llk/Llk.pp</code>.</p>
+
+ <h3 id="Processus_de_compilation" for="main-toc">Processus de compilation</h3>
+
+ <div id="overview" class="verbatim schema"></div>
+ <script>
+ Hoa.Document.onReady(function ( ) {
+
+ var paper = Hoa.Graph(Hoa.$('#overview'), 800, 360);
+ var flow = paper.grid(0, 0, 800, 360, 1, 4);
+ flow.push(paper.rect(0, 0, 200, 70, 3, 'analyseur lexical'));
+ flow.push(paper.rect(0, 0, 200, 70, 3, 'analyseur syntaxique'));
+ flow.push(paper.rect(0, 0, 200, 70, 3, 'trace'));
+ flow.push(paper.rect(0, 0, 200, 70, 3, 'AST'));
+
+ var annot = paper.grid(180, 0, 80, 360, 1, 4);
+ annot.push(paper.rect(0, 0, 45, 45, 22.5, '1'));
+ annot.push(paper.rect(0, 0, 45, 45, 22.5, '2'));
+ annot.push(paper.rect(0, 0, 45, 45, 22.5, '3'));
+ annot.push(paper.rect(0, 0, 45, 45, 22.5, '4'));
+ });
+ </script>
+ <p>Le processus de compilation qu'utilise <code>Hoa\Compiler\Llk</code> est
+ classique. Il commence par analyser <strong>lexicalement</strong> la donnée
+ textuelle, le mot, <ie /> à transformer notre donnée en une séquence de
+ lexèmes. L'<strong>ordre</strong> de déclaration des lexèmes est primordial
+ car l'analyseur lexical va les prendre les uns après les autres. Ensuite,
+ c'est l'analyseur <strong>syntaxique</strong> qui entre en jeu afin de
+ <strong>reconnaître</strong> notre donnée.</p>
+ <p>Si l'analyse syntaxique est un succès, nous obtenons une
+ <strong>trace</strong>. Cette trace peut être transformée en AST, pour
+ <em lang="en">Abstract Syntax Tree</em>. Cet arbre représente notre donnée
+ textuelle après analyse. Il a l'avantage de pouvoir être visité (nous
+ détaillerons plus loin), ce qui permet par exemple d'ajouter de nouvelles
+ <strong>contraintes</strong> qui ne peuvent pas être exprimées dans la
+ grammaire, comme une vérification de type.</p>
+ <p>Manipulons un peu <code>Hoa\Compiler\Llk</code>. Cette classe est un
+ <strong>assistant</strong> pour lire une grammaire au format PP facilement.
+ Elle prend en seul argument un flux en lecture vers la grammaire et retourne
+ un compilateur <code>Hoa\Compiler\Llk\Parser</code> prêt à l'emploi. Sur ce
+ compilateur, nous allons appeler la méthode
+ <code>Hoa\Compiler\Llk\Parser::parse</code> pour analyser une donnée JSON. Si
+ la donnée est correcte, nous aurons en retour un AST, sinon une exception sera
+ levée. Enfin, nous allons utiliser le visiteur
+ <code>Hoa\Compiler\Visitor\Dump</code> pour afficher notre AST :</p>
+ <pre><code class="language-php">from('Hoa')
+-> import('File.Read')
+-> import('Compiler.Llk.~')
+-> import('Compiler.Visitor.Dump');
+
+// 1. Load grammar.
+$compiler = Hoa\Compiler\Llk::load(new Hoa\File\Read('Json.pp'));
+
+// 2. Parse a data.
+$ast = $compiler->parse('{"foo": true, "bar": [null, 42]}');
+
+// 3. Dump the AST.
+$dump = new Hoa\Compiler\Visitor\Dump();
+echo $dump->visit($ast);
+
+/**
+ * Will output:
+ * > #object
+ * > > #pair
+ * > > > token(string, foo)
+ * > > > token(true, true)
+ * > > #pair
+ * > > > token(string, bar)
+ * > > > #array
+ * > > > > token(null, null)
+ * > > > > token(number, 42)
+ */</code></pre>
+ <p>Quand nous écrivons et testons une grammaire, nous allons répéter ces trois
+ tâches très <strong>régulièrement</strong>. C'est pourquoi, le script
+ <code>hoa</code> propose la commande <code>compiler:pp</code>. Cette commande
+ propose d'analyser une donnée par rapport à une grammaire et d'appliquer un
+ visiteur si besoin sur l'AST résultant. Notons que la lecture de la donnée
+ peut se faire à travers un
+ <a href="https://en.wikipedia.org/wiki/Pipeline_(Unix)"><em lang="en">pipe</em></a> :</p>
+ <pre><code class="language-shell">$ echo '[1, [1, [2, 3], 5], 8]' | hoa compiler:pp Json.pp 0 --visitor dump
+> #array
+> > token(number, 1)
+> > #array
+> > > token(number, 1)
+> > > #array
+> > > > token(number, 2)
+> > > > token(number, 3)
+> > > token(number, 5)
+> > token(number, 8)</code></pre>
+ <p>C'est un moyen pratique pour tester <strong>rapidement</strong> des données
+ par rapport à notre grammaire. Il ne faut pas hésiter à regarder l'aide de la
+ commande <code>compiler:pp</code> pour plus de détails !</p>
+ <p>Les analyses s'effectuent sur la règle <strong>racine</strong> mais nous
+ pouvons préciser une <strong>autre règle</strong> à l'aide du deuxième
+ argument de la méthode <code>Hoa\Compiler\Llk\Parser::parse</code> :</p>
+ <pre><code class="language-php">$compiler->parse('{"foo": true, "bar": [null, 42]}', 'object');</code></pre>
+ <p>Pour utiliser la règle racine, il suffit de passer <code>null</code>.</p>
+ <p>Et enfin, pour ne pas générer l'AST mais uniquement savoir si la donnée est
+ valide ou pas, nous pouvons utiliser le dernier argument de notre méthode en
+ lui passant <code>false</code> :</p>
+ <pre><code class="language-php">$valid = $compiler->parse('{"foo": true, "bar": [null, 42]}', null, false);
+var_dump($valid);
+
+/**
+ * Will output:
+ * bool(true)
+ */</code></pre>
+
+ <h4 id="Erreurs" for="main-toc">Erreurs</h4>
+
+ <p>Les erreurs de compilation sont remontées à travers des exceptions,
+ ainsi :</p>
+ <pre><code class="language-shell">$ echo '{"foo" true}' | hoa compiler:pp Json.pp 0 --visitor dump
+Uncaught exception (Hoa\Compiler\Exception\UnexpectedToken):
+Hoa\Compiler\Llk\Parser::parse(): (0) Unexpected token "true" (true) at line 1
+and column 8:
+{"foo" true}
+  ↑
+in hoa://Library/Compiler/Llk/Parser.php at line 1</code></pre>
+ <p>Plusieurs exceptions peuvent remonter selon le contexte :</p>
+ <ul>
+ <li>durant l'analyse <strong>lexicale</strong>,
+ <code>Hoa\Compiler\Exception\UnrecognizedToken</code> quand un lexème n'est
+ pas reconnu, <ie /> quand la donnée textuelle ne peut plus être découpée en
+ une séquence de lexèmes ;</li>
+ <li>durant l'analyse <strong>syntaxique</strong>,
+ <code>Hoa\Compiler\Exception\UnexpectedToken</code> quand un lexème
+ n'est pas attendu, <ie /> qu'il ne permet plus de dériver les règles de la
+ grammaire.</li>
+ </ul>
+ <p>L'exception parente est <code>Hoa\Compiler\Exception</code>.</p>
+
+ <h4 id="Nœuds" for="main-toc">Nœuds</h4>
+
+ <p>Le processus de compilation aboutit très souvent à la
+ <strong>production</strong> d'un AST. Il est important de contrôler sa
+ <strong>forme</strong>, sa <strong>taille</strong>, les données qu'il
+ <strong>contient</strong> etc. C'est pourquoi il est nécessaire de comprendre
+ la notation <code>#<em>node</em></code> car elle permet de créer des
+ <strong>nœuds</strong> dans l'AST. Une précision tout d'abord, les lexèmes
+ déclarés avec la syntaxe <code>&amp;lt;<em>token</em>></code> apparaîtront
+ dans l'arbre, alors que les autres lexèmes, déclarés avec la syntaxe
+ <code>::<em>token</em>::</code>, n'y apparaîtront pas. En effet, dans notre
+ dernier exemple, les lexèmes <code>quote_</code>, <code>brace_</code>,
+ <code>colon</code>, <code>comma</code> etc. n'apparaissent pas. Ensuite, il
+ est important de noter que les déclarations de nœuds se
+ <strong>surchargent</strong> les unes par rapport aux autres au sein d'une
+ <strong>même règle</strong>. Enfin, un nom de règle peut être précédé par
+ <code>#</code>, comme pour la règle <code>#array</code>, qui permet de définir
+ un nœud par <strong>défaut</strong>, mais il peut être surchargé. Par exemple,
+ si nous remplaçons la règle <code>array</code> par :</p>
+ <pre><code class="language-pp">#array:
+ ::bracket_:: value() ( ::comma:: value() #bigarray )* ::_bracket::</code></pre>
+ <p>Si le tableau ne contient qu'une seule valeur, le nœud s'appelera
+ <code>#array</code>, sinon il s'appelera <code>#bigarray</code> ; voyons
+ plutôt :</p>
+ <pre><code class="language-shell">$ echo '[42]' | hoa compiler:pp Json.pp 0 --visitor dump
+ > #array
+ > > token(number, 42)
+$ echo '[4, 2]' | hoa compiler:pp Json.pp 0 --visitor dump
+> #bigarray
+> > token(number, 4)
+> > token(number, 2)</code></pre>
+ <p>Bien sûr, il peut arriver qu'un nœud soit créé ou pas selon le dérivation
+ <strong>empruntée</strong> dans la règle. Le mécanisme est normalement assez
+ <strong>intuitif</strong>.</p>
+
+ <h4 id="Unification" for="main-toc">Unification</h4>
+
+ <p>Une caractéristique qu'apporte le langage PP par rapport à d'autres
+ langages de grammaires connus est la capacité d'exprimer une
+ <strong>unification</strong> de lexèmes. Imaginons la grammaire
+ suivante :</p>
+ <pre><code class="language-pp">%token quote '|"
+%token string \w+
+
+rule:
+ ::quote:: &amp;lt;string> ::quote::</code></pre>
+ <p>Les guillemets qui entourent la chaîne de caractère peuvent être de deux
+ sortes : simple, avec le symbole « <code>'</code> », ou double, avec le
+ symbole « <code>"</code> ». Ainsi, les données <code>"foo"</code> et
+ <code>'foo'</code> sont valides, mais <strong>également</strong>
+ <code>"foo'</code> et <code>'foo"</code> !</p>
+ <p>L'unification des lexèmes permet d'ajouter une <strong>contraine</strong>
+ supplémentaire sur la <strong>valeur</strong> des lexèmes à l'exécution. La
+ syntaxe est la suivante : <code><em>token</em>[<em>i</em>]</code>. La valeur
+ de <code><em>i</em></code> indique quels lexèmes vont devoir porter la même
+ valeur. Et enfin, l'unification est <strong>locale</strong> à une instance
+ d'une règle, c'est à dire qu'il n'y a pas d'unification entre les lexèmes de
+ plusieurs règles et que cela s'applique sur la règle <strong>appelée</strong>
+ uniquement. Ainsi, l'exemple devient :</p>
+ <pre><code class="language-pp">rule:
+ ::quote[0]:: &amp;lt;string> ::quote[0]::</code></pre>
+ <p>Ce qui invalide les données <code>"foo'</code> et <code>'foo"</code>.</p>
+ <p>L'unification trouve de nombreuses applications, comme par exemple unifier
+ les noms des balises ouvrantes et fermantes du
+ <a href="http://w3.org/TR/xml11/">langage XML</a>.</p>
+
+ <h3 id="Abstract_Syntax_Tree" for="main-toc"><em lang="en">Abstract Syntax
+ Tree</em></h3>
+
+ <div id="overview_ast" class="verbatim schema"></div>
+ <script>
+ Hoa.Document.onReady(function ( ) {
+
+ var paper = Hoa.Graph(Hoa.$('#overview_ast'), 800, 360);
+ var flow = paper.grid(0, 0, 800, 360, 1, 4);
+ flow.push(paper.rect(0, 0, 200, 70, 3, 'analyseur lexical').attr({opacity: .3}));
+ flow.push(paper.rect(0, 0, 200, 70, 3, 'analyseur syntaxique').attr({opacity: .3}));
+ flow.push(paper.rect(0, 0, 200, 70, 3, 'trace').attr({opacity: .3}));
+ flow.push(paper.rect(0, 0, 200, 70, 3, 'AST'));
+
+ var annot = paper.grid(180, 0, 80, 360, 1, 4);
+ annot.push(paper.rect(0, 0, 45, 45, 22.5, '1').attr({opacity: .3}));
+ annot.push(paper.rect(0, 0, 45, 45, 22.5, '2').attr({opacity: .3}));
+ annot.push(paper.rect(0, 0, 45, 45, 22.5, '3').attr({opacity: .3}));
+ annot.push(paper.rect(0, 0, 45, 45, 22.5, '4'));
+ });
+ </script>
+ <p>Un arbre <strong>syntaxique abstrait</strong> représente la donnée
+ textuelle sous forme <strong>structurelle</strong>. Chaque
+ <strong>nœud</strong> de cet arbre est représenté par la classe
+ <code>Hoa\Compiler\Llk\TreeNode</code>. Parmis les méthodes utiles, nous
+ trouvons :</p>
+ <ul>
+ <li><code>getId</code> pour obtenir l'identifiant du nœud ;</li>
+ <li><code>getValueToken</code> pour obtenir le nom du lexème ;</li>
+ <li><code>getValueValue</code> pour obtenir la valeur du lexème ;</li>
+ <li><code>isToken</code> si le nœud représente un lexème ;</li>
+ <li><code>getChild(<em>$i</em>)</code> pour obtenir le
+ <code><em>$i</em></code>-ème enfant d'un nœud ;</li>
+ <li><code>getChildren</code> pour obtenir tous les nœuds ;</li>
+ <li><code>getChildrenNumber</code> pour connaître le nombre d'enfants ;</li>
+ <li><code>getData</code> pour obtenir une référence vers un tableau de
+ données ;</li>
+ <li><code>accept</code> pour appliquer un visiteur.</li>
+ </ul>
+ <p>Les visiteurs sont le moyen le plus pratique pour
+ <strong>parcourir</strong> un AST. En guise d'exemple, nous allons écrire le
+ visiteur <code>PrettyPrinter</code> qui va réécrire une donnée JSON avec notre
+ propre convention (espacements, retours à la ligne etc.). Un visiteur doit
+ implémenter l'interface <code>Hoa\Visitor\Visit</code> et n'aura qu'une seule
+ méthode à écrire : <code>visit</code> qui prend trois arguments :
+ l'élément et deux arguments accessoires (en copie et en référence). Voyons
+ plutôt :</p>
+ <pre><code class="language-php">class PrettyPrinter implements Hoa\Visitor\Visit {
+
+ public function visit ( Hoa\Visitor\Element $element,
+ &amp;amp;$handle = null, $eldnah = null ) {
+
+ static $i = 0;
+ static $indent = ' ';
+
+ // One behaviour per node in the AST.
+ switch($element->getId()) {
+
+ // Object: { … }.
+ case '#object':
+ echo '{', "\n";
+ ++$i;
+
+ foreach($element->getChildren() as $e => $child) {
+
+ if(0 &amp;lt; $e)
+ echo ',', "\n";
+
+ echo str_repeat($indent, $i);
+ $child->accept($this, $handle, $eldnah);
+ }
+
+ echo "\n", str_repeat($indent, --$i), '}';
+ break;
+
+ // Array: [ … ].
+ case '#array':
+ echo '[', "\n";
+ ++$i;
+
+ foreach($element->getChildren() as $e => $child) {
+
+ if(0 &amp;lt; $e)
+ echo ',', "\n";
+
+ echo str_repeat($indent, $i);
+ $child->accept($this, $handle, $eldnah);
+ }
+
+ echo "\n", str_repeat($indent, --$i), ']';
+ break;
+
+ // Pair: "…": ….
+ case '#pair':
+ echo $element->getChild(0)->accept($this, $handle, $eldnah),
+ ': ',
+ $element->getChild(1)->accept($this, $handle, $eldnah);
+ break;
+
+ // Many tokens.
+ case 'token':
+ switch($element->getValueToken()) {
+
+ // String: "…".
+ case 'string':
+ echo '"', $element->getValueValue(), '"';
+ break;
+
+ // Booleans.
+ case 'true':
+ case 'false':
+
+ // Null.
+ case 'null':
+
+ // Number.
+ case 'number':
+ echo $element->getValueValue();
+ break;
+ }
+ break;
+ }
+ }
+}</code></pre>
+ <p>Nous allons voir tout de suite un exemple d'utilisation :</p>
+ <pre><code class="language-php">$compiler = Hoa\Compiler\Llk::load(new Hoa\File\Read('Json.pp'));
+$ast = $compiler->parse('{"foo": true, "bar": [null, 42]}');
+$prettyPrint = new PrettyPrinter();
+echo $prettyPrint->visit($ast);
+
+/**
+ * Will output:
+ * {
+ * "foo": true,
+ * "bar": [
+ * null,
+ * 42
+ * ]
+ * }
+ */</code></pre>
+ <p>La méthode <code>getData</code> est très pratique pour
+ <strong>stocker</strong> des données susceptibles d'être
+ <strong>réutilisées</strong>, par exemple d'un visiteur à l'autre. Cette
+ méthode retourne une <strong>référence</strong> sur un tableau ; ainsi :</p>
+ <pre><code class="language-php">$data = $element->getData();
+
+if(!isset($data['previousComputing']))
+ throw new Exception('Need a previous computing.', 0);
+
+$previous = $data['previousComputing'];</code></pre>
+ <p>Il est courant d'utiliser un visiteur par <strong>contrainte</strong> :
+ vérifiation des symboles, vérification de types etc. Certains peuvent laisser
+ des données nécessaires pour le suivant. La méthode <code>getData</code>
+ n'impose aucune structuration des données, elle propose uniquement un accès à
+ un tableau. Ce sera à vous de faire le reste.</p>
+ <p>Utiliser la classe <code>Hoa\Compiler\Llk\TreeNode</code> est vraiment
+ <strong>trivial</strong> et nous l'utiliserons la plupart du temps avec un
+ visiteur.</p>
+
+ <h3 id="Traces" for="main-toc">Traces</h3>
+
+ <div id="overview_trace" class="verbatim schema"></div>
+ <script>
+ Hoa.Document.onReady(function ( ) {
+
+ var paper = Hoa.Graph(Hoa.$('#overview_trace'), 800, 360);
+ var flow = paper.grid(0, 0, 800, 360, 1, 4);
+ flow.push(paper.rect(0, 0, 200, 70, 3, 'analyseur lexical').attr({opacity: .3}));
+ flow.push(paper.rect(0, 0, 200, 70, 3, 'analyseur syntaxique').attr({opacity: .3}));
+ flow.push(paper.rect(0, 0, 200, 70, 3, 'trace'));
+ flow.push(paper.rect(0, 0, 200, 70, 3, 'AST').attr({opacity: .3}));
+
+ var annot = paper.grid(180, 0, 80, 360, 1, 4);
+ annot.push(paper.rect(0, 0, 45, 45, 22.5, '1').attr({opacity: .3}));
+ annot.push(paper.rect(0, 0, 45, 45, 22.5, '2').attr({opacity: .3}));
+ annot.push(paper.rect(0, 0, 45, 45, 22.5, '3'));
+ annot.push(paper.rect(0, 0, 45, 45, 22.5, '4').attr({opacity: .3}));
+ });
+ </script>
+ <p>Le compilateur LL(<em>k</em>) que propose Hoa est clairement découpé en
+ plusieurs <strong>couches</strong>. Chaque couche est exploitable pour
+ permettre une modularité maximum. Quand la grammaire est traduite en « règles
+ machines » et que les analyseurs lexical et syntaxique ont validé une donnée,
+ il en résulte une <strong>trace</strong>. Cette trace est un tableau composé
+ de trois classes seulement :</p>
+ <ul>
+ <li><code>Hoa\Compiler\Llk\Rule\Entry</code> quand l'analyseur syntaxique
+ est rentré dans une règle ;</li>
+ <li><code>Hoa\Compiler\Llk\Rule\Ekzit</code> quand l'analyseur syntaxique
+ est sorti d'une règle ;</li>
+ <li><code>Hoa\Compiler\Llk\Rule\Token</code> quand l'analyseur syntaxique a
+ rencontré un lexème.</li>
+ </ul>
+ <p>Nous pouvons l'obtenir grâce à la méthode
+ <code>Hoa\Compiler\Llk\Parser::getTrace</code>. Pour bien comprendre cette
+ trace, nous allons commencer par un exemple :</p>
+ <pre><code class="language-php">$compiler = Hoa\Compiler\Llk::load(new Hoa\File\Read('Json.pp'));
+$ast = $compiler->parse('{"foo": true, "bar": [null, 42]}');
+$i = 0;
+
+foreach($compiler->getTrace() as $element)
+ if($element instanceof Hoa\Compiler\Llk\Rule\Entry)
+ echo str_repeat('> ', ++$i), 'enter ', $element->getRule(), "\n";
+ elseif($element instanceof Hoa\Compiler\Llk\Rule\Token)
+ echo str_repeat(' ', $i + 1), 'token ', $element->getTokenName(),
+ ', consumed ', $element->getValue(), "\n";
+ else
+ echo str_repeat('&amp;lt; ', $i--), 'ekzit ', $element->getRule(), "\n";
+
+/**
+ * Will output:
+ * > enter value
+ * > > enter object
+ * token brace_, consumed {
+ * > > > enter pair
+ * > > > > enter string
+ * token quote_, consumed "
+ * token string, consumed foo
+ * token _quote, consumed "
+ * &amp;lt; &amp;lt; &amp;lt; &amp;lt; ekzit string
+ * token colon, consumed :
+ * > > > > enter value
+ * token true, consumed true
+ * &amp;lt; &amp;lt; &amp;lt; &amp;lt; ekzit value
+ * &amp;lt; &amp;lt; &amp;lt; ekzit pair
+ * > > > enter 13
+ * > > > > enter 12
+ * token comma, consumed ,
+ * > > > > > enter pair
+ * > > > > > > enter string
+ * token quote_, consumed "
+ * token string, consumed bar
+ * token _quote, consumed "
+ * &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; ekzit string
+ * token colon, consumed :
+ * > > > > > > enter value
+ * > > > > > > > enter array
+ * token bracket_, consumed [
+ * > > > > > > > > enter value
+ * token null, consumed null
+ * &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; ekzit value
+ * > > > > > > > > enter 21
+ * > > > > > > > > > enter 20
+ * token comma, consumed ,
+ * > > > > > > > > > > enter value
+ * token number, consumed 42
+ * &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; ekzit value
+ * &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; ekzit 20
+ * &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; ekzit 21
+ * token _bracket, consumed ]
+ * &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; ekzit array
+ * &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; ekzit value
+ * &amp;lt; &amp;lt; &amp;lt; &amp;lt; &amp;lt; ekzit pair
+ * &amp;lt; &amp;lt; &amp;lt; &amp;lt; ekzit 12
+ * &amp;lt; &amp;lt; &amp;lt; ekzit 13
+ * token _brace, consumed }
+ * &amp;lt; &amp;lt; ekzit object
+ * &amp;lt; ekzit value
+ */</code></pre>
+ <p>Cet exemple nous révèle plusieurs choses. Tout d'abord, les informations
+ que nous donne la trace peuvent être utiles : si nous sommes sur une règle,
+ nous avons son <strong>nom</strong> (avec la méthode <code>getRule</code>), et
+ si nous sommes sur un lexème, nous avons son <strong>nom</strong> (avec la
+ méthode <code>getTokenName</code>), sa <strong>représentation</strong> (sous
+ la forme d'une PCRE, avec la méthode <code>getRepresentation</code>), sa
+ <strong>valeur</strong> (avec la méthode <code>getValue</code>), si c'est un
+ nœud à <strong>conserver</strong> dans l'AST (avec la méthode
+ <code>isKept</code>) et son index d'<strong>unification</strong> s'il existe
+ (avec la méthode <code>getUnificationIndex</code>). Bien sûr, tout ceci est
+ modifiable, ce qui peut influencer la construction de l'AST qui est le
+ processus (optionnel) suivant.</p>
+ <p>Ensuite, nous remarquons que parfois nous entrons dans une règle qui existe
+ dans la grammaire, comme <code>object</code>, <code>pair</code>,
+ <code>value</code> etc., et parfois nous entrons dans une règle
+ <strong>numérique</strong>, comme <code>13</code>, <code>12</code>,
+ <code>21</code>, <code>20</code> etc. Quand la grammaire est interprétée pour
+ être transformée en « règles machines », chacune de ses règles est
+ <strong>linéarisée</strong> selon les opérateurs du langage PP :</p>
+ <ul>
+ <li><code>Hoa\Compiler\Llk\Rule\Choice</code> pour une disjonction ;</li>
+ <li><code>Hoa\Compiler\Llk\Rule\Concatenation</code> pour une
+ concaténation ;</li>
+ <li><code>Hoa\Compiler\Llk\Rule\Repetition</code> pour une répétition ;</li>
+ <li><code>Hoa\Compiler\Llk\Rule\Token</code> pour un lexème (déjà vu
+ précédemment).</li>
+ </ul>
+ <p>Toutes les règles sous ce format sont accessibles à travers la méthode
+ <code>Hoa\Compiler\Llk\Parser::getRules</code> sous la forme d'un tableau.
+ Nous allons afficher toutes les règles <strong>accessibles</strong> depuis la
+ règle racine pour mieux comprendre :</p>
+ <pre><code class="language-php">$compiler = Hoa\Compiler\Llk::load(new Hoa\File\Read('Json.pp'));
+$ast = $compiler->parse('{"foo": true, "bar": [null, 42]}');
+
+// 1. Get all rules.
+$rules = $compiler->getRules();
+
+// 2. Start with the root rule.
+$stack = array($compiler->getRootRule() => true);
+
+while(false !== current($stack)) {
+
+ $rule = key($stack);
+ next($stack);
+ echo "\n", '"', $rule, '" is a ',
+ strtolower(substr(get_class($rules[$rule]), 22));
+
+ $subrules = $rules[$rule]->getContent();
+
+ // 3a. Token.
+ if(null === $subrules)
+ continue;
+
+ echo ' of rules: ';
+
+ // 3b. Other rules.
+ foreach((array) $rules[$rule]->getContent() as $subrule) {
+
+ if(!array_key_exists($subrule, $stack))
+ // 4. Unshift new rules to print.
+ $stack[$subrule] = true;
+
+ echo $subrule, ' ';
+ }
+}
+
+/**
+ * Will output:
+ * "value" is a choice of rules: 1 2 3 string object array number
+ * "1" is a token
+ * "2" is a token
+ * "3" is a token
+ * "string" is a concatenation of rules: 5 6 7
+ * "object" is a concatenation of rules: 10 pair 13 14
+ * "array" is a concatenation of rules: 18 value 21 22
+ * "number" is a token
+ * "5" is a token
+ * "6" is a token
+ * "7" is a token
+ * "10" is a token
+ * "pair" is a concatenation of rules: string 16 value
+ * "13" is a repetition of rules: 12
+ * "14" is a token
+ * "18" is a token
+ * "21" is a repetition of rules: 20
+ * "22" is a token
+ * "16" is a token
+ * "12" is a concatenation of rules: 11 pair
+ * "20" is a concatenation of rules: 19 value
+ * "11" is a token
+ * "19" is a token
+ */</code></pre>
+ <p>Si nous lisons la règle <code>object</code>, nous savons que c'est la
+ concaténation des règles <code>10</code>, <code>pair</code>, <code>13</code>
+ et <code>14</code>. <code>10</code> est un lexème, <code>pair</code> est la
+ concaténation des règles <code>string</code>, <code>16</code> et
+ <code>value</code>, et ainsi de suite. La grammaire initiale est transformée
+ pour être sous sa forme la plus <strong>réduite</strong> possible. Ceci permet
+ de <strong>raisonner</strong> beaucoup plus <strong>facilement</strong> et
+ <strong>rapidement</strong> sur les règles. En effet, les traitements sur la
+ grammaire ne sont pas réservés aux AST. À l'étape précédente, avec la trace,
+ nous pouvons déjà effectuer des traitements.</p>
+
+ <h3 id="Generation" for="main-toc">Génération</h3>
+
+ <p>Une grammaire peut être utile pour deux objectifs :
+ <strong>valider</strong> une donnée (si nous la voyons comme un automate) ou
+ <strong>générer</strong> des données. Jusqu'à présent, nous avons vu comment
+ valider une donnée à travers plusieurs processus :
+ <strong>préparation</strong> de notre compilateur, exécution des
+ <strong>analyseurs</strong> lexical et syntaxique résultant sur une
+ <strong>trace</strong>, transformation de la trace vers un
+ <strong>AST</strong> pour enfin <strong>visiter</strong> cet arbre. Mais nous
+ pouvons nous arrêter à la première étape, la préparation de notre compilateur,
+ pour exploiter les règles afin de générer une donnée qui sera valide par
+ rapport à notre grammaire.</p>
+ <p><code>Hoa\Compiler\Llk\Sampler</code> propose trois algorithmes de
+ <strong>générations</strong> de données :</p>
+ <ul>
+ <li>génération aléatoire et uniforme ;</li>
+ <li>génération exhaustive bornée ;</li>
+ <li>génération basée sur la couverture.</li>
+ </ul>
+ <p>Pourquoi proposer trois algorithmes ? Parce qu'il est illusoire de penser
+ qu'un seul algorithme peut suffir aux <strong>nombreux</strong> contextes
+ d'utilisations. Chacun répond à des besoins différents, nous l'expliquerons
+ plus loin.</p>
+ <p>Générer une donnée à partir d'une grammaire se fait en <strong>deux
+ étapes</strong> :</p>
+ <ol>
+ <li>générer des valeurs pour les <strong>lexèmes</strong> afin d'avoir des données
+ brutes ;</li>
+ <li>générer un <strong>chemin</strong> dans les règles de la grammaire.</li>
+ </ol>
+ <p>Un chemin est équivalent à une dérivation, le vocabulaire est différent
+ selon notre objectif : validation ou génération.</p>
+
+ <h4 id="Generation_isotropique_de_lexemes" for="main-toc">Génération
+ isotropique de lexèmes</h4>
+
+ <p>Pour générer les valeurs des lexèmes, peu importe l'algorithme utilisé, il
+ doit être <strong>rapide</strong>. Nous allons utiliser un parcours dit
+ <strong>isotrope</strong>. Nous partons d'une règle et nous avançons
+ uniquement à partir de choix <strong>aléatoires</strong> et <strong>uniformes
+ localement</strong> (uniquement pour ce choix). Par exemple si nous avons une
+ disjonction entre trois sous-règles, nous allons tirer aléatoirement et
+ uniformément entre 1 et 3. Si nous avons une concaténation, nous allons juste
+ concaténer chaque partie. Et enfin, une répétition n'est rien d'autre qu'une
+ disjonction de concaténation : en effet, <code><em>e</em>{1,3</code>} est
+ strictement équivalent à <code><em>e</em> | <em>ee</em> | <em>eee</em></code>.
+ Illustrons plutôt :</p>
+ <pre><code>([ae]+|[x-z]!){1,3} <em>repeat <em>[ae]+|[x-z]!</em> 2 times</em>
+→ ([ae]+|[x-z]!)([ae]+|[x-z]!) <em>choose between <em>[ae]+</em> and <em>[x-z]!</em></em>
+→ ([ae]+)([ae]+|[x-z]!) <em>repeat <code>ae</code> 2 times</em>
+→ [ae][ae]([ae]+|[x-z]!) <em>choose between <em>a</em> and <em>e</em></em>
+→ e[ae]([ae]+|[x-z]!) <em>again</em>
+→ ea([ae]+|[x-z]!) <em>choose between <em>[ae]+</em> and <em>[x-z]!</em></em>
+→ ea([x-z]!) <em>choose between <em>x</em>, <em>y</em> and <em>z</em></em>
+→ eay!</code></pre>
+ <p>Cette génération est <strong>naïve</strong> mais ce n'est pas important. Ce
+ qui est vraiment important est la génération des chemins dans les règles, ou
+ autrement dit, la génération des <strong>séquences de lexèmes</strong>.</p>
+
+ <h4 id="Generation_aleatoire_et_uniforme" for="main-toc">Génération aléatoire
+ et uniforme</h4>
+
+ <p>Le premier algorithme est celui de la génération <strong>aléatoire</strong>
+ et <strong>uniforme</strong>. Cet algorithme est utile si nous voulons générer
+ des séquences de lexèmes de <strong>taille <em>n</em> fixe</strong> et avec
+ une <strong>uniformité</strong> non pas locale (comme avec un parcours
+ isotrope) mais sur l'<strong>ensemble</strong> de toutes les séquences
+ possibles. Succinctement, l'algorithme travaille en deux étapes :
+ <strong>pré-calcul</strong> (une seule fois par taille) puis
+ <strong>génération</strong>. Le pré-calcul est une étape
+ <strong>automatique</strong> et calcule le <strong>nombre</strong> de
+ séquences et sous-séquences possibles de taille <em>n</em>. Cette étape aide
+ au calcul de <strong>fonctions de distributions</strong> pour
+ <strong>guider</strong> la génération des séquences de lexèmes finales.</p>
+ <p>Nous allons générer 10 données aléatoires de taille 7, c'est à dire
+ composées de 7 lexèmes. Pour cela, nous allons utiliser la classe
+ <code>Hoa\Compiler\Llk\Sampler\Uniform</code> qui prend en premier argument
+ notre grammaire, en deuxième le générateur de valeurs de lexèmes (ici
+ <code>Hoa\Regex\Visitor\Isototropic</code>) et enfin la taille :</p>
+ <pre><code class="language-php">from('Hoa')
+-> import('File.Read')
+-> import('Compiler.Llk.~')
+-> import('Compiler.Llk.Sampler.Uniform')
+-> import('Math.Sampler.Random')
+-> import('Regex.Visitor.Isotropic');
+
+$sampler = new Hoa\Compiler\Llk\Sampler\Uniform(
+ // Grammar.
+ Hoa\Compiler\Llk::load(new Hoa\File\Read('Json.pp')),
+ // Token sampler.
+ new Hoa\Regex\Visitor\Isotropic(new Hoa\Math\Sampler\Random()),
+ // Length.
+ 7
+);
+
+for($i = 0; $i &amp;lt; 10; ++$i)
+ echo $i, ' => ', $sampler->uniform(), "\n";
+
+/**
+ * Will output:
+ * 0 => [ false , null , null ]
+ * 1 => [ " l " , null ]
+ * 2 => [ [ true ] , true ]
+ * 3 => [ [ [ 4435 ] ] ]
+ * 4 => [ [ [ 9366 ] ] ]
+ * 5 => [ true , false , null ]
+ * 6 => { " |h&amp;lt;# " : false }
+ * 7 => [ [ [ false ] ] ]
+ * 8 => [ false , true , 7 ]
+ * 9 => [ false , 5 , 79 ]
+ */</code></pre>
+ <p>Nous pouvons redéfinir la taille avec la méthode
+ <code>Hoa\Compiler\Llk\Sampler\Uniform::setLength</code>. Nous aurons
+ peut-être remarqué que certains opérateurs de répétition n'ont pas de bornes
+ supérieures, comme <code>+</code> ou <code>*</code> ; dans ce cas, nous la
+ définissons à <em>n</em>.</p>
+
+ <h4 id="Generation_exhaustive_bornee" for="main-toc">Génération exhaustive
+ bornée</h4>
+
+ <p>Le deuxième algorithme est celui de la génération <strong>exhaustive
+ bornée</strong>. Cet algorithme génère <strong>toutes</strong> les séquences
+ (c'est le côté exhaustif) de lexèmes de taille 1 <strong>jusqu'à</strong>
+ <em>n</em> (c'est le caractère borné). Un aspect très intéressant de cet
+ algorithme est que l'exhaustivité est une forme de <strong>preuve</strong> !
+ L'algorithme fonctionne comme un itérateur et est très simple à utiliser :</p>
+ <pre><code class="language-php">from('Hoa')
+-> import('Compiler.Llk.Sampler.BoundedExhaustive');
+
+$sampler = new Hoa\Compiler\Llk\Sampler\BoundedExhaustive(
+ // Grammar.
+ Hoa\Compiler\Llk::load(new Hoa\File\Read('Json.pp')),
+ // Token sampler.
+ new Hoa\Regex\Visitor\Isotropic(new Hoa\Math\Sampler\Random()),
+ // Length.
+ 7
+);
+
+foreach($sampler as $i => $data)
+ echo $i, ' => ', $data, "\n";
+
+/**
+ * Will output:
+ * 0 => true
+ * 1 => false
+ * 2 => null
+ * 3 => " 8u2 "
+ * 4 => { " ,M@aj{ " : true }
+ * 5 => { " x`|V " : false }
+ * 6 => { " NttB " : null }
+ * 7 => { " eJWwA " : 0 }
+ * 8 => [ true ]
+ * 9 => [ true , true ]
+ * 10 => [ true , true , true ]
+ * 11 => [ true , true , false ]
+ * 12 => [ true , true , null ]
+ * 13 => [ true , true , 32 ]
+ * 14 => [ true , false ]
+ * 15 => [ true , false , true ]
+ * 16 => [ true , false , false ]
+ * 17 => [ true , false , null ]
+ * 18 => [ true , false , 729 ]
+ * 19 => [ true , null ]
+ * 20 => [ true , null , true ]
+ * 21 => [ true , null , false ]
+ * …
+ * 157 => [ 780 , 01559 , 32 ]
+ * 158 => 344
+ */</code></pre>
+ <p><em>A l'instar</em> de l'algorithme précédent, nous pouvons redéfinir la
+ borne maximum avec la méthode
+ <code>Hoa\Compiler\Llk\Sampler\BoundedExhaustive::setLength</code>. Et les
+ opérateurs de répétition sans borne supérieure utilisent <em>n</em>.</p>
+
+ <h4 id="Generation_basee_sur_la_couverture" for="main-toc">Génération basée
+ sur la couverture</h4>
+
+ <p>Le dernier algorithme est celui de la génération <strong>basée sur la
+ couverture</strong>. Cet algorithme réduit l'<strong>explosion
+ combinatoire</strong> rencontrée avec l'algorithme précédent mais l'objectif
+ est tout autre : il va générer des séquences de lexèmes qui vont
+ « <strong>activer</strong> » toutes les <strong>branches</strong> des règles
+ de la grammaire. Une règle est dite couverte si et seulement si ses
+ sous-règles sont toutes couvertes, et un lexème est dit couvert s'il a été
+ utilisé dans une séquence. Pour assurer une <strong>diversité</strong> dans
+ les séquences produites, les points de choix entre des sous-règles non
+ couvertes sont résolus par tirages <strong>aléatoires</strong>. L'algorithme
+ fonctionne également comme un itérateur :</p>
+ <pre><code class="language-php">from('Hoa')
+-> import('Compiler.Llk.Sampler.Coverage');
+
+$sampler = new Hoa\Compiler\Llk\Sampler\Coverage(
+ // Grammar.
+ Hoa\Compiler\Llk::load(new Hoa\File\Read('Json.pp')),
+ // Token sampler.
+ new Hoa\Regex\Visitor\Isotropic(new Hoa\Math\Sampler\Random())
+);
+
+foreach($sampler as $i => $data)
+ echo $i, ' => ', $data, "\n";
+
+/**
+ * Will output:
+ * 0 => true
+ * 1 => { " )o?bz " : null , " %3W) " : [ false , 130 , " 6 " ] }
+ * 2 => [ { " ny " : true } ]
+ * 3 => { " Ne;[3 " : [ true , true ] , " th: " : true , " C[8} " : true }
+ */</code></pre>
+ <p>Pour éviter l'explosion combinatoire et assurer la
+ <strong>termination</strong> de l'algorithme, nous utilisons
+ l'<strong>heuristique</strong> suivante sur les opérateurs de
+ <strong>répétition</strong> : <code>*</code> répétera <code>0</code>,
+ <code>1</code> et <code>2</code> fois, <code>+</code> répétera <code>1</code>
+ et <code>2</code> fois, et enfin <code>{<em>x</em>,<em>y</em>}, </code>
+ répétera <code><em>x</em></code>, <code><em>x</em> + 1</code>,
+ <code><em>y</em> - 1</code> et <code><em>y</em></code> fois. Cette heuristique
+ trouve ses origines dans le test aux <strong>limites</strong>.</p>
+ <p>Nous remarquons dans notre exemple que 4 données sont générées et suffisent
+ à <strong>couvrir</strong> l'ensemble de notre grammaire !</p>
+
+ <h4 id="Comparaison_entre_les_algorithmes" for="main-toc">Comparaison entre
+ les algorithmes</h4>
+
+ <p>Voici quelques <strong>indices</strong> pour savoir quand utiliser tel ou
+ tel autre algorithme.</p>
+ <dl>
+ <dt>Génération aléatoire et uniforme :</dt>
+ <dd><ul>
+ <li data-item="+">rapide pour des petites données, grande diversité dans
+ les données et taille fixe ;</li>
+ <li data-item="-">la phase de pré-calcul est exponentielle et donc
+ longue bien que, ensuite, la génération soit très rapide.</li>
+ </ul></dd>
+ <dt>Génération exhaustive bornée :</dt>
+ <dd><ul>
+ <li data-item="+">rapide pour des petites données et l'exhaustivité est
+ efficace ;</li>
+ <li data-item="-">nombre exponentiel de données.</li>
+ </ul></dd>
+ <dt>Génération basée sur la couverture :</dt>
+ <dd><ul>
+ <li data-item="+">rapide pour des données de taille moyenne ou grande,
+ et diversité des données ;</li>
+ <li data-item="-">ne considère pas de taille.</li>
+ </ul></dd>
+ </dl>
+
+ <h2 id="Compilateur_de_compilateurs_LL1" for="main-toc">Compilateur de
+ compilateurs LL(1)</h2>
+
+ <p>La documentation pour le compilateur LL(1), à travers la classe
+ <code>Hoa\Compiler\Ll1</code> n'est pas encore écrite. L'objectif est
+ différent de <code>Hoa\Compiler\Llk</code> : il n'existe pas de langage
+ intermédiaire, les automates sont codés en dur avec des tableaux et ce type de
+ compilateurs est orienté haute performance. C'est pourquoi son comportement
+ est <strong>monolothique</strong>.</p>
+
+ <h2 id="Conclusion" for="main-toc">Conclusion</h2>
+
+ <p><code>Hoa\Compiler</code> propose deux <strong>compilateurs de
+ compilateurs</strong> : <code>Hoa\Compiler\Llk</code> et
+ <code>Hoa\Compiler\Ll1</code>, afin de <strong>valider</strong> des données.
+ Le <strong>langage PP</strong> permet d'écrire des <strong>grammaires
+ algébriques</strong> de manière <strong>simple</strong> et
+ <strong>naturelle</strong>. Le compilateur de compilateurs LL(<em>k</em>) est
+ découpé en <strong>processus distincts</strong> ce qui le rend très
+ <em lang="en">hackable</em>. Enfin, différents algorithmes permettent de
+ <strong>générer</strong> des données à partir d'une grammaire selon le
+ contexte d'utilisation.</p>
+
+</yield>
+</overlay>