Théorie des langages : Td 1 grammaires algebriques
Télécharger PDFExercice 1
Une grammaire G est définie comme suit :
- S → aB | bA
- A → a | aS | bAA
- B → b | bS | aBB
Exercice 2
On considère la grammaire suivante :
- S → (L) | a
- L → L, S | S
a)
Quels sont les terminaux, les non-terminaux et l’axiome ?
b)
Déterminer les arbres de dérivation pour les phrases suivantes :
- (a,a)
- (a,(a,a))
- (a,((a,a),(a,a)))
c)
Construire une dérivation gauche pour chacune des phrases de b).
d)
Construire une dérivation droite pour chacune des phrases de b).
Exercice 3
Construire une grammaire générant l’ensemble des palindromes sur l’alphabet {a, b}.
Exercice 4
Considérons la grammaire :
- S → SSS+ | SS* | a
a)
Montrer comment la chaîne aa+a* est engendrée par cette grammaire.
b)
Construire un arbre syntaxique correspondant à cette chaîne.
c)
Quel langage est engendré par cette grammaire ?
Exercice 5
Parmi les grammaires données ci-dessous, trouver celles qui sont ambiguës :
- a) S → 0S1 | 01
- b) S → SS(S)S | ε
- c) S → aSbS | bSaS | ε
- d) S → a | S+S | SS | S* | (S)
Exercice 6
Construire des grammaires non ambiguës pour chacun des langages suivants :
- a) Expressions arithmétiques composées de nombres entiers, d’identificateurs, des quatre opérateurs binaires (+, -, *, /) et de moins unaire.
- b) Listes associatives à gauche d’identificateurs séparés par des virgules.
- c) Listes associatives à droite d’identificateurs séparés par des virgules.
FAQ
Qu’est-ce qu’une grammaire algébrique ?
Une grammaire algébrique est un ensemble de règles formelles permettant de décrire la structure syntaxique d’un langage. Elle utilise des symboles terminaux (comme les lettres ou chiffres) et non-terminaux (comme les variables S, A, B) pour générer des chaînes valides.
Comment distinguer une dérivation gauche d’une dérivation droite ?
Une dérivation gauche remplace toujours le symbole non-terminal le plus à gauche dans la chaîne, tandis qu’une dérivation droite remplace toujours le symbole non-terminal le plus à droite. Ces deux méthodes peuvent aboutir à des arbres différents pour une même chaîne.
À quoi sert un arbre de dérivation ?
Un arbre de dérivation visualise la structure hiérarchique d’une chaîne générée par une grammaire, en montrant comment chaque symbole est remplacé jusqu’à obtenir uniquement des terminaux. Cela aide à comprendre l’ordre des règles appliquées.