Modèles et langages

Sommaire

Description générale
La notation Backus-Naur Form (BNF)
La notation Extended Backus-Naur Form (EBNF)
Les langages de patrons

1. Description générale

Des données sont décrites | exprimées | modélisées | représentées par un modèle, celui s'écrit dans un langage qui peut être textuel ou graphique.
Un langage obéit | respecte des règles, sa grammaire, appelée aussi métamodèle.
On dit qu'une grammaire | un métamodèle décrit un langage, l'ensemble des possibilités correctes.
On peut tester | vérifier si un modèle obéit | respectent les règles :
- Si oui, le modèle est grammatical | correct, comme la phrase Les chats sont beaux.
- Si non, le modèle est agrammatical | incorrect, comme la phrase les chats_ est beaux.
La grammaire, l'ensemble de règles, est elle-même décrite | exprimée | modélisée | représentée par un modèle, appelée métamodèle, celui s'écrit dans un langage appelée métalangage.
Un métalangage est décrit par un métamétamodèle que respecte le métamodèle, on peut ainsi boucler à l'infini…
Mais généralement le métamodèle et le métalangage sont réflexifs : le métalangage est décrit par le métamodèle, sans ajouter un niveau supplémentaire.

2. La notation Backus-Naur Form (BNF)

La notation Backus-Naur Form (BNF) est un métalangage utilisé pour les décrire les langages de programmation.
- Elle utilise deux types de symboles : les "terminaux" et les <non-terminaux>.
- Les terminaux sont un ou plusieurs caractères entre guillemets doubles ou simples.
- La chaîne vide est symbolisée par "" ou ''.
- Les non-terminaux sont un ou plusieurs caractères entre les signes inférieur et supérieur.
- Elle est constituée de règles notées : <non-terminal> ::= expansion
- Il doit y avoir une règle par ligne.
- Une expansion est consituée de terminaux et non-terminaux arrangée en :
  - Suite par simple juxtaposition : "abc" "def"
  - Choix avec le symbole | : "abc" | "def"
La suite est prioritaire par rapport au choix : "abc" "def" | "ghi" doit se lire :
- Soit "abc" suivi obligatoirement de "def"
- Soit "ghi"
- Et non "abc" suivi de "def" ou "ghi".
Il n'y a pas de moyen de modifier la priorité en BNF, il faut passer par une règle car l'expansion est moins prioritaire que le choix :
- Pour représenter "abc" suivi de "def" ou "ghi" :
  - <règle 1> ::= "abc" <règle 2>
  - <règle 2> ::= "def" | "ghi"
L'expression d'une possible répétition se fait en combinant la suite, le choix et une définition récursive dans : <suite> ::= <item> | <item> <suite>
On peut décrire BNF en BNF, le métalangage est réflexif. Ci-dessous, le modèle de la BNF en BNF, avec des commentaires (lignes qui commencent par #) :

  # Une syntaxe correcte contient au moins une règle
  <syntaxe>               ::=     <règle> | <règle syntaxe>
  # Définition d'une règle par ligne
  <règle>                 ::=     "<"<nom>">" "::=" <expansion> "NEW_LINE"
  # Définition d'un nom de non-terminal
  <nom>                   ::=     <lettre> | <nom> <lettreplus>
  <lettre>                ::=     "a" | "b" ...
  <lettreplus>            ::=     <lettre> | <digit> | "-"
  <digit>                 ::=     "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
  # Suite ou choix
  <expansion>             ::=     <suite> | <suite> "|" <expansion>
  # Suite
  <suite>                 ::=     <symbole> | <symbole> <suite>
  <symbole>               ::=     <terminal> | <non-terminal>
  # Symbole non-terminal
  <non-terminal>          ::=     "<"nom">"
  # Symbole terminal
  <terminal>              ::=     '"'<texteDouble>'"' | '"'<texteSimple>'"'
  <texteDouble>           ::=     "" | <caractèreTexteDouble> <texte>
  <caractèreTexteDouble>  ::=     <lettre> | <digit> | <autres> | "'"
  # Il peut y avoir ' dedans car délimité par "
  <texteSimple>           ::=     "" | <caractèreTexteSimple> <texte>
  # Il peut y avoir " dedans car délimité par '
  <caractèreTexteSimple>  ::=     <lettre> | <digit> | <autres> | '"'
  <autres>                ::=     "-" | "_" | ...
  # Pour simplifier, on a pas offert les possibilités :
  # - d'avoir des lignes vides,
  # - de mettre des espaces.

3. La notation Extended Backus-Naur Form (EBNF)

La notation Extended Backus-Naur Form (EBNF) étend la BNF en y ajoutant la répétition. Ils existent plusieurs variantes.
Dans la variante définie par l'ISO, les changements sont :
- Le symbole ::= est remplacé par =
- Une règle doit être terminée par un ;
- La suite est marquée par une ,
- L'optionalité (0 ou 1) est marquée par [ ... ]
- La répétition (0 ou n) est marquée par { ... }
- La répétition avec un élément obligatoire (1 ou n) est marquée par { ... }-
Il existe également Augmented BNF (ABNF) et XBNF qui étendent la BNF. Elles sont fonctionnellement très proches de l'EBNF.
L'optionalité est parfois exprimée par le suffixe ?, la répétition (0, n) par * (étoile de Kleene) et la répétition (1, n) par +.
Liens :

4. Les langages de patrons

Les langages de patrons sont utilisés pour décrire un patron. Un patron décrit un ensemble de modèles qui peuvent ensuite être capturés ou générés par ce patron. Par exemple, le patron « A B? C », où A, B et C sont des éléments et ? désigne un élément optionnel, décrit les séquences A C et A B C.

Mon premier langage de patron, pour mon mémoire de master 1 en traitement automatique des langues, ne gérait pas la répétition mais l'optionnalité (à l'aide de ?), le choix (à l'aide de [ A B ]) et la sous-séquence (à l'aide de ( A B ). Ainsi on pouvait faire un choix entre un élément ou une sous-séquence : [ (A B) C ] D décrit les séquences A B D et C D. Techniquement, ma façon de les gérer était très bourrine : je dépliais le patron, stockant toutes les séquences qu'il générait dans une liste. Je comparais ensuite une nouvelle séquence avec les séquences générées et si une correspondait, c'est que le patron la capturait. Si plusieurs séquences correspondaient, la plus longue était choisie.

Mon second langage de patrons a été développé le 27 octobre 2018 pour un lexer de langage. Il reprend ceux de regex. Il propose, comme le premier, le choix et l'optionnalité avec les mêmes symboles, mais perd les sous-séquences et rajoute la répétition (à l'aide de + pour répéter de 1 à n fois et * pour répéter de 0 à n fois). Il propose des caractères spéciaux de classes de caractères, # pour les chiffres, @ pour les lettres et $ pour les lettres, les chiffres et _. De plus les caractères spéciaux peuvent être échappés à l'aide également de l'antislash.