avis grammaire bnf

Version imprimable

avis grammaire bnf

Salut à tous.
Voila, j'ai un projet de compilateur à faire. Première étape: écrire la grammaire du langage, en bnf. Je suppose que c'est le meilleur forum pour ça.
Comme je suis prudent vis à vis des domaines que je connais mal, je suis venu vous demander votre avis pour être sur que ma grammaire n'est pas ambiguë. Voici un exemple du langage (je zape les détails des analyseurs lexicaux et sémantiques):
Code:

1 2 3 4 5 6 7 8 9 objet "Je suis un joli objet" { couleur= blanc noir rouge; sousobjet { resousobjet "encore un objet" { taille = 5; } forme=carre; } }
Comme vous le voyez, ça permet de déclarer des objets contenant des propriétés ou d'autres objets. Les objets peuvent avoir un nom entre guillemets si désiré et les propriétés peuvent avoir une ou plusieurs valeurs.
Voici le bnf que j'en ai déduit:
Code:

1 2 3 4 5 6 7 <S>::=<bloc> <bloc>::=<declaration> <bloc>|€ <declaration>::=<property>|<objet> <property>::=identifiant "=" <listvalue> ";" <listvalue>::=<value> <listvalue>|<value> <value>::=nombre | identifiant <object>::=identifiant "{" <bloc> "}" | identifiant chaine "{" <bloc> "}"
<S> identifie le début du fichier et € signifie epsilon.
Je doute un peu pour la définition de <bloc> (je veux juste y mettre autant de <property> et de <object> que je veux dans n'importe quel ordre) et de <listvalue> (ça doit pouvoir contenir de 1 à N <value>).
S'il y a des pros du bnf dans le coin, qu'est ce que vous en pensez?
Merci d'avance.

18/04/2007, 23h00
Hibou57

Bonjour Lapinou :)

Hibou aime bien les grammaire... j'avais écrit un analyseur il y a longtemps.

J'ai bien lu ta grammaire, et voici quelques avis :

Citation:

<listvalue>::=<value> <listvalue>|<value>

Ici listvalue est récursive en « avancant en arrière ». Je veux dire que l'analyseur va devoir réduire en absorbant un élément en arrière, ce qui n'est pas le plus naturel, et cela peut aussi posé des problème de prédiction pour l'analyseur. Peut-être que <listvalue> ::= <value> | <listvalue> <value> serait mieux (<listvalue> <value> au lieu de <value> <listvalue>)

Avec <value> <listvalue>, l'analyseur va d'abord passer <value> et le laisser sur la pile, sans savoir s'il peut le réduire à <value>, car pour cela, il devra avoir un <listevalue> devant, qui posera recursivement le même problème.

Je te donne un exemple pour être plus claire.

prenons V1...V5, une série de valeur en entrée : V1 V2 V3 V4 V5

Dans le cas de <listvalue>::=<value> <listvalue>|<value>, voici comment l'analyse se déroule (le * représentre la poisition de l'analyseur)
1) * V1 V2 V3 V4 V5
2) V1 * V2 V3 V4 V5
3) V1 V2 * V3 V4 V5
4) V1 V2 V3 * V4 V5
5) V1 V2 V3 V4 * V5
6) V1 V2 V3 V4 V5 *
7) V1 V2 V3 V4 <listavalue> *
8) V1 V2 V3 <listavalue> *
9) V1 V2 <listavalue> *
10) V1 <listavalue> *
11) <listavalue> *

En 1), l'analyseur ne peut pas réduire V1 à une listvalue, car il doit voir une listvalue devant, ou voir un value isolé, qui consitue une lsiste à une élément. En 2), c'est idem, et ainsi de suite. C'est seulement arrivé en 6 que l'analyseur va reconnaître V5 comme une liste à un élément, et ensuite pouvoir réduire V4 <listevalue> à <listvalue>, et ainsi de suite, réduisant par l'arrière.

