CSI 3525 - Devoir #1

Elements de correction

I. Preliminaires et historique

Pas de problemes majeurs dans cette partie. Les reponses suivantes ne sont bien sur pas des references absolues mais juste un recueil des idees que l'on pouvait extraire du manuel de cours.

1. Orthogonalite

Toute combinaison de primitives de base est legale et a un sens.

Des avantages de l'orthogonalite sont donc :

moins d'exceptions aux regles du langage : langage plus regulier
langage plus facile a ecrire
langage plus facile a apprendre car les primitives de base sont souvent moins nombreuses

Des inconvenients de l'orthogonalite sont :

a l'exces, explosion de combinaison et donc langage plus complique
risque d'utiliser des commandes par hasard pour le debutant
le compilateur exerce moins de controle

2. Lisibilite/Fiabilite

La lisibilite est la facilite avec laquelle les programmes peuvent etre lus et compris. La fiabilite est une mesure de la correspondance entre ce que fait reellement un programme et ses specifications.

Il etait ici important d'evoquer l'importance de la phase de maintenance dans le "cycle de vie" d'un logiciel. C'est en grande partie dans cette phase que la lisibilite va trouver toute son importance surtout si ce n'est pas le concepteur original qui en est charge.

Les caracteristiques ameliorant la lisibilite sont les suivantes :

la simplicite : peu de composants de base, eviter de multiplier les moyens pour accomplir la meme tache, ne pas abuser de la surcharge d'operateurs. Attention : on parle ici de la simplicite generale du langage et pas de la simplicite des instructions de base. L'exemple de l'assembleur montre que des primitives simples ne permette pas forcement d'ecrire des programmes lisibles.
l'orthogonalite : comme discute dans la question precedente, il faut trouver un juste milieu.
des structures de controle adaptees : eviter les gotos permet de rendre la lecture du programme plus lineaire.
des types de donnees et structures pratiques : exemple des booleens et de la possibilite de construire des structures complexes
des efforts sur la syntaxe : des formes d'identifiants explicites sur leur role, des mots reserves en nombre limite mais adapte a chaque usage, la possibilite de deduire simplement la semantique de la syntaxe

3. Algol 60 / Fortran

Algol 60 est ne du desir de creer un langage universel et libre (Fortran appartenait a IBM).

Ses buts :

une syntaxe inspiree des mathematiques
un usage developpe dans les publications
compilable sur n'importe quelle plate-forme

Les innovations d'Algol 60 :

les types de donnees sont formalises par rapport a Fortran
generalisation de caracteristiques de Fortran
le symbole d'assignation := est adopte
decrit en BNF
localite des variables
structure par blocs
recursion
iteration conditionelle
structures de branchement evoluees
piles et tableaux dynamiques

Apres quelques hesitations, IBM decide de ne pas soutenir Algol, se souvenant des difficultes pour developper un compilateur efficace pour Fortran. Cette decision est probablement a l'origine de l'echec d'Algol, avec le fait que la forme BNF etait alors difficile a comprendre.

Mais Algol a ete accepte dans la publication et a donc fait evoluer enormement la conception des langages. C'est pourquoi nombreux sont les langages posterieurs qui lui doivent beaucoup : PL/I, SIMULA 67, ALGOL 68, C, Pascal, Ada et C++ sont les plus importants...

II. Analyse syntaxique

1. Trouver une grammaire...

Probablement la question la plus difficile du devoir.
Les bonnes idees : le cas difficile est celui des crochets et on ne peut mettre le meme element a gauche et a droite (c'est precisement ce qui differencie A et Z), les caracteres x et y doivent etre traites a part et doivent pouvoir etre generes par la grammaire...
Et les mauvaises : dissocier les crochets [ et ] en les faisant apparaitre avec les caracteres x et y, reproduire la meme formule dans plusieurs non-terminaux (cela genere tres souvent des ambiguites), utiliser plus de deux non-terminaux en plus des caracteres...

La reponse ideale etait probablement :

<chaine> -> (<chaine>) | [(<chaine>),<chaine>] | [<caractere>,<chaine>] | <caractere>
<caractere> -> x | y

La variante suivante etait egalement acceptable et meme plus lisible :

<chaine> -> <element> | [<element>,<chaine>]
<element> -> (<chaine>) | <caractere>
<caractere> -> x | y

2. Derivation

La question etait relativement facile donc la correction a ete relativement peu tolerante. Comme aucune derivation particuliere n'etait imposee, toutes les formes ont ete acceptees.

abag
S -> aA
    -> abA
    -> abCg
    -> abag

aabg
S -> Bg
    -> CBg
    -> aBg
    -> aCbg
    -> aabg

                                S
                               / \
                             B   g
                            / \
                          C   B
                          |    / \
                         a C   b
                              |
                             a

3. Ambiguite

La seule demonstration valable et rigoureuse de l'ambiguite etait d'utiliser un exemple. Prenons a * b *a.

                                 S
                                 |
                                X
                               / | \
                            X * X
                           / | \      |
                         X *X   Y
                          |     |     |
                         Y   Y    a
                          |     |
                         a     b

                                S
                                 |
                                X
                               / | \
                            X * X
                             |     / | \
                            Y X *X
                             |    |     |
                            a   Y   Y
                                  |     |
                                  b    a

On obtient donc deux arbres differents pour la meme expression, la grammaire est ambigue.

Les propositions suivantes etaient valables :
S -> X
X -> X * Y | Y
Y -> a | b | c

S -> X
X -> Y*X | Y
Y -> a | b | c

S -> Y*S | Y
Y -> a | b | c

rigouste@site.uottawa.ca