Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Grammaire formelle

Une grammaire formelle est un formalisme permettant de définir une syntaxe et donc un langage formel, c'est-à-dire un ensemble de mots sur un alphabet donné.

La notion de grammaire formelle est particulièrement utilisée dans les domaines suivants :

• La compilation (analyse syntaxique) ;
• L'analyse et le traitement des langues naturelles ;
• Les modèles de calcul (automates, circuits, machines de Turing, ...) ;

Définition d'une grammaire

Pour définir une grammaire, on a besoin :

• d'un alphabet de non-terminaux ;
• d'un alphabet de terminaux ;
• d'un symbole initial (l'axiome) pris parmi les non-terminaux ;
• d'un ensemble de règles de production.

Exemples

Expressions arithmétiques

On peut définir des expressions arithmétiques de la façon suivante :

Les non-terminaux sont ici implicitement et , les terminaux sont et les chiffres. L'axiome est .

Une utilisation de cette grammaire peut-être la suivante :

Logique propositionnelle classique

La syntaxe de la logique propositionnelle classique ou calcul des propositions peut se définir de la façon suivante :

P,Q, ... sont les variables propositionnelles (terminaux).

Grammaires particulières

Les types de grammaires les plus couramment utilisées sont :

• les grammaires linéaires gauches qui produisent les mêmes langages que les expressions régulières ;
• les grammaires hors-contexte (exemple ci-dessus)
• les grammaires LL et LR (utilisées par les générateurs d'analyseurs lexicaux comme le couple lex et yacc)