Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 2 sur 2
  1. #1
    Membre éclairé
    Profil pro
    Inscrit en
    février 2009
    Messages
    355
    Détails du profil
    Informations personnelles :
    Localisation : France, Sarthe (Pays de la Loire)

    Informations forums :
    Inscription : février 2009
    Messages : 355
    Points : 394
    Points
    394

    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 :
    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 :
    1
    2
     
    1+-0.2 * 5.6 + (4 * 6)
    Et renverra l'arbre suivant

    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
     
    {
        "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 éclairé
    Profil pro
    Inscrit en
    février 2009
    Messages
    355
    Détails du profil
    Informations personnelles :
    Localisation : France, Sarthe (Pays de la Loire)

    Informations forums :
    Inscription : février 2009
    Messages : 355
    Points : 394
    Points
    394

    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...

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •