Grammaire LL(k) du langage C

Bonjour !

Vous vous dites surement, "tiens, ce mec a décidé de réécrire un parseur C". C'est vrai. Et il est bien ennuyé. C'est vrai aussi. Et ca dépends fortement du générateur de parseur qu'il utilise. C'est encore vrai. Il utiliserait un autre outil, quelque chose de costaud comme ANTLR, il n'aurait pas les problèmes qu'il rencontre. Je ne peux pas dire non. Mais au lieu de ça, il utilise un outil plus simple comme Coco/R et du coup, il est limité à des grammaires simplistes type LL(k) avec prédicats. Encore une fois, vous avez raison.

(note: un prédicat permet de choisir une alternative particulière lorsqu'on a lu N symboles supplémentaires ; ça permet de limiter le parser au travail nécessaire pour traiter une grammaire LL(k) au lieu de lui demander de traiter une grammaire LL(k+N) alors que le cas ou on a besoin de k+N symboles pour faire un choix est rare).

Histoire de situer le contexte : la grammaire proposée dans la norme C99 est une grammaire formelle qui n'est pas une grammaire LR (pour autant que je sache), mais ce n'est pas pour autant une grammaire LL(1). Je soupçonne que c'est une grammaire LL(k) avec k grand mais je ne sais pas le prouver. Terence Parr a proposé une grammaire LL(*) pour ANTLR avec un seul prédicat (un tour de force, en fait ; mais les grammaires LL(*) sont bien plus permissives que les grammaires LL(k)) mais je n'utilise pas ANTLR - j'utilise Coco/R pour C# et cet outil est limité à l'apréciations de grammaires LL(1) avec prédicats.

Je pense (mais je n'en suis pas sûr) que la grammaire du C peut être en grande majorité parsée par un parseur LL(1)+prédicats. Il y a quelques points noirs (les déclarations de fonction, qui peuvent être tordues à souhait).

Question : est-ce que quelqu'un a déjà réalisé ce travail ? est-ce que quelqu'un, quelque part, a une grammaire LL(1) complète du C (avec ou sans prédicats) ?

Merci d'avance !

Desole, je n'ai pas de suggestion. Juste une note si tu dois te lancer dans les details toi-meme (je l'avais fait dans une vie precedente pour yacc, qui est du LALR(1), donc plus puissant que LL(1), et la grammaire de la norme avait eu besoin de peu de modification -- mais il y en avait fallu; mais je connais mal ce que la gestion des predicats apportent).

La principale difficulte que je connais proviens des typedef

Code:

---

{ foo * bar ; }

---

est soit une declaration de bar en tant que pointeur sur foo ou une multiplication de foo par bar. Ca se traite classiquement par une retroaction avec l'analyse lexicale, mais attention au code comme:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

typedef int foo; void f() { foo x = 42; { int foo = x; } { foo y = x; int foo = y; } }

---

qui est valide.

Cela pourrait peut-être t'intéresser, une grammaire YACC pour AINSI C.

Elle est jolie cette grammaire, merci pour le lien.

Par contre, je suis surpris par une séquence du lexer de cette grammaire :

Code:

---

1 2 3 4 5

("{"|"<%") { count(); return('{'); } ("}"|"%>") { count(); return('}'); } ... ("["|"<:") { count(); return('['); } ("]"|":>") { count(); return(']'); }

---

ce qui semble dire qu'en C, '{' est pareil que '<%'. Quelqu'un avait déjà vu cela ? ou bien c'est une disgression de l'auteur ?

Citation:

---

Envoyé par Jean-Marc.Bourguet

Desole, je n'ai pas de suggestion. Juste une note si tu dois te lancer dans les details toi-meme (je l'avais fait dans une vie precedente pour yacc, qui est du LALR(1), donc plus puissant que LL(1), et la grammaire de la norme avait eu besoin de peu de modification -- mais il y en avait fallu; mais je connais mal ce que la gestion des predicats apportent).

---

C'est ce que j'avais pensé. Et du coup, je suis en train de le faire. Par contre, je suis plus ou moins obligé de réduire mes prétentions, et certaines structures un peu complexe du langage ne seront pas traitées.

Exemple: un pointeur sur une fonction qui renvoie un pointeur sur fonction qui renvoie un pointeur sur fonction. C'est suffisamment tordu de toute façon pour que le programmeur soit passé par des typedefs donc en pratique, ça doit être relativement rare.

Citation:

---

Envoyé par Jean-Marc.Bourguet

La principale difficulte que je connais proviens des typedef

Code:

---

{ foo * bar ; }

---

est soit une declaration de bar en tant que pointeur sur foo ou une multiplication de foo par bar. Ca se traite classiquement par une retroaction avec l'analyse lexicale, mais attention au code comme:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

typedef int foo; void f() { foo x = 42; { int foo = x; } { foo y = x; int foo = y; } }

---

qui est valide.

---

Je vois ce que tu veux dire. La partie validation de la grammaire est un poil sensible. Du point du vue du parseur, et sans vérification, le code peut être validé ainsi : "ident ident initializerspec ;" ==> valide (définition d'une variable), quel que soit les deux ident.

Maintenant, pour véritablement parser du C, il faut quand même vérifier que sémantiquement, on est OK. Auquel cas, dans l'expression "ident ident initializer ;", il faut que
1) le premier ident soit un type défini pour la portée en cours
2) si on décompose initializerspec en "= initializer", il faut que initializer soit du type défini par le premier ident (y compris une expression cast), ou qu'une promotion implicite du type de initializer vers le type défini par le premier ident existe.

