Chapitre Introduction à la compilation
Construire une grammaire et le formalisme
Cette leçon explique ce qu'est la notion de grammaire, comment elles sont définies et les différentes normes.
Construire une grammaire et le formalisme
La composition d'une grammaire
Une grammaire est composée :
- d'un ensemble de terminaux
- d'un ensemble de nom-terminaux
- un ensemble de règles exprimées sous la forme
:=
Certaines règles peuvent être récursives :
VariableList :=
La récursivité peut être à gauche ou à droite en fonction de l'arbre que vous souhaitez produire.
Les règles avec une récursivité à gauche ne sont pas parsables par les analyseurs de type LL(k).
Attention certains langages de programmations ne peuvent pas être exprimés formellement parce que la reconnaissance de l'instruction est trop complexe.
En général, les langages "colonnés" posent des soucis aux générateurs de parsers à cause de cette notion de colonnes.
On appelle ce type de grammaire contextuelle en opposition aux grammaires plus simples "non contextuelles" qui ne dépendent que de l'analyse des règles de la grammaire.
Il existe une forme de notation standard pour les grammaires, la notion EBNF
Il existe plusieurs types d'algorithmes d'analyses syntaxiques :
- DFA
- PEG
- LL(x)
- LR(x)
- LALR(x)
ANTLR 4 est un générateur de parser Adaptive LL(k).
la différence entre un parseur LL et LR dépend de la façon que le parseur choisit de "résoudre les non-terminaux".
- LL : analyse descendante ;
- LR : analyse montante.
S → S + S
S → 1
S → a`
1+1+a
S+S+S ? on résout lequel S en premier ?
