Compiler les expressions rationnelles (par substitution)

21

Votre tâche consiste à compiler des expressions régulières ... en spécifiant une substitution pour chaque caractère dans une expression régulière.

Regexes

Les expressions régulières soutiennent ces

REGEX       = (LITERAL REGEX / GROUP REGEX / STAR REGEX / ALTERNATIVE)
LITERAL     = 1 / 0
GROUP       = '(' REGEX ')'
STAR        = (LITERAL / GROUP) '*'
ALTERNATIVE = '('REGEX ('|' REGEX)*')'

Pourquoi seulement 1 ou 0? C'est pour simplifier. Le regex n'a donc que les caractères suivants:

*()|10

Il est interprété comme suit:

  1. * est une étoile de Kleene (répétez le groupe de gauche ou littéral 0 ou plusieurs fois).
  2. | est l'alternance (correspond si la regex à gauche ou la regex à droite correspond).
  3. () est le regroupement.
  4. 1 correspond au caractère 1.
  5. 0 correspond au caractère 0.

Comment compiler?

Vous spécifiez six extraits de code: un pour remplacer chaque caractère regex. Par exemple, si votre réponse est:

*: FSAGFSDVADFS
|: GSDGSAG
(: GSDG
): GDSIH
1: RGIHAIGH
0:GIHEBN

Ensuite, vous remplacez chaque expression régulière par son extrait de code respectif, donc:

(0|11)*

est transformé en:

GSDGGIHEBNGSDGSAGRGIHAIGHRGIHAIGHGDSIHFSAGFSDVADFS

Quel est le programme résultant censé faire?

Votre programme:

  1. Prenez l'entrée.
  2. Sortez une valeur véridique si l'expression régulière correspond à l'entrée entière.
  3. Sinon, émettez une valeur fausse.

L'entrée à l'extérieur 01est un comportement indéfini. L'entrée peut être vide.

Règles supplémentaires

  1. Pour un caractère regex donné, l'extrait de code résultant doit toujours être le même.
  2. Aucun préfixe ou suffixe n'est ajouté par la suite.
  3. Le regex est garanti non vide.

Notation

L'extrait le moins combiné est le gagnant. Ainsi, le score pour l'exemple de cas serait calculé comme suit:

FSAGFSDVADFS+ GSDGSAG+ GSDG+ GDSIH+ RGIHAIGH+GIHEBN

12 + 7 + 4 + 5 + 8 + 6 = 42

Akangka
la source
Chaque extrait doit-il contenir au moins 1 caractère?
trichoplax
L'extrait peut avoir une longueur nulle. L'édition est OK.
Akangka
La langue RegEx est-elle valable pour ce défi? : P
Loovjo
Je considère que RegEx a intégré RegEx. Je suis obligé de faire ça. Je veux exclure Retina et regex, cependant, selon Mego, ce n'est pas autorisé. Pourtant, je ne sais pas pour les escargots et les amis.
Akangka
@ChristianIrwan Fait intéressant, je ne suis toujours pas sûr que cela soit même résoluble dans la rétine, et même si c'est le cas, ce sera loin d'être compétitif.
Martin Ender

Réponses:

7

Escargots , 48 octets

0 -> )0(\0!(l.)(~

1 -> )0(\1!(l.)(~

( -> )0({{(

) -> )0}}(~

| -> )0}|{(

* -> )0),(~

Si nous devions rechercher des correspondances partielles plutôt que de rechercher uniquement l'entrée complète, ce serait très facile. 0deviendrait \0, 1deviendrait \1, *deviendrait ,, et les autres se cartographieraient. Au lieu de cela, il y a beaucoup de manigances pour empêcher les matchs de commencer ailleurs que le début ou de se terminer ailleurs que la fin. !(l.)est une assertion qui échouera si le début de la correspondance n'est pas au début de l'entrée. ~correspond à une cellule en dehors de l'entrée, elle est donc ajoutée à tous les caractères autorisés à la fin de l'expression régulière. S'il y a un autre caractère regex suivant, il est annulé par un quantificateur numérique0ce qui nécessite qu'il soit mis en correspondance 0 fois, essentiellement en le commentant. Pour permettre à *( ,) de fonctionner correctement malgré le fait que le test fictif hors limites soit gênant, les règles de correspondance des parenthèses du langage sont largement utilisées. De la documentation:

Les paires de parenthèses ()ou d'accolades assorties {}se comporteront comme prévu (comme les parenthèses dans l'expression régulière), mais il est également possible d'omettre la moitié d'une paire et de la déduire, selon les règles suivantes. )ou }regroupe tout vers la gauche jusqu'à l'instruction d'ouverture de groupe non fermée la plus proche du même type ( (ou {respectivement), ou le début du modèle s'il n'en existe pas. Il ferme toutes les instructions d'ouverture non fermées du type opposé au milieu de cette plage. Un autre inégalé (ou {est fermé à la fin du motif.

Clair comme de la boue, non?

feersum
la source
Soupir, j'oublie qu'il y a même un langage correspondant en dehors des expressions régulières. Beau travail, mais désolé, pas de vote positif (pas de vote négatif non plus)
Akangka
@ChristianIrwan il y a en fait tout un défi sur ce site pour développer des langages 2d correspondants, dont la plupart ont des utilisations dégénérées 1d. codegolf.stackexchange.com/questions/47311/…
Sparr
7

CJam, 151 octets

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

Les lignes correspondent aux caractères 01(|)*(dans cet ordre). Essayez-le en ligne!

Cela n'utilise aucune expression régulière intégrée ou d'autres types de correspondance de modèle. En fait, CJam n'a aucune de ces fonctionnalités. Au lieu de cela, il commence à partir de l'expression régulière qu'il représente et construit toutes les chaînes possibles qu'il pourrait correspondre, pour enfin vérifier si l'entrée utilisateur est l'une d'entre elles.

Essais

Ce qui suit utilise un programme qui lit une expression régulière à partir de STDIN, remplace chacun de ses caractères par l'extrait de code approprié et évalue enfin le code généré pour voir s'il correspond à l'entrée spécifiée dans l'argument de ligne de commande.

$ cat regex.cjam
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

"N%ers~
$ cjam regex.cjam '' <<< '(|)'
1
$ cjam regex.cjam '0' <<< '(|)'
0
$ cjam regex.cjam '' <<< '0(|)'
0
$ cjam regex.cjam '0' <<< '0(|)'
1
$ cjam regex.cjam '' <<< '(0|11)*'
1
$ cjam regex.cjam '0' <<< '(0|11)*'
1
$ cjam regex.cjam '11' <<< '(0|11)*'
1
$ cjam regex.cjam '011011000' <<< '(0|11)*'
1
$ cjam regex.cjam '1010' <<< '(0|11)*'
0

Malheureusement, ce n'est pas particulièrement rapide. Il s'étouffera assez rapidement s'il y a plus de 9 caractères dans l'entrée ou plus d'une seule étoile Kleene dans l'expression régulière.

Au coût de 5 octets supplémentaires - pour un total de 156 octets - nous pouvons générer des chaînes plus courtes pour faire correspondre l'entrée potentielle et les dédupliquer. Cela ne change pas le fonctionnement du code; cela le rend simplement plus efficace.

$ cat regex-fast.cjam 
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+eas,)m*:sSf-L|\"T

"N%ers~
$ cjam regex-fast.cjam '0101001010' <<< '(01|10)*'
0
$ cjam regex-fast.cjam '011001101001' <<< '(01|10)*'
1
$ cjam regex-fast.cjam '0' <<< '(0*1)*'
0
$ time cjam regex-fast.cjam '101001' <<< '(0*1)*'
1
Dennis
la source
J'ai encore une idée de comment je pourrais rendre cela plus court et / ou plus rapide. J'ajouterai une explication lorsque je serai satisfait des résultats.
Dennis
Il semble y avoir un superflu `-escaping of the "" dans le schéma de *. Indépendamment de cela, je n'ai pas pu faire accepter ce programme à n'importe quelle entrée, même pour le cas le plus simple où l'expression régulière ne consiste qu'en un 0(voir test dans l' interpréteur en ligne ). Je me trompe?
matz
1
@matz Mon code utilise des arguments de ligne de commande, qui ne sont pas implémentés dans cet interpréteur. Essayez plutôt celui-ci .
Dennis