For heureusement, je pressent que dans la majeure partie des cas, je n'aurais pas besoin d'aller à ce niveau de détail. Je ne cherche pas à valider le code - il est censé être compilable, en fait. Ce que je cherche, c'est à récupérer la structure du fichier, les déclarations, les définitions de fonction, les appels de fonctions, etc. En fait, penser à ce parseur comme un outil de reverse engineering qui sort un pseudo-graphe UML - c'est tout. Il ne préserve même pas le code, puisque je n'implémente aucune fonction de génération de code (donc je n'ai aps besoin de garder l'existant quelque part).

En tout état de cause, je construit quand même une table des symboles au fur et à mesure de l'avancée du parse. Ce qui, avec deux doigts d'intelligence, devrait me permettre de réaliser la fonction que je souhaite réaliser.

Citation:

---

Envoyé par ssmario2

Cela pourrait peut-être t'intéresser, une grammaire YACC pour AINSI C.

---

Je l'ai vu, le l'ai lu, et je l'ai discardu. Le principe du parser LALR rend cette grammaire peu viable pour la transformer en LL(1) (ou la récursion à gauche est interdite car elle provoque un conflit).

Citation:

---

Envoyé par ram-0000

Elle est jolie cette grammaire, merci pour le lien.

Par contre, je suis surpris par une séquence du lexer de cette grammaire :

Code:

---

1 2 3 4 5

("{"|"<%") { count(); return('{'); } ("}"|"%>") { count(); return('}'); } ... ("["|"<:") { count(); return('['); } ("]"|":>") { count(); return(']'); }

---

ce qui semble dire qu'en C, '{' est pareil que '<%'. Quelqu'un avait déjà vu cela ? ou bien c'est une disgression de l'auteur ?

---

Non, c'est dans la norme (enfin, un amendement de la norme). Ce sont les bien nommés digraphs, qui sont justifiés par le fait que certains trigtaphs était un poil compliqués et peu lisibles.

Voir http://en.wikipedia.org/wiki/Digraphs_and_trigraphs

Citation:

---

Envoyé par Jean-Marc.Bourguet

Desole, je n'ai pas de suggestion. Juste une note si tu dois te lancer dans les details toi-meme (je l'avais fait dans une vie precedente pour yacc, qui est du LALR(1), donc plus puissant que LL(1), et la grammaire de la norme avait eu besoin de peu de modification -- mais il y en avait fallu; mais je connais mal ce que la gestion des predicats apportent).

---

Pour information, un petit tour sur les prédicats (dans Coco/R ; ANTLR les traite de manière différente, mais le principe est le même).

Soit une grammaire permettant de définir :
1) des fonctions avec un type de retour
2) des variables avec un type de retour
3) des expressions, qui sont soit des opérations sur des variables, soit des appels fonctions, soit un mix des deux.

Notation utilisée :
* { x } == 0 ou plus x.
* x y == x suivi de y
* [ x ] == 0 ou 1 x
* x | y == x ou y
* ( x ) == x
* 'x' == symbole terminal x
* tkx == token terminal

On a une grammaire qui ressemble à ceci :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

program = declarations   declarations = { type tkidentifier ( ';' | initializer ';' | parameter-block [ statement-block ] ) | 'typedef' type user-type ';' /* pour définir des types utilisateur */ }   initializer = '=' constant   type = predefined-type | user-type       user-type = tkidentifier   statement-block = '{' internal-declaration statements '}'   parameter-block = '(' [ parameter-list ] ')'   parameter-list = tkidentifier { ',' tkidentifier }   internal-declaration = { type tkidentifier [ initializer ] ';' }   statements = { expression ';' }   expression = function-call | variable [ binary-operator expression ]   variable = tkidentifier   function-call = tkidentifier '(' [ expression-list ] ')'   expression-list = expression { ',' expression }

