Une notation pour décrire la syntaxe de Modula-2
Un langage formel est un ensemble infini de séquences de symboles. Les membres de cet ensemble sont appelés phrases, et dans le cas d'un langage de programmation, ces phrases sont des programmes. Les symboles sont tirés d'un ensemble fini appelé vocabulaire. Comme l'ensemble des programmes est infini, il ne peut pas être énuméré, mais est défini par des règles de composition. Les séquences de symboles composées selon ces règles sont dites programmes syntaxiquement corrects ; l'ensemble des règles est la syntaxe du langage de programmation.
Les programmes d'un langage formel correspondent alors à des phrases grammaticalement correctes de langages parlés. Chaque phrase a une structure et se compose de parties distinctes, d'entités syntaxiques, telles que des expressions d'énoncé ou des déclarations. Si une construction A factorise et décrit A par la formule syntaxique :
| A = BC |
Si, au contraire, un A est constitué d'un B ou, au contraire, d'un C, nous appelons B et C formes syntaxiques et exprimons A comme :
| A = B | C |
Les parenthèses peuvent être utilisées pour regrouper des termes et des facteurs. Il convient de noter qu'ici A, B et C désignent des entités syntaxiques du langage formel à décrire, tandis que les symboles =, |, les parenthèses et le point sont des symboles des méta-notations de la syntaxe décrite. Ces dernières sont appelées méta-symboles, et la méta-notation introduite ici est appelée formalisme Backus-Naur étendu (EBNF).
En plus de la concaténation et du choix, l'EBNF permet également d'exprimer l'option et la répétition. Si une construction A peut être soit un B, soit rien (vide), cela s'exprime comme suit :
| A = [ B ]. |
et si un A est constitué de la concaténation d'un nombre quelconque de B (y compris aucun), cela est noté par :
| A = { B }. |
C'est tout ce qu'il y a à savoir sur l'EBNF ; quelques exemples montrent comment les ensembles de phrases sont définis par les formules EBNF :
| (A|B)(C|D) | AC AD BC BD |
| A|B|C | ABC AC |
| A{BA} | A ABA ABABA ABABABA ... |
| (A|B)C | C AC BC AAC ABC BBC BAC ... |
De toute évidence, l'EBNF est lui-même un langage formel. S'il convient à l'objectif, il doit au moins être capable de se décrire lui-même ! Dans la définition suivante de l'EBNF dans l'EBNF, on utilise les noms suivants pour les entités :
| Nom | Description |
|---|---|
| statement | Une équation syntaxique |
| expression | Une liste de termes alternatifs |
| term | Une concaténation de facteurs |
| factor | une entité syntaxique unique ou une expression entre parenthèses |
La définition formelle de l'EBNF est désormais donnée comme suit :
|
syntax = {statement}. statement = identifier "=" expression ".". expression = term {"|" term} term = factor {factor} factor = identifier | string | "(" expression ")" | "[" expression "]" | "(" expression ")". |
Les identificateurs (identifier) désignent des entités syntaxiques ; les chaînes de caractères (string) sont des séquences de symboles tirés du vocabulaire du langage défini. Pour la dénotation des identificateurs, on adopte les conventions largement utilisées pour les langages de programmation, à savoir :
«Un identificateur est constitué d'une séquence de lettres et de chiffres, où le premier caractère doit être une lettre. Une chaîne de caractères est constituée de toute séquence de caractères entourée de guillemets (ou d'apostrophes).»