Théorie des langages : Td 1 grammaires algebriques
Télécharger PDFH. Kassel 1 langages/compilation (2011/2012) TD 1 Analyse syntaxique : grammaires algébriques.
Exercice 1Une grammaire G est définie ci-dessous : S aB | bA A a | aS | bAA B b | bS | aBB Trouver l’arbre de dérivation, la dérivation gauche et la dérivation droite pour des mot aababbab, aabaab.
Exercice 2On 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))) (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 3Construire une grammaire générant l’ensemble des palindromes sur l’alphabet {a,b}.
Exercice 4Considérons la grammaire : 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 5Parmi les grammaires données ci-dessous trouver les grammaires qui sont ambiguës. a) S0S1|01 b) SS(S)S| c) SaSbS|bSaS| d) Sa|S+S|SS|S*|(S)
Exercice 6Construire 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.