Discuter:Expression rationnelle

Un article de Wikipédia, l'encyclopédie libre.

Note sur la traduction originale:

• D'accord avec les traductions suivantes ?
  • "ensembles réguliers" for "regular set"
  • "théorie des langages formels" pour "formal language theory"
  • "étoile de Kleene" pour "Kleene star"
  • problème de degré d'étoile pour star height problem. Là, j'ai traduit un peu au hasard !
  • "opérateur de choix" pour "choice operator": pq pas "opérateur alternatif" ?

• Comment traduire "match" en français ? Le paragraphe pour les expr.reg. sous Unix utilise beaucoup "match", j'ai dû contourner la difficulté, est-ce que çà donne bien ?

• J'ai modifié certain passages:
  • L'original dit que "Perl, for example, has a particularly rich set of extensions that allows even bracket matching which is usually not possible with more conventional regular expresssions." Veut-il dire qu'on peut construire en Perl une regexp qui accepte exactement les expressions avec des parenthèses bien imbriquées ? Je doute que ce soit possible, donc je n'ai pas traduit.

---

Pour match, on peut p.e. essayer : «association»

Quant au texte sur PERL, p.e. "Par exemple, PERL possède un ensemble particulièrement intéressant d'extensions qui permet, entre autres, l'association même de crochets, ce qui n'est généralement pas possible dans les systèmes d'expressions rationnelles plus conventionnels."

--- Pour match, à mon avis "correspondance" est intéressant.

