Partage
  • Partager sur Facebook
  • Partager sur Twitter

Parser

    20 mai 2022 à 12:18:37

    Bonjour à tous,

    Connaissez-vous un guide des bonnes pratiques pour parser des fichiers ? Je me retrouve toujours avec de grosses fonctions et des if imbriqués dans tous les sens... pas très lisible ni élégant. Utilisez-vous toujours les regex dans vos parseurs ?

    • Partager sur Facebook
    • Partager sur Twitter
      20 mai 2022 à 12:22:21

      Salut,

      Ca vas dependre de ce que tu veux faire, moi j'aime bien utiliser Flex/Bison mais c'est probablement l'artillerie lourde pour ton besoin.

      C'est pour du C je ne sais pas si il y a un equivalent C++ mais j'imagine.

      • Partager sur Facebook
      • Partager sur Twitter

      Architecte logiciel - Software craftsmanship convaincu.

        20 mai 2022 à 13:46:22

        Il vaut mieux écrire le parseur à la main plutôt que d'utiliser des générateurs de parseurs. De nos jours le parsing ça prend pas beaucoup de temps dans le temps total de compilation (c'est plutôt la génération de code/optimisation qui est lourde) donc c'est pas la peine de perdre du temps à trouver des techniques avancées de parsing (style LALR), vous faites une vieille descente récursive et ça roule. D'ailleurs c'est ce que tout le monde fait bizarrement :

        GCC : https://gcc.gnu.org/wiki/New_C_Parser

        Clang : "We are convinced that the right parsing technology for this class of languages is a hand-built recursive-descent parser" https://clang.llvm.org/features.html

        MSVC : "it’s been far easier to implement modern C++ features on a modern compiler than it was on our decades-old parser [basé sur YACC, ndlr], where some features just could not be implemented altogether." https://devblogs.microsoft.com/cppblog/announcing-msvc-conforms-to-the-c-standard

        Après si c'est juste pour faire un petit truc tout simple on peut utiliser des générateurs mais si c'est pour faire un gros truc sérieux, mieux vaut le faire à la main.

        Sinon pour répondre à la question originale, il faut demander à Lynix.

        -
        Edité par JadeSalina 20 mai 2022 à 13:54:25

        • Partager sur Facebook
        • Partager sur Twitter
          20 mai 2022 à 14:03:08

          Merci de vos réponses.

          @JadeSalina

          Qu'appelles-tu une "vieille descente récursive" ? Peux tu me montrer un petit exemple simple juste pour voir le principe ? et qu'est-ce qu'un "générateur" pour toi ? c'est une bibliothèque spécialisée ? Désolé, je ne connais pas le domaine, je m'en suis toujours sorti avec des boucles while, et des regex, des if... un peu à l'instinct.

          • Partager sur Facebook
          • Partager sur Twitter
            20 mai 2022 à 14:39:30

            Fais des recherches sur la "technique de descente récursive". Ça se code en n'importe quel langage.
            • Partager sur Facebook
            • Partager sur Twitter

            Le Tout est souvent plus grand que la somme de ses parties.

              20 mai 2022 à 14:42:56

              Généralement, je me fais pas chier, j'utilise des technologies de sérialisation/désérialisation  pour gérer tout ce bordel.

              -
              Edité par bacelar 20 mai 2022 à 15:27:03

              • Partager sur Facebook
              • Partager sur Twitter
              Je recherche un CDI/CDD/mission freelance comme Architecte Logiciel/ Expert Technique sur technologies Microsoft.
                20 mai 2022 à 14:57:13

                J'ai trouvé ceci:


                https://leptinerd.wordpress.com/2017/06/11/introduction-a-la-theorie-de-la-compilation-24-les-parsers/


                http://michel.billaud3.free.fr/blog/index.php/2013/01/20/72-programmation-la-technique-de-descente-recursive-

                Tu auras tout de même des if à coder ...

                Si tu nous disais ce que tu veux parser?

                Pour des expressions arithmétiques / algébriques, j'utilise les arbres binaires.

                -
                Edité par PierrotLeFou 20 mai 2022 à 15:00:27

                • Partager sur Facebook
                • Partager sur Twitter

                Le Tout est souvent plus grand que la somme de ses parties.

                  20 mai 2022 à 15:47:19

                  Umbre37 a écrit:

                  Utilisez-vous toujours les regex dans vos parseurs ?

                  Parser avec des regex ? Oo


                  La vraie question ici, c'est "tu veux parser quoi ?"

                  • Partager sur Facebook
                  • Partager sur Twitter

                  Mes articles | Nazara Engine | Discord NaN | Ma chaîne Twitch (programmation)

                    20 mai 2022 à 16:04:50

                    Umbre37 a écrit:

                    Merci de vos réponses.

                    @JadeSalina

                    Qu'appelles-tu une "vieille descente récursive" ? Peux tu me montrer un petit exemple simple juste pour voir le principe ? et qu'est-ce qu'un "générateur" pour toi ? c'est une bibliothèque spécialisée ? Désolé, je ne connais pas le domaine, je m'en suis toujours sorti avec des boucles while, et des regex, des if... un peu à l'instinct.


                    Il y a un exemple ici : https://en.wikipedia.org/wiki/Recursive_descent_parser

                    Il faut imaginer qu'il y a une grammaire qui décrit le langage. Dans l'exemple il y a par exemple un "block" qui commence optionnellement par "const" suivi d'un identifiant suivi de "=", etc suivi optionnellement de "var" suivi d'un identifiant, etc, suivi d'une procédure.

                    Les générateurs de parseur il suffit de leur donner ce genre de description de grammaire et ils génèrent le code qui fait le parsing. Sinon on peut le faire à la main avec une descente récursive comme c'est montré dans l'exemple et l'idée c'est de suivre simplement ce que dit la grammaire, par exemple il y a une fonction pour parser un "block" et bien tout ce qu'elle fait c'est regarder si ça commence par "const", auquel cas on s'attend à ce qu'il y ait un identifiant, un "=", etc, ensuite on regarde si il y a un "var" auquel cas on attend un identifiant, etc, et ensuite on parse la procédure, etc, comme indiqué par la grammaire (là cette grammaire décrit je ne sais quel langage tordu, mais c'est ça l'idée)

                    Sinon il y a aussi une explication ici : https://craftinginterpreters.com/parsing-expressions.html#recursive-descent-parsing

                    D'ailleurs tout ce livre peut être intéressant pour mieux comprendre.

                    Sinon l'idée vraiment de base à tout ça c'est de ne pas lire les caractères directement, pour éviter d'avoir un code illisible du genre

                    if (str[0] == 'b' && str[1] == 'o' && str[2] == 'n' && str[3] == 'j' && str[4] == 'o' && str[5] == 'u' && str[6] == 'r') {
                      // bonjour !!
                    } else {
                      // erreur : bonjour attendu
                    }

                    A la place il vaut mieux raisonner à un niveau au dessus, celui des "tokens", par exemple on peut avoir un token de type "identifiant" qui peut contenir une valeur textuelle, du coup on récupère le prochain token avec une fonction qui ira lire caractère par caractère mais nous on a juste à vérifier qu'elle a bien trouvé un "bonjour" :

                    struct Token {
                        TokenType type;
                        union {
                            std::string_view str;
                            int i;
                            // ...
                            // la valeur peut être de différents types
                        } value;
                    }
                    
                    struct Context {
                        std::string_view str;
                        int cur_pos;
                    };
                    
                    Token get_next_token(Context& context) {
                        skip_spaces(context); // on s'en fiche des espaces
                    
                        Token token;
                        int start_token = context.cur_pos;
                    
                        // On avance tant qu'on a pas rencontré une espace
                        while (!is_space(context.str[context.cur_pos])) {
                            context.cur_pos++;
                        }
                    
                        // On vient de lire un "mot", qu'on extrait (on considère que c'est une string mais ça
                        // pourrait être un nombre ou autre)
                        std::string_view str = context.str.substr(start_token, context.cur_pos);
                    
                        // Peut être qu'on vient de lire un mot clé du langage, auquel cas ce n'est
                        // pas un "identifiant"
                        if (str == "while") {
                            token.type = WHILE;
                        } else if (str == "for") {
                            token.type = FOR;
                        } else if (...) {
                            ...
                        } else {
                            // Sinon c'est un identifiant
                            token.type = IDENTIFIANT;
                            token.value.str = str;
                        }
                    
                        return token;    
                    }
                    
                    void parse(std::string_view str) {
                        Context context{str, 0};
                        Token token;
                    
                        do {
                            token = get_next_token(context);
                    
                            switch (token.type) {
                                case IDENTIFIANT:
                                    if (token.str == "bonjour") {
                                        // on vient de lire bonjour
                                    } else {
                                        // erreur : bonjour attendu
                                    }
                                    break;
                    
                                // case ...
                            }
                        } while (token.type != END_OF_STREAM);
                    }

                    (c'est vraiment fait à la rache et on va me crier dessus parce que j'ai pas utilisé le pattern visitor mais vous voyez l'idée)

                    Et sinon oui, que voulez vous parser exactement, là je balance un peu des trucs au pif qui sont pas forcément ce que vous voulez faire



                    -
                    Edité par JadeSalina 20 mai 2022 à 16:14:35

                    • Partager sur Facebook
                    • Partager sur Twitter
                      20 mai 2022 à 17:49:17

                      Les choix des gens qui parsent C++ ne sont pas forcément ceux qu'il faut particulièrement mettre en avant sur le sujet du parsing. C++ est notoirement connu pour avoir une grammaire vraiment ignoble qui de toute façon ne peut pas être prise en compte via des générateurs de parsers, et qui est une plaie à faire à la main aussi. Il faudrait que je retrouve ça, mais il y a quelques années j'avais vu une pres à ISSTA d'une équipe qui avait voulu faire un outil à la CSmith mais pour C++. La barrière principale qu'ils avaient rencontré était qu'ils n'ont jamais pu atteindre le compilateur : leur générateur déclenchait des core dump partout dans les parsers bien avant d'atteindre la compilation. Et personne ne voulait corriger les bugs en question car le code généré était trop tordu pour être facilement débuggé.

                      • Partager sur Facebook
                      • Partager sur Twitter

                      Posez vos questions ou discutez informatique, sur le Discord NaN | Tuto : Preuve de programmes C

                        20 mai 2022 à 18:05:08

                        @Umbre37:
                        Je répète la question, que veux-tu parser?
                        Les regex c'est compliqué. Je l'ai fait en Python et ce n'est pas évident. Je ne le suggère pas.

                        • Partager sur Facebook
                        • Partager sur Twitter

                        Le Tout est souvent plus grand que la somme de ses parties.

                          20 mai 2022 à 18:53:05

                          Les regex peuvent être utiles pour les éléments les plus simples du parsing. Typiquement des choses comme le format d'un identifiant, d'un nombre, d'une chaîne, etc.

                          Au dessus de ça, on ne se limite généralement plus au langages réguliers, on passe aux langages algébriques (et donc ça ne peut plus être reconnu par une expression régulière).

                          • Partager sur Facebook
                          • Partager sur Twitter

                          Posez vos questions ou discutez informatique, sur le Discord NaN | Tuto : Preuve de programmes C

                            20 mai 2022 à 19:45:20

                            Ksass`Peuk a écrit:

                             C++ est notoirement connu pour avoir une grammaire vraiment ignoble qui de toute façon ne peut pas être prise en compte via des générateurs de parsers, et qui est une plaie à faire à la main aussi.

                            L'héritage de C... + les complications ajoutées

                            http://trevorjim.com/c-and-cplusplus-are-not-context-free/



                            • Partager sur Facebook
                            • Partager sur Twitter
                              20 mai 2022 à 21:48:07

                              Pour du parsing, j'aime bien utiliser des lib type peg, parce que c'est simple et qu'on peut écrire l'action à effectuer directement dans la grammaire. Il en existe plein, j'ai en tête boost.x3, boost.metaparse et PEGTL. Je n'ai pas vérifié, mais je suppose que les 2 libs boost sont disponibles sans boost (presque sûr pour metaparse).

                              Et quand c'est bien fait, on peut même avoir une gestion d'erreur de syntaxe assez précise capable de dire la position exacte du problème et ce qui est attendu.

                              Faire à la main, c'est chiant, rébarbatif, déduire la syntaxe depuis le code est pénible et les rare fois où je l'ai fait, j'ai commencé par écrire ma propre lib de parsing du genre x3 ou pegtl...

                              -
                              Edité par jo_link_noir 20 mai 2022 à 21:48:46

                              • Partager sur Facebook
                              • Partager sur Twitter
                                21 mai 2022 à 0:55:24

                                Merci pour tous vos messages ! Je vais mettre un peu de temps à regarder toutes les ressources que vous m'avez communiquées. Pour répondre à la question la plus fréquemment posée : je traduis un langage interprété en c++ afin de pourvoir le compiler et gagner en performances. C'est un langage peu utilisé, maintenu en vie par un petit cercle de passionnés. Il s'agit d'un dérivé du Basic.

                                Lynix a écrit:

                                Umbre37 a écrit:

                                Utilisez-vous toujours les regex dans vos parseurs ?

                                Parser avec des regex ? Oo

                                Parser, c'est analyser un texte et en extraire des données utiles non ? N'est-ce pas la fonction des regex ?

                                -
                                Edité par Umbre37 21 mai 2022 à 0:59:46

                                • Partager sur Facebook
                                • Partager sur Twitter
                                  21 mai 2022 à 1:33:23

                                  > Parser, c'est analyser un texte et en extraire des données utiles non ? N'est-ce pas la fonction des regex ?

                                  Comme le dit Peuk, les regex (regular expression) s'utilisent sur des langages réguliers. Le parsing d'un langage n'est pas régulier. Notamment, la récursion n'est pas possible. On me dira que c'est possible avec pcre, mais en pratique, on ne peut pas faire de capture.

                                  Généralement on décrit une syntaxe au format BNF ou dans un dialecte proche qui sont plus lisibles qu'une regex. Beaucoup de générateurs utilisent une syntaxe similaire.

                                  Ça me fait penser que j'ai pas mal vu passer tree-sitter ces derniers temps.

                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    21 mai 2022 à 1:42:18

                                    Umbre37 a écrit:

                                    Parser, c'est analyser un texte et en extraire des données utiles non ? N'est-ce pas la fonction des regex ?

                                    Heu non, le but premier des regex est de faire correspondre un motif à une chaine de caractère (pour simplifier: faire des recherches).
                                    Ensuite, s'y ajoutent les fonctionnalités d'extraction et substitution.

                                    Certes, on peut parser avec, encore faut-il que la source s'y prête (le HTML par exemple: Pas faisable).

                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      21 mai 2022 à 8:45:09

                                      En informatique le mot "parsing" est assez flou. On considère en général deux étapes

                                      • L'analyse lexicale, qui consiste à extraire d'une chaîne des elements successifs. Par exemple de "toto = 123 *toto + tutu"  on va récupérer un identificateur, le signe égal, un autre identificateur, etc
                                      • L'analyse syntaxique qui va y trouver un sens : il s'agit d'une affectation avec une expression qui est la somme d'un produit avec un autre identificateur.

                                      Si on veut ça correspond à l'orthographe (écrire les mots correctement) et la grammaire (les combiner correctement).

                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        21 mai 2022 à 9:26:05

                                        @JadeSalina

                                        Merci beaucoup pour les liens et pour tes explications, ton code m'aide bien à comprendre le principe.

                                        Merci à tous vous m'avez donné beaucoup de pistes. Je vais lire 

                                        https://fr.wikipedia.org/wiki/Langage_rationnel

                                        et 

                                        https://fr.wikipedia.org/wiki/Langage_alg%C3%A9brique

                                        et

                                        https://en.wikipedia.org/wiki/Parsing_expression_grammar

                                        pour comprendre de quoi vous me parlez, mais le domaine est visiblement assez complexe. Jusqu'ici j'ai parsé des choses à l'arrache sans me poser ce genre de questions.

                                        Je vais aussi regarder les lib que me conseille @jo_link_noir  PEGTL en particulier semble sympa.

                                        • Partager sur Facebook
                                        • Partager sur Twitter

                                        Parser

                                        × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                        • Editeur
                                        • Markdown