IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Contribuez Discussion :

Recursive descent parser


Sujet :

Contribuez

  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2009
    Messages
    354
    Détails du profil
    Informations personnelles :
    Localisation : France, Sarthe (Pays de la Loire)

    Informations forums :
    Inscription : Février 2009
    Messages : 354
    Points : 491
    Points
    491
    Par défaut Recursive descent parser
    Bonjour! Je voulais vous faire partager mon petit script alias tokemon, un parser basé sur une grammaire innovante.

    j'ai crée ce script pour un projet d'extension des css, comme less ou sass (un mélange des deux en faite)

    Voici l'exemple d'une grammaire parssant une expression arithmétique.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
     
     
    var parser = new Tokemon({
     
            /**
             * this could be done much more simply as
             * 
             * exp : '{primary} sum=( op=["+"|"-"|"*"|"/"] {primary} )*',
             * primary : 'int=@integer | neg="-"? "(" exp=exp ")"'
             * 
             * But there's  priority operators, as * and  ^
             * so whenever there's a product, we create a new node.
             * It allows to recover the products more simply than just a "linear" search
             * There's just to test if the next node has a product, and retrieve the corresponding table
             */
     
            /**
             * sum inherits from product for the rightmost symbol
             * sum create a nested rule sum.sum, that also inherits from product
             * without product inheritance , it gives:
             *  {primary} product=( op=["*"|"/"] {primary} )* sum=( op=["+"|"-"] {primary} product=( op=["*"|"/"] {primary} )*)*
             */
            sum : '{product} sum=( op=@sum {product} )*',
     
            /**
             * product inherits from primary for the rightmost symbol
             * product create a nested rule product.product , define operators + or - and also inherits it product
             * without primary inheritance , it gives:
             *  int=@integer | neg="-"? "(" exp=sum ")" product=( op=["*"|"/"] int=@integer | neg="-"? "(" exp=sum ")" )*
             */
            product : '{primary} product=( op=@product {primary} )*',
     
            // an integer, or a group in parenthesis,
            primary : 'number=@number | neg="-"?  "(" exp=sum ")"'
     
        },{
     
            sum : ['+', '-'],
     
            product : ['*', '/'],
     
            //the tokenizer return a  number through parseFloat
            number : [
                function (parser, node, input, index, length){
     
                   var start = 0,
                        minlen = 1,
                        float_ = false,
                        ch;
     
                    input.charCodeAt(index) === 45 && start++ && minlen++;
                    input.charCodeAt(index + start) === 46 && start++ && (float_ = true);
     
                    do{
     
                        ch = input.charCodeAt(index + start);
     
                        if(ch >= 48 && ch <= 57){
     
                            ++start ;
                            continue;
                        }
     
                        if(!float_ && ch === 46 ){
     
                            ++start ;
                            minlen = start;
                            float_ = true;
                            continue;
                        }
     
                        break;
     
                    }
                    while(true);
     
                    return start >= minlen ? input.substr(index, start) : null;
     
                }, 
                parseFloat
            ],
     
            whitespace : function(parser, node, input, index, length){
     
                var start = 0,
                    ch;
     
                do{
     
                    ch = input.charCodeAt(index + start);
     
                    if(ch === 32 || (ch >= 9 && ch <= 13)){
                        ++start ;
                        continue;
                    }
     
                    break;
                }
                while(true);
     
                return start ? input.substr(index, start) : null;
            }
     
        }, 
     
        ['whitespace'], //skip space
     
        'sum' , //boot rule
     
        false //not case sensitive
    );
    Cette grammaire parssera une entrée du type:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    1+-0.2 * 5.6 + (4 * 6)
    Et renverra l'arbre suivant

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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
     
    {
        "parent": "null",
        "type": "sum",
        "number": 1,
        "sum": [
            {
                "parent": "[object Object]",
                "type": "sum.sum",
                "op": "+",
                "number": -0.2,
                "product": [
                    {
                        "parent": "[object Object]",
                        "type": "product.product",
                        "op": "*",
                        "number": 5.6
                    }
                ]
            },
            {
                "parent": "[object Object]",
                "type": "sum.sum",
                "op": "+",
                "exp": {
                    "parent": "[object Object]",
                    "type": "sum",
                    "number": 4,
                    "product": [
                        {
                            "parent": "[object Object]",
                            "type": "product.product",
                            "op": "*",
                            "number": 6
                        }
                    ]
                }
            }
        ]
    }
    Le projet et une mini doc se trouve à cette adresse https://github.com/Kimoja/Tokemon

    Tokemon est assez rapide, même si il ne sera jamais aussi rapide qu'un parser écrit à la main et spécifique pour une grammaire. L'algo utilisé est très simple, et n'est pas prédictif comme peuvent l'être des parsers LL(1) ou LALR(1), il sera donc le plus souvent plus lent que ce genre de parser, mais la taille du code sera aussi bien moindre.

    A titre de comparaison, en parsing pure (sans génération de noeud) sur une grammaire simple, tokemon est entre 3 à 6 fois plus rapide que PEG.js (valeur subjective, j'ai plus les bon chiffre et bench sous la main). Mais il reste en deçà de jscc (1.25 à 2 fois plus rapide sous chrome et opera, mais entre 1.8 et 4 fois plus lent sur FF et IE)


    Dans la version 1, tokemon n'est pas un générateur de parser, peut être pour la version 2

    N'hésitez pas à me faire parvenir vos remarques!

    Edit : Je viens de me rendre compte qu'il y'a un petit bug sur le report d'érreur. La correction viendra après mes vacances

  2. #2
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2009
    Messages
    354
    Détails du profil
    Informations personnelles :
    Localisation : France, Sarthe (Pays de la Loire)

    Informations forums :
    Inscription : Février 2009
    Messages : 354
    Points : 491
    Points
    491
    Par défaut
    Le bug sur le report d’erreur est corrigé.

    J'ai effectué des mini bench, et les chiffres que j'avais avancé sont erroné, notamment ceux de pegjs. Tokemon est aussi rapide que pegjs, donc désolé de mettre avancé autant (pas une question de prétention, juste de maladresse dans les bench ). Concernant jscc, le script est assez bugué, et il est donc difficile d'établir une réelle comparaison, même si sur l’arithmétique, jscc était plus rapide.

    L'exemple ci-dessus, (l’arithmétique) n'utilise pas le mécanisme usuel de priorité d'opérateur pour ce type de grammaire, mais est efficace quand même...

Discussions similaires

  1. [COMPILATION][RECURSIVE] outil ?
    Par narmataru dans le forum Build
    Réponses: 6
    Dernier message: 14/01/2009, 16h05
  2. [JAXP] com.sun.xml.parser.ValidatingParser
    Par yolepro dans le forum Format d'échange (XML, JSON...)
    Réponses: 7
    Dernier message: 05/11/2008, 16h36
  3. [Servlet] parser la requete
    Par jaimepasteevy dans le forum Servlets/JSP
    Réponses: 3
    Dernier message: 15/10/2003, 17h43
  4. Parser XML
    Par miloux32 dans le forum XML/XSL et SOAP
    Réponses: 4
    Dernier message: 18/07/2003, 04h17
  5. [langage] Continuer a parser une ligne
    Par D[r]eadLock dans le forum Langage
    Réponses: 5
    Dernier message: 30/09/2002, 19h49

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo