Analyse lexicale

Les procédures standard sont implémentées plutôt comme méthodes que comme fonctions.

Le débruitage et la tokenisation des textes humains peuvent être plus compliqués que l'on n'y pense, et pas seulement à sause des séparateurs comme les apostrophes ou les tirets (dans des mots composites). La ponctuation peut être ou ne pas être importante ! Si nous voulons construire une base documentaire (un dictionnaire, un document indexé par des mots cherchables), alors les virgules, points, interrogations, etc. ne jouent aucun rôle.

Mais si on veut faire une analyse fréquentielle, la distribution des n-grammes au niveau des mots, afin de pouvoir faire des phrases synthétiques, les marqueurs de fin de phrase (au moins le point), et les séparateurs de segments dans les phrases : les virgules – deviennent utiles, constituent des "mots". Le rôle des apostrophes peut aussi être ambigu (guillemet, séparateur avec l'élision : "l'élision", ou lien dans des formes composées : "aujourd'hui". Bref, l'analyse lexicale, encore à la phase typographique, loin des raisonnements structurels, pose déjà quelques problèmes, et son automatisation n'est pas si facile.

Nous serons modestes, parlerons des techniques de tokenisation de base, surtout à l'aide des expressions régulières qui décrivent des classes des mots respectant quelques contraintes. Ce que vous apprenez ici, vous servira également dans le cours de compilation en L3, et dans plusieurs projets de programmation.

Regexps, définition et usage de base

Afin qu'un motif puisse représenter une classe (plus d'un élément), on place dedans quelques métacaractères : caractères spéciaux, qui symbolisent d'autres choses que les caractères eux-mêmes. Parfois ces métacaractères sont des "séquences d'échappement", par ex. \s ou \t, avec quelques lettres ayant un sens spécial seulement si préfixées par le backslash \ . Voici quelques métacaractères et séquences :

• "." Le point représente n'importe quel caractère. Le pattern "st.p" peut représenter : "step", "stop", "stXp", "st@p", "st p", "st.p", etc.
• "|" La barre verticale c'est alternative : "alpha|beta" représente "alpha" OU "beta". Plus tard nous utiliserons les parenthèses pour grouper/factoriser les sous-chaînes alternatives, mais c'est plus compliqué que ça.
• "?" dénote un caractère optionnel (donc un ou zéro caractères), et c'est le caractère qui précède le point d'interrogation qui peut on non être présent. "st?p" décrit "stp" et "sp". Mais le prédecesseur peut être composite, "al(ph)?a" reconnaît "ala" et "alpha". Les parenthèses sont aussi des métacaractères, qui groupent les sous-chaînes. Elles seront discutées séparément.
• "*" représente 0 ou un nombre quelconque d'entités (caractères ou groupes) identiques au prédécesseur. "st*p" s'apparie avec : "sp", "stp", "sttp", "stttp", etc.
• "+" représente 1 ou un nombre quelconque plus grand d'entités constituant le prédécesseur. Par exemple, le motif : "(0|1|2|3|4|5|6|7|8|9)+" représente une séquence non-vide de chiffres décimaux. Nous verrons que ceci peut être codé de manière plus commode (imaginez coder ainsi n'importe quelle lettre...).
• Tout métacaractère précédé par "\" devient littéral. "\." décrit le point, "\\" est le backslash.

Avant de continuer, attention ! Le "langage" formel des patterns réguliers peut être un peu différent des patterns figurant dans les programmes dans des langages de programmation ! (Python, Javascript, PHP ...). Quelques autres regexps.

• Classes de caractères. La forme "[x-y]" décrit UN caractère entre x et y. Ainsi un chiffre est "[0-9]". On peut les lister individuellement : "[1023459867]". Le premier caractère dans une classe étant "^" signifie la négation : [^A] – n'importe quel caractère sauf "A".
• Séquences. "\s" : un caractère blanc (espace, tab, fin de ligne). "\S" : un caractère NON-blanc. "\w" : un caractère alpha-numérique (plus l'underscore "_"). "\W" : NON-alphanumérique. "\d" : un chiffre, "\D" : un non-chiffre.
• "\A" : s'apparie avec rien (chaîne vide), mais seulement en début de la chaîne. C'est un "marqueur". "\Z" : fin de chaîne.
• {m} : Répétition, comme + ou *, mais avec exactement m occurrences de l'entité précédente. {m,n} : entre m et n, en essayant de s'apparier avec la chaîne la plus longue. {m,n}? : entre m et n, mais essayant de trouver la chaîne la plus courte.
• \nombre , par ex. \1, \3, \0, etc. s'apparie avec un groupe numéroté, identifié auparavant. ceci sera discuté et exemplifié dans quelques instants. Ceci n'est pas une regexp "formelle", plutôt un mécanisme de programmation.

Voici quelques utilités de base. Nos descriptions ne peuvent être complètes.

• re.findall(pat, chn, flags=0), où pat est un motif (compilé ou non). Cette fonction retourne toutes les chaînes conformes avec le motif. Les flags est une combinaison de drapeaux – infos sur les caractères nationaux, les options comme : "." reconnaît la fin de ligne ou non, etc. Il existe la variante re.finditer(...) qui retourne non pas une liste, mais un itérateur sur les match objects.
• re.sub(pat, repl, chn, count=0, flags=0) remplace dans la chaîne la sous-chaîne appariée par le motif par repl. Le drapeau count peut limiter le nombre de substitutions.
• re.search(pat, chn, flags=0) Cette procédure est le dispositif de recherche de base, elle cherche la correspondance entre le motif et une sous-chaîne. Puisque cette correspondance peut être multi-value et contenir des fragments attrapés par les groupes (discutés tout de suite), le résultat est un objet spécial, un match-object que nous appelerons l'appariement, ou None au cas d'échec. Il existe une procédure similaire : re.match(...) qui devra trouver l'appariement en tout début de la chaîne (search : n'importe où).

Les méthodes des motifs compilés, et les groupes

Nous avons aussi rex.findall(...), rex.split(chn, maxsplit=0) qui scinde la chaîne en utilisant le motif comme séparateur, etc.

Les parenthèses dans [la source d'] un motif : "xxx(yyy)zzz(www)uuu" ont plus d'utilité que de grouper les sous-expressions répétées ou alternatives.

Chaque groupe "...(...) ..." stocke l'appariement correspondant comme un "groupe" au sens technique, qui peut ensuite être enquêté et réutilisé. Par exemple, si la chaîne est tst=" avant #contenu# après", et le motif :
dl = re.compile("#(\w+)#"), l'appariement complet trouve "#contenu#". Mais après l'exécution de mtch=dl.search(tst), on vérifie : mtch.group(1) → 'contenu'. On peut choisir d'autre groupe si existant, et ..groups() repertorie tous les groupes. Le motif : "([*|#+])(\w+)\\1" trouvera le texte délimité comme mtch.group(2). Le premier choisit le délimiteur, qui doit se répéter. On peut trouver donc #contenu#, *contenu*, etc. Bien sûr, mtch est un match-object.

La nécessité de dédoubler le backslash est pénible. Dans le motif il n'est pas un caractère d'échappement, mais un symbole. Si on veut éviter cela, on utilise les chaînes "crues" (raw strings) : r"([*|#+])(\w+)\1".

La réutilisation des groupes dans les motifs permet d'analyser l'information contextuelle. D'autres mécanismes seront décrits et testés en TP. Mais nous avons vu que .group(n), groups() ce sont des méthodes spécifiques des objets appariements. .group(0) identifie la totalité de la chaîne reconnue.

Plusieurs autres méthodes existent, on ne peut pas les décrire ici, mais quelques unes doivent être mentionnées.

mtch.start(groupe) retourne l'indice du début de la chaîne appariée avec le groupe portant ce numéro. On a aussi .end, .span, .pos et .endpos : voir la doc.

Dans quelques circonstances nous voulons grouper les éléments dans une regexp, mais sans vouloir "attraper" le groupe. Ceci en Python est codé par " ... (?: ....) ...". Si on remplace ":" par d'autres caractères, on construit des extensions spécifiques, qui ne seront pas décrites.

Exemple : écrivons un motif permettant de reconnaître des nombres réels, comme 1.2, -3e-12, +0.9e10, etc., dont la spécification est la suivante :

• Le nombre complet contient le signe, la partie entiere, le point décimal, la partie fractionnelle, la lettre e (eu E) et l'exposant, un entier avec signe.
• Les signes sont optionnels.
• La partie exponentielle est optionnelle, mais si elle est absente, la partie fractionnelle, la séquence de chiffres après le point, doit être présente. Avec la partie exposant, le point et la partie fractionnelle deviennet optionnels (ensemble).
• Dans quelques langages de programmation un nombre peut commencer ou terminer par ".", mais ici - non. C'est un exercice supplémentaire pour vous.

nombre="[+-]?\d+((\.\d+)?[eE][+-]?\d+|\.\d+)"

L'exposant peut être présent avec ou sans la partie fractionnelle, mais si cette variante échoue, la partie fractionnelle est obligatoirement présente. La solution n'est pas optimale, car le point et les chiffres qui suivent peuvent être scannés deux fois ! Il faut savoir optimiser / factoriser de telles expressions. Pire, la solution n'est pas suffisamment sélective, et accepte des textes mauvais. Si :

tst="A 1.2 -6.0e+11 et 12. ou .2e5 :-21E-05 +123.87E+32 fin"
nn=re.compile(nombre)
mtc=re.search(nn,tst)
p=nn.finditer(tst)
for k in p: print(k.group(0))

1.2
-6.0e+11
2e5
-21E-05
+123.87E+32

En cours de langages et compilation, on apprend que les expressions régulières sont équivalents aux automates finis, des structures formelles possédant un état interne, et consommant des données d'un flot d'entrée. Leur utilité dépasse des questions linguistiques, donc nous n'allons pas en parler.
(Au moins en cours. En TP on verra...)

Cependant c'est un domaine très utile et important. Les regexps compilés en Python sont de tels automates (ou les graphes – objets Python qui pilotent les automates de reconnaissance.)

La plupart d'éditeurs de texte modernes disposent d'utilités capables d'effectuer les recherches et les remplacements basés sur les regexps. Cependant, c'est à l'utilisateur de les définir, selon ses besoins. Il est dans votre intérêt vous entraîner.

Expressions régulières et grammaires

aoub --> [a] | [b].
star --> [] | star, aoub. % ou : --> [] | aoub,star.

à présent attention !!

Ceci n'est pas une forme uniquement pour vos beaux yeux. C'est un programme exécutable, un code DCG (Definite Clause Grammar) en langage Prolog [Progs/dcg0.pl]. (Implémentation SWI-Prolog. Un jour vous en aurez besoin).

Les formes DCG ici servent – uniquement pour simplicité – à engendrer les séquences plutôt qu'à les reconnaître, mais en général DCG sont utilisées assez fréquemment pour la recherche / reconnaissance. Exercice, prouver que la forme ci-dessous engendre le langage $a^n b^n$. Est-ce une expression régulière?...

s --> [a], [b].
s --> [a], s, [b].

phrase(s,[a,a,a,X,b|Rst]).

  % Réponses du système
X = b,
Rst = [b] ;
X = a,
Rst = [b, b, b] ;
false.  % Plus rien...

Si on lance phrase(GramClause,chaîne,Var)., la Variable prolog Var est instanciée à la chaîne restante, après la reconnaissance, et Prolog l'affiche ou utilise, permettant d'autres manipulations.