1<?xml version="1.0" encoding="utf-8"?>
2
3<overlay xmlns="http://hoa-project.net/xyl/xylophone">
4<yield id="chapter">
5
6  <p>Les <strong>compilateurs</strong> permettent d'<strong>analyser</strong> et
7  <strong>manipuler</strong> des données <strong>textuelles</strong>. Leurs
8  applications sont très nombreuses. <code>Hoa\Compiler</code> propose de
9  manipuler plusieurs compilateurs selon les besoins.</p>
10
11  <h2 id="Table_of_contents">Table des matières</h2>
12
13  <tableofcontents id="main-toc" />
14
15  <h2 id="Introduction" for="main-toc">Introduction</h2>
16
17  <blockquote cite="https://fr.wikipedia.org/wiki/Nicolas_Boileau">Ce qui se
18  conçoit bien s'énonce clairement, et les mots pour le dire viennent
19  aisément.</blockquote>
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
23  lisons et écrivons dans plusieurs langages au quotidien, et certains de ces
24  langages sont <strong>compris</strong> par des <strong>machines</strong>.
25  Cette opération est possible grâce aux <strong>compilateurs</strong>.</p>
26  <p>La <a href="https://fr.wikipedia.org/wiki/Théorie_des_langages">théorie des
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
30  bien comprendre tous ces concepts. Toutefois, nous allons essayer de
31  vulgariser un minimum pour permettre une utilisation correcte de
32  <code>Hoa\Compiler</code>.</p>
33
34  <h3 id="Language_and_grammar" for="main-toc">Langage et grammaire</h3>
35
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).
41  Les séquences de lexèmes représentant les mots sont construites avec des
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
47  règles suivantes :</p>
48  <pre><code>    exp ::= exp + exp
49          | nombre
50 nombre ::= chiffre nombre
51          | chiffre
52chiffre ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9</code></pre>
53  <p>Le mot que nous voulons reconnaître est <code>7 + 35</code>. La règle
54  racine est <code><em>exp</em></code>. Si nous la dérivons (de gauche à droite
55  et de haut en bas, ou <em lang="en">left-to-right</em> et
56  <em lang="en">top-to-bottom</em> en anglais), nous pouvons avoir
57  <code><em>exp</em> + <em>exp</em></code> ou <code><em>nombre</em></code> (la
58  <strong>disjonction</strong>, <em>i.e.</em> le « ou », est représentée par le
59  symbole « <code>|</code> ») :</p>
60  <pre><code>exp + exp | nombre
61→ exp + exp
62→ ( exp + exp | nombre ) + exp
63→ nombre + exp
64→ ( chiffre nombre | chiffre ) + exp</code></pre>
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>
67  <pre><code>…
68→ ( chiffre nombre | chiffre ) + exp
69→ chiffre + exp
70→ ( 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ) + exp
71→ 7 + exp
72→ 7 + ( exp + exp | nombre )
73→ 7 + nombre
74→ 7 + ( chiffre nombre | chiffre )
75→ 7 + chiffre nombre
76→ 7 + ( 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ) nombre
77→ 7 + 3 nombre
78→ 7 + 3 ( chiffre nombre | chiffre )
79→ 7 + 3 chiffre
80→ 7 + 3 ( 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 )
81→ 7 + 3 5</code></pre>
82  <p>Une dériviation existe bel et bien pour reconnaître le mot <code>7 +
83  35</code>, c'est donc un mot valide pour ces règles.</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>
86  <p>Toutefois, il existe plusieurs catégories de grammaires. C'est en 1956 qu'a
87  été formulée la
88  <a href="https://fr.wikipedia.org/wiki/Hi%C3%A9rarchie_de_Chomsky">hiérarchie
89  de Chomsky</a>, classant les grammaires en quatre
90  <strong>niveaux</strong> :</p>
91  <ol>
92    <li>grammaires <strong>générales</strong>, ou <em lang="en">unrestricted
93    grammars</em>, reconnaissant les langages dits de Turing, aucune
94    restriction n'est imposée aux règles ;</li>
95    <li>grammaires <strong>contextuelles</strong>, ou
96    <em lang="en">context-sensitive grammars</em>, reconnaissant les langages
97    contextuels ;</li>
98    <li>grammaires <strong>algébriques</strong>, ou <em lang="en">context-free
99    grammars</em>, reconnaissant les langages algébriques, basés sur les
100    automates à pile ;</li>
101    <li>grammaires <strong>régulières</strong>, ou <em lang="en">regular
102    grammars</em>, reconnaissant les langages réguliers.</li>
103  </ol>
104  <p>Chaque niveau reconnait le niveau suivant. <code>Hoa\Compiler</code> ne
105  traite que les langages définis par les grammaires de niveau 3 et 4. Pour
106  donner rapidement une idée, les grammaires régulières peuvent s'apparenter aux
107  <a href="https://fr.wikipedia.org/wiki/Expression_régulière">expressions
108  régulières</a> (comme les <a href="http://pcre.org/">PCRE</a>), bien connues
109  des développeurs. Mais les grammaires régulières ne permettent pas par exemple
110  de reconnaître des <strong>couples de symboles</strong> (comme des
111  parenthèses, des accolades ou des guillemets), alors que les grammaires
112  algébriques le permettent (grâce à la notion de piles de lexèmes).</p>
113
114  <h3 id="Matching_words" for="main-toc">Reconnaissance de mots</h3>
115
116  <div id="parsers" class="schema"></div>
117  <script>
118  Hoa.Document.onReady(function ( ) {
119
120      var paper    = Hoa.Graph(Hoa.$('#parsers'), 800, 180);
121      var grid     = paper.grid(0, 0, 800, 180, 5, 2);
122      var word     = grid.push(paper.rect(0, 0, 140, 80, 3, 'mot'), 0, 0);
123      var sequence = grid.push(paper.rect(0, 0, 140, 80, 3, 'séquence'), 2, 0);
124      var trace    = grid.push(paper.rect(0, 0, 140, 80, 3, 'résultat'), 4, 0);
125      grid.push(paper.rect(0, 0, 140, 50, 3, 'abcdef'), 0, 1);
126      grid.push(paper.rect(0, 0, 380, 50, 3, '[[a ⟼ …], [bc ⟼ …], [d ⟼ …], [ef ⟼ …]]'), 2, 1);
127      grid.push(paper.rect(0, 0, 140, 50, 3, 'valide/invalide'), 4, 1);
128
129      paper.link.between(word, sequence, 'analyseur lexical');
130      paper.link.between(sequence, trace, 'analyseur syntaxique');
131  });
132  </script>
133  <p>En général, le processus de compilation débute par deux
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>.
137  Cette séquence sera ensuite utilisée par l'analyseur syntaxique afin de
138  vérifier que le mot <strong>appartient</strong> au langage.</p>
139  <p>Selon la grammaire, la reconnaissance ne se fera pas de la même manière,
140  mais le principe reste identique : prendre les lexèmes les uns après les
141  autres dans la séquence et vérifier qu'ils permettent
142  d'<strong>avancer</strong> dans la <strong>dérivation</strong> des règles de
143  notre grammaire.</p>
144  <p>Les analyses syntaxiques sont aussi classées en
145  <strong>catégories</strong> : LL, LR, LALR etc. <code>Hoa\Compiler</code> ne
146  propose que des analyseurs syntaxiques LL, pour <em lang="en">Left-to-right
147  Leftmost derivation</em>, <em>i.e.</em> de la plus haute règle vers la plus
148  profonde, et les règles sont dérivées de la gauche vers la droite. Là encore,
149  il existe des sous-catégories, dont deux que traite
150  <code>Hoa\Compiler</code> : LL(1) et LL(*). D'une manière générale, nous
151  parlons d'analyseurs syntaxiques LL(<em>k</em>) : si un lexème ne permet pas
152  de dériver une règle comme il faut, alors l'analyseur peut
153  <strong>revenir</strong> jusqu'à <em>k</em> étapes en arrière ; nous parlons
154  aussi de <em lang="en">backtrack</em>.  Autrement dit, les règles peuvent être
155  <strong>ambiguës</strong> : à chaque fois que nous dérivons une règle de la
156  grammaire, nous avons plusieurs choix possibles et l'analyseur peut se
157  tromper, c'est pourquoi il doit parfois revenir en arrière. La variable
158  <em>k</em> permet de définir le <strong>niveau</strong> d'ambiguïté. Si une
159  grammaire peut être analysée par un analyseur syntaxique LL(1), elle est dite
160  <strong>non-ambiguë</strong> : à chaque lexème utilisé pour dériver nos
161  règles, il n'y a qu'un seul choix possible. Et si nous avons un analyseur
162  syntaxique LL(*), cela signifie que la variable <em>k</em> est
163  <strong>indéfinie</strong>. L'exemple suivant illustre une grammaire
164  non-ambiguë :</p>
165  <pre><code>rule ::= a b c | d e f</code></pre>
166  <p>Et cet exemple illustre une grammaire ambiguë :</p>
167  <pre><code>rule1 ::= a rule2
168rule2 ::= b rule3 | b rule4
169rule3 ::= c d
170rule4 ::= e f</code></pre>
171  <p>Voyons quand nous essayons de trouver une dérivation pour le mot
172  <code>abef</code> à partir de la règle racine <code>rule1</code> :</p>
173  <pre><code>rule1
174→ a rule2                   <em>   a  bef ✔</em>
175  → a (b rule3 | b rule4)   <em>   a  bef</em>
176    → a b rule3             <em>  ab  ef  ✔</em>
177      → a b c d             <em> abe  f   ✖</em>
178    ← a b rule3             <em>  ab  ef  ✖</em>
179  ← a (b rule3 | b rule4)   <em>   a  bef</em>
180    → a b rule4             <em>  ab  ef  ✔</em>
181      → a b e f             <em>abef      ✔</em></code></pre>
182  <p>La règle <code>rule2</code> est ambiguë, ce qui peut entraîner une mauvaise
183  dérivation et donc un retour en arrière, un
184  <em lang="en">backtracking</em>.</p>
185
186  <h2 id="LLk_compiler-compiler" for="main-toc">Compilateur de compilateurs
187  LL(<em>k</em>)</h2>
188
189  <p>Écrire des compilateurs est une tâche <strong>laborieuse</strong>. Ce n'est
190  pas forcément toujours difficile mais souvent répétitif et long. C'est
191  pourquoi il existe des <strong>compilateurs de compilateurs</strong>, ou
192  autrement dit, des générateurs de compilateurs. La plupart du temps, ces
193  compilateurs de compilateurs utilisent un langage
194  <strong>intermédiaire</strong> pour écrire une grammaire. La bibliothèque
195  <code>Hoa\Compiler</code> propose la classe <code>Hoa\Compiler\Llk\Llk</code>
196  qui permet l'écriture de compilateurs de compilateurs à travers un langage
197  <strong>dédié</strong>.</p>
198
199  <h3 id="PP_language" for="main-toc">Langage PP</h3>
200
201  <p>Le langage PP, pour <em lang="en">PHP Parser</em>, permet d'exprimer des
202  <strong>grammaires algébriques</strong>. Il s'écrit dans des fichiers portant
203  l'extension <code>.pp</code> (voir le fichier
204  <a href="@central_resource:path=Library/Compiler/.Mime"><code>hoa://Library/Compiler/.Mime</code></a>).</p>
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
207  suivante : <code>%token <em>namespace_in</em>:<em>name</em> <em>value</em> ->
208  <em>namespace_out</em></code>, où <code><em>name</em></code> représente le
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>
211  (attention à ne pas reconnaître de valeur vide, auquel cas une exception sera
212  levée), et <code><em>namespace_in</em></code> et
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
215  exemple <code>number</code> qui représente un nombre composé de chiffres de
216  <code>0</code> à <code>9</code> :</p>
217  <pre><code class="language-pp">%token number \d+</code></pre>
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.
220  Une déclaration <code>%skip</code> est similaire à <code>%token</code>
221  excepté qu'elle représente un lexème à <strong>sauter</strong>, c'est à dire
222  à ne pas considérer. Un exemple courant de lexèmes <code>%skip</code> est les
223  espaces :</p>
224  <pre><code class="language-pp">%skip space \s</code></pre>
225  <p>Pour expliquer les règles, nous allons utiliser comme exemple la grammaire
226  <code>Json.pp</code>, grammaire légèrement <strong>simplifiée</strong> du
227  <a href="http://json.org/">langage JSON</a> (voir la
228  <a href="https://tools.ietf.org/html/rfc4627">RFC4627</a>). La grammaire
229  <strong>complète</strong> se situe dans le fichier
230  <a href="@central_resource:path=Library/Json/Grammar.pp"><code>hoa://Library/Json/Grammar.pp</code></a>.
231  Ainsi :</p>
232  <pre><code class="language-pp">%skip   space          \s
233// Scalars.
234%token  true           true
235%token  false          false
236%token  null           null
237// Strings.
238%token  quote_         "        -> string
239%token  string:string  [^"]+
240%token  string:_quote  "        -> default
241// Objects.
242%token  brace_         {
243%token _brace          }
244// Arrays.
245%token  bracket_       \[
246%token _bracket        \]
247// Rest.
248%token  colon          :
249%token  comma          ,
250%token  number         \d+
251
252value:
253    &amp;lt;true> | &amp;lt;false> | &amp;lt;null> | string() | object() | array() | number()
254
255string:
256    ::quote_:: &amp;lt;string> ::_quote::
257
258number:
259    &amp;lt;number>
260
261#object:
262    ::brace_:: pair() ( ::comma:: pair() )* ::_brace::
263
264#pair:
265    string() ::colon:: value()
266
267#array:
268    ::bracket_:: value() ( ::comma:: value() )* ::_bracket::</code></pre>
269  <p>Nous remarquons que nous avons deux espaces de noms pour les lexèmes :
270  <code>default</code> et <code>string</code> (cela permet de ne pas
271  <strong>confondre</strong> les lexèmes <code>quote_</code> et
272  <code>string:_quote</code> qui ont la même représentation). Nous remarquons
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
275  PP sont les suivantes :</p>
276  <ul>
277    <li><code><em>rule</em>()</code> pour <strong>appeler</strong> une
278    règle ;</li>
279    <li><code>&amp;lt;<em>token</em>></code> et <code>::<em>token</em>::</code>
280    pour <strong>déclarer</strong> un lexème (les espaces de noms n'apparaissent
281    pas ici) ;</li>
282    <li><code>|</code> pour une <strong>disjonction</strong> (un choix) ;</li>
283    <li><code>(<em>…</em>)</code> pour grouper ;</li>
284    <li><code><em>e</em>?</code> pour dire que <code><em>e</em></code> est
285    <strong>optionel</strong> ;</li>
286    <li><code><em>e</em>+</code> pour dire que <code><em>e</em></code> peut
287    apparaître <strong>1 ou plusieurs</strong> fois ;</li>
288    <li><code><em>e</em>*</code> pour dire que <code><em>e</em></code> peut
289    apparaître <strong>0 ou plusieurs</strong> fois ;</li>
290    <li><code><em>e</em>{<em>x</em>,<em>y</em>}</code> pour dire que
291    <code><em>e</em></code> peut apparaître entre <code><em>x</em></code> et
292    <code><em>y</em></code> fois ;</li>
293    <li><code>#<em>node</em></code> pour créer un <strong>nœud</strong>
294    <code><em>node</em></code> dans l'arbre ;</li>
295    <li><code><em>token</em>[<em>i</em>]</code> pour <strong>unifier</strong>
296    des lexèmes entre eux.</li>
297  </ul>
298  <p>Peu de constructions mais amplement suffisantes.</p>
299  <p>Enfin, la grammaire du langage PP est écrite… dans le langage PP ! Vous
300  pourrez la trouver dans le fichier
301  <a href="@central_resource:path=Library/Compiler/Llk/Llk.pp"><code>hoa://Library/Compiler/Llk/Llk.pp</code></a>.</p>
302
303  <h3 id="Compilation_process" for="main-toc">Processus de compilation</h3>
304
305  <div id="overview" class="schema"></div>
306  <script>
307  Hoa.Document.onReady(function ( ) {
308
309      var paper = Hoa.Graph(Hoa.$('#overview'), 800, 360);
310      var flow  = paper.grid(0, 0, 800, 360, 1, 4);
311      flow.push(paper.rect(0, 0, 200, 70, 3, 'analyseur lexical'));
312      flow.push(paper.rect(0, 0, 200, 70, 3, 'analyseur syntaxique'));
313      flow.push(paper.rect(0, 0, 200, 70, 3, 'trace'));
314      flow.push(paper.rect(0, 0, 200, 70, 3, 'AST'));
315
316      var annot = paper.grid(180, 0, 80, 360, 1, 4);
317      annot.push(paper.rect(0, 0, 45, 45, 22.5, '1'));
318      annot.push(paper.rect(0, 0, 45, 45, 22.5, '2'));
319      annot.push(paper.rect(0, 0, 45, 45, 22.5, '3'));
320      annot.push(paper.rect(0, 0, 45, 45, 22.5, '4'));
321  });
322  </script>
323  <p>Le processus de compilation qu'utilise <code>Hoa\Compiler\Llk\Llk</code>
324  est classique. Il commence par analyser <strong>lexicalement</strong> la
325  donnée textuelle, le mot, <em>i.e.</em> à transformer notre donnée en une
326  séquence de lexèmes. L'<strong>ordre</strong> de déclaration des lexèmes est
327  primordial car l'analyseur lexical va les prendre les uns après les autres.
328  Ensuite, c'est l'analyseur <strong>syntaxique</strong> qui entre en jeu afin
329  de <strong>reconnaître</strong> notre donnée.</p>
330  <p>Si l'analyse syntaxique est un succès, nous obtenons une
331  <strong>trace</strong>. Cette trace peut être transformée en AST, pour
332  <em lang="en">Abstract Syntax Tree</em>. Cet arbre représente notre donnée
333  textuelle après analyse. Il a l'avantage de pouvoir être visité (nous
334  détaillerons plus loin), ce qui permet par exemple d'ajouter de nouvelles
335  <strong>contraintes</strong> qui ne peuvent pas être exprimées dans la
336  grammaire, comme une vérification de type.</p>
337  <p>Manipulons un peu <code>Hoa\Compiler\Llk\Llk</code>. Cette classe est un
338  <strong>assistant</strong> pour lire une grammaire au format PP facilement.
339  Elle prend en seul argument un flux en lecture vers la grammaire et retourne
340  un compilateur <code>Hoa\Compiler\Llk\Parser</code> prêt à l'emploi. Sur ce
341  compilateur, nous allons appeler la méthode
342  <code>Hoa\Compiler\Llk\Parser::parse</code> pour analyser une donnée JSON. Si
343  la donnée est correcte, nous aurons en retour un AST, sinon une exception sera
344  levée. Enfin, nous allons utiliser le visiteur
345  <code>Hoa\Compiler\Visitor\Dump</code> pour afficher notre AST :</p>
346  <pre><code class="language-php">// 1. Load grammar.
347$compiler = Hoa\Compiler\Llk\Llk::load(new Hoa\File\Read('Json.pp'));
348
349// 2. Parse a data.
350$ast      = $compiler->parse('{"foo": true, "bar": [null, 42]}');
351
352// 3. Dump the AST.
353$dump     = new Hoa\Compiler\Visitor\Dump();
354echo $dump->visit($ast);
355
356/**
357 * Will output:
358 *     >  #object
359 *     >  >  #pair
360 *     >  >  >  token(string:string, foo)
361 *     >  >  >  token(true, true)
362 *     >  >  #pair
363 *     >  >  >  token(string:string, bar)
364 *     >  >  >  #array
365 *     >  >  >  >  token(null, null)
366 *     >  >  >  >  token(number, 42)
367 */</code></pre>
368  <p>Quand nous écrivons et testons une grammaire, nous allons répéter ces trois
369  tâches très <strong>régulièrement</strong>. C'est pourquoi, le script
370  <code>hoa</code> propose la commande <code>compiler:pp</code>. Cette commande
371  propose d'analyser une donnée par rapport à une grammaire et d'appliquer un
372  visiteur si besoin sur l'AST résultant. Notons que la lecture de la donnée
373  peut se faire à travers un
374  <a href="https://en.wikipedia.org/wiki/Pipeline_(Unix)"><em lang="en">pipe</em></a> :</p>
375  <pre><code class="language-shell">$ echo '[1, [1, [2, 3], 5], 8]' | hoa compiler:pp Json.pp 0 --visitor dump
376>  #array
377>  >  token(number, 1)
378>  >  #array
379>  >  >  token(number, 1)
380>  >  >  #array
381>  >  >  >  token(number, 2)
382>  >  >  >  token(number, 3)
383>  >  >  token(number, 5)
384>  >  token(number, 8)</code></pre>
385  <p>C'est un moyen pratique pour tester <strong>rapidement</strong> des données
386  par rapport à notre grammaire. Il ne faut pas hésiter à regarder l'aide de la
387  commande <code>compiler:pp</code> pour plus de détails !</p>
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
390  argument de la méthode <code>Hoa\Compiler\Llk\Parser::parse</code> :</p>
391  <pre><code class="language-php">$compiler->parse('{"foo": true, "bar": [null, 42]}', 'object');</code></pre>
392  <p>Pour utiliser la règle racine, il suffit de passer <code>null</code>.</p>
393  <p>Et enfin, pour ne pas générer l'AST mais uniquement savoir si la donnée est
394  valide ou pas, nous pouvons utiliser le dernier argument de notre méthode en
395  lui passant <code>false</code> :</p>
396  <pre><code class="language-php">$valid = $compiler->parse('{"foo": true, "bar": [null, 42]}', null, false);
397var_dump($valid);
398
399/**
400 * Will output:
401 *     bool(true)
402 */</code></pre>
403
404  <h4 id="Errors" for="main-toc">Erreurs</h4>
405
406  <p>Les erreurs de compilation sont remontées à travers des exceptions,
407  ainsi :</p>
408  <pre><code class="language-shell">$ echo '{"foo" true}' | hoa compiler:pp Json.pp 0 --visitor dump
409Uncaught exception (Hoa\Compiler\Exception\UnexpectedToken):
410Hoa\Compiler\Llk\Parser::parse(): (0) Unexpected token "true" (true) at line 1
411and column 8:
412{"foo" true}
413       ↑
414in hoa://Library/Compiler/Llk/Parser.php at line 1</code></pre>
415  <p>Plusieurs exceptions peuvent remonter selon le contexte :</p>
416  <ul>
417    <li>durant l'analyse <strong>lexicale</strong>,
418    <code>Hoa\Compiler\Exception\UnrecognizedToken</code> quand un lexème n'est
419    pas reconnu, <em>i.e.</em> quand la donnée textuelle ne peut plus être
420    découpée en une séquence de lexèmes, et
421    <code>Hoa\Compiler\Exception\Lexer</code> quand d'autres erreurs plus
422    générales arrivent, par exemple si un lexème reconnaît une valeur
423    vide ;</li>
424    <li>durant l'analyse <strong>syntaxique</strong>,
425    <code>Hoa\Compiler\Exception\UnexpectedToken</code> quand un lexème n'est
426    pas attendu, <em>i.e.</em> qu'il ne permet plus de dériver les règles de la
427    grammaire.</li>
428  </ul>
429  <p>L'exception parente est <code>Hoa\Compiler\Exception\Exception</code>.</p>
430
431  <h4 id="Nodes" for="main-toc">Nœuds</h4>
432
433  <p>Le processus de compilation aboutit très souvent à la
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
437  la notation <code>#<em>node</em></code> car elle permet de créer des
438  <strong>nœuds</strong> dans l'AST. Une précision tout d'abord, les lexèmes
439  déclarés avec la syntaxe <code>&amp;lt;<em>token</em>></code> apparaîtront
440  dans l'arbre, alors que les autres lexèmes, déclarés avec la syntaxe
441  <code>::<em>token</em>::</code>, n'y apparaîtront pas. En effet, dans notre
442  dernier exemple, les lexèmes <code>quote_</code>, <code>brace_</code>,
443  <code>colon</code>, <code>comma</code> etc. n'apparaissent pas. Ensuite, il
444  est important de noter que les déclarations de nœuds se
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
447  <code>#</code>, comme pour la règle <code>#array</code>, qui permet de définir
448  un nœud par <strong>défaut</strong>, mais il peut être surchargé. Par exemple,
449  si nous remplaçons la règle <code>array</code> par :</p>
450  <pre><code class="language-pp">#array:
451    ::bracket_:: value() ( ::comma:: value() #bigarray )* ::_bracket::</code></pre>
452  <p>Si le tableau ne contient qu'une seule valeur, le nœud s'appelera
453  <code>#array</code>, sinon il s'appelera <code>#bigarray</code> ; voyons
454  plutôt :</p>
455  <pre><code class="language-shell">$ echo '[42]' | hoa compiler:pp Json.pp 0 --visitor dump
456>  #array
457>  >  token(number, 42)
458$ echo '[4, 2]' | hoa compiler:pp Json.pp 0 --visitor dump
459>  #bigarray
460>  >  token(number, 4)
461>  >  token(number, 2)</code></pre>
462  <p>Bien sûr, il peut arriver qu'un nœud soit créé ou pas selon le dérivation
463  <strong>empruntée</strong> dans la règle. Le mécanisme est normalement assez
464  <strong>intuitif</strong>.</p>
465
466  <h4 id="Namespaces" for="main-toc">Espace de noms</h4>
467
468  <p>Détaillons un peu le fonctionnement de l'analyseur lexical vis à vis des
469  <strong>espaces de noms</strong>.</p>
470  <p>Les <strong>lexèmes</strong> sont placés dans des espaces de noms,
471  c'est à dire que seuls les lexèmes de l'espace de noms
472  <strong>courant</strong> seront utilisés par l'analyseur lexical. L'espace de
473  noms par défaut est <code>default</code>. Pour déclarer l'espace de noms d'un
474  lexème, il faut utiliser l'opérateur <code>:</code>.  Quand un lexème est
475  consommé, il peut <strong>changer</strong> l'espace courant pour la suite de
476  l'analyse lexicale, grâce à l'opérateur <code>-></code>.  Ainsi, nous allons
477  déclarer cinq lexèmes : <code>foo</code> et <code>bar</code> dans l'espace
478  <code>default</code>, <code>baz</code> dans <code>ns1</code> et
479  <code>qux</code> et <code>foo</code> dans <code>ns2</code>. Le fait de
480  déclarer deux fois <code>foo</code> n'est pas gênant car ils sont dans des
481  espaces de noms <strong>différent</strong> :</p>
482  <pre><code class="language-pp">%token      foo   fo+     -> ns1
483%token      bar   ba?r+   -> ns2
484%token  ns1:baz   ba?z+   -> default
485%token  ns2:qux   qux+
486%token  ns2:foo   FOO     -> ns1</code></pre>
487  <p>Écrire <code>default:bar</code> est strictement équivalent à
488  <code>bar</code>. Le lexème <code>foo</code> emmène dans <code>ns1</code>,
489  <code>bar</code> dans <code>ns2</code>, <code>ns1:baz</code> dans
490  <code>default</code>, <code>ns2:qux</code> reste dans <code>ns2</code> et
491  <code>ns2:foo</code> emmène dans <code>ns1</code>. Observons la séquence de
492  lexèmes produite par l'analyseur lexical avec la donnée
493  <code>fooooobzzbarrrquxFOObaz</code> :</p>
494  <pre><code class="language-php">$pp = '%token      foo   fo+     -> ns1'     . "\n" .
495      '%token      bar   ba?r+   -> ns2'     . "\n" .
496      '%token  ns1:baz   ba?z+   -> default' . "\n" .
497      '%token  ns2:qux   qux+'               . "\n" .
498      '%token  ns2:foo   FOO     -> ns1';
499
500// 1. Parse PP.
501Hoa\Compiler\Llk\Llk::parsePP($pp, $tokens, $rawRules);
502
503// 2. Run the lexical analyzer.
504$lexer    = new Hoa\Compiler\Llk\Lexer();
505$sequence = $lexer->lexMe('fooooobzzbarrrquxFOObaz', $tokens);
506
507// 3. Pretty-print the result.
508$format   = '%' . (strlen((string) count($sequence)) + 1) . 's  ' .
509            '%-13s %-20s  %-20s  %6s' . "\n";
510$header   = sprintf($format, '#', 'namespace', 'token name', 'token value', 'offset');
511
512echo $header, str_repeat('-', strlen($header)), "\n";
513
514foreach ($sequence as $i => $token) {
515    printf(
516        $format,
517        $i,
518        $token['namespace'],
519        $token['token'],
520        $token['value'],
521        $token['offset']
522    );
523}
524
525/**
526 * Will output:
527 *      #  namespace     token name            token value           offset
528 *     ---------------------------------------------------------------------
529 *      0  default       foo                   fooooo                     0
530 *      1  ns1           baz                   bzz                        6
531 *      2  default       bar                   barrr                      9
532 *      3  ns2           qux                   qux                       14
533 *      4  ns2           foo                   FOO                       17
534 *      5  ns1           baz                   baz                       20
535 *      6  default       EOF                   EOF                       23
536 */</code></pre>
537  <p>Nous lisons les lexèmes, leur espace et leur valeur dans le tableau. La
538  donnée a pu être <strong>découpée</strong>, et nous sommes passés d'un espace
539  à un autre. Si cette fois nous essayons avec la donnée <code>foqux</code>,
540  nous aurons une erreur : <code>fo</code> correspond au lexème <code>foo</code>
541  dans l'espace <code>default</code>, nous changeons alors d'espace pour
542  <code>ns1</code>, et là, aucun lexème dans cet espace ne peut reconnaître au
543  moins <code>q</code>.  Une erreur sera levée.</p>
544  <p>Jusqu'à maintenant, nous avons vu comment passer d'un espace à l'autre avec
545  l'opérateur <code>-></code>. Aucun <strong>historique</strong> sur les espaces
546  traversés n'est conservé. Toutefois, dans certains cas rares, il peut arriver
547  qu'un espace de lexèmes soit accessible via <strong>plusieurs</strong> autres
548  et que nous aimerions qu'un lexème déclenche le retour vers l'espace de noms
549  <strong>précédent</strong>. Autrement dit, nous aimerions un historique des
550  espaces traversés et pouvoir y naviguer (en arrière uniquement). C'est le rôle
551  du mot-clé <code>__shift__ * <em>n</em></code>, à utiliser après l'opérateur
552  <code>-></code> et à la place du nom d'un espace. <code>__shift__</code> est
553  équivalent à dire : revient à l'espace précédent. <code>__shift__</code> est
554  équivalent à <code>__shift__ * 1</code>, et
555  <code>__shift__ * <em>n</em></code> à : revient <code><em>n</em></code> fois à
556  l'espace précédent.</p>
557  <p>Lorsque le mot-clé <code>__shift__</code> apparaît dans la grammaire, les
558  espaces sont gérés comme une <strong>pile</strong>, d'où le vocabulaire
559  <em lang="en">shift</em>. Il faut faire attention à bien dépiler les espaces
560  pour ne pas avoir une pile trop conséquente.</p>
561  <p>Prenons en exemple la grammaire suivante :</p>
562  <pre><code class="language-pp">%token       foo1  a    -> ns1
563%token       foo2  x    -> ns2
564%token       end   e
565
566%token   ns1:bar   b
567%token   ns1:baz   c    -> ns3
568%token   ns1:tada  t    -> __shift__
569
570%token   ns2:bar   y
571%token   ns2:baz   z    -> ns3
572%token   ns2:tada  T    -> __shift__
573
574%token   ns3:qux   =   -> __shift__
575
576#test:
577    ( &amp;lt;foo1> | &amp;lt;foo2> ) &amp;lt;bar> &amp;lt;baz> &amp;lt;qux> &amp;lt;tada> &amp;lt;end></code></pre>
578  <p>Cette grammaire reconnaît deux données : <code>abc=te</code> et
579  <code>xyz=Te</code>. Si le premier lexème <code>foo1</code> est rencontré,
580  l'analyseur syntaxique changera d'espace pour <code>ns1</code>. Quand il
581  rencontrera le lexème <code>ns1:baz</code>, il passera dans <code>ns3</code>.
582  Ensuite, quand il rencontrera <code>ns3:qux</code>, il reviendra à l'espace
583  précédent, soit <code>ns1</code>. Et ainsi de suite. Maintenant, s'il ne
584  rencontre pas <code>foo1</code> mais <code>foo2</code>, il ira dans l'espace
585  <code>ns2</code>, puis dans <code>ns3</code> puis à nouveau <code>ns2</code>.
586  Les mots-clés <code>__shift__</code> pour <code>ns1:tada</code> et
587  <code>ns2:tada</code> n'ont pas d'autres buts que de dépiler les espaces, mais
588  aucune ambiguïté n'existe : ces espaces ne sont accessibles que par un seul
589  espace, à savoir <code>default</code>.</p>
590  <p>Maintenant, enregistrons cette grammaire dans un fichier
591  <code>NamespaceStack.pp</code> et utilisons l'option
592  <code>-s/--token-sequence</code> de la commande <code>hoa
593  compiler:pp</code> :</p>
594  <pre><code class="language-shell">$ echo -n 'abc=te' | hoa compiler:pp NamespaceStack.pp 0 --token-sequence
595 #  namespace     token name            token value                     offset
596-------------------------------------------------------------------------------
597 0  default       foo1                  a                                    0
598 1  ns1           bar                   b                                    1
599 2  ns1           baz                   c                                    2
600 3  ns3           qux                   =                                    3
601 4  ns1           tada                  t                                    4
602 5  default       end                   e                                    5
603 6  default       EOF                   EOF                                  6
604
605$ echo -n 'xyz=Te' | hoa compiler:pp NamespaceStack.pp 0 --token-sequence
606 #  namespace     token name            token value                     offset
607-------------------------------------------------------------------------------
608 0  default       foo2                  x                                    0
609 1  ns2           bar                   y                                    1
610 2  ns2           baz                   z                                    2
611 3  ns3           qux                   =                                    3
612 4  ns2           tada                  T                                    4
613 5  default       end                   e                                    5
614 6  default       EOF                   EOF                                  6</code></pre>
615  <p>Nous voyons que l'analyse lexicale a réussi à jongler avec les espaces de
616  noms, comme attendu. Nous avions deux façons d'accéder à l'espace
617  <code>ns3</code> : soit depuis <code>ns1</code>, soit depuis <code>ns2</code>.
618  L'analyseur a réussi à créer un historique des espaces et à y naviguer.</p>
619
620  <h4 id="Unification" for="main-toc">Unification</h4>
621
622  <p>Une caractéristique qu'apporte le langage PP par rapport à d'autres
623  langages de grammaires connus est la capacité d'exprimer une
624  <strong>unification</strong> de lexèmes. Imaginons la grammaire
625  suivante :</p>
626  <pre><code class="language-pp">%token  quote   '|"
627%token  string  \w+
628
629rule:
630    ::quote:: &amp;lt;string> ::quote::</code></pre>
631  <p>Les guillemets qui entourent la chaîne de caractère peuvent être de deux
632  sortes : simple, avec le symbole « <code>'</code> », ou double, avec le
633  symbole « <code>"</code> ». Ainsi, les données <code>"foo"</code> et
634  <code>'foo'</code> sont valides, mais <strong>également</strong>
635  <code>"foo'</code> et <code>'foo"</code> !</p>
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
638  syntaxe est la suivante : <code><em>token</em>[<em>i</em>]</code>. La valeur
639  de <code><em>i</em></code> indique quels lexèmes vont devoir porter la même
640  valeur. Et enfin, l'unification est <strong>locale</strong> à une instance
641  d'une règle, c'est à dire qu'il n'y a pas d'unification entre les lexèmes de
642  plusieurs règles et que cela s'applique sur la règle <strong>appelée</strong>
643  uniquement. Ainsi, l'exemple devient :</p>
644  <pre><code class="language-pp">rule:
645    ::quote[0]:: &amp;lt;string> ::quote[0]::</code></pre>
646  <p>Ce qui invalide les données <code>"foo'</code> et <code>'foo"</code>.</p>
647  <p>L'unification trouve de nombreuses applications, comme par exemple unifier
648  les noms des balises ouvrantes et fermantes du
649  <a href="http://w3.org/TR/xml11/">langage XML</a>.</p>
650
651  <h3 id="Abstract_Syntax_Tree" for="main-toc"><em lang="en">Abstract Syntax
652  Tree</em></h3>
653
654  <div id="overview_ast" class="schema"></div>
655  <script>
656  Hoa.Document.onReady(function ( ) {
657
658      var paper = Hoa.Graph(Hoa.$('#overview_ast'), 800, 360);
659      var flow  = paper.grid(0, 0, 800, 360, 1, 4);
660      flow.push(paper.rect(0, 0, 200, 70, 3, 'analyseur lexical').attr({opacity: .3}));
661      flow.push(paper.rect(0, 0, 200, 70, 3, 'analyseur syntaxique').attr({opacity: .3}));
662      flow.push(paper.rect(0, 0, 200, 70, 3, 'trace').attr({opacity: .3}));
663      flow.push(paper.rect(0, 0, 200, 70, 3, 'AST'));
664
665      var annot = paper.grid(180, 0, 80, 360, 1, 4);
666      annot.push(paper.rect(0, 0, 45, 45, 22.5, '1').attr({opacity: .3}));
667      annot.push(paper.rect(0, 0, 45, 45, 22.5, '2').attr({opacity: .3}));
668      annot.push(paper.rect(0, 0, 45, 45, 22.5, '3').attr({opacity: .3}));
669      annot.push(paper.rect(0, 0, 45, 45, 22.5, '4'));
670  });
671  </script>
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
675  <code>Hoa\Compiler\Llk\TreeNode</code>. Parmis les méthodes utiles, nous
676  trouvons :</p>
677  <ul>
678    <li><code>getId</code> pour obtenir l'identifiant du nœud ;</li>
679    <li><code>getValueToken</code> pour obtenir le nom du lexème ;</li>
680    <li><code>getValueValue</code> pour obtenir la valeur du lexème ;</li>
681    <li><code>isToken</code> si le nœud représente un lexème ;</li>
682    <li><code>getChild(<em>$i</em>)</code> pour obtenir le
683    <code><em>$i</em></code>-ème enfant d'un nœud ;</li>
684    <li><code>getChildren</code> pour obtenir tous les nœuds ;</li>
685    <li><code>getChildrenNumber</code> pour connaître le nombre d'enfants ;</li>
686    <li><code>getParent</code> pour obtenir le nœud parent ;</li>
687    <li><code>getData</code> pour obtenir une référence vers un tableau de
688    données ;</li>
689    <li><code>accept</code> pour appliquer un visiteur.</li>
690  </ul>
691  <p>Les visiteurs sont le moyen le plus pratique pour
692  <strong>parcourir</strong> un AST. En guise d'exemple, nous allons écrire le
693  visiteur <code>PrettyPrinter</code> qui va réécrire une donnée JSON avec notre
694  propre convention (espacements, retours à la ligne etc.). Un visiteur doit
695  implémenter l'interface <code>Hoa\Visitor\Visit</code> et n'aura qu'une seule
696  méthode à écrire : <code>visit</code> qui prend trois arguments :
697  l'élément et deux arguments accessoires (en référence et en copie). Voyons
698  plutôt :</p>
699  <pre><code class="language-php">class PrettyPrinter implements Hoa\Visitor\Visit
700{
701    public function visit (
702        Hoa\Visitor\Element $element,
703        &amp;amp;$handle = null,
704        $eldnah = null
705    ) {
706        static $i      = 0;
707        static $indent = '    ';
708
709        // One behaviour per node in the AST.
710        switch ($element->getId()) {
711            // Object: { … }.
712            case '#object':
713                echo '{', "\n";
714                ++$i;
715
716                foreach ($element->getChildren() as $e => $child) {
717                    if (0 &amp;lt; $e) {
718                        echo ',', "\n";
719                    }
720
721                    echo str_repeat($indent, $i);
722                    $child->accept($this, $handle, $eldnah);
723                }
724
725                echo "\n", str_repeat($indent, --$i), '}';
726
727                break;
728
729            // Array: [ … ].
730            case '#array':
731                echo '[', "\n";
732                ++$i;
733
734                foreach ($element->getChildren() as $e => $child) {
735                    if (0 &amp;lt; $e) {
736                        echo ',', "\n";
737                    }
738
739                    echo str_repeat($indent, $i);
740                    $child->accept($this, $handle, $eldnah);
741                }
742
743                echo "\n", str_repeat($indent, --$i), ']';
744
745                break;
746
747            // Pair: "…": ….
748            case '#pair':
749                echo
750                    $element->getChild(0)->accept($this, $handle, $eldnah),
751                    ': ',
752                    $element->getChild(1)->accept($this, $handle, $eldnah);
753
754                break;
755
756            // Many tokens.
757            case 'token':
758                switch ($element->getValueToken()) {
759                    // String: "…".
760                    case 'string':
761                        echo '"', $element->getValueValue(), '"';
762
763                        break;
764
765                    // Booleans.
766                    case 'true':
767                    case 'false':
768
769                    // Null.
770                    case 'null':
771
772                    // Number.
773                    case 'number':
774                        echo $element->getValueValue();
775
776                        break;
777                }
778
779                break;
780        }
781    }
782}</code></pre>
783  <p>Nous allons voir tout de suite un exemple d'utilisation :</p>
784  <pre><code class="language-php">$compiler    = Hoa\Compiler\Llk\Llk::load(new Hoa\File\Read('Json.pp'));
785$ast         = $compiler->parse('{"foo": true, "bar": [null, 42]}');
786$prettyPrint = new PrettyPrinter();
787echo $prettyPrint->visit($ast);
788
789/**
790 * Will output:
791 *     {
792 *         "foo": true,
793 *         "bar": [
794 *             null,
795 *             42
796 *         ]
797 *     }
798 */</code></pre>
799  <p>La méthode <code>getData</code> est très pratique pour
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>
803  <pre><code class="language-php">$data = $element->getData();
804
805if (!isset($data['previousComputing'])) {
806    throw new Exception('Need a previous computing.', 0);
807}
808
809$previous = $data['previousComputing'];</code></pre>
810  <p>Il est courant d'utiliser un visiteur par <strong>contrainte</strong> :
811  vérifiation des symboles, vérification de types etc. Certains peuvent laisser
812  des données nécessaires pour le suivant. La méthode <code>getData</code>
813  n'impose aucune structuration des données, elle propose uniquement un accès à
814  un tableau. Ce sera à vous de faire le reste.</p>
815  <p>Utiliser la classe <code>Hoa\Compiler\Llk\TreeNode</code> est vraiment
816  <strong>trivial</strong> et nous l'utiliserons la plupart du temps avec un
817  visiteur.</p>
818
819  <h3 id="Traces" for="main-toc">Traces</h3>
820
821  <div id="overview_trace" class="schema"></div>
822  <script>
823  Hoa.Document.onReady(function ( ) {
824
825      var paper = Hoa.Graph(Hoa.$('#overview_trace'), 800, 360);
826      var flow  = paper.grid(0, 0, 800, 360, 1, 4);
827      flow.push(paper.rect(0, 0, 200, 70, 3, 'analyseur lexical').attr({opacity: .3}));
828      flow.push(paper.rect(0, 0, 200, 70, 3, 'analyseur syntaxique').attr({opacity: .3}));
829      flow.push(paper.rect(0, 0, 200, 70, 3, 'trace'));
830      flow.push(paper.rect(0, 0, 200, 70, 3, 'AST').attr({opacity: .3}));
831
832      var annot = paper.grid(180, 0, 80, 360, 1, 4);
833      annot.push(paper.rect(0, 0, 45, 45, 22.5, '1').attr({opacity: .3}));
834      annot.push(paper.rect(0, 0, 45, 45, 22.5, '2').attr({opacity: .3}));
835      annot.push(paper.rect(0, 0, 45, 45, 22.5, '3'));
836      annot.push(paper.rect(0, 0, 45, 45, 22.5, '4').attr({opacity: .3}));
837  });
838  </script>
839  <p>Le compilateur LL(<em>k</em>) que propose Hoa est clairement découpé en
840  plusieurs <strong>couches</strong>. Chaque couche est exploitable pour
841  permettre une modularité maximum. Quand la grammaire est traduite en « règles
842  machines » et que les analyseurs lexical et syntaxique ont validé une donnée,
843  il en résulte une <strong>trace</strong>. Cette trace est un tableau composé
844  de trois classes seulement :</p>
845  <ul>
846    <li><code>Hoa\Compiler\Llk\Rule\Entry</code> quand l'analyseur syntaxique
847    est rentré dans une règle ;</li>
848    <li><code>Hoa\Compiler\Llk\Rule\Ekzit</code> quand l'analyseur syntaxique
849    est sorti d'une règle ;</li>
850    <li><code>Hoa\Compiler\Llk\Rule\Token</code> quand l'analyseur syntaxique a
851    rencontré un lexème.</li>
852  </ul>
853  <p>Nous pouvons l'obtenir grâce à la méthode
854  <code>Hoa\Compiler\Llk\Parser::getTrace</code>. Pour bien comprendre cette
855  trace, nous allons commencer par un exemple :</p>
856  <pre><code class="language-php">$compiler = Hoa\Compiler\Llk\Llk::load(new Hoa\File\Read('Json.pp'));
857$ast      = $compiler->parse('{"foo": true, "bar": [null, 42]}');
858$i        = 0;
859
860foreach ($compiler->getTrace() as $element) {
861    if ($element instanceof Hoa\Compiler\Llk\Rule\Entry) {
862        echo str_repeat('>   ', ++$i), 'enter ', $element->getRule(), "\n";
863    } elseif ($element instanceof Hoa\Compiler\Llk\Rule\Token) {
864        echo
865            str_repeat('    ', $i + 1), 'token ', $element->getTokenName(),
866            ', consumed ', $element->getValue(), "\n";
867    } else {
868        echo str_repeat('&amp;lt;   ', $i--), 'ekzit ', $element->getRule(), "\n";
869    }
870}
871
872/**
873 * Will output:
874 *     >   enter value
875 *     >   >   enter object
876 *                 token brace_, consumed {
877 *     >   >   >   enter pair
878 *     >   >   >   >   enter string
879 *                         token quote_, consumed "
880 *                         token string, consumed foo
881 *                         token _quote, consumed "
882 *     &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   ekzit string
883 *                     token colon, consumed :
884 *     >   >   >   >   enter value
885 *                         token true, consumed true
886 *     &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   ekzit value
887 *     &amp;lt;   &amp;lt;   &amp;lt;   ekzit pair
888 *     >   >   >   enter 13
889 *     >   >   >   >   enter 12
890 *                         token comma, consumed ,
891 *     >   >   >   >   >   enter pair
892 *     >   >   >   >   >   >   enter string
893 *                                 token quote_, consumed "
894 *                                 token string, consumed bar
895 *                                 token _quote, consumed "
896 *     &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   ekzit string
897 *                             token colon, consumed :
898 *     >   >   >   >   >   >   enter value
899 *     >   >   >   >   >   >   >   enter array
900 *                                     token bracket_, consumed [
901 *     >   >   >   >   >   >   >   >   enter value
902 *                                         token null, consumed null
903 *     &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   ekzit value
904 *     >   >   >   >   >   >   >   >   enter 21
905 *     >   >   >   >   >   >   >   >   >   enter 20
906 *                                             token comma, consumed ,
907 *     >   >   >   >   >   >   >   >   >   >   enter value
908 *                                                 token number, consumed 42
909 *     &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   ekzit value
910 *     &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   ekzit 20
911 *     &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   ekzit 21
912 *                                     token _bracket, consumed ]
913 *     &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   ekzit array
914 *     &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   ekzit value
915 *     &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   ekzit pair
916 *     &amp;lt;   &amp;lt;   &amp;lt;   &amp;lt;   ekzit 12
917 *     &amp;lt;   &amp;lt;   &amp;lt;   ekzit 13
918 *                 token _brace, consumed }
919 *     &amp;lt;   &amp;lt;   ekzit object
920 *     &amp;lt;   ekzit value
921 */</code></pre>
922  <p>Cet exemple nous révèle plusieurs choses. Tout d'abord, les informations
923  que nous donne la trace peuvent être utiles : si nous sommes sur une règle,
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
927  la forme d'une PCRE, avec la méthode <code>getRepresentation</code>), sa
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
931  (avec la méthode <code>getUnificationIndex</code>). Bien sûr, tout ceci est
932  modifiable, ce qui peut influencer la construction de l'AST qui est le
933  processus (optionnel) suivant.</p>
934  <p>Ensuite, nous remarquons que parfois nous entrons dans une règle qui existe
935  dans la grammaire, comme <code>object</code>, <code>pair</code>,
936  <code>value</code> etc., et parfois nous entrons dans une règle
937  <strong>numérique</strong>, comme <code>13</code>, <code>12</code>,
938  <code>21</code>, <code>20</code> etc. Quand la grammaire est interprétée pour
939  être transformée en « règles machines », chacune de ses règles est
940  <strong>linéarisée</strong> selon les opérateurs du langage PP :</p>
941  <ul>
942    <li><code>Hoa\Compiler\Llk\Rule\Choice</code> pour une disjonction ;</li>
943    <li><code>Hoa\Compiler\Llk\Rule\Concatenation</code> pour une
944    concaténation ;</li>
945    <li><code>Hoa\Compiler\Llk\Rule\Repetition</code> pour une répétition ;</li>
946    <li><code>Hoa\Compiler\Llk\Rule\Token</code> pour un lexème (déjà vu
947    précédemment).</li>
948  </ul>
949  <p>Toutes les règles sous ce format sont accessibles à travers la méthode
950  <code>Hoa\Compiler\Llk\Parser::getRules</code> sous la forme d'un tableau.
951  Nous allons afficher toutes les règles <strong>accessibles</strong> depuis la
952  règle racine pour mieux comprendre :</p>
953  <pre><code class="language-php">$compiler = Hoa\Compiler\Llk\Llk::load(new Hoa\File\Read('Json.pp'));
954
955// 1. Get all rules.
956$rules    = $compiler->getRules();
957
958// 2. Start with the root rule.
959$stack    = [$compiler->getRootRule() => true];
960
961while (false !== current($stack)) {
962    $rule = key($stack);
963    next($stack);
964    echo
965        "\n", '"', $rule, '" is a ',
966        strtolower(substr(get_class($rules[$rule]), 22));
967
968    $subrules = $rules[$rule]->getContent();
969
970    // 3a. Token.
971    if (null === $subrules) {
972        continue;
973    }
974
975    echo ' of rules: ';
976
977    // 3b. Other rules.
978    foreach ((array) $rules[$rule]->getContent() as $subrule) {
979        if (!array_key_exists($subrule, $stack)) {
980            // 4. Unshift new rules to print.
981            $stack[$subrule] = true;
982        }
983
984        echo $subrule, ' ';
985    }
986}
987
988/**
989 * Will output:
990 *     "value" is a choice of rules: 1 2 3 string object array number
991 *     "1" is a token
992 *     "2" is a token
993 *     "3" is a token
994 *     "string" is a concatenation of rules: 5 6 7
995 *     "object" is a concatenation of rules: 10 pair 13 14
996 *     "array" is a concatenation of rules: 18 value 21 22
997 *     "number" is a token
998 *     "5" is a token
999 *     "6" is a token
1000 *     "7" is a token
1001 *     "10" is a token
1002 *     "pair" is a concatenation of rules: string 16 value
1003 *     "13" is a repetition of rules: 12
1004 *     "14" is a token
1005 *     "18" is a token
1006 *     "21" is a repetition of rules: 20
1007 *     "22" is a token
1008 *     "16" is a token
1009 *     "12" is a concatenation of rules: 11 pair
1010 *     "20" is a concatenation of rules: 19 value
1011 *     "11" is a token
1012 *     "19" is a token
1013 */</code></pre>
1014  <p>Si nous lisons la règle <code>object</code>, nous savons que c'est la
1015  concaténation des règles <code>10</code>, <code>pair</code>, <code>13</code>
1016  et <code>14</code>. <code>10</code> est un lexème, <code>pair</code> est la
1017  concaténation des règles <code>string</code>, <code>16</code> et
1018  <code>value</code>, et ainsi de suite. La grammaire initiale est transformée
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
1022  grammaire ne sont pas réservés aux AST. À l'étape précédente, avec la trace,
1023  nous pouvons déjà effectuer des traitements.</p>
1024
1025  <h3 id="Generation" for="main-toc">Génération</h3>
1026
1027  <p>Une grammaire peut être utile pour deux objectifs :
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
1030  valider une donnée à travers plusieurs processus :
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
1035  pouvons nous arrêter à la première étape, la préparation de notre compilateur,
1036  pour exploiter les règles afin de générer une donnée qui sera valide par
1037  rapport à notre grammaire.</p>
1038  <p><code>Hoa\Compiler\Llk\Sampler</code> propose trois algorithmes de
1039  <strong>générations</strong> de données :</p>
1040  <ul>
1041    <li>génération aléatoire et uniforme ;</li>
1042    <li>génération exhaustive bornée ;</li>
1043    <li>génération basée sur la couverture.</li>
1044  </ul>
1045  <p>Pourquoi proposer trois algorithmes ? Parce qu'il est illusoire de penser
1046  qu'un seul algorithme peut suffir aux <strong>nombreux</strong> contextes
1047  d'utilisations. Chacun répond à des besoins différents, nous l'expliquerons
1048  plus loin.</p>
1049  <p>Générer une donnée à partir d'une grammaire se fait en <strong>deux
1050  étapes</strong> :</p>
1051  <ol>
1052    <li>générer des valeurs pour les <strong>lexèmes</strong> afin d'avoir des données
1053    brutes ;</li>
1054    <li>générer un <strong>chemin</strong> dans les règles de la grammaire.</li>
1055  </ol>
1056  <p>Un chemin est équivalent à une dérivation, le vocabulaire est différent
1057  selon notre objectif : validation ou génération.</p>
1058
1059  <h4 id="Isotropic_generation_of_lexemes" for="main-toc">Génération
1060  isotropique de lexèmes</h4>
1061
1062  <p>Pour générer les valeurs des lexèmes, peu importe l'algorithme utilisé, il
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
1067  disjonction entre trois sous-règles, nous allons tirer aléatoirement et
1068  uniformément entre 1 et 3. Si nous avons une concaténation, nous allons juste
1069  concaténer chaque partie. Et enfin, une répétition n'est rien d'autre qu'une
1070  disjonction de concaténation : en effet, <code><em>e</em>{1,3}</code> est
1071  strictement équivalent à <code><em>e</em> | <em>ee</em> | <em>eee</em></code>.
1072  Illustrons plutôt :</p>
1073  <pre><code>([ae]+|[x-z]!){1,3}              <em>repeat <em>[ae]+|[x-z]!</em> 2 times</em>
1074→ ([ae]+|[x-z]!)([ae]+|[x-z]!)  <em>choose between <em>[ae]+</em> and <em>[x-z]!</em></em>
1075→ ([ae]+)([ae]+|[x-z]!)         <em>repeat <code>ae</code> 2 times</em>
1076→ [ae][ae]([ae]+|[x-z]!)        <em>choose between <em>a</em> and <em>e</em></em>
1077→ e[ae]([ae]+|[x-z]!)           <em>again</em>
1078→ ea([ae]+|[x-z]!)              <em>choose between <em>[ae]+</em> and <em>[x-z]!</em></em>
1079→ ea([x-z]!)                    <em>choose between <em>x</em>, <em>y</em> and <em>z</em></em>
1080→ eay!</code></pre>
1081  <p>Cette génération est <strong>naïve</strong> mais ce n'est pas important. Ce
1082  qui est vraiment important est la génération des chemins dans les règles, ou
1083  autrement dit, la génération des <strong>séquences de lexèmes</strong>.</p>
1084
1085  <h4 id="Uniform_random_generation" for="main-toc">Génération aléatoire
1086  et uniforme</h4>
1087
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
1093  possibles. Succinctement, l'algorithme travaille en deux étapes :
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
1097  séquences et sous-séquences possibles de taille <em>n</em>. Cette étape aide
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>
1100  <p>Nous allons générer 10 données aléatoires de taille 7, c'est à dire
1101  composées de 7 lexèmes. Pour cela, nous allons utiliser la classe
1102  <code>Hoa\Compiler\Llk\Sampler\Uniform</code> qui prend en premier argument
1103  notre grammaire, en deuxième le générateur de valeurs de lexèmes (ici
1104  <code>Hoa\Regex\Visitor\Isototropic</code>) et enfin la taille :</p>
1105  <pre><code class="language-php">$sampler = new Hoa\Compiler\Llk\Sampler\Uniform(
1106    // Grammar.
1107    Hoa\Compiler\Llk\Llk::load(new Hoa\File\Read('Json.pp')),
1108    // Token sampler.
1109    new Hoa\Regex\Visitor\Isotropic(new Hoa\Math\Sampler\Random()),
1110    // Length.
1111    7
1112);
1113
1114for ($i = 0; $i &amp;lt; 10; ++$i) {
1115    echo $i, ' => ', $sampler->uniform(), "\n";
1116}
1117
1118/**
1119 * Will output:
1120 *     0 => [ false , null , null ]
1121 *     1 => [ " l " , null ]
1122 *     2 => [ [ true ] , true ]
1123 *     3 => [ [ [ 4435 ] ] ]
1124 *     4 => [ [ [ 9366 ] ] ]
1125 *     5 => [ true , false , null ]
1126 *     6 => { " |h&amp;lt;# " : false }
1127 *     7 => [ [ [ false ] ] ]
1128 *     8 => [ false , true , 7 ]
1129 *     9 => [ false , 5 , 79 ]
1130 */</code></pre>
1131  <p>Nous pouvons redéfinir la taille avec la méthode
1132  <code>Hoa\Compiler\Llk\Sampler\Uniform::setLength</code>. Nous aurons
1133  peut-être remarqué que certains opérateurs de répétition n'ont pas de bornes
1134  supérieures, comme <code>+</code> ou <code>*</code> ; dans ce cas, nous la
1135  définissons à <em>n</em>.</p>
1136
1137  <h4 id="Bounded_exhaustive_generation" for="main-toc">Génération exhaustive
1138  bornée</h4>
1139
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>
1143  <em>n</em> (c'est le caractère borné). Un aspect très intéressant de cet
1144  algorithme est que l'exhaustivité est une forme de <strong>preuve</strong> !
1145  L'algorithme fonctionne comme un itérateur et est très simple à utiliser :</p>
1146  <pre><code class="language-php">$sampler = new Hoa\Compiler\Llk\Sampler\BoundedExhaustive(
1147    // Grammar.
1148    Hoa\Compiler\Llk\Llk::load(new Hoa\File\Read('Json.pp')),
1149    // Token sampler.
1150    new Hoa\Regex\Visitor\Isotropic(new Hoa\Math\Sampler\Random()),
1151    // Length.
1152    7
1153);
1154
1155foreach ($sampler as $i => $data) {
1156    echo $i, ' => ', $data, "\n";
1157}
1158
1159/**
1160 * Will output:
1161 *     0 => true
1162 *     1 => false
1163 *     2 => null
1164 *     3 => " 8u2 "
1165 *     4 => { " ,M@aj{ " : true }
1166 *     5 => { " x`|V " : false }
1167 *     6 => { " NttB " : null }
1168 *     7 => { " eJWwA " : 0 }
1169 *     8 => [ true ]
1170 *     9 => [ true , true ]
1171 *     10 => [ true , true , true ]
1172 *     11 => [ true , true , false ]
1173 *     12 => [ true , true , null ]
1174 *     13 => [ true , true , 32 ]
1175 *     14 => [ true , false ]
1176 *     15 => [ true , false , true ]
1177 *     16 => [ true , false , false ]
1178 *     17 => [ true , false , null ]
1179 *     18 => [ true , false , 729 ]
1180 *     19 => [ true , null ]
1181 *     20 => [ true , null , true ]
1182 *     21 => [ true , null , false ]
1183 *     …
1184 *     157 => [ 780 , 01559 , 32 ]
1185 *     158 => 344
1186 */</code></pre>
1187  <p><em>A l'instar</em> de l'algorithme précédent, nous pouvons redéfinir la
1188  borne maximum avec la méthode
1189  <code>Hoa\Compiler\Llk\Sampler\BoundedExhaustive::setLength</code>. Et les
1190  opérateurs de répétition sans borne supérieure utilisent <em>n</em>.</p>
1191
1192  <h4 id="Grammar_coverage-based_generation" for="main-toc">Génération basée
1193  sur la couverture</h4>
1194
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
1198  est tout autre : il va générer des séquences de lexèmes qui vont
1199  « <strong>activer</strong> » toutes les <strong>branches</strong> des règles
1200  de la grammaire. Une règle est dite couverte si et seulement si ses
1201  sous-règles sont toutes couvertes, et un lexème est dit couvert s'il a été
1202  utilisé dans une séquence. Pour assurer une <strong>diversité</strong> dans
1203  les séquences produites, les points de choix entre des sous-règles non
1204  couvertes sont résolus par tirages <strong>aléatoires</strong>. L'algorithme
1205  fonctionne également comme un itérateur :</p>
1206  <pre><code class="language-php">$sampler = new Hoa\Compiler\Llk\Sampler\Coverage(
1207    // Grammar.
1208    Hoa\Compiler\Llk\Llk::load(new Hoa\File\Read('Json.pp')),
1209    // Token sampler.
1210    new Hoa\Regex\Visitor\Isotropic(new Hoa\Math\Sampler\Random())
1211);
1212
1213foreach ($sampler as $i => $data) {
1214    echo $i, ' => ', $data, "\n";
1215}
1216
1217/**
1218 * Will output:
1219 *     0 => true
1220 *     1 => { " )o?bz " : null , " %3W) " : [ false , 130 , " 6 " ] }
1221 *     2 => [ { " ny  " : true } ]
1222 *     3 => { " Ne;[3 " : [ true , true ] , " th: " : true , " C[8} " : true }
1223 */</code></pre>
1224  <p>Pour éviter l'explosion combinatoire et assurer la
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>,
1228  <code>1</code> et <code>2</code> fois, <code>+</code> répétera <code>1</code>
1229  et <code>2</code> fois, et enfin <code>{<em>x</em>,<em>y</em>}</code>
1230  répétera <code><em>x</em></code>, <code><em>x</em> + 1</code>,
1231  <code><em>y</em> - 1</code> et <code><em>y</em></code> fois. Cette heuristique
1232  trouve ses origines dans le test aux <strong>limites</strong>.</p>
1233  <p>Nous remarquons dans notre exemple que 4 données sont générées et suffisent
1234  à <strong>couvrir</strong> l'ensemble de notre grammaire !</p>
1235
1236  <h4 id="Comparison_between_algorithms" for="main-toc">Comparaison entre
1237  les algorithmes</h4>
1238
1239  <p>Voici quelques <strong>indices</strong> pour savoir quand utiliser tel ou
1240  tel autre algorithme.</p>
1241  <dl>
1242    <dt>Génération aléatoire et uniforme :</dt>
1243    <dd><ul>
1244      <li data-item="+">rapide pour des petites données, grande diversité dans
1245      les données et taille fixe ;</li>
1246      <li data-item="-">la phase de pré-calcul est exponentielle et donc
1247      longue bien que, ensuite, la génération soit très rapide.</li>
1248    </ul></dd>
1249    <dt>Génération exhaustive bornée :</dt>
1250    <dd><ul>
1251      <li data-item="+">rapide pour des petites données et l'exhaustivité est
1252      efficace ;</li>
1253      <li data-item="-">nombre exponentiel de données.</li>
1254    </ul></dd>
1255    <dt>Génération basée sur la couverture :</dt>
1256    <dd><ul>
1257      <li data-item="+">rapide pour des données de taille moyenne ou grande,
1258      et diversité des données ;</li>
1259      <li data-item="-">ne considère pas de taille.</li>
1260    </ul></dd>
1261  </dl>
1262
1263  <h2 id="LL1_compiler-compiler" for="main-toc">Compilateur de compilateurs
1264  LL(1)</h2>
1265
1266  <p>La documentation pour le compilateur LL(1), à travers la classe
1267  <code>Hoa\Compiler\Ll1</code>, n'est pas encore écrite. L'objectif est
1268  différent de <code>Hoa\Compiler\Llk</code> : il n'existe pas de langage
1269  intermédiaire, les automates sont codés en dur avec des tableaux et ce type de
1270  compilateurs est orienté haute performance. C'est pourquoi son comportement
1271  est <strong>monolithique</strong>.</p>
1272
1273  <h2 id="Conclusion" for="main-toc">Conclusion</h2>
1274
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
1282  <em lang="en">hackable</em>. Enfin, différents algorithmes permettent de
1283  <strong>générer</strong> des données à partir d'une grammaire selon le
1284  contexte d'utilisation.</p>
1285
1286</yield>
1287</overlay>
1288