Feuille 3. Analyse lexicalePage principale des TDFeuille 1. Théorie des langages : langages réguliersFeuille 2. Théorie des langages : grammairesKiosk

Feuille 2. Théorie des langages : grammaires

Exercice 1
Soit la grammaire G suivante :

Exp  n
Exp  Exp - Exp

  1. Montrer que G est ambiguë. Proposer une grammaire, non ambiguë, équivalente à G.
  2. Le langage engendré par G est-il régulier ?

Exercice 2
Donner des grammaires non ambiguës engendrant les langages suivants :

  1. { an bp  |  n > p  0 }
  2. { an bp  |  n  p }
  3. { an bp  |  2p  n  p }
  4. { an bp cq  |  n+p=q }

Exercice 3
En Ada, l'instruction d'affectation a la forme suivante :

Inst  Place := Exp.

Le but de l'exercice est de définir la catégorie syntaxique Place.



Rappel : en Ada, en partie gauche d'une affectation, on peut trouver les éléments suivants :

  1. Proposer un type pour la variable P de façon à ce que l'affectation P.Tab(1) := 0 soit correctement typée.
  2. Écrire une grammaire décrivant la catégorie syntaxique Place. On utilisera, sans les définir, les catégories syntaxiques Idf et Exp. Préciser le vocabulaire terminal.

Exercice 4
On s'intéresse aux expressions booléennes dans deux langages de programmation, Ada et Pascal. On se limite au vocabulaire terminal suivant : VT = { true, false, not, and, or, ( , ) }.

  1. En Pascal : Donner une grammaire non ambiguë des expressions booléennes de ce langage.

  2. En Ada : Donner une grammaire non ambiguë des expressions booléennes de ce langage.

Exercice 5
On considère le langage des entiers basés. Un entier basé est constitué d'une indication de base apparaissant entre deux parenthèses, et d'un entier écrit dans cette base. L'indication de base est écrite en base 10 et est comprise entre 2 et 16. Le vocabulaire terminal est

VT = { '(', ')', 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }.

Le tableau suivant donne quelques exemples de chaînes du langage , avec leur valeur correspondante en base 10.

entier basé valeur
(10)123 123
(2)0101 5
(16)1F 31

Les chaînes suivantes n'appartiennent pas au langage : (17)1F, (2)012.

Écrire une grammaire attribuée qui permet de décrire le langage des entiers basés et le calcul de leur valeur.

Exercice 6
Un littéral décimal en Ada est défini par :

litteral_decimal ::= entier [.entier] [exposant]
entier ::= chiffre {[trait_bas] chiffre}
exposant ::= E [+] entier | E - entier

Rappel : [e] signifie que e est optionnel ; {e} signifie que e peut être répété un nombre quelconque de fois (éventuellement 0).

Donner une grammaire attribuée permettant de calculer la valeur dénotée par un littéral décimal.


Feuille 3. Analyse lexicalePage principale des TDFeuille 1. Théorie des langages : langages réguliersFeuille 2. Théorie des langages : grammairesKiosk