---

La grammaire est assez proche de celle du C pour voir ce vous compreniez ce qui se passe (n'est-ce pas, hein ?). J'ai laissé de coté de nombreuses choses, comme les statements classiques if ou return qui ne posent pas de problèmes majeurs.

Le code suivant est censé être parsé avec cette grammaire :

Code:

---

1 2 3 4 5 6 7

montype funcname(p1, p2) { montype result = 0; if (p1) result = otherfunc(p2); return result; }

---

Une des règles primordiales est la suivante : dans une grammaire LL(k), deux productions qui peuvent être utilisées à un instant donné pour continuer l'opération de parsing ne peuvent pas commencer par le même terminal (car dans ce cas, le parseur ne sait pas quelle production choisir). Pour les grammaires suffisamment simples, ça ne pose guère de problèmes - on factorise aisément les productions.

Ainsi, si on a les productions suivantes :

Code:

---

1 2 3 4

X -> A | B A -> 'a' B B -> 'a' 'c'

---

A et B commencent par le même terminal. Lorsque le parseur rencontre ce terminal, il ne sait pas q'il doit continuer sur la production A ou la production B. Mais cet exemple est suffisamment simple pour que vous imaginiez une solution de contournement au problème (hint : ça passe par remonter 'a' d'un niveau).

Il y a d'autres règles (pas de récursivité à gauche, par exemple).

Dans le cas d'une grammaire un peu plus complexe, comme celle présentée ci-dessus, Le problème peut aussi se poser - et d'ailleurs, il se pose (c'est fait exprès, en même temps). Dans un statement-block, un tkidentifier peut débuter :
*) une internal-declaration (dans ce cas, c'est un user-type)
*) une expression, dans ce cas c'est soit une variable, soit un appel de fonction.

On peut bien évidemment essayer de factoriser cette grammaire, mais elle se complique de manière étonnante (car il faut gérer les cas tordus ; encore que pour l'exemple donné, ça n'est pas trop tordu).

Une autre solution est de prendre en compte le contexte au moment où l'on rencontre un problème - c'est alors le rôle des prédicats de permettre la sélection de la bonne production. Dans l'exemple ci-dessus, supposons que je maintienne une liste des symboles définis. A chaque symbole, j'associe un type de symbole (fonction, variable, type utilisateur). Alors mon problème devient :
*) si le tkidentifier que je considère est un type utilisateur, alors je choisi la production 'internal-declaration'
*) si c'est une variable, alors je choisi la production 'variable'
*) si c'est une fonction, alors je choisi la production 'function-call'

On est pas obligé de couvrir toutes les possibilités (toutes - 1 est suffisant).

Comment se présente un prédicat dans Coco/R ? Il s'agit tout simplement d'une fonction qui sera ajouté comme fonction membre de la classe Parser générée et utilise le contexte courant (notamment t, le token courant et la, le prochain token ; l'API de Coco/R permet ensuite de récupérer les tokens à suivre si la décision ne peut pas se faire aisément). Un exemple :

Code:

---

1 2 3 4 5 6 7 8 9

bool isAType() { return symtable.IsType(t.val); } bool isAFunction() { return symtable.IsFunction(t.val); }

---

L'utilisation de ce prédicat est relativement simple : dans la production à choisir, je fais le test. Celui-ci sera recopié verbatim dans le code du parseur généré, qui pourra donc effectuer le test correctement et choisir la production correcte.

Code:

---

1 2 3 4 5 6 7

internal-declaration = { IF(isAType()) type tkidentifier [ initializer ] ';' }   expression = IF(isAFunction()) function-call | variable [ binary-operator expression ]

---

Voilà le principe. ANTLR les implémente différemment, mais l'idée maitresse est toujours d'autoriser l'utilisateur à spécifier une production plutôt qu'une autre lorsque plusieurs possibilités se présente, en fonction d'informations que le parseur (qui est contexte-free) ne peut pas savoir. Généralement, le choix se fait sur des questions de sémantique liées au contexte en cours.

Dans l'exemple C donné par Jean-Marc.Bourguet

Code:

---

1 2	{ foo * bar; }

---

Le choix de la production 'variable-definition' ou 'mult-expression' se fait sur le type associé au symbole foo.

J'espère que ça vous aura éclairé !

Citation:

---

Envoyé par Emmanuel Deloget

J'espère que ça vous aura éclairé !

---

Merci. C'est bien ce que je pensais.