D'une reconnaissance d'expressions à une traduction de programmes ✍🏼🟩➡🌳➡🔵📱

Seconde publication d'une série d'articles sur le sujet

Croisillons: #RegExp #Traduction

Lectrices et lecteurs que j'avais en tête lors de l’écriture :

• Personnes ayant rencontré
  une expression régulière (RegExp)
  une fois dans sa vie et
  curieuse d’en apprendre plus à son sujet

Notre état d’avancement dans cette série : 2 / 2
🟩⬜

Temps approximatif de lecture : 5 min

---

Le premier article de cette série sur le sujet des RegExp
peut être découvert à cette adresse :

thierry.sioukam.re/pages/reconnaissance-expressions-regulieres-traduction-programmes

Exemples de mise en application de règles syntaxiques

Les expressions sont reconnues au moyen

• de règles 📏 exprimées sous forme de RegExp 📐et

• d'analyse récursive ^1 descendante ^2

En informatique, les arbres (comme structures de données 🌳)
nous mettent la tête à l’envers si vous voyez ce que je veux dire et
quand ils sont inversés, peut-être de manière à pouvoir les lire,
écrire ou imprimer de haut en bas (?) 🙃 ^3

Et ce, quand bien même on tenterait de les gravir 🧗🏼,
ces arbres 🌳 (pardi !)
depuis leur racine (code source dans sa totalité) c.a.d.
d'interpréter du code décomposable en jetons ou «Token» 🪙🤔
jusqu'à atteindre des feuilles🍃,
encore connus sous le nom de symboles terminaux
tels que «const» en JavaScript.

Règle de grammaire pour JavaScript comprenant des symboles terminaux : "var" et "const"

^1

La reconnaissance de l’essence d’une expression fait intervenir une récursivité
(ou comment s’attraper soi-même par le col de sa propre veste en défiant toutes les lois de la physique - bien entendu, aucun châton universel n’aura jamais été séparé de sa mère ici mais une douce pile d’appel aura été mis à contribution de manière habile).

Mathis Hammel @MathisHammel

Mini-thread : pourquoi il est dangereux d'utiliser des fonctions récursives sans réfléchir aux conditions de sortie.

July 30th 2022

2,412 Retweets10,949 Likes

Voici par exemple une règle suggèrant qu'au plus proche
de la racine d'un arbre (syntaxique),
un source est constitué d'une expression de type «statement» :

sourceElement
    : statement
    ;

Règle de grammaire pour JavaScript impliquant la définition de la racine de l’arbre syntaxique représentant un source

Cette autre règle tronquée sert lors de la reconnaissance d'éléments
de syntaxe sous-jacents à notre expression de type «statement» précédente :

statement
    : block
    | variableStatement
    | importStatement
    | exportStatement
[...]
    | functionDeclaration
    ;

Règle concernant la définition d'une déclaration de type «statement» pour une grammaire de JavaScript.

C'est ainsi qu'un interpréteur parcourt des blocs d'expression 🚶🏼
en s’intéressant à ses sous-expressions (régulières) par endroit et
au moyen de «sortes d’agrandissements» ¹ 🔍
et ce afin de valider la conformité aux règles formulées
sous forme de RegExp.

En effet, les symboles "|" dans les exemples ci-dessus sont des OU logiques
(comme on pourrait le soupçonner dans le cas
où on les aurait rencontré auparavant).

In fine, tout code source est parcouru 🏃🏼
(et validé pour une grammaire donnée voire même plusieurs fusionnées (!)
- telle qu’avec celle de PHP par exemple embarquant
des éléments de syntaxe de type balises XHTML
(ou tout source contenant du JSX,
feuilles de style et gabarits proche de documents HTML).

Extrait de grammaire de PHP en provenance du projet ANTLR https://github.com/antlr/grammars-v4/blob/master/php/PhpParser.g4

^2 ^3

Pourquoi un parcours «descendant» quand un arbre monte (généralement) au ciel ?

On pourrait très bien se contenter d’exprimer

• que des structures de données
  en informatique seraient ce qu'elles sont 😅🤷🏼 ou encore

• qu’on peut s'imaginer une terre ronde,
  flottante dans un quasi-vide sans haut ni bas et
  tout irait alors (un peu) mieux. 🙃😌

Aller un peu loin

Comment donc relier ces expressions avec les automates cités
à certaines intersections du fil original ?

🌳 Olivier Pirson — OPi 🇧🇪🇫🇷🇬🇧 @OPirson

@ledevnovice À l'origine c'est un concept théorique équivalant aux automates finis. Dans l'usage pratique, qui en est souvent une version étendue, c'est un super CTRL-F, une façon concise (et illisible 😉) de décrire un motif textuel, avec des caractères génériques, des répétitions, etc.

August 13th 2022

3 Likes

Par ailleurs, j'ai déployé auparavavant
un outil d'aide à la visualisation du passage possible de RegExp à des automates 👀 .
Cet outil s'appuie sur des bibliothèques aux sources ouverts et qui ont été citées.

Je recommande vivement la consultation du «dragon book» 🐲,
et ce malgré le fait de n’avoir encore jamais été en mesure
de terminer la lecture complète de
«Compilers: Principles, Techniques, and Tools»
de Alfred V. Aho, Jeffrey D. Ullman, Ravi Sethi Avaya et Monica S. Lam.

En dépit du fait qu'il s'agisse d'un «incontournable» du sujet, 🫥🙊😓
je tiens à souligner que rien ne devrait nous empêcher
de picorer des principes, idées fondatrices afin de répondre à besoins métier
qu’on est susceptible de rencontrer en entreprise ou ailleurs. 🌱

Des écrits tels que ceux de

• Thorsten Ball (@thorstenball),

• Terence Parr (@the_antlr_guy),

• Bob Nystrom (@munificentbob)

sont immédiatement «actionnables» et
à corréler étroitement à l’objet d’une recherche en lien avec ces sujets
(curiosité, formation etc.) :

• Projet ANTLR (ANother Tool for Language Recognition) - antlr.org

• Writing A Compiler In Go - compilerbook.com

• Crafting Interperters - craftinginterpreters.com

Parenthèse(s)? fermante(s)? 🌯

Interprétation, transpilation, compilation…
sont autant de traductions nécessitant des règles décrites avec

• RegExp et

• uriosités feuillues :
  des arbres syntaxiques. 🌳

La Tour de Babel - Pieter Bruegel the Elder, 1563

🧗🏼 Grimper à ces arbres consistent ni plus ni moins à traduire avec fidélité.

Message d’utilité publique 📢

Veillons toutefois à n’injecter des RegExp dans nos programmes
qu’avec modération 🥴

Après déjeuner, elles iraient mieux de paire avec

• 🛑 un nombre de caractères limités

• 😌 des parenthèses capturantes bien nommées

• 🛩 un biais des survivants renforcé

Le dernier point pourra en laisser plus d’un sceptique alors j’ajoute
les liens suivants en référence soulignant dans quelle mesure,
l’utilisation de ces expressions peut s’avérer risquée ou
contre-productive sur le long terme:

• Issue intitulée [RFC] Simplify the Email Validator
  découverte au gré du hasard au sein de la communauté Symfony

• Details of the Cloudflare outage on July 2, 2019.

1. C’est à dire qu’au moyen de la récursivité,
on applique des opérations similaires à celles appliquées auparavant
de manière répétée et en gardant en mémoire des résultats intermédiaires,
qu’on réutilisera ensuite. ➰