• Malian
  • Petite pousse
  • Offline
  • Enregistré : 25 May. 2009
  • Posts info : 32

Sujet : Regex + Grammar

Bien le bonjour ici,

Je suis régulièrement le dépot Mercurial et je vois que tu "joues" beaucoup avec le fichier Library/Regex/Grammar.pp ...
Alors voilà, je me demande bien à quoi il sert ou va servir ?
C'est quoi cette extension .pp ?

Si tu savais m'éclairer je t'en remercierais smile

Malian

2 réponse par Hywan

  • Hywan
  • Administrateur
  • Offline
  • De : Montécheroux
  • Enregistré : 06 Apr. 2008
  • Posts info : 1,659

Re : Regex + Grammar

Hey smile,

Pour mon mémoire de fin de master, je dois travailler entre autre les expressions régulières (mais pas que, c'est bien plus compliqué).

Avant, on avait Hoa\Compiler\Ll1 qui est un compiler compiler, c'est à dire un compilateur de compilateur, une sorte de compilateur abstrait, comme le fait par exemple JavaCC/JJTree, Flex/Bison etc. Sauf que comme son nom l'indique, il n'est que LL(1), et non LL(k) ou LALR. C'est utile pour Hoa\Xml\CssToXPath par exemple, qui compile à la volée et très rapidement des expressions de sélecteurs CSS3 en XPath2, ou même pour Hoa\Test\Praspel\Compiler qui est un langage de spécification.
Mais le besoin se faisait sentir d'avoir un LL(k). C'est pourquoi mon encadrant de recherche (Frédéric Dadeau) a créé un compiler compiler LL(k), que j'ai adapté pour donner lieu à Hoa\Compiler\Llk. Pour faciliter son utilisation, j'ai créé un langage par dessus (exemple : la grammaire du langage pp écrite en … pp !). Langage stocké dans des fichiers portant l'extension .pp.

Du coup, on est capable d'analyser lexicalement et syntaxiquement des expressions régulières, grâce à Library/Regex/Grammar.pp. Ça nous donne quoi ? Un exemple ? Facille : 

<?php

require '/usr/local/lib/hoa/Core/Core.php';

from('Hoa')
-> import('Compiler.Llk')
-> import('Compiler.Visitor.Dump')
-> import('File.Read');

$compiler = Hoa\Compiler\Llk::load(
    new Hoa\File\Read('hoa://Library/Regex/Grammar.pp')
);
$regex    = 'ab(cd)?xy(z{2,4}|rs*(?(1)t?|t??))[^a-c]';


echo '= ' . $regex . "\n\n\n";
$ast      = $compiler->parse($regex);
$dump     = new Hoa\Compiler\Visitor\Dump();
echo $dump->visit($ast);

À l'exécution ça donne ceci (quand on affiche l'AST — Abstract Syntax Tree) : 

= ab(cd)?xy(z{2,4}|rs*(?(1)t?|t??))[^a-c]


>  #expression
>  >  #concatenation
>  >  >  token(literal, a)
>  >  >  token(literal, b)
>  >  >  #quantification
>  >  >  >  #capturing
>  >  >  >  >  #concatenation
>  >  >  >  >  >  token(literal, c)
>  >  >  >  >  >  token(literal, d)
>  >  >  >  token(zero_or_one, ?)
>  >  >  token(literal, x)
>  >  >  token(literal, y)
>  >  >  #capturing
>  >  >  >  #alternation
>  >  >  >  >  #quantification
>  >  >  >  >  >  token(literal, z)
>  >  >  >  >  >  token(n_to_m, {2,4})
>  >  >  >  >  #concatenation
>  >  >  >  >  >  token(literal, r)
>  >  >  >  >  >  #quantification
>  >  >  >  >  >  >  token(literal, s)
>  >  >  >  >  >  >  token(zero_or_more, *)
>  >  >  >  >  >  #absolutecondition
>  >  >  >  >  >  >  token(index, 1)
>  >  >  >  >  >  >  #quantification
>  >  >  >  >  >  >  >  token(literal, t)
>  >  >  >  >  >  >  >  token(zero_or_one, ?)
>  >  >  >  >  >  >  #quantification
>  >  >  >  >  >  >  >  token(literal, t)
>  >  >  >  >  >  >  >  token(zero_or_one_lazy, ??)
>  >  >  #negativeclass
>  >  >  >  #range
>  >  >  >  >  token(literal, a)
>  >  >  >  >  token(literal, c)

Tu peux t'amuser avec. Normalement, quasiment la totalité des PCRE est maintenant supportée.

