Analyse syntaxique - Page 1

Salut! Après mon topic sur l'analyse lexicale c'était prévisible que j'allais pas m'en sortir comme ça pour la prochaine étape...
J'ai implémenté une analyse descendante. En fait pour résumer je vous mets une liste des règles que j'ai définies:

PROG => (DECLARE L_DECL | e) BEGIN (L_INST | e) END
L_DECL => DECL (L_DECL | e)
DECL => ID (, ID)* DEUXPOINTS TYPE POINTVIRGULE
L_INST => INST (L_INST | e)
INST => I_ASSIGNEMENT | I_SI | I_TANTQUE
I_ASSIGNEMENT => ID OP_ASSIGNEMENT EXPR POINTVIRGULE
I_SI => SI COND ALORS INST (SINON INST | e)
I_TANTQUE => TANTQUE COND INST
EXPR => (CTE_ENTIERE | ID) (OP_MATH EXPR | e) | '(' EXPR ')'
COND => EXPR OP_COMPARAISON EXPR
TYPE = ID

(j'ai remplacé epsilon par e parce que yN n'aime pas). Pourriez-vous me confirmer que ma grammaire est bien LL(1) jusqu'ici? Même si plusieurs règles de productions commencent par le même jeton elles se différencient par le contexte: par exemple on n'a jamais (DECL | I_ASSIGNEMENT).
Maintenant mon souci c'est pour gérer les cas où on déclare des tuples ou des tableaux comme en Ada/Pascal:

-- Cas #1: pas géré par mon prog, juste pour info
a: array (1..3) of integer := (1, 2, 3);
-- Cas #2: une structure ou un array pré-déclaré et contraint
b: couleur := (255, 192, 0, 255);

Dans le cas 1 ça va encore, mais dans le cas 2 je n'arrive pas à écrire la règle de production pour ce qui est entre parenthèses. En effet, cela commence exactement comme une expression, mais ce n'est plus tard qu'elle s'en différencie... Et une déclaration attend bien id ':' id (type) ':=' expr ';'.
Une solution que je vois c'est de déterminer si le type fourni est un tableau et de modifier la suite de la règle de production en conséquence, mais c'est plutôt bourrin et pas très flexible... (imaginons qu'on n'utilise pas une descente récursive codée en dur, mais cette fois un parseur LL justement, ou autre)
Quelqu'un pourrait-il m'aider svp?

pour savoir si c'est LL1 buche ton cours et les ensembles premiers, suivant.
tip: écris pas de | mais répète bien les parties gauches ça aide a voir


2: tu peux pas savoir au niveau de l'analyse syntaxique, c'est l'analyse sémantique qui analysera les types.

tout ce que tu peux faire c'est
déclaration ::= ident ':' [decltab] ident [ ':=' initialisation ]
decltab ::= 'array' '(' entier '..' entier ')' 'of'
initialisation ::= init_simple | init_tableau
init_simple ::= expression
init_tableau ::='(' entier ( ',' entier )* ')'
avec [a] = a zéro ou une fois
et (a)* = a un nombre quelconque de fois même zéro

les types tu les connais pas encore a cette étape, donc faut prévoir tous les cas, et certains programmes syntaxiquement corrects seront sémantiquement incorrects.

oui, les langages avec assignement de tableaux comme pascal ou ada sont chiants

C'est pas bon, tu brises la contrainte LL(1) avec ta solution : une init_simple et une init_tableau commencent par les mêmes lexèmes, tu n'as connaissance de la différence que plus tard.

Sinon je suis pas sûr de comprendre le problème : en quoi (1, 2, 3) n'est pas une expression ? (pour moi c'est un tableau constant, ça peut tout à fait être une expression, auquel cas le problème n'existe plus)

