[JavaScript] Recursive descent parser

[kimjoa]

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

[kimjoa]

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