Mais quel intérêt ?
Bah mes recherches actuelles au LIFC sont concentrées sur l'automation de génération de tests unitaires, et plus génériquement sur la génération automatique de données de tests. Pour cela, on a les domaines réalistes. Et les principes que proposent les domaines réalistes sont la vérification et la génération. Si on est capable de sortir l'AST d'une expression régulière, alors on est aussi capable de générer des données validant cette expression régulière ! Les opportunités sont très grandes. Les expressions régulières sont un langage puissant pour exprimer des contraintes sur la forme d'une chaîne de caractères (et sur bien plus que des chaînes d'ailleurs). Ce serait donc un domaine réaliste très important. Par exemple, si on reprend notre programme avec une regex différente et un visiteur différent : 

<?php

require '/usr/local/lib/hoa/Core/Core.php';

from('Hoa')
-> import('Compiler.Llk')
-> import('Compiler.Visitor.Dump')
-> import('Regex.Visitor.Realdom')
-> import('Test.Sampler.Random')
-> import('File.Read');

$compiler = Hoa\Compiler\Llk::load(
    new Hoa\File\Read('hoa://Library/Regex/Grammar.pp')
);
$regex    = '[x-yza-c]+(?<foo>\.[abcdefg]+){0,2}@[a-z]+\.(fr|com|org)';


echo '= ' . $regex . "\n\n\n";
$ast      = $compiler->parse($regex);
$dump     = new Hoa\Compiler\Visitor\Dump();
echo $dump->visit($ast);

echo "\n\n";

$realdom = new Hoa\Regex\Visitor\Realdom(new Hoa\Test\Sampler\Random());
echo $realdom->visit($ast);

On va dumper notre AST comme avant, mais on va faire un deuxième visite de notre AST avec Hoa\Regex\Visitor\Realdom accompagné d'un générateur (d'entier et de nombre flottants) aléatoire. Le résultat pourra être : 

= [x-yza-c]+(?<foo>\.[abcdefg]+){0,2}@[a-z]+\.(fr|com|org)


>  #expression
>  >  #concatenation
>  >  >  #quantification
>  >  >  >  #class
>  >  >  >  >  #range
>  >  >  >  >  >  token(literal, x)
>  >  >  >  >  >  token(literal, y)
>  >  >  >  >  token(literal, z)
>  >  >  >  >  #range
>  >  >  >  >  >  token(literal, a)
>  >  >  >  >  >  token(literal, c)
>  >  >  >  token(one_or_more, +)
>  >  >  #quantification
>  >  >  >  #namedcapturing
>  >  >  >  >  token(capturing_name, foo)
>  >  >  >  >  #concatenation
>  >  >  >  >  >  token(literal, \.)
>  >  >  >  >  >  #quantification
>  >  >  >  >  >  >  #class
>  >  >  >  >  >  >  >  token(literal, a)
>  >  >  >  >  >  >  >  token(literal, b)
>  >  >  >  >  >  >  >  token(literal, c)
>  >  >  >  >  >  >  >  token(literal, d)
>  >  >  >  >  >  >  >  token(literal, e)
>  >  >  >  >  >  >  >  token(literal, f)
>  >  >  >  >  >  >  >  token(literal, g)
>  >  >  >  >  >  >  token(one_or_more, +)
>  >  >  >  token(n_to_m, {0,2})
>  >  >  token(literal, @)
>  >  >  #quantification
>  >  >  >  #class
>  >  >  >  >  #range
>  >  >  >  >  >  token(literal, a)
>  >  >  >  >  >  token(literal, z)
>  >  >  >  token(one_or_more, +)
>  >  >  token(literal, \.)
>  >  >  #capturing
>  >  >  >  #alternation
>  >  >  >  >  #concatenation
>  >  >  >  >  >  token(literal, f)
>  >  >  >  >  >  token(literal, r)
>  >  >  >  >  #concatenation
>  >  >  >  >  >  token(literal, c)
>  >  >  >  >  >  token(literal, o)
>  >  >  >  >  >  token(literal, m)
>  >  >  >  >  #concatenation
>  >  >  >  >  >  token(literal, o)
>  >  >  >  >  >  token(literal, r)
>  >  >  >  >  >  token(literal, g)


azycbyy@xyiegx.fr

Si tu relances le programme, tu auras d'autres données produites : 

yzbazx@utes.org
yxzzzz@bboko.fr
bccb@sjlmgfe.org
x@wu.fr
etc.

Depuis hier, je travaille sur un meta compiler compiler c'est à dire que le compilateur analyse n'importe quel grammaire en utilisant sa propre grammaire et est donc capable de générer des données validant n'importe quelle grammaire (comme on le fait dans l'exemple mais de manière générique et abstraite).

Voilà pourquoi je travaille sur ça en ce moment smile.
Bien sûr, ça concerne le côté « universitaire » de Hoa. Ni le développement de Hoa ni de Hoathis n'est mis de côté. Je dirais même qu'ils n'ont jamais été aussi actifs smile.

« Un handicap est le résultat d'une rencontre entre une déficience ou différence et une incapacité de la société à répondre à celle-ci. »

Hywan Website

3 réponse par Malian

  • Malian
  • Petite pousse
  • Offline
  • Enregistré : 25 May. 2009
  • Posts info : 32

Re : Regex + Grammar

Intéressant !

Maintenant si j'ai bien compris, ça permettrait par exemple de générer un certain nombre de valeurs juste à partir d'une regex pour les test unitaires comme par exemple les emails ci-dessus ?

Merci pour ta réponse en tout ca!

4 réponse par Hywan

  • Hywan
  • Administrateur
  • Offline
  • De : Montécheroux
  • Enregistré : 06 Apr. 2008
  • Posts info : 1,659

Re : Regex + Grammar

Oui c'est l'idée. Comme Praspel (le langage d'annotation et de spécification) utilise les domaines réalistes, si tu as le domaine réaliste regex, tu peux exprimer de sacrés contraintes sur la forme des chaînes de caractères que prend ta méthode en entrée. Et on peut soit tester manuellement soit automatiquement (par génération automatique).

« Un handicap est le résultat d'une rencontre entre une déficience ou différence et une incapacité de la société à répondre à celle-ci. »

Hywan Website