("ASSIGNEMENT", c'est la fusion entre "assignment" et "assignation" ? ^^)

Zeph> ben le problème c'est qu'à ce moment là je n'ai plus moyen de différencier une expression d'une constante tableau tu vois? Puisqu'une expression peut commencer par '(' et une constante tableau aussi
Pareil pour le tien squalyl, tu as dit qu'une initialisation peut être une init_simple, c-à-d une expression, mais tu n'as pas défini l'expression. A ce moment ce serait ambigu...

squalyl (./2) :
tip: écris pas de | mais répète bien les parties gauches ça aide a voir

Heu je ne comprends pas? Tu veux dire que je remplace les non terminaux par le premier terminal?
Merci à vous ^^

Je crois qu'il te dit d'éviter les pipes, pour mieux voir ce qui se passe en temps réel.

Brunni (./4) :
Zeph> ben le problème c'est qu'à ce moment là je n'ai plus moyen de différencier une expression d'une constante tableau tu vois? Puisqu'une expression peut commencer par '(' et une constante tableau aussi

Je suis pas sûr de comprendre ton problème, pour moi une constante est une expression donc si tu as une règle de type "id : type [:= expr]" ça prend en compte tous les cas possibles ?

(et ton lexeur sera de toutes façons incapable de savoir si une expression est constante ou pas, ce n'est qu'à la construction de ton arbre syntaxique que tu pourras t'en rendre compte ; en l'occurrence un tableau dont tous les éléments sont des constantes est lui-même constant)

Donc tu veux dire que je définisse qu'une expression est beaucoup plus générale, genre:
EXPR ::= (CTE_ENTIERE | ID) [OP_MATH EXPR] | '(' EXPR {',' EXPR} ')'
Et je me rendrai compte à la construction de l'arbre syntaxique que par exemple 2 + (1, 2, 3) n'est pas une expression?
Tiens marrant en cherchant diagramme syntaxique pascal je tombe sur le site de mon école. Pourtant on l'a pas dans notre cours
C'est vraiment impressionnant comment j'arrive pas à m'en sortir juste avec des cours sur le net ils sont soit incomplets soit juste sommaires.

Je pense qu'il manque des choses pour EXPR.
Il faut aussi pouvoir reconnaitre « (1 - 5) * 2 » et « -truc »...

Arf oui merci. Disons ça alors:
EXPR ::= [OP_MOINS] ((CTE_ENTIERE | ID) | '(' EXPR {',' EXPR} ')') [OP_MATH EXPR]

« ! » n'est pas valable aussi comme opérateur unaire ? Peut-être pourrais-tu différencier OP_MATH_BINAIRE et OP_MATH_UNAIRE

Possible, mais pour l'instant mon langage ne le gère pas ^^
Et pour les opérateurs binaires bonne idée
Par contre maintenant mon souci c'est de différencier les assignations [merci Zephyr] d'un appel à une fonction, commençant tous les deux par un identificateur
Alors oui je me rappelle de langages comme FoxPro ou même Ada n'autorisant pas l'appel simple de fonction (il fallait faire = appel() ou forcément assigner la valeur de retour), et C considérant toute expression comme une instruction.
Peut être que c'est finalement la bonne voie de définir l'assignement comme une expression et instruction comme expression, mais c'est franchement un gros trou dans le langage

un appel à une fonction est également une expression : "1 + plop ()" est tout à fait valide ^^ (et une assignation peut l'être aussi, c'est le cas en C par exemple)

Oui oui, sauf que comme instruction 1 + plop() est faux ^^
Sauf en C.
Si je fais une bidouille genre:

INSTRUCTION => I_SI | I_WHILE | I_QCM
I_QCM => ID (TUPLE | OP_AFFECTATION EXPR)
avec TUPLE => '(' EXPR {VIRGULE EXPR} ')'
EXPR => [OP_UNAIRE] (CTE_ENTIERE | ID [TUPLE] | TUPLE) [OP_BINAIRE EXPR]

Le non terminal I_QCM permettant de partir soit sur une affectation soit sur un appel. C'est "propre" à ton avis?

Wééééééééé!
J'ai pu générer un arbre syntaxique pour le programme suivant avec ma grammaire infâme:

declare
  rouge, vert, jaune, magenta: RGB;
debut
  rouge = (255, 0, 0);
  vert = (0, 255, 0);
  jaune = (rouge + vert);
  magenta = -rouge;
  display(rouge);
  display(rouge.R);
  si vert.R == 0 alors vert.R = 127 sinon vert.R = 255;
  tantque rouge.R < 255 inc(rouge.R);
fin

Figure 1: code

PROG => [DECLARE L_DECL] BEGIN [L_INST] END
L_DECL => DECL [L_DECL]
DECL => ID {VIRGULE ID} DEUXPOINTS TYPE_SCALAIRE [OP_AFFECTATION EXPR] POINTVIRGULE
L_INST => INST [L_INST]
INST => INST_SIMPLE POINTVIRGULE
INST_SIMPLE => I_AFFECTATION_OU_APPEL | I_SI | I_TANTQUE
I_AFFECTATION_OU_APPEL => ID {POINT ID} (TUPLE | OP_AFFECTATION EXPR)
I_SI => SI COND ALORS INST_SIMPLE [SINON INST]
I_TANTQUE => TANTQUE COND INST_SIMPLE
EXPR => [OP_UNAIRE] (CTE_ENTIERE | ID [TUPLE | {POINT ID}] | TUPLE) [OP_BINAIRE EXPR]
	(note: ID [TUPLE] pour un appel de fonction)
TUPLE => '(' EXPR {VIRGULE EXPR} ')'
COND => EXPR OP_COMPARAISON EXPR

Figure 2: grammaire infâme

PROG
    motDeclare: declare
    L_DECL
        DECL
            identifiant: rouge
            virgule: ,
            identifiant: vert
            virgule: ,
            identifiant: jaune
            virgule: ,
            identifiant: magenta
            deuxPoints: :
            identifiant: RGB
            pointVirgule: ;
    motDebut: debut
    L_INST
        INST
            INST_SIMPLE
                I_AFFECTATION_OU_APPEL
                    identifiant: rouge
                    assignement: =
                    EXPR
                        TUPLE
                            parenthèseOuvrante: (
                            EXPR
                                constanteEntière: 255
                            virgule: ,
                            EXPR
                                constanteEntière: 0
                            virgule: ,
                            EXPR
                                constanteEntière: 0
                            parenthèseFermante: )
            pointVirgule: ;
        INST
            INST_SIMPLE
                I_AFFECTATION_OU_APPEL
                    identifiant: vert
                    assignement: =
                    EXPR
                        TUPLE
                            parenthèseOuvrante: (
                            EXPR
                                constanteEntière: 0
                            virgule: ,
                            EXPR
                                constanteEntière: 255
                            virgule: ,
                            EXPR
                                constanteEntière: 0
                            parenthèseFermante: )
            pointVirgule: ;
        INST
            INST_SIMPLE
                I_AFFECTATION_OU_APPEL
                    identifiant: jaune
                    assignement: =
                    EXPR
                        TUPLE
                            parenthèseOuvrante: (
                            EXPR
                                identifiant: rouge
                                plus: +
                                EXPR
                                    identifiant: vert
                            parenthèseFermante: )
            pointVirgule: ;
        INST
            INST_SIMPLE
                I_AFFECTATION_OU_APPEL
                    identifiant: magenta
                    assignement: =
                    EXPR
                        moins: -
                        identifiant: rouge
            pointVirgule: ;
        INST
            INST_SIMPLE
                I_AFFECTATION_OU_APPEL
                    identifiant: display
                    TUPLE
                        parenthèseOuvrante: (
                        EXPR
                            identifiant: rouge
                        parenthèseFermante: )
            pointVirgule: ;
        INST
            INST_SIMPLE
                I_AFFECTATION_OU_APPEL
                    identifiant: display
                    TUPLE
                        parenthèseOuvrante: (
                        EXPR
                            identifiant: rouge
                            point: .
                            identifiant: R
                        parenthèseFermante: )
            pointVirgule: ;
        INST
            INST_SIMPLE
                I_SI
                    motSi: si
                    COND
                        EXPR
                            identifiant: vert
                            point: .
                            identifiant: R
                        égale: ==
                        EXPR
                            constanteEntière: 0
                    motAlors: alors
                    INST_SIMPLE
                        I_AFFECTATION_OU_APPEL
                            identifiant: vert
                            point: .
                            identifiant: R
                            assignement: =
                            EXPR
                                constanteEntière: 127
                    motSinon: sinon
                    INST_SIMPLE
                        I_AFFECTATION_OU_APPEL
                            identifiant: vert
                            point: .
                            identifiant: R
                            assignement: =
                            EXPR
                                constanteEntière: 255
            pointVirgule: ;
        INST
            INST_SIMPLE
                I_TANTQUE
                    motTantQue: tantque
                    COND
                        EXPR
                            identifiant: rouge
                            point: .
                            identifiant: R
                        plusPetit: <
                        EXPR
                            constanteEntière: 255
                    INST_SIMPLE
                        I_AFFECTATION_OU_APPEL
                            identifiant: inc
                            TUPLE
                                parenthèseOuvrante: (
                                EXPR
                                    identifiant: rouge
                                    point: .
                                    identifiant: R
                                parenthèseFermante: )
            pointVirgule: ;
    motFin: fin

Figure 3: arbre généré
=> next step: analyseur sémantique, même si j'ai pas encore vraiment compris ce que je vais faire là dedans ni ce que je vais générer ^^

ça me fait bizarre de voir des virgules dans l'arbre syntaxique (vers DECL je veux dire) normalement on les voit plus, il font juste partie de la syntaxe.

Hu? En fait c'est un jeton la virgule. En majuscules: règles de production (excepté RGB) et le reste c'est des jetons dont j'affiche la valeur (et non le type).
J'avoue que je ne comprends pas ton commentaire "normalement on les voit plus, il font juste partie de la syntaxe". Tu veux dire que dans mon arbre je ne devrais pas avoir les terminaux? Comment je vais m'en servir alors?
[Edit] Voilà j'ai rajouté le nom des terminaux à côté

imagine un cas simple : une expression à parenthèses du genre:


2*(3+4)

l'arbre va faire

MULT
  2
  ADD
    3
    4

et on voit plus les parenthèses.

là c'est pareil t'as

a,b,c: integer;

moi j'aurais plutot vu un truc du genre

DECLARATION
  type: integer
  LISTE_VARIABLES
    a
    b
    c

les virgules sont là dans le code, ce sont des terminaux de la grammaire mais en aucun cas des noeuds de l'arbre syntaxique.

en fait ce que t'as généré c'est pas un arbre syntaxique abstrait mais un affichage de l'ordre des appels des règles de ta grammaire. OK tu vas passer par la règle qui reconnait "virgule" si t'as codé un analyseur LL1 à la main, mais ça n'a rien à faire dans l'arbre syntaxique

et l'analyse sémantique ne génère pas de nouvel arbre, elle fait des vérifications.

... donc je n'ai rien compris...

Type est déjà reconnu à ce moment là? Et pour la génération d'une expression en RPN avec priorité des opérateurs effectivement j'ai pas hâte d'y arriver...
L'arbre c'est donc moi qui le définis comme ça m'arrange le mieux, il ne reflète pas exactement la syntaxe, c'est ça?
Merci, bon ben je vais devoir regarder ça mieux... quelqu'un aurait un lien vers un cours sur le net où je pourrais me documenter sur les étapes de réalisation d'un compilateur? J'ai trouvé que des trucs super succints

squalyl a raison, l'arbre que tu construit est censé te simplifier la vie et donc proposer une structure bien plus facile à traiter que le code source initial. Les expressions mathématiques sont un bon exemple : la notation infixe n'est pas faite pour être traitée informatiquement, alors que les notations polonaise et polonaise inverse sont au contraire très faciles à interpréter (pas de priorité, pas de parenthèses, un seul parcourt et c'est évalué).

Pour l'instant quelle est l'utilité d'avoir construit un arbre si il respecte exactement l'ordre du code source ? C'est une information que tu avais déjà en utilisant ton analyseur lexical, donc la transformation en arbre n'a rien apporté. À toi de définir quelle est la représentation de données qui te semble la plus pratique pour chaque construction dans ton langage

Même si aujourd'hui il n'y a plus grand monde qui écrit des parseurs à la main, peut-être qu'avec un coup de [google]mathematical expression parser[/google] tu trouveras des choses intéressantes.

Tu ne peux pas faire une grammaire pour expressions arithmétiques qui respecte les priorités (c'est-à-dire telle que l'arbre de parsage ait la même structure que l'arbre syntaxique) avec du LL(1): le LL(1) ne permet la récurrence dans les règles que dans un seul sens, or c'est le sens de la récurrence qui détermine l'ordre d'associativité de tes opérations. Il est plus judicieux de passer par du LALR(1).

Merci vous deux ^^ je vais voir ça, j'aurai peut être des questions sur le moment

Je vais peut être paraître un peu con mais j'ai beaucoup de peine à voir comment je pourrais caser la construction de mon arbre syntaxique pendant l'analyse syntaxique :/
J'ai défini une grammaire, et donc un moyen de la parser (je rappelle juste la construction pour les expressions):

static void EXPR() {
	// [OP_UNAIRE] (CTE_ENTIERE | ID [TUPLE] | TUPLE) [OP_BINAIRE EXPR]
	if (opUnaire())
		lit();
	if (prochain(CTE_ENTIERE))
		lit();
	else if (prochain(IDENTIFICATEUR)) {
		lit();
		if (prochain(PAR_OUVRANTE))
			TUPLE();
	}
	else if (prochain(PAR_OUVRANTE))
		TUPLE();
	else
		erreur("expression attendue");
	// Opérateur binaire + autre expr
	if (opBinaire()) {
		lit();
		EXPR();
	}
}

Vous m'avez dit que le parse tree ne servait alors à rien puisqu'il donnait une construction comme ceci qui ne m'avance pas:

EXPR 
    identifiant: rouge 
    plus: + 
    EXPR 
        identifiant: vert

Mettons maintenant que je veux transformer mon expression en RPN pour la foutre dans mon arbre syntaxique. Je vais utiliser un algo connu avec une pile et tutti. Mon analyse syntaxique devient alors inutile puisqu'on travaille directement avec les lexèmes, non?
Qu'est-ce que je devrais faire à ce moment? Je ne comprends pas bien...

Ben non elle ne devient pas inutile ? Ton analyse syntaxique permet de parcourir tes lexèmes en s'assurant que la grammaire est respectée. Au fur et à mesure que tu les lis, tu es donc en présence de constructions connues puisque tu les as toi-même définies, et tu peux donc en profiter pour construire un arbre de la façon qui te semble la plus adaptée en vue des futures passes d'optimisation, de compilation, d'interprétation, ou autres...

Je suis pas sûr de comprendre la question ?

En fait vu que ma grammaire est LL(1), comme le dit Kevin c'est impossible de décrire des expressions "complexes" (avec des priorités et tout).
Je ne peux donc pas faire d'analyse formelle de mes expressions, je peux par contre bidouiller pour coder ma règle de production EXPR avec un algo de conversion en RPN, mais cette fois je n'aurai plus de règle formelle, c'est ça?

J'aurais tendance à partir dans ce sens-là en tout cas. Plutôt que de se borner à respecter telle ou telle grammaire (LL(1) c'est quand même sacrément limitatif), profite du fait que tu écris ton parseur à la main et utilises les techniques qui te semblent les plus efficaces.

Le squelette de ton parseur restera de toutes façons le même, mais effectivement une fois à l'intérieur de ta fonction "parser_expression_mathematique", rien ne t'empêche de changer de méthode. J'ai l'impression que tu t'inventes beaucoup de contraintes depuis le début ?

Brunni (./22) :
Je vais peut être paraître un peu con mais j'ai beaucoup de peine à voir comment je pourrais caser la construction de mon arbre syntaxique pendant l'analyse syntaxique :/

Ton problème est exactement celui que j'ai écrit dans le ./20.

Brunni (./24) :
En fait vu que ma grammaire est LL(1), comme le dit Kevin c'est impossible de décrire des expressions "complexes" (avec des priorités et tout).

C'est possible de le décrire, mais tu dois le faire en spécifiant l'ordre d'associativité en dehors de la grammaire et il faut travailler plus pour construire ton arbre syntaxique (parce qu'effectivement l'arbre de parsage ne correspond pas).

Faut-il absolument que tu parses ça en LL(1)? Je sais bien que c'est le plus intuitif à coder parce qu'il y a la descente récursive (ce que tu fais), mais ce n'est pas très pratique pour construire les arbres syntaxiques corrects.

Ce que tu peux faire, c'est de, quand tu remontes dans ton algorithme par récurrence (donc quand tu as construit quelque chose), "retourner" ton arbre de parsage pour les opérations associatives à gauche (donc la plupart), bref, si tu as:

  -
 / \
A   -
   / \
  B   C

tu le changes en:

    -
   / \
  -   C
 / \
A   B

De même:

  -
 / \
A   -
   / \
  -   D
 / \
B   C

(qui a déjà subi la première transformation quand l'arbre a été construit pour la sous-expression) en:

      -
     / \
    -   D
   / \
  -   C
 / \
A   B

(Tu vois à l'aide de ces exemples qu'il faut retirer le 'A' de la racine et le rattacher au nœud tout en bas à gauche à la place.) Il faut juste faire attention à ne pas oublier les parenthèses dans tout ça.

Il y a certainement aussi d'autres moyens d'arriver au même résultat.

Zephyr (./25) :
J'aurais tendance à partir dans ce sens-là en tout cas. Plutôt que de se borner à respecter telle ou telle grammaire (LL(1) c'est quand même sacrément limitatif), profite du fait que tu écris ton parseur à la main et utilises les techniques qui te semblent les plus efficaces.

Je signale quand-même que les parseurs codés à la main sont presque toujours à descente récursive et donc en LL(1), on contourne les limitations en codant une construction de l'arbre syntaxique qui ne correspond pas à l'arbre de parsage. Le LR(1) ou LALR(1) est beaucoup moins évident à coder à la main, donc on passe par un générateur de tables de parsage (genre Yacc, Bison etc.).

Bon sinon ça me démange de poster cet URL depuis un moment mais je saurais pas forcément t'aider maintenant, ça fait un moment que je suis plus dans le code.
Néanmoins voici:

http://code.google.com/p/etpbasiccompiler/source/browse/trunk/ETPC/ETPC/Syntax/verisyn.cpp
(voir la fonction VerifyExpression)
J'avais fait une bidouille un peu comme tu dis. Pour les expressions on sort du schéma d'analyse classique de la fonction VerifSyntax

Tu as aussi la vérif sémantique:
http://code.google.com/p/etpbasiccompiler/source/browse/trunk/ETPC/ETPC/Verif/verisem.cpp

t1 ya de ces trucs dans ton code !!!

{         if (bTag->GetToken() >= TOKEN_TYPEINTEGER  &&  bTag->GetToken() <= TOKEN_TYPEBYTE)  
                     return true;
                 else
                     return false; } 

Mouarf

en tout cas chapeau, ya un sacré boulot derrière ^^

Merci
A voir le code, ça me donne envie de reprendre le truc. En plus coder un compilo est assez amusant.

En attendant, j'aimerais que la publication du code serve à ceux qui veulent voir un code de compilo fait maison.

Pourquoi n'as-tu pas utilisé Bison?