Compilation Conception de grammaire

ne grammaire pour C

le niveau global

• un programme C est suite de d´clarations (variables, types ou e

fonctions)

programmeC ::= ( declaration )* declaration ::= declVars | declType | declFonc | defFonc • une d´claration de variables (oublions pointeurs et tableaux) e

est une suite de noms avec ´ventuellement une initialisation e

declVars ::= type declVar ( "," declVar )* declVar ::= IDENT [ "=" expr ] • une d´claration/d´finition de fonction a des param`tres et e e e

´ventuellement un corps e

declFonc ::= entete ";" defFonc ::= entete bloc entete ::= ( type | "void" ) IDENT "(" [parFormels] ")" parFormels ::= parFormel ( "," parFormel)* parFormel ::= type [ IDENT ]

Universit´ de Nice - Sophia Antipolis Licence 3 Informatique 2008-2009 e 4/14

Conception (partielle) d’une grammaire pour C

les blocs

• un bloc est une suite d’instructions pr´c´d´e ´ventuellement e e e e

de d´clarations e

bloc ::= "{" ( declBloc )* ( instruction )* "}" declBloc ::= declVar | declType | declFonc on aurait pu utiliser declaration : on aurait alors accept´ e

syntaxiquement une d´finition de fonction dans un bloc e

• ce qui aurait l’avantage de ne pas provoquer une erreur

syntaxique difficilement rattrapable si le cas arrivait

• on peut toujours positionner un bool´en si on a une d´finition e e

de fonction, et ´mettre un message d’erreur (qui de plus sera e plus explicite, du genre “on n’a pas le droit de d´finir une e fonction dans un bloc”, plutˆt que “{ non attendu”) o

Universit´ de Nice - Sophia Antipolis Licence 3 Informatique 2008-2009 e

5/14

Conception (partielle) d’une grammaire pour C

les instructions

• on a ´videmment plusieurs types d’instructions e instruction ::= bloc | ( [expression ] ";" ) | si | tantque | ...

• l’affectation est une expression en C et a + b; est l´gal bien e

que sans int´rˆt ee

• comme un appel de fonction est une expression, on r`gle le cas e

F(...);

• le fait que l’expression soit optionelle autorise l’instruction vide

(bien utile dans while (t[i++] != n);)

• ´videmment, si seuls l’affectation et l’appel sont autoris´s, il e e

faudra ´crire ( ( affectation | appel ) ";" ) au lieu de e ( expression ";" ) et ( [ affectation | appel ] ";" ) si on veut garder l’instruction vide

Universit´ de Nice - Sophia Antipolis Licence 3 Informatique 2008-2009 e 6/14

Conception (partielle) d’une grammaire pour C

l’instruction si-sinon

• le si est simple si ::= "if" "(" condition ")" instruction [ "else" instruction ]

puisqu’un bloc est une instruction, on r`gle sans probl`me la e e question des {...} • la grammaire est ambigu¨ : elle provoque un conflit quelque e soit le g´n´rateur d’analyseur utilis´ : en g´n´ral, la r´solution e e e e e e par d´faut des conflits associe le else au if le plus proche e qui n’a pas de else, ce que l’on veut • une grammaire non ambigu¨ (pas LL(k), mais LALR(1)) e

instruction ::= complet | incomplet complet ::= "if" "(" condition ")" complet "else" complet | ... incomplet ::= "if" "(" condition ")" ( instruction | ( complet "else" incomplet )

les instructions compl`tes sont toutes les instructions sauf les si sans e sinon et les si avec sinon qui contiennent des si sans sinon

Universit´ de Nice - Sophia Antipolis Licence 3 Informatique 2008-2009 e 7/14

Conception (partielle) d’une grammaire pour C

les conditions

• en g´n´ral, ne pas essayer de “sp´cialiser” les expressions en e e e

distinguant les conditions (bool´ennes), les indices de tableaux e (enti`res) . . . e • on peut en effet ´crire (entre autres exemples) e

if (b) ... if (a == b + 1) ... if (estPair(i) && b) ... while ( (c=getchar()) != EOF) ...

car ce qui compte, ce n’est pas la forme syntaxique de l’expression, mais son type • donc condition ::= expression

• en Java, une affectation n’est pas une expression, mais une

instruction : affectation ::= ( variable "=" )+ expression

Universit´ de Nice - Sophia Antipolis Licence 3 Informatique 2008-2009 e 8/14

Conception (partielle) d’une grammaire pour C

les expressions

• sauf ` ´crire une grammaire ambigu¨ (si le g´n´rateur d’analyseur ae e e e

utilis´ donne des moyens de lever les ambigu¨ es, par exemple bison mais e ıt´ pas JavaCC), il est pr´f´rable d’´crire des r`gles qui refl`tent la ee e e e

priorit´ et l’associativit´ des op´rateurs, par exemple e e e

expression ::= termBool ( "||" termBool )* termBool ::= factBool ( "&&" factBool )* factBool ::= expr [ ("=="|"!="|"=") expr ] expr ::= terme ( ( "+" | "-" ) terme )* terme ::= fact ( ( "*" | "/" | "%" ) fact )* fact ::= litteral | appel | variable | ("(" expression ")")

• ce qui permet syntaxiquement d’accepter des phrases comme

"abc" || a + 1 && 3.0 % (a == b)

• il serait trop fastidieux d’´crire une grammaire qui ne e

permettrait pas, par exemple, "abc" % true

• c’est la s´mantique statique qui v´rifiera que le type de chaque e e

op´rande est correct pour son op´rateur e e

Universit´ de Nice - Sophia Antipolis Licence 3 Informatique 2008-2009 e 9/14

Conception (partielle) d’une grammaire pour C

les variables

• les variables ne sont pas seulement de simples identificateurs • ce sont aussi des variables indic´es (t[exp]), des s´lections de e e champs (a.b.c), des d´r´f´renciations de pointeurs (*p), et eee possiblement une combinaison de tout ca : *t[i].a.b[j], et ¸ aussi (*t[i]).a.b[j] • donc (en oubliant que *p++ est aussi possible, parmi bien d’autres) variable ::= pvar | ’*’ variable pvar ::= svar | pvar "[" expression "]" | pvar "." IDENT svar ::= IDENT | "(" variable ")"

Universit´ de Nice - Sophia Antipolis Licence 3 Informatique 2008-2009 e

10/14

Conception (partielle) d’une grammaire

les variables dans un langage ` objets a

• dans un langage ` objets, une m´thode pouvant retourner un a e

objet, on peut avoir this.a.M(i,j).b.F(k).c

• donc (sans les tableaux) : variable ::= prefixe var appel ::= prefixe app var ::= IDENT app ::= IDENT "(" [ arguments ] ")" prefixe ::= [ THIS "." ] ( ( var | app ) "." )* arguments ::= expression ( "," expression )*

Universit´ de Nice - Sophia Antipolis Licence 3 Informatique 2008-2009 e

11/14