Je vois un autre problème de traduction qui concerne le titre même "Expressions Régulières". S'il s'avère que ce sont bien des expressions, les termes "régulières" et "rationelles" qui n'ont, ni l'un ni l'autre fait l'unanimité dans les ouvrages traitant ce sujet (bien que "rationel" soit généralement présenté comme la traduction correcte), Il me semble que le terme "regular" dans la version anglaise ne sache même pas exactement ce qu'il signifie (mais là je m'avance sans doute n'ayant que peu de connaissances en anglais). Donc, je propose le terme "regexp" (à prononcer "reguex") qui s'il est un terme nouveau (issu de l'abréviation anglaise) et pose des problèmes de cohérence au niveau de la prononciation dans la langue française (le "g" devant le "e" devrait se prononcer "j")permet de désigner de façon non équivoque le principe même de ces expressions. Bien évidemment, des liens seraient à mettre depuis les pages "expressions régulièresé et "expressions rationelles".

           luna 22/02/2003 14:50 (CET)

---

Note sur la traduction originale:

• D'accord avec les traductions suivantes ?
  • "ensembles réguliers" for "regular set"

Parfaitement.

• • "théorie des langages formels" pour "formal language theory"

Aussi.

• • "étoile de Kleene" pour "Kleene star"

Itou. Avec la variante "fermeture de Kleene" quand on parle de l'étoile d'un langage (mais peut-être que Kleene closure ou je ne sais quoi de ce goût-là se dit aussi en anglais ?)

• • problème de degré d'étoile pour star height problem. Là, j'ai traduit un peu au hasard !

http://www.liafa.jussieu.fr/~jep/Resumes/StarHeight.html dit "hauteur d'étoile", de même que http://www-igm.univ-mlv.fr/Seminaire/1994-1995/1995-06-06/ et http://www.infres.enst.fr/~jsaka/PUB/StarHeightResume.html.

• • "opérateur de choix" pour "choice operator": pq pas "opérateur alternatif" ?

Les deux me paraissent clairs...

• Comment traduire "match" en français ? Le paragraphe pour les expr.reg. sous Unix utilise beaucoup "match", j'ai dû contourner la difficulté, est-ce que çà donne bien ?

Oui. À titre d'info, l'excellente traduction française du 'Dragon Book' (Compilateurs : Principes, techniques et outils -- à mettre peut-être en bibliographie sur le sujet ?) dit qu'une expression dénote un langage, que '.' désigne un caractère quelconque, et qu'un regexp ou un automate reconnaît une chaîne donnée. (Ils précisent bien qu'ils se sont permis tous les néologismes nécessaires, mais j'ai l'impression qu'un certain nombre ont été largement adoptés.)

• J'ai modifié certain passages:
  • L'original dit que "Perl, for example, has a particularly rich set of extensions that allows even bracket matching which is usually not possible with more conventional regular expresssions." Veut-il dire qu'on peut construire en Perl une regexp qui accepte exactement les expressions avec des parenthèses bien imbriquées ? Je doute que ce soit possible, donc je n'ai pas traduit.

D'après la page man de la bibliothèque pcre, c'est presque le cas...

 RECURSIVE PATTERNS
    Consider the problem of matching a  string  in  parentheses,
    allowing  for  unlimited nested parentheses. Without the use
    of recursion, the best that can be done is to use a  pattern
    that  matches  up  to some fixed depth of nesting. It is not
    possible to handle an arbitrary nesting depth. Perl 5.6  has
    provided   an  experimental  facility  that  allows  regular
    expressions to recurse (amongst other things). It does  this
    by  interpolating  Perl  code in the expression at run time,
    and the code can refer to the expression itself. A Perl pat-
    tern  to  solve  the parentheses problem can be created like
    this:

      $re = qr{\( (?: (?>[^()]+) | (?p{$re}) )* \)}x;

    The (?p{...}) item interpolates Perl code at run  time,  and
    in  this  case refers recursively to the pattern in which it
    appears. Obviously, PCRE cannot support the interpolation of
    Perl  code.  Instead,  the special item (?R) is provided for
    the specific case of recursion. This PCRE pattern solves the
    parentheses  problem (assume the PCRE_EXTENDED option is set
    so that white space is ignored):

      \( ( (?>[^()]+) | (?R) )* \)

    First it matches an opening parenthesis. Then it matches any
    number  of substrings which can either be a sequence of non-
    parentheses, or a recursive  match  of  the  pattern  itself
    (i.e. a correctly parenthesized substring). Finally there is
    a closing parenthesis.

    This particular example pattern  contains  nested  unlimited
    repeats, and so the use of a once-only subpattern for match-
    ing strings of non-parentheses is  important  when  applying
    the  pattern to strings that do not match. For example, when
    it is applied to

      (aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa()

    it yields "no match" quickly. However, if a  once-only  sub-
    pattern  is  not  used,  the match runs for a very long time
    indeed because there are so many different ways the + and  *
    repeats  can carve up the subject, and all have to be tested
    before failure can be reported.

    The values set for any capturing subpatterns are those  from
    the outermost level of the recursion at which the subpattern
    value is set. If the pattern above is matched against

      (ab(cd)ef)

    the value for the capturing parentheses is  "ef",  which  is
    the  last  value  taken  on  at the top level. If additional
    parentheses are added, giving

      \( ( ( (?>[^()]+) | (?R) )* ) \)
         ^                        ^
         ^                        ^ the string they  capture  is
    "ab(cd)ef",  the  contents  of the top level parentheses. If
    there are more than 15 capturing parentheses in  a  pattern,
    PCRE  has  to  obtain  extra  memory  to store data during a
    recursion, which it does by using  pcre_malloc,  freeing  it
    via  pcre_free  afterwards. If no memory can be obtained, it
    saves data for the first 15 capturing parentheses  only,  as
    there is no way to give an out-of-memory error from within a
    recursion.

--MM

---

Tout d abord felicitations pour la qualite du travail. Pour le langage, expression rationnel viens du fait que ce sont les langages exprimables par les operateurs +, *, ect... et non pas tout les langages, c est une analogie avec les expressions algebriques. Operateur de choix me sembe bien. On peut definir ^* par E^*=U_i>=0 Eⁱ avec comme convention E⁰={&epsilon} ca peut être interessant de le mettre On peut definir E⁺par E⁺=U_i>0 Eⁱ donc comme * mais sans &epsilon.

Dtcube

Sommaire 1 Où ajouter : "+?" et "*?" ? 2 Article de Qualité 3 régulier vs rationnel 4 Allusif ? 5 régulier ou pas

[modifier] Où ajouter : "+?" et "*?" ?

Je ne sais pas trop où placer dans l'article les notations "+?" c-à-d "+" (=1 à infini) suivi du "?" signifiant dans ce cas-ci : minimiser la structure produite.
exemple :

• a{b|c}+ sur la structure "abbbbcbbbbcccc" => "abbbbcbbbbcccc"
• a{b|c}+? sur la structure "abbbbcbbbbcccc" => "ab"

[modifier] Article de Qualité

J'enlève le bandeau article de qualité pour les raisons suivantes:

1. pas de justification (bandeau apposé avant le système de passage en AdQ, semble-t-il)
2. le plan laisse à désirer:
   1. Les expressions rationnelles en théorie des langages formels
      1. Exemples
   2. Les expressions rationnelles sous Unix
      1. Exemples
      2. Exemples
   3. Annexes
      1. Liens externes
      2. Bibliographie
3. La présentation de l'article ne casse pas des briques
4. Dans les cas concrets, seules les expressions régulières sous Unix semblent être présentées (ou du moins la formulation le laisse entendre)

GôTô ¬¬ 25 novembre 2005 à 17:34 (CET)

Je suis d'accord.

Je trouve que l'anathème sur ceux qui persistent à appeler ces langages «réguliers» est excessif. J'ai appris les langages réguliers en 1969 de Claude Pair et il les appelait comme ça et je trouvais et trouve cela très bien et je continuerai à les appeler ainsi et je ne pense pas avoir tort. Il ne s'agit même pas d'un angliscisme.

Pierre de Lyon 21 décembre 2005 à 10:58 (CET)

[modifier] régulier vs rationnel

Les deux usages sont répendus. M'a question est de savoir pourquoi existe-t-il cette gueguerre? Quelles sont les origines de ces deux apelations?

Le terme anglais étant "Regular Expressions", la traduction "Expressions Régulières" trouve sa légitimité dans le rapprochement accoustique des termes. De plus le sens est très proche, bien qu'on puisse noter que le terme français "régulier" a tendance à désigner une notion de fréquence autant qu'une notion de règle. Cette famille de notations a originellement été conçue pour simuler la logique neuronale. C'est pourquoi le terme "rationnelles" convient également à qualifier ces expressions : elles doivent suivre une règle rationnelle.

Cette explication n'a pas un caractère "authentique", ça n'est qu'une explication qui me semble tout à fait légitime, et je pense pouvoir l'avancer sans trop prendre de risque : les deux termes trouvent ainsi leur légitimité.

Kitai 11 août 2006 à 18:58 (CEST)

[modifier] Allusif ?

Le bandeau comme quoi l'article est trop allusif me parait franchement... abusif et n'est pas justifié sur cette page de discussion. Je pense l'enlever. --Bortzmeyer 4 octobre 2006 à 22:45 (CEST)

J'imagine que c'est le sujet qui veut qu'il faille se concentrer pour comprendre. — Meithal - Tav 4 octobre 2006 à 22:47 (CEST)

[modifier] régulier ou pas

Je connaissais les appellations régulier et rationnel pour les avoir apprises en cours et les avoir plusieurs fois rencontrées dans la littérature mais j'ignorais l'existence d'une opposition.

En tout cas je suis venu lire les discussions pour comprendre la raison du sentiencieux "parfois traduite erronément" qui n'est justifié nullepart dans le texte et qui est faux dans les faits, sauf à considérer que "parfois" s'applique dans la grande majorité des cas. Je ne connais que la littérature de Schützenberger, Nivat et étudiants pour offrir un échantillon où la fréquence s'inverse.

Il est parfaitement exact que rationnel, avec son origine équationnelle, est bien mieux fondé que régulier mais le lecteur n'est pas intéressé par des petites saillies pédantes; il veut comprendre et il vient avec son vocabulaire.

À mon sens il faudrait soit retirer ce erronément, soit l'expliquer.