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 &lt;true> | &lt;false> | &lt;null> | string() | object() | array() | number() 254 255string: 256 ::quote_:: &lt;string> ::_quote:: 257 258number: 259 &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>&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>&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 ( &lt;foo1> | &lt;foo2> ) &lt;bar> &lt;baz> &lt;qux> &lt;tada> &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:: &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]:: &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;$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 &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 &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('&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 * &lt; &lt; &lt; &lt; ekzit string 883 * token colon, consumed : 884 * > > > > enter value 885 * token true, consumed true 886 * &lt; &lt; &lt; &lt; ekzit value 887 * &lt; &lt; &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 * &lt; &lt; &lt; &lt; &lt; &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 * &lt; &lt; &lt; &lt; &lt; &lt; &lt; &lt; ekzit value 904 * > > > > > > > > enter 21 905 * > > > > > > > > > enter 20 906 * token comma, consumed , 907 * > > > > > > > > > > enter value 908 * token number, consumed 42 909 * &lt; &lt; &lt; &lt; &lt; &lt; &lt; &lt; &lt; &lt; ekzit value 910 * &lt; &lt; &lt; &lt; &lt; &lt; &lt; &lt; &lt; ekzit 20 911 * &lt; &lt; &lt; &lt; &lt; &lt; &lt; &lt; ekzit 21 912 * token _bracket, consumed ] 913 * &lt; &lt; &lt; &lt; &lt; &lt; &lt; ekzit array 914 * &lt; &lt; &lt; &lt; &lt; &lt; ekzit value 915 * &lt; &lt; &lt; &lt; &lt; ekzit pair 916 * &lt; &lt; &lt; &lt; ekzit 12 917 * &lt; &lt; &lt; ekzit 13 918 * token _brace, consumed } 919 * &lt; &lt; ekzit object 920 * &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 &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&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