Créer un parser en Javascript

Bonjour,

Récemment, j’ai fait un lexer, voici le code :

const tokenTypes = [
    { regex: /^\+/, tokenType: 'OP_ADD' },
    { regex: /^\-/, tokenType: 'OP_MIN' },
    { regex: /^\*/, tokenType: 'OP_MUL' },
    { regex: /^\//, tokenType: 'OP_DIV' },
    { regex: /^\d+/, tokenType: 'NUMBER' }
];

function getTokens(input) {
    input = input.replace(/\s/g, '')
    console.log(input)
    let tokens = [];
    let findToken = false;

    let match;
    
    let i;
    let numTokenTypes = tokenTypes.length;

    do {
        for (i = 0; i < numTokenTypes; i++) {
        match = tokenTypes[i].regex.exec(input);
        if (match) {
            tokens.push({ type: tokenTypes[i].tokenType, value: match[0]});
            input = input.substring(match[0].length);
            findToken = true;
            break;
        }
    }
}  while (input.length > 0 && findToken);


return tokens;
}

console.log(getTokens("4 / 2"))

Désormais, j’aimerais faire un parser histoire de faire l’opération correctement mais je ne sais pas comment m’y prendre.

Merci d’avance.

Bonne fin de journée !

Coucou

Ce que tu peux faire, c’est commencer par faire un parser pour la NPI. Par exemple : "4 2 /"
On simplifie le problème en premier lieu

C’est très simple à parser. Ça se fait avec une simple pile
Je n’ai pas lu mais wikipédia doit expliqué ça.

Notation polonaise inversée

En gros, quand c’est un nombre, tu l’ajoutes à la pile. Quand c’est une fonction, tu pop les deux derniers éléments de la pile, leur applique la fonction et rajoute le résultat sur la pile.

Ensuite, il te faudra convertir une expression infix (comme on utilise tous les jours) en NPI. Pour ça, tu peux t’inspirer de l'algo Shunting-yard.

Avec tout ça, créer ton évaluateur d’expression mathématique devrait être très bien

Bon WE à toi aussi l’ami \o

Ce qui est relativement complexe et demande alors à analyser une première fois l’expression infixe pour la convertir en NPI, puis l’expression NPI pour l’évaluer. Traiter directement l’expression infixe me paraît largement plus simple.

Tu trouves ?
Je pense que ça donne de la structure au code et le fait de n’utiliser que des piles rends la chose assez abordable, amha. Ça donne une direction, on sait quoi faire et comment le faire.

Après bien-sûr, il peut transformer directement l’expression infixe en arbre syntaxique puis l’évaluer. Mais tenter d’évaluer directement l’expression infixe, c’est assez tricky, des cas comme l’expression "4 + 2 / 2" vont dans tous les cas demander de mettre en attente des opérations (et donc de simuler un arbre).

Après bien-sûr, il peut transformer directement l’expression infixe en arbre syntaxique puis l’évaluer.

Je pense que c’est ce que voulait dire @entwanne. Passer par une représentation NPI n’apporte pas grand chose, dans tous les cas il faudra passer par une représentation en arbre de l’expression infixe à un moment où à un autre, et cette représentation n’est pas plus facile ni plus dure à évaluer qu’une expression en NPI, donc s’embêter à faire infixe > arbre > NPI > évaluation au lieu de infixe > arbre > évaluation ne fait que compliquer les choses…

Au fond c’est de toute manière toujours Shunting-yard qui est fait, je ne vois pas d’alternative (edit : que les piles soient gérées explicitement ou implicitement par des appels récursifs). Même pour produire un arbre syntaxique, c’est juste qu’au lieu d’évaluer f(x,y), on produit Node(f,x,y). Et autant évaluer directement f(x,y) sans passer par l’arbre.

Vous inquiétez pas, je lis vos messages. Ca s’avère juste plus compliqué que prévu mais j’essaie encore.

Merci !

Comme tu peux le voir, il y a débat sur la manière de faire

Perso je serais passé par la NPI car même si j’adore ça, j’évite les arbres quand je peux. Il existe d’autres méthodes toutes aussi bonnes présentées par les autres membres

Sinon, au niveau de ton code, fait bien attention à l’indentation
Ça risque de te porter préjudice un jour.

Les arbres syntaxiques ont l’avantage d’être conceptuellement générique, et c’est facile de rajouter de la sémantique dessus après pour complexifier.

C’est bon, j’ai compris le principe de la NPI :p.

Pour l’indentation je vais la revoir, j’ai pas pris le temps de faire un code propre :o.

Maintenant je vais voir comment faire pour la mettre en place via du code.

Ben en fait ce qui me gêne c’est que quand ton construis ton expression en NPI, tu as déjà analysé les opérations et leurs priorités, tu es donc en mesure de directement en calculer le résultat.

Mais après c’est aussi l’algorithme en question que je trouve peu clair. Pour moi le plus facile à appréhender c’est un parseur récursif qui localise l’opérateur de plus faible priorité (en faisant attention à son associativité) et qui demande l’évaluation des opérandes gauche et droite.

¯_(ツ)_/¯

Chacun sa méthode. Moi je préfère tout faire linéairement.

En fait j’ai compris le principe de la NPI, mais je ne sais pas comment l’appliquer via du code, on peut parler de manière plus pratique que théorique s’il vous plaît ? Merci

Sinon bien évidemment j’ai avancé et voici mon code :

const tokenTypes = [
    { regex: /^\s+/, tokenType: 'WHITESPACE' },
    { regex: /^\+/, tokenType: 'OP_ADD' },
    { regex: /^\-/, tokenType: 'OP_MIN' },
    { regex: /^\*/, tokenType: 'OP_MUL' },
    { regex: /^\//, tokenType: 'OP_DIV' },
    { regex: /^\d+/, tokenType: 'NUMBER' }
];

function getTokens(input) {
    console.log(input)
    let tokens = [];
    let findToken = false;

    let match;

    let i;
    let numTokenTypes = tokenTypes.length;

    do {
        for (i = 0; i < numTokenTypes; i++) {
            match = tokenTypes[i].regex.exec(input);
            if (match) {
                tokens.push({ type: tokenTypes[i].tokenType, value: match[0] });
                input = input.substring(match[0].length);
                findToken = true;
                break;
            }
        }
    } while (input.length > 0 && findToken);


    return tokens;
}



var op = {
    OP_ADD(a, b) {
        return a + b
    },
    OP_MIN(a, b) {
        return a - b
    },
    OP_MUL(a, b) {
        return a * b
    },
    OP_DIV(a, b) {
        return a / b
    }
}


let stack = [

];

for (let o of getTokens("1 + 5")) {
    if (o.type === "WHITESPACE") {
        continue;
    };
    console.log(o)
};

Bonne journée !

Tout dépend de ce que tu souhaites faire et du format de ton entrée. Puisque tu parles de NPI, on peut considérer que tu as opté pour une entrée sous ce format. Tu possèdes donc une liste de tokens étant des nombres ou des opérateurs.

Pour l’évaluer, c’est très simple, il te suffit d’une pile. Chaque nombre lu depuis l’entrée sera ajouté à la pile, et chaque opérateur dépilera deux nombres pour ensuite empiler le résultat.
À la fin, si l’expression était valide, il ne devrait te rester qu’un nombre dans la pile, le résultat de l’évaluation.

Si ton entrée est en notation infixe, c’est plus compliqué. Tu peux opter pour ce que conseille @ache mais c’est doubler la charge de travail, ou te renseigner sur les algorithmes possibles pour l’évaluation d’une expression mathématique. Quelle que soit la méthode adoptée, le tout est de savoir identifier la priorité des opérateurs, pour savoir dans quel ordre les appliquer.
Tu peux visualiser une expression mathématique comme un arbre, où les nœuds seraient des nombres ou des opérateurs. Chaque opérateur aurait deux nœuds fils représentant ses deux opérandes. Ainsi, les opérateurs de plus haute priorité se retrouveraient à proximité des feuilles, et celui de plus faible priorité serait la racine de l’arbre.

Coucou \o

J’ai pas le temps de regarder ton code avant tard dans la soirée.

Mais ! Il se trouve qu’un vieux copain (@GuilOooo <3) à écrit un exercice à ce propos. Cet exercice se nomme zParser et est disponible sur un site que je mets à disposition pour l’instant : https://md.ache.one Section "Défis Zestuels" puis "zParser.md"¹

Là-bas, le niveau 2 correspond à la création d’un arbre comme suggérer par entwanne. Deux méthodes sont présentées. La méthode dite naïve qui consiste à construre l’arbre petit à petit (et l’évalué en même temps si tu veux, peu importe) en cherchant les opérateurs. Et la méthode un peu plus ² compliquée qui passe pas l’utilisation d’une grammaire et d'un analyseur LR.

Dans tous les cas, je regarde ton code ce soir

Voilà, c’est bon j’ai réussi !

const tokenTypes = [
    { regex: /^\s+/, tokenType: 'WHITESPACE' },
    { regex: /^\+/, tokenType: 'OP_ADD' },
    { regex: /^\-/, tokenType: 'OP_MIN' },
    { regex: /^\*/, tokenType: 'OP_MUL' },
    { regex: /^\//, tokenType: 'OP_DIV' },
    { regex: /^\d+/, tokenType: 'NUMBER' }
];

function getTokens(input) {
    console.log(input)
    let tokens = [];
    let findToken = false;

    let match;

    let i;
    let numTokenTypes = tokenTypes.length;

    do {
        for (i = 0; i < numTokenTypes; i++) {
            match = tokenTypes[i].regex.exec(input);
            if (match) {
                tokens.push({ type: tokenTypes[i].tokenType, value: match[0] });
                input = input.substring(match[0].length);
                findToken = true;
                break;
            }
        }
    } while (input.length > 0 && findToken);


    return tokens;
}



let op = {
    OP_ADD(a, b) {
        return a + b
    },
    OP_MIN(a, b) {
        return a - b
    },
    OP_MUL(a, b) {
        return a * b
    },
    OP_DIV(a, b) {
        return a / b
    }
}

let stack = [

];

for (let o of getTokens("1 6 -")) { // return -5
    if (o.type === "WHITESPACE") {
        continue;
    }
    if (o.type === "NUMBER") {
        stack.push(parseInt(o.value, 10))
    }
    else {
        let a = stack.pop()
        let b = stack.pop()
        let result = op[o.type](b, a)
        stack.push(result)
    }
}
console.log(stack)

Merci à vous !

Bonne soirée.

Voilà, c’est bien ça.

Juste une petite chose par rapport à ta fonction getTokens : elle provoque une boucle infinie dans le cas où un caractère de l’entrée n’est pas reconnu.

Bon pour garder ça quelque part et vu que le problème initial est résolu.

Voilà une implémentation utilisant Shunting-Yard et évaluant la NPI obtenue :

'use strict';

const tokenTypes = [
 {regex: /^\+ ?/, tokenType: 'OP_ADD'},
 {regex: /^- ?/, tokenType: 'OP_MIN'},
 {regex: /^\* ?/, tokenType: 'OP_MUL'},
 {regex: /^\/ ?/, tokenType: 'OP_DIV'},
 {regex: /^\d+ ?/, tokenType: 'NUMBER'}
];

const precedence = {
 OP_ADD: 1,
 OP_MIN: 1,
 OP_MUL: 2,
 OP_DIV: 2
};

const ope = {
 OP_ADD: (x,y) => x + y,
 OP_MUL: (x,y) => x * y,
 OP_DIV: (x,y) => x ? y / x : NaN,
 OP_MIN: (x,y) => y - x,
};



function getTokens(input) {

 // Pre-processing
 input = input.replace(/\s+/g, ' ');

 const tokens = [];
 let findToken = false;


 const numTokenTypes = tokenTypes.length;

 do {
   findToken = false;
   for (let i = 0; i < numTokenTypes; i++) {
     const match = tokenTypes[i].regex.exec(input);
     if (match) {
       tokens.push({type: tokenTypes[i].tokenType, value: match[0].trim()});
       input = input.substring(match[0].length);
       findToken = true;
       break;
     }
   }
 } while (input.length > 0 && findToken);

 return tokens;
}

function npiEval(tokens) {
 const pileTmp = [];

 tokens.forEach( token => {
   if( token.type === 'NUMBER' )
     pileTmp.push(token.value);
   else
     pileTmp.push(ope[token.type]( pileTmp.pop(), pileTmp.pop()) );

   if (isNaN(pileTmp[0])) {
     return NaN;
   }
 });

 return pileTmp.pop();
}

function shuntingYard(tokens) {
 const outQueue = [];
 const opeStack = [];

 tokens.forEach(token => {
   if (token.type === 'NUMBER') {
     outQueue.push(token);
   } else {
     while (opeStack.length > 0 && precedence[opeStack[0].type] >= precedence[token.type]) {
       outQueue.push(opeStack.pop());
     }
     opeStack.push(token);
   }
 });

 outQueue.push(...opeStack.reverse());

 return outQueue;
}

console.log(npiEval(shuntingYard(getTokens('2 - 6 * 2 + 3 /2'))));

Priorité opératoire, pas de gestion de parenthèses.

Y a deux trois trucs qui me déplaisent dans ce code, je le sais déjà.

Un petit conseil :

En JS ont recommandent fortement de ne pas utiliser de let mais d’utiliser que des const

De n’utiliser des let que lorsque nécessaire.*

Tu as raison, il vaut mieux être prudent.