Option Traduction de Programmes TD Mercredi 14 février

Grammaires (fortement) non-circulaires

• Une grammaire attribuée est ordonnée si, pour tout non-terminal P, on peut ordonner les attributs de P, (mettons a_{1}, a_{2}, ⋯ a_{n}) de telle façon que, pour n’importe quel programme généré par la grammaire, il existe un ordre de calcul de tous les attributs qui respecte l’ordre a_{1}, a_{2}, ⋯ a_{n} dans le calcul des attributs de chaque occurrence de P. Une grammaire fortement non-circulaire est-elle forcément ordonnée?

• S → T T S.c = T_{2}.r S.a = T_{1}.r S.b = 0 S.d = S.a + 1

T_{1}.l = S.b T_{2}.l = S.d S → UU S.a = U_{2}.r − 1 + S.c S.b = 1 S.c = U_{1}.r + 1 S.d = 1

U_{1}.l = S.b U_{2}.l = S.d T → U T.r = U.r U.l = T.l U → T U.r = T.r T.l = U.l T → X X.a = T.l + 1 T.r = X.a + 1

• L → A L.z = A.z A.c = 0 A → sB B.a = B.y B.b = A.c A.z = B.x A → tB B.a = A.c B.b = B.x A.z = B.y B → u B.x = B.a B.y = B.b B → v B.x = B.a B.y = 0

1. Les grammaires données, sont-elles circulaires, non-circulaires ou fortement non-circulaires?

2. Si une grammaire était circulaire, donner le programme le plus court possédant un circuit dans son graphe de calcul des attributs; sinon quels sont les graphes produits par l’algorithme du dragon en décidant si elle est circulaire?