“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 29 — #39
i
i
i
i
i
i
i
i
2.1 Définir un langage de programmation pratique
29
séquence de
fun
if
N
Fact
1
*
==
N
0
Fact
N
−
1
N
[f u n ’{’ ’F’ a c t ’ ’ ’N’ ’}’ ’\n’ ’ ’ i f ’ ’
n d ’\n’ e n d]
’ ’ ’N’ ’*’ ’{’ ’F’ a c t ’ ’ ’N’ ’−’ 1 ’}’ ’ ’ e
’N’ ’=’ ’=’ 0 ’ ’ t h e n ’ ’ 1 ’\n’ ’ ’ e l s e
lexical
Analyseur
séquence de
caractères
Parseur
[’fun’ ’{’ ’Fact’ ’N’ ’}’ ’if’ ’N’ ’==’ ’0’ ’then’
’end’ ’end’]
’1’ ’else’ ’N’ ’*’ ’{’ ’Fact’ ’N’ ’−’ ’1’ ’}’
arbre syntaxique
qui représente
une instruction
jetons
Figure 2.1 Des caractères aux instructions.
La Forme Étendue de Backus-Naur (EBNF)
Un des formalismes les plus populaires pour définir les grammaires s’appelle la Forme
Étendue de Backus-Naur (« Extended Backus-Naur Formalism », EBNF), d’après ses
inventeurs John Backus et Peter Naur. Le formalisme EBNF distingue des symboles
terminaux et des symboles non terminaux. Un symbole terminal est simplement un
jeton. Un symbole non terminal représente une séquence de jetons. Le non terminal est
défini avec une règle de grammaire, qui montre comment le convertir en une séquence
de jetons. Par exemple, la règle suivante définit le non terminal digit :
digit : := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Elle dit que digit représente un des dix jetons 0, 1, . . . , 9. Le symbole « | » est lu
« ou » ; il désigne un choix entre des alternatives. Les règles de grammaire peuvent
référer à d’autres non terminaux. Par exemple, nous pouvons définir le non terminal
int qui définit comment écrire les entiers positifs :
int : := digit { digit }
Cette règle dit qu’un entier est écrit comme un chiffre suivi d’un nombre quelconque
de chiffres, y compris zéro. Les accolades « { digit } » autour de digit définissent
la répétition de digit zéro ou plusieurs fois.
© Dunod – La photocopie non autorisée est un délit