Comments on Méditations sur les regexps « étendues »

Ruxor (2013-03-25T22:20:14Z)

@Yang: <URL: http://www.lrde.epita.fr/~akim/thl/lecture-notes/theorie-des-langages-1.pdf > (ce n'est pas moi qui en suis l'auteur, j'enseigne juste à un des cinq groupes ; par ailleurs, nous traitons un sous-ensemble assez petit de ce que ce poly recouvre).

Yang (2013-03-25T20:29:14Z)

Est-ce que les cours sont disponibles en PDF ?

Arnaud Spiwack (2013-03-23T08:14:17Z)

Par curiosité, j'ai regardé comment OCaml se comportait. Et apparemment il se comporte comme egrep (les \n non-affectés ne matchent rien, les \n correspondent au dernier groupe matché par le groupe concerné, le backtrack revient sur les assignation de valeurs aux backreferences).

Je soupçonne qu'on pourrait essayer de définir des automates où l'action des lettres a lieu dans la catégorie de Kleisli de la monade d'état (la monade associée à l'adjonction des catégories cartésienne close). La somme qui backtracke sur l'état se définit là-dedans assez naturellement. Après, je ne sais pas trop par quel bout le prendre après ça (et je n'ai surtout pas franchement le temps…).

Les motifs récursifs, en revanche, me paraissent plus domesticable. Si je devais faire une conjecture, je dirais que ça va capturer exactement les grammaires hors-contexte.


You can post a comment using the following fields:
Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: df8679


Recent comments