Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Devoir, analyse syntaxique Novembre 96 1 Ensembles premier, suivant Exercice 1.

Devoir, analyse syntaxique Novembre 96 1 Ensembles premier, suivant Exercice 1.1 On donne la grammaire suivante: 1 <programme > − → d´ ebut<liste instructions> fin 2 <liste instructions > − → <instruction> <ﬁn liste instr> 3 <ﬁn liste instr > − → <instruction> <ﬁn liste instr> 4 <ﬁn liste instr > − → ε 5 <instruction > − → ID := <expression> ; 6 <instruction > − → lire ( <liste id> ); 7 <instruction > − → ´ ecrire ( <liste expr> ); 8 <liste id > − → ID <ﬁn liste id> 9 <ﬁn liste id > − → ,ID<ﬁn liste id> 10 <ﬁn liste id > − → ε 11 <liste expr > − → <expression> <ﬁn liste expr> 12 <ﬁn liste expr > − → , <expression> <ﬁn liste expr> 13 <ﬁn liste expr > − → ε 14 <expression > − → <expr simple> <ﬁn expr simple> 15 <ﬁn expr simple > − → <op> <expr simple> <ﬁn expr simple> 16 <ﬁn expr simple > − → ε 17 <expr simple > − → ( <expression> ) 18 <expr simple > − → ID 19 <expr simple > − → INT 20 <op > − → + 21 <op > − → - Calculer les ensembles premier et suivant pour chacun des non terminaux de la grammaire. Exercice 1.2 Calculer les ensembles premier et suivant pour chacun des non terminaux de la grammaire suivante. A− → BaCB | D B− → CA | b | ε C− → BAD | BB | c D− → AA | d Mˆ eme question pour la grammaire obtenue en rempla¸ cant AA dans la derni` ere r` egle par CA. 2 Analyse syntaxique 2.1 Analyse descendante Exercice 2.1 V´ eriﬁer que la grammaire de l’exercice 1.1 est bien LL(1) et construire sa table de pr´ ediction. ´ Ecrire les proc´ edures de l’analyseur syntaxique correspondant ` a chaque non-terminal. Les grammaires de l’exercice 1.2 sont-elles LL(1)? 1 Exercice 2.2 Une grammaire LL(1) peut-elle ˆ etre ambigu¨ e? Peut-elle ˆ etre r´ ecursive gauche? Peut-elle ˆ etre non factoris´ ee? Pour essayer de transformer une grammaire non LL(1) en grammaire LL(1), que peut-on faire? Une grammaire factoris´ ee et non r´ ecursive gauche est-elle n´ ecessairement LL(1)? Exercice 2.3 Les grammaires suivantes sont-elles LL(1)? Justiﬁer. S − →ABc S − →Ab S − →ABBA S − →aSe | B A − →a | ϵ A − →a | B | ϵ A − →a | ϵ B − →bBe | C B − →b | ϵ B − →b | ϵ B − →b | ϵ C − →cCe | d Exercice 2.4 Construire la table de pr´ ediction des grammaire de l’exercice 1.2. Ces grammaires sont-elles LL(1)? Exercice 2.5 Construire la table de pr´ ediction de la grammaire suivante: 1 <Expr > − → - <Expr> 2 <Expr > − → ( <Expr> ) 3 <Expr > − → <Var> <FinExpr> 4 <FinExpr > − → - <Expr> 5 <FinExpr > − → ε 6 <Var > − → ID <FinVar> 7 <FinVar > − → ( <Expr> ) 8 <FinVar > − → ε Exercice 2.6 Transformer la grammaire suivante en grammaire LL(1). <ListeDecl> − →<ListeDecl> ; <Decl> | <Decl> <Decl> − →<ListeId> : <Type> <ListeId> − →<ListeId> ,ID | ID <Type> − →<TypeScalaire> | tableau<ListeTypesScalaires> de <Type> <TypeScalaire> − →ID | <Borne> .. <Borne> <Borne> − →<Signe> INT | ID <Signe> − →+ | −| ε <ListeTypesScalaires> − →<ListeTypesScalaires> , <TypeScalaire> | <TypeScalaire> 2 uploads/s3/ devoir-compilation-maitrise-96-97-2.pdf