Avec la variante que je te propose (<value> | <listvalue> <value>), voici comment la même chaîne serait lue.
1) * V1 V2 V3 V4 V5
2) V1 * V2 V3 V4 V5
3) <listevalue> * V2 V3 V4 V5
4) <listevalue> V2 * V3 V4 V5
5) <listevalue> * V3 V4 V5
6) <listevalue> V3 * V4 V5
7) <listevalue> * V4 V5
8) <listevalue> V4 * V5
9) <listevalue> * V5
10) <listevalue> V5 *
11) <listevalue> *

En 2), l'analyseur peut immédiatement reconnaître V1 comme une liste à un élément, puis ensuite en 4), reconnaître V2 comme s'ajoutant à la liste, et ainsi de suite.

Le nombre d'étape est le même, mais la charge sur la pile est moindre (ce qui t'épargnera des débordement de pile si un fichier source contient une trés longue liste par exemple... c'est plus robuste et plus fiable), et c'est donc aussi plus simple si tu décide d'encoder une analyseur manuellement.

La même remarque s'applique à <bloc>, qui est en fait une liste de <declaration>. Mais là il y a une erreur en plus. Car aucune règle de la grammaire n'indique comment avoir un bloc ne contenant qu'une seule déclaration, et ainsi, aucun source ne vérifiera jamais le grammaire.

Exemple : de source
1) <declaration>
2) <declaration> <declaration>
3) <declaration> <declaration> <declaration>

Essais d'imaginer les étapes de l'analyse pour de telles entrées, et tu verra qu'elle ne peuvent pas êtres reconnues par ta grammaire.

1) ne peut pas être reconnu comme <bloc>, car il n'y a rien devant.
2) ne peut pas être un <bloc>, car un <bloc> ne peut pas être un <declaration> seul, encore une fois.
3) idem... et ainsi de suite.

Peut-être que <bloc>::=<bloc> | <bloc> <declaration> | € conviendrait mieux. Et pour être plus claire, je proposerais même
<bloc> ::= <listedeclaration> | €
<listedeclaration> ::= <declaration> | <listedeclaration> <declaration>
19/04/2007, 11h59
PRomu@ld

Citation:

Peut-être que <listvalue> ::= <value> | <listvalue> <value> serait mieux (<listvalue> <value> au lieu de <value> <listvalue>)

Attention, suivant l'outil que l'on va utiliser derrière, le fait d'utiliser une grammaire récursive gauche peut poser des problèmes.
19/04/2007, 18h00
zais_ethael

Merci pour tes explications Hibou, c'est très instructif.
Pour ce qui est du type d'outil, le prof veut un analyseur syntaxique "ascendant à précédence faible", ce dont je ne connais pas grand chose de par son cours quasi inexistant :(. Enfin on fait avec, j'essaie de lire les 2 cours sur developpez concernant les compilos pour me mettre dans le bain.

Pour la remarque sur <listvalue> j'ai compris l'interet mais j'ai une question supplémentaire. Est-ce que l'ordre des choix influence quelque chose? Donc est-ce que <value> | <listvalue> <value> et <listvalue> <value> | <value> provoquent un comportement différent?

Pour <bloc> j'ai deux questions:
- tu n'aurais pas fait une faute à <bloc>::=<bloc> | <bloc> <declaration> | €. Ce serait pas plutot <bloc>::=<declaration> | <bloc> <declaration> | € ? Ou alors j'y capte vraiment rien :P
- je ne comprends pas très bien pourquoi un <bloc> ne peut être défini par <bloc>::=<declaration> <bloc>|€ , pour moi 1 bloc contenant un élément se représente:
bloc(declaration bloc(€))
Je suppose que ça a toujours un rapport avec la récursivité à gauche (que j'ai croisé recemment dans un cours) mais je ne comprends pas l'impact que cela peut avoir sur l'algo ni pourquoi ça semble plus important que la récursivité à droite.