Loading [MathJax]/jax/output/CommonHTML/fonts/TeX/fontdata.js

Grammaires non-contextuelles

Rappels

• $\Sigma$ un alphabet,

• $\Sigma^*$ l'ensemble des mots sur $\Sigma$

• Un langage $\mathcal{L}$ est ensemble de mots ($\mathcal{L} \subset \Sigma^*$)

Rappel : (niveau 3 de la hiérarchie de Chomsky)

• Les langages réguliers,

• décrits par les expressions régulières

• reconnus par les automates

Limitation des langages réguliers

Certains langages très simples ne sont pas réguliers

ex : $\mathcal{L} = \{a^nb^n \,|\, n \in \mathbb{N} \}$ (cf lemme de l'étoile)

• donc pas descriptibles par une regexp

• donc pas reconnaissables par un automate

Autres langages non réguliers

• langages de programmation : C, OCaml ...

• langages de description : HTML, XML, JSON ...

• langues naturelles : la langue française ...

Il y a pourtant une notion de "règles grammaticales" ou "règles syntaxiques" : on ne peut pas écrire n'importe quoi ...

Point de vue génératif : règles de production

On change de point de vue : comment peut-on générer un mot d'un langage donné ?

On définit des règles de ré-écriture (règles de production)

Exemple de grammaire non-contextuelle :

• $S \rightarrow aSb$

• $S \rightarrow \epsilon$

Notion de "dérivation"

Grammaire, version compacte :

• $S \rightarrow aSb$ $|$ $\epsilon$

A partir du symbole $S$, on peut par dérivations successives obtenir :

$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaaSbbb \Rightarrow aaabbb$

On se rend compte que cette grammaire semble générer $\mathcal{L} = \{a^nb^n \,|\, n \in \mathbb{N} \}$. A démontrer

Langages algébriques (niveau 2 de la hiérarchie de Chomsky)

Un langage qui peut être décrit par une grammaire non-contextuelle est dit langage algébrique

Un tel langage est reconnaissable par un automate à pile (HP)

NB : les langages de programmation, les langages à balise sont des langages algébriques

NB : les langages naturels ne sont pas algébriques (les règles sont plus complexes)

Grammaires non-contextuelles et langages algébriques

cf cours

Version "technique" des grammaires : la syntaxe BNF

(HP)

BNF : Backus-Naur Form

• John Backus (prix Turing 1977),

• Peter Naur (prix Turing 2005), pionniers de langages de programmation (Algol 60)

Permet de spécifier les constructions syntaxiques autorisées

Extrait de la grammaire BNF du C

(6 pages de règles de production !)

NB : les parenthèses sont obligatoires après un if ou un while

NB

Cette grammaire permet de produire tous les programmes possibles en langage C !

Grammaires contextuelles (niveau 1 de la hiérarchie de Chomsky)

(HP) les réécritures peuvent être conditionnées par les symboles voisins

Exemple de règle de production contextuelle :

• $aSb \rightarrow acb$

NB : lorsque $S$ se trouve entre $a$ et $b$ (contexte), alors S peut se réécrire en $c$

Grammaires générales (niveau 0 de la hiérarchie de Chomsky)

(HP) les règles de réécritures sont encore plus souples ...